linux-kernel - RE: [PATCHv6 0/8] zswap: compressed swap caching

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <9e251fb2-be82-41d2-b6cd-e46525b263cb@default>
Date:	Thu, 21 Feb 2013 07:50:06 -0800 (PST)
From:	Dan Magenheimer <dan.magenheimer@...cle.com>
To:	Seth Jennings <sjenning@...ux.vnet.ibm.com>,
	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
	Nitin Gupta <ngupta@...are.org>,
	Minchan Kim <minchan@...nel.org>,
	Konrad Wilk <konrad.wilk@...cle.com>,
	Robert Jennings <rcj@...ux.vnet.ibm.com>,
	Jenifer Hopper <jhopper@...ibm.com>,
	Mel Gorman <mgorman@...e.de>,
	Johannes Weiner <jweiner@...hat.com>,
	Rik van Riel <riel@...hat.com>,
	Larry Woodman <lwoodman@...hat.com>,
	Benjamin Herrenschmidt <benh@...nel.crashing.org>,
	Dave Hansen <dave@...ux.vnet.ibm.com>,
	Joe Perches <joe@...ches.com>,
	Joonsoo Kim <iamjoonsoo.kim@....com>,
	Cody P Schafer <cody@...ux.vnet.ibm.com>, linux-mm@...ck.org,
	linux-kernel@...r.kernel.org, devel@...verdev.osuosl.org
Subject: RE: [PATCHv6 0/8] zswap: compressed swap caching

> From: Seth Jennings [mailto:sjenning@...ux.vnet.ibm.com]
> Subject: [PATCHv6 0/8] zswap: compressed swap caching
> 
> Changelog:
> 
> v6:
> * fix improper freeing of rbtree (Cody)

Cody's bug fix reminded me of a rather fundamental question:

Why does zswap use a rbtree instead of a radix tree?

Intuitively, I'd expect that pgoff_t values would
have a relatively high level of locality AND at any one time
the set of stored pgoff_t values would be relatively non-sparse.
This would argue that a radix tree would result in fewer nodes
touched on average for lookup/insert/remove.

Do you have evidence that rbtree is better here?
(Preferably over a set of workloads larger than
kernbench and SPECjbb ;-)  Or are there other
important design issues that disqualify a radix tree?

In the end, I guess either one (rbtree or radix tree)
will work, but it would be nice to get this kind of
fundamental design issue properly solved before merging
is to be considered.

Dan
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/