From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756023Ab3EAINU (ORCPT ); Wed, 1 May 2013 04:13:20 -0400 Received: from mail-ye0-f176.google.com ([209.85.213.176]:51677 "EHLO mail-ye0-f176.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753821Ab3EAINP (ORCPT ); Wed, 1 May 2013 04:13:15 -0400 Message-ID: <5180CD1C.7050206@gmail.com> Date: Wed, 01 May 2013 16:06:52 +0800 From: Ric Mason User-Agent: Mozilla/5.0 (X11; Linux i686; rv:17.0) Gecko/20130329 Thunderbird/17.0.5 MIME-Version: 1.0 To: Seth Jennings CC: Dan Magenheimer , Andrew Morton , Greg Kroah-Hartman , Nitin Gupta , Minchan Kim , Konrad Wilk , Robert Jennings , Jenifer Hopper , Mel Gorman , Johannes Weiner , Rik van Riel , Larry Woodman , Benjamin Herrenschmidt , Dave Hansen , Joe Perches , Joonsoo Kim , Cody P Schafer , linux-mm@kvack.org, linux-kernel@vger.kernel.org, devel@driverdev.osuosl.org Subject: Re: [PATCHv6 0/8] zswap: compressed swap caching References: <1361397888-14863-1-git-send-email-sjenning@linux.vnet.ibm.com> <9e251fb2-be82-41d2-b6cd-e46525b263cb@default> <512666B2.1020609@linux.vnet.ibm.com> In-Reply-To: <512666B2.1020609@linux.vnet.ibm.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi Seth, On 02/22/2013 02:25 AM, Seth Jennings wrote: > On 02/21/2013 09:50 AM, Dan Magenheimer wrote: >>> From: Seth Jennings [mailto:sjenning@linux.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. > I considered using a radix tree, but I don't think there is a compelling > reason to choose a radix tree over a red-black tree in this case > (explanation below). > > From a runtime standpoint, a radix tree might be faster. The swap > offsets will be largely in linearly bunched groups over the indexed > range. However, there are also memory constraints to consider in this > particular situation. > > Using a radix tree could result in intermediate radix_tree_node > allocations in the store (insert) path in addition to the zswap_entry > allocation. Since we are under memory pressure, using the red-black Then in which case radix tree is prefer and in which case redblack tree is better? > tree, whose metadata is included in the struct zswap_entry, reduces the > number of opportunities to fail. > > On my system, the radix_tree_node structure is 568 bytes. The > radix_tree_node cache requires 4 pages per slab, an order-2 page > allocation. Growing that cache will be difficult under the pressure. > > In my mind, cost of even a single node allocation failure resulting in > an additional page swapped to disk will more that wipe out any possible > performance advantage using a radix tree might have. > > Thanks, > Seth > > -- > To unsubscribe, send a message with 'unsubscribe linux-mm' in > the body to majordomo@kvack.org. For more info on Linux MM, > see: http://www.linux-mm.org/ . > Don't email: email@kvack.org