From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id DF7B9C54E58 for ; Wed, 20 Mar 2024 10:14:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 73FD66B0098; Wed, 20 Mar 2024 06:14:49 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6EDE76B0099; Wed, 20 Mar 2024 06:14:49 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5B5896B009A; Wed, 20 Mar 2024 06:14:49 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 49A1A6B0098 for ; Wed, 20 Mar 2024 06:14:49 -0400 (EDT) Received: from smtpin17.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id EB6DCA1920 for ; Wed, 20 Mar 2024 10:14:48 +0000 (UTC) X-FDA: 81917008656.17.7DA92BF Received: from mail-qv1-f41.google.com (mail-qv1-f41.google.com [209.85.219.41]) by imf12.hostedemail.com (Postfix) with ESMTP id 9A03B4001C for ; Wed, 20 Mar 2024 10:14:46 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=cmpxchg-org.20230601.gappssmtp.com header.s=20230601 header.b=dilSp0OX; dmarc=pass (policy=none) header.from=cmpxchg.org; spf=pass (imf12.hostedemail.com: domain of hannes@cmpxchg.org designates 209.85.219.41 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1710929687; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=eIdNQKimwbO4SdsHu9cO1H1ZXloSska94vh6QN7qHYo=; b=61YyVsI1hFtsHIYnJgfvfKhTAaaQaQ0MBeP4BnNuqIDDiWQ0055UZZWQKW8hmu7erENX+G VFTZ23OXxWSBiTmhibzVgFDkdG0WJoJRCN9qf/4DJtjszSPQoRnPaR94gWT8GzuPYU4qi8 IDZPPL1vkqTRYhkHszldHFh6Fhcz4NY= ARC-Authentication-Results: i=1; imf12.hostedemail.com; dkim=pass header.d=cmpxchg-org.20230601.gappssmtp.com header.s=20230601 header.b=dilSp0OX; dmarc=pass (policy=none) header.from=cmpxchg.org; spf=pass (imf12.hostedemail.com: domain of hannes@cmpxchg.org designates 209.85.219.41 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1710929687; a=rsa-sha256; cv=none; b=AnMJa1896jOg0B1U0YSKQvMdRjtyEkuenjLtFT9AaeF7D/P28AG14yqIVH/ohKNGYmGNZd 8XMryd+C9Mdc7YV/HaB4PRoA1rytk7USFY9s2xIkKKTycJsjuh1lq1e4HuOmPEqqJzsgUg +/JSbwmgaZuKzwqCtJs4hPFT7tIkCd8= Received: by mail-qv1-f41.google.com with SMTP id 6a1803df08f44-690cd5b0f07so39735596d6.3 for ; Wed, 20 Mar 2024 03:14:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cmpxchg-org.20230601.gappssmtp.com; s=20230601; t=1710929685; x=1711534485; darn=kvack.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=eIdNQKimwbO4SdsHu9cO1H1ZXloSska94vh6QN7qHYo=; b=dilSp0OXfXmJjSGNa0KK9oRXjy01Jfgwjv4ZoXpF6WKrJrOp7xLyM1LCGwtbLLHijC Q+XIwHYfku2irjt42pQcLqiw3JYsSteMRKVET4vKsP7mSMV5HDsKKv4RmaQSXZ7p2vmr 4c6Xmud+bwc2J9YYTn1sJY2T3OCJpIXsYcW2xu6Wu8zPbMVevUklBL/PeeNuyQAzfIja 0HMKcj+dkeLFMg5KH5aPC3KEbUudDRgU3jbYV0/gpj1bKgeZVfiJONQDs7G+1sGtzUgD MVEnD3pAC30o3k7KlUnumityynaAw16TP+E/U+5TD6Lqi8Hym99SnfkXKUdwDjNR7MQX /EZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710929685; x=1711534485; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=eIdNQKimwbO4SdsHu9cO1H1ZXloSska94vh6QN7qHYo=; b=BUY+FpwEk+Savq2rbT27i7F3a2Nu6VDjHFTPP002POHJ2/FsQyoBi9EDJzcmkkpPfk Gg+cZ9Ka9v2qHz0qUgqXUqok1vIlcQH9Shol7guMfmct5zaO6gv51/ftDaGY4EfP3Iqj TmJFSIFairVDcjGGVgJVbEkPgdqZvimGjHCkmh4oX9bPip9EMOfSdD5gxMcp2u8TiDpd Qg9etDD17oFc6ef0CF173Nc5MDjd8qJyDfq14dX7yR7TcvglGVrEz2Oick/+D7ulSqpd 35CBHLQfXrfaHyE351yKm1w212CeCnQlFsWE/USCPBiCsE1jiBFXegGNCb8sU2Xyoh12 TWvg== X-Forwarded-Encrypted: i=1; AJvYcCWfqoyJErGNAR0LPfVUJ6iL6xYHlG/DDqEP5P71jxYGMGhUwphH4hv1JtOuPxeO4S36Hq04jxPm7ROq/Vwn1363Iyg= X-Gm-Message-State: AOJu0YyynjWMYcMzKy/EXIHXgESJLxAERzr//evC3YF8A7em7l8DRi2s 2nzmd+YOJEwm4LvLPP/N8sy+W93tOcFZYhCFXRnt7UhxZxV1jzxHBzwmQi8mQek= X-Google-Smtp-Source: AGHT+IGUfT/MYBgGd9ydckJcwXtGLh1R76fV0hknm0SpugndiPCs6yl7UiANH3JRfS0vaJzxAHIezA== X-Received: by 2002:a05:6214:bc1:b0:690:dcce:227 with SMTP id ff1-20020a0562140bc100b00690dcce0227mr15873225qvb.29.1710929685588; Wed, 20 Mar 2024 03:14:45 -0700 (PDT) Received: from localhost (2603-7000-0c01-2716-da5e-d3ff-fee7-26e7.res6.spectrum.com. [2603:7000:c01:2716:da5e:d3ff:fee7:26e7]) by smtp.gmail.com with ESMTPSA id jn10-20020ad45dea000000b00690dd47a41csm7669869qvb.86.2024.03.20.03.14.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 03:14:45 -0700 (PDT) Date: Wed, 20 Mar 2024 06:14:44 -0400 From: Johannes Weiner To: Chris Li Cc: Andrew Morton , linux-kernel@vger.kernel.org, linux-mm@kvack.org, Yosry Ahmed , Nhat Pham , "Matthew Wilcox (Oracle)" , Chengming Zhou , Barry Song Subject: Re: [PATCH v7] zswap: replace RB tree with xarray Message-ID: <20240320101444.GC294822@cmpxchg.org> References: <20240319-zswap-xarray-v7-1-e9a03a049e86@kernel.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20240319-zswap-xarray-v7-1-e9a03a049e86@kernel.org> X-Rspamd-Queue-Id: 9A03B4001C X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: 6ab43sa7r313ncoka69zyxgk5xdgqscw X-HE-Tag: 1710929686-665497 X-HE-Meta: U2FsdGVkX1+6hAC+PommCFjBD5fUWLkSNhg3HiLiBr2yHoB8Y/+fafjEm4o7HqRF+mxnjet8ePgITUSl9b9JMG9mASOVAVwm6iOBB7bD3kT1rKveq0lMLTfiSP43E3PbuVpLlaPA0FowwExG8WedeemxpwsKYbAdseKAOoTMDxjwuqmQw4+rvTBOScmhSIBucaGlo7tGilCKrgU6F96P7nzMO0EDQa9Wl4aXXrdxlfyXDask7htlNPzViuJj4N89mKFEzi73AG+VQZE2KHnzzjyaUPjR/hW8SG/1UKF87Z03sNGNbtsm7M1R7/vHI7JMgHsbPiIYKcxJ8/S7czLTBQq3Zid52Hd+u5aRCZG8OWrbqJgD69+X545KB3Y6nQrl78QQ+7RnF0p6C0vO5+2rG8QaB0kQ0Iq6SG0aW6swGW0bxLmRF6UV0a8mBmwnjpJikbBYBA6OCl6cbtwrbpKglxOHEW+Pzdm21WklrpD1S2hxk67ZyrREtqjV98dzT4ZzlH6aqj08MrESchygMCrxcTBW8CikMBJx3JZGA+Zmrq+fTyoQCGtgOitJ+HbMYpD7u1ekkO7Ha0wdVTpEGxfZYgW/0Q8LCN6CmDS0RNXtoGizRYBFpWmZ4AsA1RJDD/nkHwapMe2cLGP73i2CWfWfmoNupVvtMrF0Jb+HegTWrH+pfPEp8zupnfWGljsG3Ra9k4pA+xScxkDpk4jQpEiVS4t8A2MREiGJL9rrIyW6+BhVvGx2OCLaMNIPK3Q6LNkJXe1gTnORK1opbtP5CTBb9S4G+u6arGdLjpqUDnamyz+uqb0vr7zI8OHd1R81VOz3/U1/weLYwt9aRvsDvl0PNpKxI+lEzeYSd7u5olhvd+mVgEufMTXdojyKFShX3Rfw56gLeKvs8hpGKId6IMu3BxVF+J7QqkkZKAs2Lj/xTW4Pb0RTJuXJ2Yk/QP029S5mQsFhhJpTv6qAcNlZy8B X38x4SDg uMoxXxVlHPxrzvZ/bHWWZyDfQUV3i1ySr5tkCDYFCDq5p6lfIFEtXDm3lfsPdvb4qYcFQgeqDlkGvOwWoD1tXTEaxKqICHEZbFKwpirsI66Btd/NWTHE0AGYT79vT7nC+1MY/4Tpyapn+e7DWNJc/5I/HckKljz5nYS6rUBRUTfD+cklt6ry+6+LVTqwvKbM+M91t7CoWcK0VHnQGPZnfndbfiv064JZ5dKoJv4ZFLLjeNqnj7rSXm6Ta595COPuNyHaSFZuEWArR9Ox8Wn4UmzeRS7UKvJHNu0fZ9OOeDSSG3DcXdsriEmGm1RzpiJ5J87zvcR3S65bcge09CQgMByammcDyvlyAoo7WTGoSNGXVMGb4rT/CwHB57KjPJBQWSVylgrmT5P7yMdW3Mqn2soyKcWknGzRBiCDkjBXjf8QquLgJ6H/xeZJRZG1GQY4TIPGhkObZX1FPb8seqhnAb9PnxN2K3+GZyc5A7qHFGpcemuEgkxZ2jR0krvDGTBHcG53tAxJPYERIeE/elykZ1yAxVSr5K30zAX5Z X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Tue, Mar 19, 2024 at 10:52:26PM -0700, Chris Li wrote: > 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. > > The zswap_entry size will reduce a bit due to removing the > RB node, which has two pointers and a color field. Xarray > store the pointer in the xarray tree rather than the > zswap_entry. Every entry has one pointer from the xarray > tree. Overall, switching to xarray should save some memory, > if the swap entries are densely packed. > > Notice the zswap_rb_search and zswap_rb_insert always > followed by zswap_rb_erase. Use xa_erase and xa_store > directly. That saves one tree lookup as well. > > Remove zswap_invalidate_entry due to no need to call > zswap_rb_erase any more. Use zswap_free_entry instead. > > The "struct zswap_tree" has been replaced by "struct xarray". > The tree spin lock has transferred to the xarray lock. > > Run the kernel build testing 10 times for each version, averages: > (memory.max=2GB, zswap shrinker and writeback enabled, > one 50GB swapfile, 24 HT core, 32 jobs) > > mm-unstable-a824831a082f xarray v7 > user 3547.264 3541.509 > sys 531.176 526.111 > real 200.752 201.334 > > --- > Reviewed-by: Nhat Pham > > Signed-off-by: Chris Li Excellent! With the checkpatch issues fixed, Acked-by: Johannes Weiner