From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Subject: Re: [tarantool-patches] Re: [PATCH v4 03/12] rlist: introduce rlist_add_tail_entry_sorted References: <7f34e14d373180ce57bfea36e3eb333c2d5c6a6a.1548883137.git.v.shpilevoy@tarantool.org> <20190215132650.GF24683@chai> From: Vladislav Shpilevoy Message-ID: <3ea52afc-7425-883b-44df-69376aa2e1b1@tarantool.org> Date: Fri, 15 Feb 2019 16:34:03 +0300 MIME-Version: 1.0 In-Reply-To: <20190215132650.GF24683@chai> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit To: tarantool-patches@freelists.org, Konstantin Osipov Cc: vdavydov.dev@gmail.com List-ID: On 15/02/2019 14:26, Konstantin Osipov wrote: > * Vladislav Shpilevoy [19/01/31 10:28]: >> Add an entry to an ascending sorted list. Scan is started from >> the tail. Applicable when new elements are usually already bigger >> than all other ones, since insertion into a sorted list is O(N). >> >> Necessary for SWIM implementation, where a list is stored of >> members, waiting for an ACK. Sometimes there can be inserted an >> indirect ACK, which deadline could be bigger, than deadlines >> of next direct ACKs. So new elements are inserted either into the >> tail, or almost into the tail. >> >> Order allows to stop checking next elements for an unacknowledged >> ping when on a next one deadline is not exceeded yet. >> >> Needed for #3234 > > I don't mind having an insert into a sorted list, but > 1) we're not stl, so this algorithm is not a generic one. Soon > we'll get slist_insert_sorted, array_insert_sorted, etc. It is generic for rlist. It takes a comparator. > 2) I don't understand if there is any reason to use rlist in this > case, why not use a red-black tree? RB-tree is an overkill here. As I described in the commit message, almost always a new element is pushed at the end of the list. Also, out generic RB tree does not have O(1) access to the smallest element. Honestly, I understand your complaint, and recently I decided to use a heap here in later versions of the patchset. Heap gives me O(1) access to the smallest element, while still proving O(log) removal/addition. Moreover, when a new element is the biggest, insertion is O(1) also. And this is the most popular case here. > 3) Why do we have the test in the server, while the library itself > is a subproject? I believe the library does have unit tests, > why not add tests there? For an unknown for me reason, rlist tests are stored in the server repo. I do not know why and I decided not to break it here. > > > -- > Konstantin Osipov, Moscow, Russia, +7 903 626 22 32 > http://tarantool.io - www.twitter.com/kostja_osipov >