Hello, As this bug report ( https://bugs.documentfoundation.org/show_bug.cgi?id=109097) suggests it is highly desirable to improve the lookup time in multi_type_vector (currently in worst case it takes O(N)) without position hints. One way to improve the situation is to store absolute position of first element of each block in the block instead of the block size member. This can improve the lookup time up to log(log(N)) using linear interpolation search or at least log(N) if we fallback to binary search after a few initial passes of linear-interpolation search.
Down side of this approach is that in the worst case, insert/deletes incur O(N) cost because absolute positions stored in each block subsequent to the delete/insert block have to be changed, but this still would be way better than old cell storage case when there was no concept of blocks. Before working on any change from my side, I would love to hear everyone's thoughts on the topic first. Thanks ! Regards, Dennis
_______________________________________________ LibreOffice mailing list LibreOffice@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/libreoffice
