Re: [PATCH v2] lib: test bitmap vs IDA vs Maple Tree performance for region allocations

Matthew Wilcox <[email protected]> Thu, 16 Jul 2026 15:02:04 +0100
Newsgroups dev.linux.lists.nova-gpu,org.freedesktop.lists.dri-devel,org.kernel.vger.linux-kernel,org.kernel.vger.rust-for-linux
Message-ID <[email protected]>
On Wed, Jul 15, 2026 at 08:52:52PM -0400, Yury Norov wrote:
> 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.

From my work with the IDA, there are definitely ID allocators which
allocate only a single ID, less than ten or less than a hundred.  Could
you scale the benchmark down to 10 and 100 rather than starting at 1000?