From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp36.i.mail.ru (smtp36.i.mail.ru [94.100.177.96]) (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 49A0646970E for ; Thu, 16 Jan 2020 16:13:09 +0300 (MSK) From: Chris Sosnin Message-Id: <43C3FC7F-38CB-49EB-B52E-8762C391D5CA@tarantool.org> Content-Type: multipart/alternative; boundary="Apple-Mail=_F80C490D-FB22-4F05-8BB6-B33BC0C3A7C8" Mime-Version: 1.0 (Mac OS X Mail 13.0 \(3608.40.2.2.4\)) Date: Thu, 16 Jan 2020 16:13:07 +0300 In-Reply-To: <8c5c71e4-b637-a39b-1de4-2172dea88d66@tarantool.org> References: <20200110074609.68016-1-k.sosnin@tarantool.org> <8c5c71e4-b637-a39b-1de4-2172dea88d66@tarantool.org> 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: Vladislav Shpilevoy Cc: tarantool-patches@dev.tarantool.org --Apple-Mail=_F80C490D-FB22-4F05-8BB6-B33BC0C3A7C8 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Hi! Thank you very much for the review! > There is no '_session' space. Please, add '_' between > '_session' and 'settings=E2=80=99. I agree, it=E2=80=99s 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. >=20 > 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=E2=80=99t think it=E2=80=99s a good idea, consider the following: tarantool> box.space._session_settings:select('a', {iterator =3D = 'GE=E2=80=99}) 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,=20 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=20 with binary search, and the rest with linear. What do you think? Best regards, Chris.= --Apple-Mail=_F80C490D-FB22-4F05-8BB6-B33BC0C3A7C8 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 Hi! = Thank you very much for the review!

There is no '_session' space. = Please, add '_' between
'_session' and 'settings=E2=80=99.

I agree, it=E2=80=99= 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=E2=80=99t think it=E2=80=99s a = good idea, consider the following:

tarantool> = box.space._session_settings:select('a', {iterator =3D = 'GE=E2=80=99})

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.
= --Apple-Mail=_F80C490D-FB22-4F05-8BB6-B33BC0C3A7C8--