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.
Marc > On Oct 26, 2015, at 7:43 AM, Jörg F. Wittenberger > <[email protected]> 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 >>> <[email protected]> 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 >>> [email protected] >>> https://lists.nongnu.org/mailman/listinfo/chicken-users >> > _______________________________________________ Chicken-users mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/chicken-users
