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 X-Spam-Level: X-Spam-Status: No, score=-2.0 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1BDB4C43215 for ; Mon, 18 Nov 2019 19:04:36 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id D92BA2063A for ; Mon, 18 Nov 2019 19:04:35 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=purestorage.com header.i=@purestorage.com header.b="CFzGLpEv" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org D92BA2063A Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=purestorage.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 722E76B0003; Mon, 18 Nov 2019 14:04:35 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 6D3EA6B0006; Mon, 18 Nov 2019 14:04:35 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5E9FE6B0007; Mon, 18 Nov 2019 14:04:35 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 496236B0003 for ; Mon, 18 Nov 2019 14:04:35 -0500 (EST) Received: from smtpin05.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay04.hostedemail.com (Postfix) with SMTP id EE25B4DCB for ; Mon, 18 Nov 2019 19:04:34 +0000 (UTC) X-FDA: 76170324468.05.berry97_7f43b6505b311 X-HE-Tag: berry97_7f43b6505b311 X-Filterd-Recvd-Size: 4965 Received: from mail-pf1-f196.google.com (mail-pf1-f196.google.com [209.85.210.196]) by imf39.hostedemail.com (Postfix) with ESMTP for ; Mon, 18 Nov 2019 19:04:34 +0000 (UTC) Received: by mail-pf1-f196.google.com with SMTP id q26so10803466pfn.11 for ; Mon, 18 Nov 2019 11:04:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=purestorage.com; s=google; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:content-transfer-encoding:in-reply-to :user-agent; bh=g7UeeAiDpLXIZyawULy9LChbDuT/bywV3sjowK/21oA=; b=CFzGLpEvo9h0wavIJ3BvGjj0jIxdJfl3uvMW6e/3/t2n6cMtudA+A4GFwZADhoL3E7 z2YU0QkdAvSVsIByFtEpc8VmgrPBUyOtNkkWDXcSgqDMLrgm/16SLQ6Qy2wg++nqoQ8u voZe3/N/5SNSh94yGyJbvTZV/kWNwLyQMNDC8= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:content-transfer-encoding :in-reply-to:user-agent; bh=g7UeeAiDpLXIZyawULy9LChbDuT/bywV3sjowK/21oA=; b=GoQia3hdQVOY5jqx/T7M1tnIPaGTkSTB5/xyNfIstI1xLTdK0P3vgTFbXXP3l5DsML ZYSAB2Xygr1uhcnrmAZglPUekBHURUFWrtPnZz2favz5UhSBI86oBMgUhMX5U6z/WAXg ElLHg3UOFM80ULqgSF2rLVKFexxkDPsvRccrgZhmqp/yPPSeWXRCtGYwIdeEbArvwveS oRcg0gS45s2s6BPFsn+/4TYJajfAMITr65MUQxDj+dCbbdewH/m1zGK9sGP7eZ9kFaQ9 XVPNPIO6uj99Acv/Hu3Y9Ay+gN3FiF3trOSK59yzYEnHhxF4rsb2/deO7U5YKLzp90QO cPMg== X-Gm-Message-State: APjAAAVAcYEuTHy1uAIng20dSB8TzrZFHJKz+pmdr6gg6mVajgtvTbi9 Y12ythrAeMZ+HALrrO8EvA/rcA== X-Google-Smtp-Source: APXvYqyN61GhWD0e4l8K0o5t6WK1hRFpzORALbbg2skfjaUQSNQ00893/Ae5TjNzrzgd5tHXUVwy3A== X-Received: by 2002:a63:1b4e:: with SMTP id b14mr927755pgm.280.1574103872977; Mon, 18 Nov 2019 11:04:32 -0800 (PST) Received: from cork ([64.84.68.252]) by smtp.gmail.com with ESMTPSA id d187sm5272521pgc.1.2019.11.18.11.04.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 18 Nov 2019 11:04:32 -0800 (PST) Date: Mon, 18 Nov 2019 11:04:30 -0800 From: =?iso-8859-1?Q?J=F6rn?= Engel To: vitaly.wool@konsulko.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, ddstreet@ieee.org, akpm@linux-foundation.org, sjenning@redhat.com, johannes@sipsolutions.net Subject: Re: [PATCH] zswap: use B-tree for search Message-ID: <20191118190430.GA16134@cork> References: <20191117185332.18998-1-vitaly.wool@konsulko.com> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline In-Reply-To: <20191117185332.18998-1-vitaly.wool@konsulko.com> User-Agent: Mutt/1.10.1 (2018-07-13) Content-Transfer-Encoding: quoted-printable 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: On Sun, Nov 17, 2019 at 08:53:32PM +0200, vitaly.wool@konsulko.com wrote: > From: Vitaly Wool >=20 > The current zswap implementation uses red-black trees to store > entries and to perform lookups. Although this algorithm obviously > has complexity of O(log N) it still takes a while to complete > lookup (or, even more for replacement) of an entry, when the amount > of entries is huge (100K+). >=20 > B-trees are known to handle such cases more efficiently (i. e. also > with O(log N) complexity but with way lower coefficient) so trying > zswap with B-trees was worth a shot. >=20 > The implementation of B-trees that is currently present in Linux > kernel isn't really doing things in the best possible way (i. e. it > has recursion) but the testing I've run still shows a very > significant performance increase. >=20 > The usage pattern of B-tree here is not exactly following the > guidelines but it is due to the fact that pgoff_t may be both 32 > and 64 bits long. >=20 > Tested on qemu-kvm (-smp 2 -m 1024) with zswap in the following > configuration: > * zpool: z3fold > * max_pool_percent: 100 > and the swap size of 1G. >=20 > Test command: > $ stress-ng --io 4 --vm 4 --vm-bytes 1000M --timeout 300s --metrics >=20 > This, averaged over 20 runs on qemu-kvm (-smp 2 -m 1024) gives the > following io bogo ops: > * original: 73778.8 > * btree: 393999 Impressive results. Was your test done with a 32bit guest? If yes, I would assume results for a 64bit guess to drop to about 330k. > + if (sizeof(pgoff_t) =3D=3D 8) > + btree_pgofft_geo =3D &btree_geo64; > + else > + btree_pgofft_geo =3D &btree_geo32; > + You could abuse the fact that pgoff_t is the same size as unsigned long and use the "l" suffix variant. But apart from the obvious abuse, the "l" variant hasn't been used before and the implementation appears to be buggy. So no complaints about your use of the interface. J=F6rn -- Cryptographic protocols should not be designed by a committee. -- Niels Ferguson & Bruce Schneier