apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yann Ylavic <ylavic....@gmail.com>
Subject Re: Skiplist improvements
Date Fri, 11 Jul 2014 16:29:48 GMT
Grr, off the list...

On Fri, Jul 11, 2014 at 6:29 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
> On Fri, Jul 11, 2014 at 6:24 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
>> On Fri, Jul 11, 2014 at 4:28 PM, Jim Jagielski <jim@jagunet.com> wrote:
>>>
>>> On Jul 10, 2014, at 8:07 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
>>>
>>>>
>>>> I propose to garantee the ordering presumably at low coding and
>>>> performance (if any) cost, so that one can choose between apr_table or
>>>> apr_skiplist to do similar things (iterate over all the values of a
>>>> key is one such thing, in a deterministic order is an other, both not
>>>> feasible with the current skiplist implementation).
>>>>
>>>
>>> ++1... For me, performance is key. Or, at least, some sort
>>> of option to allow for a skiplist to be created that
>>> guarantees order or not, depending on whether performance
>>> or ordering is more important.
>>>
>>> After all, the intent of skiplist *is* in performance,
>>> and not ordering, so sacrificing performance for ordering
>>> seems kinda wonky, unless one can turn that off :)
>>
>> I think I can add this option, but in "performance mode", what would
>> be the behaviour of :
>> 1. apr_skiplist_remove(),
>> 2. apr_skiplist_remove_first(), apr_skiplist_remove_last()
>> 3. apr_skiplist_find_last()
>>
>> 2. and 3. are introduced by this patch so the can return NULL (or
>> ENOTIMPL by changing the declaration) because it makes no sense to use
>> them without ordering.
>>
>> 1. is more tricky, should it remove one single value or all doublons?
>> Doublons are a new 1.6 feature, in 1.5 apr_skiplist_remove() had not
>> this to handle. Now we have to rule.
>> In the case apr_skiplist_remove() should act on a single value, the
>> caller would have to loop to remove all the doublons (restarting from
>> the top each time).
>> In the case apr_skiplist_remove() should act on all doublons, I don't
>> think there is an efficient way to do it without ordering (once a
>> value is reached, this is not necessarily the first, and we'd have to
>> compare both up and down->next until none remain).
>>
>> In both case we are stuck with non-ordered-remove performances outside
>> the insert/add()/pop() scheme.
>> Performance for a use case can't apply to all the others (one may not
>> need ordering but still remove to be performant).
>
> Maybe we could also leave skiplist as is and introduce a new type
> (skipmap?) that would be ordered and that would take both key and
> value as arguments (in the relevant functions)...

Mime
View raw message