From: Yury Norov <ynorov@nvidia.com>
To: Matthew Wilcox <willy@infradead.org>
Cc: "Eliot Courtney" <ecourtney@nvidia.com>,
"Greg KH" <gregkh@linuxfoundation.org>,
"Burak Emir" <bqe@google.com>,
"John Hubbard" <jhubbard@nvidia.com>,
"Alice Ryhl" <aliceryhl@google.com>,
"Liam R . Howlett" <liam@infradead.org>,
"Andrew Ballance" <andrewjballance@gmail.com>,
"Alexandre Courbot" <acourbot@nvidia.com>,
"Alistair Popple" <apopple@nvidia.com>,
"Andreas Hindborg" <a.hindborg@kernel.org>,
"Benno Lossin" <lossin@kernel.org>,
"Björn Roy Baron" <bjorn3_gh@protonmail.com>,
"Boqun Feng" <boqun@kernel.org>,
"Daniel Almeida" <daniel.almeida@collabora.com>,
"Danilo Krummrich" <dakr@kernel.org>,
"David Airlie" <airlied@gmail.com>, "Gary Guo" <gary@garyguo.net>,
"Miguel Ojeda" <ojeda@kernel.org>,
"Onur Özkan" <work@onurozkan.dev>,
"Simona Vetter" <simona@ffwll.ch>,
"Tamir Duberstein" <tamird@kernel.org>,
"Timur Tabi" <ttabi@nvidia.com>,
"Trevor Gross" <tmgross@umich.edu>,
"Yury Norov" <yury.norov@gmail.com>, "Zhi Wang" <zhiw@nvidia.com>,
maple-tree@lists.infradead.org, linux-kernel@vger.kernel.org,
nova-gpu@lists.linux.dev, dri-devel@lists.freedesktop.org,
rust-for-linux@vger.kernel.org
Subject: Re: [PATCH] lib: test bitmap vs Maple Tree performance for region allocations
Date: Sat, 11 Jul 2026 01:27:06 -0400 [thread overview]
Message-ID: <alHUKv78lizZeln-@yury> (raw)
In-Reply-To: <alG9NEYLCkMMYTEI@casper.infradead.org>
On Sat, Jul 11, 2026 at 04:49:08AM +0100, Matthew Wilcox wrote:
> On Fri, Jul 10, 2026 at 09:39:09PM -0400, Yury Norov wrote:
> > Compare the cost of allocating and freeing variable-sized regions using
> > a bitmap and a Maple Tree. Both implementations process the same randomly
> > generated sequence of region sizes, ranging from 1 to 32 entries, until
> > the configured capacity is exhausted.
>
> I'd suggest the IDA might be a better comparison than the maple tree.
> Essentially it's a sparse bitmap which plays some fun tricks to lower
> the cost.
>
> Eventually, I expect the IDA to be reimplemented on top of the maple
> tree data structure instead of the XArray.
Sure, will send v2
prev parent reply other threads:[~2026-07-11 5:27 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-07-11 1:39 [PATCH] lib: test bitmap vs Maple Tree performance for region allocations Yury Norov
2026-07-11 3:49 ` Matthew Wilcox
2026-07-11 5:27 ` Yury Norov [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=alHUKv78lizZeln-@yury \
--to=ynorov@nvidia.com \
--cc=a.hindborg@kernel.org \
--cc=acourbot@nvidia.com \
--cc=airlied@gmail.com \
--cc=aliceryhl@google.com \
--cc=andrewjballance@gmail.com \
--cc=apopple@nvidia.com \
--cc=bjorn3_gh@protonmail.com \
--cc=boqun@kernel.org \
--cc=bqe@google.com \
--cc=dakr@kernel.org \
--cc=daniel.almeida@collabora.com \
--cc=dri-devel@lists.freedesktop.org \
--cc=ecourtney@nvidia.com \
--cc=gary@garyguo.net \
--cc=gregkh@linuxfoundation.org \
--cc=jhubbard@nvidia.com \
--cc=liam@infradead.org \
--cc=linux-kernel@vger.kernel.org \
--cc=lossin@kernel.org \
--cc=maple-tree@lists.infradead.org \
--cc=nova-gpu@lists.linux.dev \
--cc=ojeda@kernel.org \
--cc=rust-for-linux@vger.kernel.org \
--cc=simona@ffwll.ch \
--cc=tamird@kernel.org \
--cc=tmgross@umich.edu \
--cc=ttabi@nvidia.com \
--cc=willy@infradead.org \
--cc=work@onurozkan.dev \
--cc=yury.norov@gmail.com \
--cc=zhiw@nvidia.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox