tdf#109097 - mdds accelerating random lookups

[Eike Rathke]

Hi Dennis,

On Thursday, 2017-08-24 15:33:26 +0530, Dennis Francis wrote:

> 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.

Does not sound very appealing to me. A better lookup time is certainly
desirable by means of interpolation or binary search, but at the cost of
insertion/deletion time that's not gonna fly. We still have bottlenecks
where inserting and especially changing type of a cell, which leads to
shrinkage of one block and enlargement or insertion of another, can
build up to looong waiting times. I don't have the bug number at hand
right now, but the worst case is a Find&Replace that changes string
cells to numeric (or vice versa) in a column of data. I think these
should be addressed first.

  Eike

-- 
LibreOffice Calc developer. Number formatter stricken i18n transpositionizer.
GPG key 0x6A6CD5B765632D3A - 2265 D7F3 A7B0 95CC 3918  630B 6A6C D5B7 6563 2D3A
Care about Free Software, support the FSFE https://fsfe.org/support/?erack
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <https://lists.freedesktop.org/archives/libreoffice/attachments/20170825/01e7659f/attachment.sig>