* H. Peter Anvin <hpa@xxxxxxxxx> wrote: > On 10/18/2010 09:48 AM, Eric Paris wrote: > > > 1) IMA uses radix trees which end up wasting 500 bytes per inode because the key > > is too sparse. I've got a patch which uses an rbtree instead I'm testing and > > will send along shortly. I found it funny working on the patch to see that > > Documentation/rbtree.txt says "This differs from radix trees (which are used to > > efficiently store sparse arrays and thus use long integer indexes to > > insert/access/delete nodes)" Which flys in the face of this report. > > Radix trees can efficiently store data associated with sparse keys *as long as the > keys are clustered*. For random key distributions, they perform horribly. For random key distributions hash and rbtree data structures are pretty good choices. But the (much) more fundamental question is to turn the non-trivial allocation overhead of this opt-in feature into truly opt-in overhead. Thanks, Ingo _______________________________________________ kernel mailing list kernel@xxxxxxxxxxxxxxxxxxxxxxx https://admin.fedoraproject.org/mailman/listinfo/kernel
