On Tue, Aug 13, 2013 at 06:44:28PM -0400, Tejun Heo wrote: > Hello, Kent. > > On Tue, Aug 13, 2013 at 03:27:59PM -0700, Kent Overstreet wrote: > > It's only naturally a radix tree problem _if_ you require sparseness. > > Well, it's not necessarily about requiring it but more about surviving > it with some grace when things don't go as expected, which is an > important characteristic for common library stuff.
The patch I posted should solve the high order allocations stuff, and sparseness from cyclic allocations was already solved. > > Otherwise, radix trees require pointer chasing, which we can avoid - > > which saves us both the cost of chasing pointers (which is significant) > > and the overhead of storing them. > > Vast majority of which can be avoided with simple caching, right? Whatever caching optimizations you do with a radix tree version I could apply to this bitmap tree version, and my bitmap tree code is simpler and _considerably_ faster than the existing code. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
