tdf#109097 - mdds accelerating random lookups

[Dennis Francis]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/libreoffice/attachments/20170824/640de156/attachment.html>