From: Chris Sosnin <k.sosnin@tarantool.org> To: Vladislav Shpilevoy <v.shpilevoy@tarantool.org> Cc: tarantool-patches@dev.tarantool.org Subject: Re: [Tarantool-patches] [PATCH] box: add binary search for _session settings space Date: Thu, 16 Jan 2020 16:13:07 +0300 [thread overview] Message-ID: <43C3FC7F-38CB-49EB-B52E-8762C391D5CA@tarantool.org> (raw) In-Reply-To: <8c5c71e4-b637-a39b-1de4-2172dea88d66@tarantool.org> [-- Attachment #1: Type: text/plain, Size: 1463 bytes --] 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. [-- Attachment #2: Type: text/html, Size: 10246 bytes --]
next prev parent reply other threads:[~2020-01-16 13:13 UTC|newest] Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top 2020-01-10 7:46 Chris Sosnin 2020-01-15 20:24 ` Vladislav Shpilevoy 2020-01-16 13:13 ` Chris Sosnin [this message] 2020-01-16 20:27 ` Vladislav Shpilevoy
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=43C3FC7F-38CB-49EB-B52E-8762C391D5CA@tarantool.org \ --to=k.sosnin@tarantool.org \ --cc=tarantool-patches@dev.tarantool.org \ --cc=v.shpilevoy@tarantool.org \ --subject='Re: [Tarantool-patches] [PATCH] box: add binary search for _session settings space' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox