> From: Keir Fraser [mailto:keir.xen@xxxxxxxxx]
> Subject: Re: Update radix-tree.[ch] from upstream Linux to gain RCU
> On 11/05/2011 21:38, "Dan Magenheimer" <dan.magenheimer@xxxxxxxxxx>
> > I'm not sure the height=0 special-casing is pointless. IIRC, a
> > radix-tree node contains 64 pointers (512 bytes). When trees
> > a single item are common, 512 bytes may be a relatively large
> > For tmem, each tree contains pages from a file, many files on
> > many filesystems are less than one-page, and, when compressed that
> > one page may be represented by far less than 4096 bytes, so avoiding
> > the overhead is a big win.
> > While I like your improvements avoiding the extra args passed on each
> > insert/delete, I'm not sure for tmem the tradeoff is a good one.
> > A basic assumption of tmem is that memory is constrained and
> > CPU cycles are abundant. While we've all been trained to avoid
> > passing parameters when possible to reduce CPU overhead,
> > the world is changing. If radix-tree.c is used in Xen in the future
> > for non-tmem high-frequency inserts/deletes, your CPU optimization
> > is probably best, but for tmem I think it's a net loss as now
> > each radix tree (and there may be thousands or millions in a
> > large tmem-enabled Xen system) "wastes" 24 bytes.
> If this is critical, you simply shouldn't represent such small files
> with a
> radix tree. I'm sure you could easily come up with some scheme to
> switch to
> a single direct reference in the <= 1 page case, thus saving a whole
> radix_tree_root structure (and a radix_tree_node structure if I do kill
> height=0 special case). I'd recommend changing the radix_tree_root
> structure in tmem_object_root into a pointer which points at a
> radix_tree_root or a singleton page, discriminating between these two
> perhaps on pgp_count.
True, the special casing could be handled in tmem. (On the chance
that you decide to do this, the special case only applies if
the pgp_count is 1 AND the index of the page is zero.) Note
also that tmem doesn't have a clue about the size of the file
and may frequently need to change between an object that only
has page index==0 in tmem and one that has more than that.
The net result is that you would simply be moving the special
casing and "automatic transformation" code from radix-tree to
tmem, for a net result of no advantage (AFAICT) and IMHO since
the code needs to be somewhere, it might as well be in radix-tree
since it is already there and debugged for Linux.
Xen-devel mailing list