Re: [Chicken-users] ANN: new eggs "llrb-syntax" and "llrb-tree"

[Jörg F. Wittenberger]

Am 26.10.2015 um 13:20 schrieb Marc Feeley:
> Sorry, I had forgotten our email exchanges on the subject 7 years ago!
> 
> I’ll have to look into your implementation because I don’t understand why the 
> allocation free version is slower.

That's been to my biggest surprise!

I only can guess: To my understanding mutation goes though C_mutate_slot
in runtime.c - correct?  And later the GC has to clear the
mutation_stack.  That's quite some overhead.  In the allocation code I
this does not happen.  (At least I did not find it.)  That's why the
implementation is careful to use the minimum amount of mutation using
local variables for the rotation operations.  Still this much of a
difference.

But maybe I'm totally wrong at this guess.

/Jörg


> 
> Marc
> 
>> On Oct 26, 2015, at 7:43 AM, Jörg F. Wittenberger <address@hidden> wrote:
>>
>> Hi Marc,
>>
>> Am 25.10.2015 um 19:42 schrieb Marc Feeley:
>>> Interesting… it looks a lot like the define-rbtree macro used in the Gambit 
>>> runtime system to implement priority queues for the scalable thread 
>>> scheduler.
>>>
>>> Is there any historical link between your implementation and the Gambit one?
>>>
>>> Marc
>>
>> Yes, there is.  Documented in the archives of this mailing list from
>> 2008.  Search for "Feeley priority queue".
>>
>> I studied the rb-tree code as well as weight balanced trees and skip
>> lists.  And tried them in the scheduler.
>>
>> Eventually I settled with llrb.  The latter especially because the
>> implementation as a syntax would allow me to produce lowlevel chicken
>> code and have threads with slots for two independent queues timeout and
>> blocking reason (directly in the thread object, not as two separate
>> references to some intermediate queue entry node).  And there was this
>> license issue blocking inclusion into chicken.
>>
>> The archives even reflect my now proven false assumption that the
>> allocation free version would be faster.  More work to do...  ;-)
>>
>> But more important than the use as a priority queue I found the use case
>> as alists replacement.  Especially when the miss is not an error but
>> handled.  I recall having seen this suspiciously often.
>>
>> Best
>>
>> /Jörg
>>
>>>
>>>> On Oct 24, 2015, at 2:57 PM, Jörg F. Wittenberger <address@hidden> wrote:
>>>>
>>>> Hi all,
>>>>
>>>> attached the code of two new eggs.
>>>>
>>>> llrb-syntax contains a syntax-rules implementation of left-leaning
>>>> red-black trees.  It expands code maintaining LLRB trees in a data
>>>> structure defined by the user.  Depending at the use case it will either
>>>> allocate temporary space (in the pure case) or allocate no temporary
>>>> space at all and use the minimum amount of mutations to maintain the
>>>> LLRB tree in place.
>>>>
>>>> llrb-tree uses llrb-syntax to implement generic alternatives for
>>>> assoc-list drop-ins (having a much better lookup behavior) and srfi-69
>>>> hash table drop-ins.  Plus versions specialized for fixnums, strings and
>>>> symbols as key.
>>>>
>>>>
>>>> Both have a README, which should (hopefully) be ready to be pasted into
>>>> the wiki.  (Can't test the syntax, but hey, it's not that much I can
>>>> have done wrong.)
>>>>
>>>>
>>>> As I don't see the point in hosting my own infrastructure to publish
>>>> them (after all I assume that once I'm past the inevitable bugs an
>>>> shortcomings those will not see frequent updates by nature), I'd prefer
>>>> if those would eventually go into the CHICKEN projects repository.
>>>> (Where I only have r/o access so far.)
>>>>
>>>> ---
>>>>
>>>> While preparing I learned something I want to share.  CHICKEN is always
>>>> good for a surprise.  And I'm astonished to say the least.  Something is
>>>> strange here.
>>>>
>>>> 1)  Intuitively I'd assume that conserving space to reduce the load on
>>>> the garbage collector should pay off.  Even for CHCIKEN, which is
>>>> supposed to be highly effective on temporary allocations.  The numbers
>>>> (included in "numbers.txt" in the tarball, though those should probably
>>>> not make it into svn) did prove me wrong.  The version specialized to
>>>> fixnum keys is roughly 4x slower when running allocation free (thus
>>>> loading the mutation stack) than the pure version.  The same I found to
>>>> be true for mutating versions having string-keys.
>>>>
>>>> 2) I never had the idea to actually use LLRB trees as a *replacement*
>>>> for hash tables.  After all LLRB maintains an order relation and is
>>>> according to theories and urban legends *supposed* to be slower.  See
>>>> yourself: in the fixnum case, llrb is almost twice as fast as the
>>>> corresponding hash table.  (1M inserts in 90 seconds for Hashtable vs.
>>>> 46 seconds for LLRB; References are even faster 1M refs in 19sec. vs.
>>>> 10sec. for LLRB.)
>>>>
>>>> I'm astonished.
>>>>
>>>> Even the LLRB build using generic = and < is almost a fast and much
>>>> faster than Hashtables.
>>>>
>>>> 3)  Things become slightly more confusing when taking symbols as key.
>>>> For those hash tables appear about 30% faster than LLRB on inserts
>>>> and about 5% faster on referencing.  (However randomization, which is
>>>> commented out in the attached source was still active during the test.
>>>> Maybe there's something hidden.)
>>>>
>>>> From memory: before I tested with smaller numbers of keys, which
>>>> resulted in the opposite finding: LLRB was found relative faster for
>>>> smaller numbers of keys.  After all it's O(log n), thus this is expected.
>>>>
>>>>
>>>> 4) string->symbol puts #3 upside down:
>>>> string->symbol 1000000 calls in 111935.0 ms
>>>> caching the result in a LLRB-string tree naturally adds overhead on the
>>>> first call: str2sym 1000000 refs in 185748.0ms – almost twice.
>>>> Wait, what? *Almost* twice?  How comes?  Should have been around 230%
>>>> according to #3.
>>>>
>>>> But on the second call string->symbol still takes those 112403.0ms,
>>>> while the LLRB-cached version needs only 16321.0ms.
>>>>
>>>> I guess something is wrong in string->symbol.  So far I've been unable
>>>> to spot it.
>>>>
>>>> But who would have predicted that a balanced tree could be sorta faster
>>>> than a hash table?  Me not.
>>>>
>>>>
>>>> Have a nice day!
>>>>
>>>> /Jörg
>>>>
>>>>
>>>>
>>>> PS: there's a tblbench.scm in the tarball as well, which produced those
>>>> numbers.  After all that's kind of a benchmark and if there's something
>>>> lying to me, then it's probably benchmark.
>>>> <llrb.tar.gz>_______________________________________________
>>>> Chicken-users mailing list
>>>> address@hidden
>>>> https://lists.nongnu.org/mailman/listinfo/chicken-users
>>>
>>
>