>> Because at one point I studied red-black trees (not as in dendrology, >> but as data structures), I looked into the implementation that is >> being used in NetBSD. I have made some drastic optimisations on sys/ >> sys/tree.h and would like to have the changes imported into NetBSD >> repository. >> >> I would like someone to take a look at the patch, which is attached to >> this message, and verify the code. I have also attached a short PDF >> document, in which I comment on changes made to the implementation of >> the red-black tree algorithm. >> >> If it's okay, I can commit the changes myself. >> >> I think we all will benefit from faster and smaller code. :) > > Can you present numbers to support your claims of drastic optimizations? > > I've used tree.h in out-of-NetBSD projects and don't mind this being > committed. However, I did not review your changes, so I hope you have > made 100% sure there are no regressions. Remember that usually the only > way to win is not to play at all ;) Hello again :) 1. I analysed the algorithm and the changes are correct. 2. I wrote a test program to compare the two implementations (original and mine) and it gives the same result. I am attaching an updated patch. This one works even better with node insertions. (Yes, I am trying to do some benchmarking, but can't give any reasonable numbers at the moment.) And you are right. I think I should spend more time looking into the source tree and try to get rid of tree.h in favour of rb.c, and make the later better. And incorporate rb.c into jemalloc.c, if no one else is doing this. :) Kind regards, Adam
Attachment:
tree.h.pch
Description: Binary data