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: 4+ 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 1:48 ` sashiko-bot
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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.