[Tarantool-patches] [PATCH] box: add binary search for _session settings space

[Chris Sosnin]

Hi! Thank you very much for the review!

> There is no '_session' space. Please, add '_' between
> '_session' and 'settings’.

I agree, it’s a typo.

> 1. 'Module' is different on each iteration, because I do '++module'
> each time. Here you took count only for the first module, but use it
> for all of them.
> 
> The same below.

I agree here too, thank you for the catch!

> 2. We don't really need this function anywhere except session_settings.c.
> Besides, even in that file it is needed only in session_settings_next_in_module().
> So you can just patch the latter function.


I don’t think it’s a good idea, consider the following:

tarantool> box.space._session_settings:select('a', {iterator = 'GE’})

With the current version, we will find the first element which is GE with linear lookup,
and the rest loops will consist of one iteration (overall it will always be the number of elements
in the array). If we change session_settings_next_in_module() to use binary search, 
however, it will highly increase the number of comparisons, because, even though we know
that the next element is greater or equal, we are still looking for it in the array.

My initial patch takes advantage of the array being sorted for update and get methods,
leaving the case from above untouched. Perhaps I could try to make the first lookup 
with binary search, and the rest with linear. What do you think?

Best regards,
Chris.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.tarantool.org/pipermail/tarantool-patches/attachments/20200116/53100c0a/attachment.html>