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

[Jörg F. Wittenberger]

I got that fixed.

I attach one more copy here. (I'd rather post it elsewhere, but right
now I have a problem posting to my website.)

I slightly changed the names and removed the "generic-" prefix altogether.

Actually I'd like to go one step further and export "set!" "delete!"
etc.  However this requires "set!" and "empty?" to be available to the
implementation as syntax and then be bound to procedures and exported.

Is there is recipe how to do that?

Best

/Jörg

Am 25.10.2015 um 19:41 schrieb "Jörg F. Wittenberger":
> Sorry for this.
> 
> I made two big mistakes I'll have to fix.
> 
> a)  My impatience waiting for the test to finish: I changed the export
> list in llrb-tree but did not recompile the test case.  Sure: the tests
> did not work anymore.
> 
> b) Worse: I consistently got the argument order wrong on "fold" API wrt.
> to srfi-1 vs. srfi-69 order.
> 
> So I'll have to redo some things.  Sorry for the noise.
> 
> /Jörg
> 
> 
> Am 24.10.2015 um 20:57 schrieb "Jörg F. Wittenberger":
>> 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.
>>
>>
>>
>> _______________________________________________
>> Chicken-users mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/chicken-users
>>
> 
> 
> _______________________________________________
> Chicken-users mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/chicken-users
>

llrb.tar.gz
Description: application/gzip