tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: Red-black tree optimisation

>> 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,

Attachment: tree.h.pch
Description: Binary data

Home | Main Index | Thread Index | Old Index