From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp16.mail.ru (smtp16.mail.ru [94.100.176.153]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 0D35846970E for ; Thu, 16 Jan 2020 23:27:15 +0300 (MSK) References: <20200110074609.68016-1-k.sosnin@tarantool.org> <8c5c71e4-b637-a39b-1de4-2172dea88d66@tarantool.org> <43C3FC7F-38CB-49EB-B52E-8762C391D5CA@tarantool.org> From: Vladislav Shpilevoy Message-ID: <2c25b764-dc7a-ce62-73ba-53554adfd263@tarantool.org> Date: Thu, 16 Jan 2020 21:27:13 +0100 MIME-Version: 1.0 In-Reply-To: <43C3FC7F-38CB-49EB-B52E-8762C391D5CA@tarantool.org> Content-Type: text/plain; charset="utf-8" Content-Language: en-US Content-Transfer-Encoding: 8bit Subject: Re: [Tarantool-patches] [PATCH] box: add binary search for _session settings space List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Chris Sosnin Cc: tarantool-patches@dev.tarantool.org Hi! >> 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? Hm, you are right. session_settings_next_in_module() perhaps is not the best place. Yes, I think all linear places should be fixed and become binary search. For the iterators case you can patch session_settings_index_create_iterator() so as it initializes module_id and setting_id with a first matching module and setting (or last, depending on the iterator type). Although not sure if it is correct, because usually creation of an iterator does not position the iterator. At least it does not happen in all our other iterators. Alternative solution - for forward iterator initialize module_id with -1. In session_settings_iterator_next() check, that if module_id is -1, then find a first setting with a binary search. For backward iterator the same - init module_id with session_setting_type_MAX, and use a binary search first time in session_settings_iterator_prev(), when you see module_id == MAX. Motivation is that even though 'update' and 'get' are the most important places, and you fixed them, some users may still use :select() even when they want to select just one tuple, with EQ iterator and a full key. And it will be linear, because select() is always an iterator.