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 >> <joerg.wittenber...@softeyes.net> 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 >>>> <joerg.wittenber...@softeyes.net> 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 >>>> Chicken-users@nongnu.org >>>> https://lists.nongnu.org/mailman/listinfo/chicken-users >>> >> > _______________________________________________ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users