Received-SPF: pass (google.com: domain of linux-kernel+bounces-89200-linux.lists.archive=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99;
Precedence: bulk
MIME-Version: 1.0
References: <20240229-zswap-xarray-v2-1-e50284dfcdb1@kernel.org> <26e77602326d4e169a9484314cac2465@AcuMS.aculab.com>
In-Reply-To: <26e77602326d4e169a9484314cac2465@AcuMS.aculab.com>
From: Chris Li <chrisl@kernel.org>
Date: Fri, 1 Mar 2024 14:33:37 -0800
Message-ID: <CAF8kJuP1=n_U4VsPh9eezmta1gYKEt0vqAJSLFnxBFBV1DzHcA@mail.gmail.com>
Subject: Re: [PATCH v2] zswap: replace RB tree with xarray
To: David Laight <David.Laight@aculab.com>
Cc: Andrew Morton <akpm@linux-foundation.org>, 
	"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>, "linux-mm@kvack.org" <linux-mm@kvack.org>, 
	Yosry Ahmed <yosryahmed@google.com>, Nhat Pham <nphamcs@gmail.com>, 
	Johannes Weiner <hannes@cmpxchg.org>, "Matthew Wilcox (Oracle)" <willy@infradead.org>, 
	Chengming Zhou <zhouchengming@bytedance.com>, Barry Song <v-songbaohua@oppo.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Fri, Mar 1, 2024 at 1:58=E2=80=AFPM David Laight <David.Laight@aculab.co=
m> wrote:
>
> From: Chris Li
> > Sent: 29 February 2024 08:46
> >
> > Very deep RB tree requires rebalance at times. That
> > contributes to the zswap fault latencies. Xarray does not
> > need to perform tree rebalance. Replacing RB tree to xarray
> > can have some small performance gain.
> >
> > One small difference is that xarray insert might fail with
> > ENOMEM, while RB tree insert does not allocate additional
> > memory.
>
> What is the difference in kernel memory use?
> IIRC someone pointed out (in the rosebush thread) that xarray
> uses a lot of kernel memory if the items are randomly distributed.

Do you have any suggestions on what script I can run to collect that
information for you?

If the swapfile is fully utilized, then every 1G of swapfile space
will save about 4M of memory using xarray compared to RB tree. Every
swap entry saves about 2 pointers (ignoring the intermedia xarray
node)
Every 1G of swapfile, fully populated xarray pointer uses about 2M of
memory. The RB tree node (left pointer, right pointer, color) will use
about 6M of memory.
In the worst case, you are wasting at most 2M of memory on xarray for
every 1G of swapfile.
Hope that calculation helps.

Keep in mind that the swap cache is already using xarray, using the
same swap entry offset as index. So whatever memory waste caused by
the sparse distribution of the swap entry, you are already getting
that in the current swap cache.

Chris