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