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

[rmind%NetBSD.org@localhost]

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

State-Changed-From-To: open->closed
State-Changed-By: rmind%NetBSD.org@localhost
State-Changed-When: Thu, 05 Dec 2013 17:58:23 +0000
State-Changed-Why:
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.