NetBSD-Bugs archive

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

Re: kern/47931 (ptree(9) implementation does not demonstrate O(k) lookup times)

Synopsis: ptree(9) implementation does not demonstrate O(k) lookup times

State-Changed-From-To: open->closed
State-Changed-When: Thu, 05 Dec 2013 17:58:23 +0000
A while ago I did some analysis.  The keys in our ptree(9) implementation 
are externalised, so the cache effects are taking over and performance on 
modern x86 machines barely differs from e.g. rbtree(9).  With larger keys
it gets even worse (i.e. O(k) just shows that it is more expensive).  So, 
this structure is just inefficient.  Close the PR; will get a better one.

Home | Main Index | Thread Index | Old Index