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@xxxxxxxxxxxxxxxxxx]
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@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>
_______________________________________________
devel mailing list
devel@xxxxxxxxxxxxxxxxxxxxxx
http://driverdev.linuxdriverproject.org/mailman/listinfo/devel
