Re: [tarantool-patches] Re: [PATCH v4 03/12] rlist: introduce rlist_add_tail_entry_sorted

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

On 15/02/2019 14:26, Konstantin Osipov wrote:
> * Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [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
>