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 B9DA2C48BF6 for ; Tue, 5 Mar 2024 03:08:20 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4DC766B0085; Mon, 4 Mar 2024 22:08:20 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 48BFB6B0088; Mon, 4 Mar 2024 22:08:20 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3A1B16B008C; Mon, 4 Mar 2024 22:08:20 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 2B2CA6B0085 for ; Mon, 4 Mar 2024 22:08:20 -0500 (EST) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id F2A59140126 for ; Tue, 5 Mar 2024 03:08:19 +0000 (UTC) X-FDA: 81861501918.08.0E517D6 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) by imf18.hostedemail.com (Postfix) with ESMTP id 5B9DA1C000E for ; Tue, 5 Mar 2024 03:08:18 +0000 (UTC) Authentication-Results: imf18.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=1rnRqCMk; spf=pass (imf18.hostedemail.com: domain of 3oYzmZQoKCIoC265Cov0sru22uzs.q20zw18B-00y9oqy.25u@flex--yosryahmed.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=3oYzmZQoKCIoC265Cov0sru22uzs.q20zw18B-00y9oqy.25u@flex--yosryahmed.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1709608098; 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=nDzznBYOi0dF52rtfqsKSRGkfPC1ojEUUGU2w0MtsAs=; b=OjKWi57yVecHXNICiuc+ouH3BMfr3P1o9m21HgHuPbAwe7IWybWB3GTGCmPNMxZtqz9FqN C7g0h2qRqPISg9zOnyHyTwaGMKeV3tbQdK7W1ArGFokJci5grsp31NTey1OWqsuLczjT39 p9DAwF6MM8gYZ+FI/VHCyTiOVI4NsvE= ARC-Authentication-Results: i=1; imf18.hostedemail.com; dkim=pass header.d=google.com header.s=20230601 header.b=1rnRqCMk; spf=pass (imf18.hostedemail.com: domain of 3oYzmZQoKCIoC265Cov0sru22uzs.q20zw18B-00y9oqy.25u@flex--yosryahmed.bounces.google.com designates 209.85.219.202 as permitted sender) smtp.mailfrom=3oYzmZQoKCIoC265Cov0sru22uzs.q20zw18B-00y9oqy.25u@flex--yosryahmed.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1709608098; a=rsa-sha256; cv=none; b=R9HovoCkk6U0K4PJXoQ72nMIpfum+thijACKlWUduWF5Z6E4PuLHBPgThUDctdmewS+/hC /wWfc4iTxWx+Osf56J+1F78gLtwWegZrWK3i+ps8iV4heo9s9/rvTCP2NZWrU+bWwZNbBP RnZ3StR5f+0y3z+F8Oapsv9JtPEODQQ= Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-dc6b26845cdso8051934276.3 for ; Mon, 04 Mar 2024 19:08:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1709608097; x=1710212897; darn=kvack.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=nDzznBYOi0dF52rtfqsKSRGkfPC1ojEUUGU2w0MtsAs=; b=1rnRqCMkkGwnS9Kh0zJrrFV0iWdx/jfcSb1dZVRadmKY60ia7Odm+5DtGW5KevH6Ph mVJoZkHZOtg4YLEual07Gm6zuNScZhYRgIIH9yAaVUuLZUq5F9bPCySFixfKVI2zwFq+ RYH7AFSvbqBLsi7t/uSIN3LZcXBeHs5+Ww0+fdUzLrubv3Gx7whhiaP3jad+gCUMiE8Y ew6T62wce8L/RRetM9n8uGGAX9IUgRXN/Rnp04LNO+84Y7upwAhO6Cpljc5lDN8RKbdQ FMixpdL0OzQWsmXjhNtArEwveSYrZ3IbEA6KbuEb8rz57lcCzTrPHOvlkx+VkMnR2DR8 a41A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709608097; x=1710212897; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=nDzznBYOi0dF52rtfqsKSRGkfPC1ojEUUGU2w0MtsAs=; b=DUlNG5zNncNmRKBCVBrA2VIp5Ywv0RYWeoy9dcA08WTYosWJ1vQnTs5kC68QZ/spz/ YXlxXWVvMa1oUeHyE4mWJiJHpexMr6qtuK+y7jKyRfwLw4nh8t8NJsf2GSBVySbGuR/M c4VxMCxXdFO0+Wfu0QnYMxk7Aq/uUfp0D2U3B3btVF7V8qK3fJ5sADYINJf0eUHb8mSo nRjjg7xu6smakW/QolCIsNfiGkL5tWE8tVpDG18kjxiYbA5dIPpBuaNkznc5DPVc7wuA Gl1+fX9RABylR760M04NktyBRjZqnFSiFyKahrBgDDeMsu7eR6fPSDVM3kV/OWCeXk4u /VQQ== X-Forwarded-Encrypted: i=1; AJvYcCUrMLDuTfXGpRzrCGRV5dSSA/7dgIIzseEPyP86Z8dVTeQH2BF4tW+sgh68uPHbMT8qL3caXRK+AmfVnmipEFXI5pM= X-Gm-Message-State: AOJu0Ywfmrc9fm6Pe3Q1otN/Lhsu84x96ZqJ0rINZhi/7TZ4/hE0AI98 oPvF/0uS/JGRmfEuiQVUnzvSq4WnWd4wGh8REycz0u23eeSK85mDF0Q7VjRPHrIy1QX/PkljgMY HAYw3pYznNm8UVF8Hng== X-Google-Smtp-Source: AGHT+IHTEk4Zd44swTyP6CvApoyuoRjmegZa4AO1IVkvbSIipJki8ATrFIgu/J/HXlP8DjKh4LNIawbeTiiM6cqz X-Received: from yosry.c.googlers.com ([fda3:e722:ac3:cc00:20:ed76:c0a8:29b4]) (user=yosryahmed job=sendgmr) by 2002:a05:6902:124a:b0:dc6:e1ed:bd1a with SMTP id t10-20020a056902124a00b00dc6e1edbd1amr2743294ybu.2.1709608097459; Mon, 04 Mar 2024 19:08:17 -0800 (PST) Date: Tue, 5 Mar 2024 03:08:15 +0000 In-Reply-To: <26e77602326d4e169a9484314cac2465@AcuMS.aculab.com> Mime-Version: 1.0 References: <20240229-zswap-xarray-v2-1-e50284dfcdb1@kernel.org> <26e77602326d4e169a9484314cac2465@AcuMS.aculab.com> Message-ID: Subject: Re: [PATCH v2] zswap: replace RB tree with xarray From: Yosry Ahmed To: David Laight Cc: "'Chris Li'" , Andrew Morton , "linux-kernel@vger.kernel.org" , "linux-mm@kvack.org" , Nhat Pham , Johannes Weiner , "Matthew Wilcox (Oracle)" , Chengming Zhou , Barry Song Content-Type: text/plain; charset="us-ascii" X-Rspamd-Queue-Id: 5B9DA1C000E X-Rspam-User: X-Stat-Signature: ndrhhoeiihc9jm45f1pf44t1nuudyb6w X-Rspamd-Server: rspam01 X-HE-Tag: 1709608098-54944 X-HE-Meta: U2FsdGVkX1+ZJMc5Jh8fgJeHRzGDBOjVR9/VBK8RpCxrvb8VdvY05OaccFL7b3aofRGRixsck5bsNkz8tiMJhPf+ur/AxhtOBakQPSosm+TQd4DHcr2mmyRdkL5lMB3iF8zR7UagaXRs4TwMz7BR/mchY3BemAzR4A8XHxTrzh9Z/Dy1kcyqBAii7hyT37Sb/PaUTYa4m4yxBL2OUJztKISsxGYjrPCADHK8C0RbgJf8bNGlPgZ2C4Iimw0wsuAa8StWcyuTOA0xaChmZ8DObyAe62WZsnbMy5/0ag2Gxteo0wDpjs2Seq/6vDY+c1CPdzMkbguwpcaOG6+VX+a2zHd6EQSBqSkPwnHQ4RJNOsANKDdcO1EwpkDo8NkHY/5BnAmSu1G947Qi5SVWj+SvLFt0LTBBgIYy4fy5BKHlKWlAq6YDQgpEH3OGCKo3rZl+679OjO/DA+Cva1AJ+hxKgZr2GsH1jlOkgb3SMbbFg9eeiCNeNaWRqMKGqeOAevhKgwJGpckFoE7WUUe73MBdMkPCrTY64XSZTfN/Z2ur2wObB0UnEagF31+CVZlhsd3lVtvXkf02eHD2k/Mlb5nsOgQ86djsNDpA8rr3xkvBU4Xs23OyZ4DsyPkscdgvXA6InUSsqCSBJ0slgFUk/CAdziwKuYcC4w1361tonhtEgsz/0+urshvtzIvVmUjMksPtlDfvKWPskCVgJW5fRNmZd/98U57GIHT5Rt/j8yTABMkFrOtHZjXA6a+JQ3s+S185zhtGULcMsMZedGe1koaTf9BJRgsP7LYPQOPacZBmdj/WOV/gtb8TEzJJfvSTO8DcFEe1Uuqu+YCPFe2WdJVBMzgRI4/oiVhnhrKe/JeQVC6WalIkStTAne9gaXBYp9sfqce8Fg9cUPr2tcaW2G7CZuWpe+ugQczqXhbROAz40dxcQKeHuoRoVAsmDgGmFYu20GDUyehi0barrn8F7uP 4aDZ6P3f fcvNbW6yiLAx7dzZIJjirmH2MMiYy/XhL0ArMLsqwrkmZ15cScZKf95g6iyMXkLUwQc2bw59hfzJIN0bG9ueGVNv6JJxY2tx09BcKsl/woVQF1ND0NXX4lmE8omVlrGhHfsd7ll57OTQEFVh0vFACVyLLsH7pYO296ab5cg1SjAdnkEcTi6bdhuINsX3NYcaG+Mpb1if2soXGCdo38GfHCjdR+uMY4wY50tmXKQpQAE2RyBnmAQzL3spZDl0X8HqWHev/D5SfEJHobckYMoNJ1Y9epKLlVo1gQpOGhRxwWzImE23vuST0Z7gTq+MjJzjkBjSKXs/hjJyreQeIRMIB1A8Oa8U9/tRI5txVhzzIcapQJ3mnHYL+aS/sCDvls+BPu3PKgy63WvjTBnvUQcHf/qH5zMiwrH7BpEaxEZR2+hy5fQQ= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000548, 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 Fri, Mar 01, 2024 at 09:58:43PM +0000, David Laight 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. I often thought it would be useful if there is an API for the xarray to report how much memory it's using. For zswap, we could plumb this to a debugfs interface or so to measure the tree usage and compare to the rbtree. The cost is fixed with the rbtree IIUC, 3 words per zswap entry.