On Wed, Jul 15, 2026 at 10:41:01PM +0100, Pedro Falcato wrote: > On Sat, Jul 11, 2026 at 02:36:01AM -0400, Yury Norov wrote: > > Compare the cost of allocating and freeing variable-sized regions using > > a bitmap, IDA and a Maple Tree. All implementations process the same > > randomly generated sequence of region sizes, ranging from 1 to 32 entries, > > until the configured capacity is exhausted. > > > > Run the benchmark at several capacities to show how the approaches > > scale. Report allocation and free times separately because bitmap, > > IDA and Maple Tree removal have substantially different costs. > > > > On x86/kvm, the output example is: > > > > type alloc (ns) free (ns) capacity memory (B) > > bitmap 179573071 342105 1000000 125000 > > IDA 46555636 33931498 1000000 134864 > > maple 18629665 19741396 1000000 1548304 > > bitmap 1630912 30933 100000 12504 > > IDA 6144785 3354590 100000 14288 > > maple 1745026 1825032 100000 155408 > > bitmap 28448 3374 10000 1256 > > IDA 418978 333641 10000 1872 > > maple 185398 211138 10000 15632 > > bitmap 2253 610 1000 128 > > IDA 42755 36432 1000 144 > > maple 19728 23474 1000 1552 > > > > I don't understand the comparison. bitmap, IDA and maple are > completely different data structures for completely different purposes.
Sure. Please check this link from the patch description: https://lore.kernel.org/all/[email protected]/ The test is very well motivated by that discussion. I'm not saying it compares apples to apples. I'm trying to quantify the answer to a very specific question: what is better for NOVA ID allocator. Or more broadly: what's the best data structure for range ID allocators of a given capacity. > 1) IDA is 16 bytes when empty, maple is 16 bytes when empty, bitmap > is $size bytes > 2) bitmap is statically sized, IDA and maple have to deal with actual > allocation and freeing of memory > 3) xarray and maple (especially maple) are optimized for RCU usage and > have different tradeoffs > 4) IDA does not support ranges > 5) xarray (the underlying data structure for IDA) does not support ranges > in any optimal way > 6) maple is not optimized for 1-sized ranges, nor ID allocation; it > actually stores data, so instead of 1 bit per index you get 8 whole > bytes. > 7) maple and IDA both handle locking implicitly Yes, this to some extent follows John's arguments why bitmaps are preferred for NOVA Id allocator. I'd also add serializeability, if it's needed. > There are also other pressing questions about the benchmark itself: > it's pretty much the ideal scenario for bitmap. It's pretty much the worst scenario for bitmaps, because the test starts searching for a region from the beginning of the bitmap on every iteration, making it "Shlemiel the Painter" algorithm with O(N^2) complexity. If I wanted to cheat, I'd carry the last allocated ID over the loop. It would make the complexity O(N). I could choose to start searching from a random ID, saying it's 'more realistic'. It makes the complexity converging to O(N*logN). This is how cpumask_*_distribute() works, btw. So no, this is far from being the ideal scenario. > doing the find in > bitmap is essentially testing how far the CPU can speculate, and how > large the cache is. It's pretty darn large on modern hardware. Yes, it's a very effective data structure. That's why it's the 2nd most popular in the kernel, after spinlocks. > Since you > never actually free the ranges in any way, every bitmap branch should predict > extremely well. Fragmentation in the bitmap can very quickly turn into a > nightmare, while maple will eat it up just fine. Assuming "fragmentation" is the uniform distribution of free areas, it wouldn't "turn to nightmare", it would asymptotically turn to O(N*logN). > These are very different data structures and picking between them requires > understanding all the tradeoffs. I don't think this benchmark helps with > that. OK, I see. You seemingly think that I want to throw all and every data structure away from the kernel in favor of the bitmaps. No, I don't. Thanks, Yury
