linux-kernel - Re: [PATCH] zswap: use B-tree for search

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 18 Nov 2019 11:04:30 -0800
From:   Jörn Engel <joern@...estorage.com>
To:     vitaly.wool@...sulko.com
Cc:     linux-mm@...ck.org, linux-kernel@...r.kernel.org,
        ddstreet@...e.org, akpm@...ux-foundation.org, sjenning@...hat.com,
        johannes@...solutions.net
Subject: Re: [PATCH] zswap: use B-tree for search

On Sun, Nov 17, 2019 at 08:53:32PM +0200, vitaly.wool@...sulko.com wrote:
> From: Vitaly Wool <vitaly.wool@...sulko.com>
> 
> 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+).
> 
> 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.
> 
> 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.
> 
> 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.
> 
> 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.
> 
> Test command:
> $ stress-ng --io 4 --vm 4 --vm-bytes 1000M --timeout 300s --metrics
> 
> 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) == 8)
> +		btree_pgofft_geo = &btree_geo64;
> +	else
> +		btree_pgofft_geo = &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örn

--
Cryptographic protocols should not be designed by a committee.
-- Niels Ferguson & Bruce Schneier