Michael Matz <m...@suse.de> writes: >> > There were other people pointing out issues with the splay tree (but >> > all w/o copyright assignment and much larger patches). >> > >> > I know I did the last re-write of this piece of code but it's been a >> > long time ... in any case, previous reports were that the current >> > implementation degenerates in some cases. >> >> And I also distinctly remember some actual measurements where our >> current non-splay-tree is faster for a bootstrap (or similar testcases) >> than a real splay tree. Couple years ago, on this list. > > Referenced from: > http://gcc.gnu.org/ml/gcc/2006-10/msg00616.html
Thanks. I knew I must be missing something. I can't explain why I didn't notice that when searching... > Basically the reimplementation of richi (r106584) improved on the > benchmarks (the former implementation was fairly bogus). The one from > Brian Makin with some changes by Ian Barnes was only slightly better (and > without copyright assignment). > > So it's very well possible that Richi doesn't rotate in optimal order. I > think it's harmless for the average O(log n) invariants of a splay tree. > Try some benchmarks :) Nah. Now I know the reason, I'm happy. :-) FWIW, the reason I asked was because I'm using a splay tree in a patch that I hope to send soon. The libiberty structures are a bit heavyweight, with the hooks stored alongside the root pointer, and with each node being a separate structure from the key and value. Since all I needed was a find-or-insert operation, I thought it would be OK to have a splay function in the pass itself. The justification was going to be that splaying is a fairly short textbook algorithm. Then I realised that we don't actually implement the libiberty one in what I thought was the textbook way. I'll have another look at whether I can reuse the libiberty code without bloating things too much. If not, I might just copy the algorithm we use there. Richard
