Re: 2.5 page cache improvement idea

[Ben LaHaise <bcrl@redhat.com>]

On Mon, 26 Feb 2001, Chuck Lever wrote:

> didn't andrea archangeli try this with red-black trees a couple of years
> ago?

Yes.  However, keep in mind that red-black are not particularly well
suited to the cache design of most modern cpus.

> instead of hashing or b*trees, let me recommend self-organizing data
> structures. using a splay tree might improve locality of reference and
> optimize the tree so that frequently used pages appear close to the
> root.

splay trees might well be an option, however keep in mind the benefits of
the hybrid hash/b*tree structure: for the typical case of a small number
of entries (ie a small file), the hash buckets will provide optimal O(1)
performance.  Once we move into larger data files, the operation becomes
slightly more overhead (but still tunable according by increasing the hash
size) but still relatively low (2 cache misses for a two level b*tree
which maps a *lot* of data).  The problem with something like a splay tree
is that it will generate bus traffic for the common case of reading from
the data file, which is something we don't want for a frequently accessed
mapping like glibc on a NUMA system.  B*trees, while originally designed
for use on disks, apply quite well to modern cache heirarchies.

		-ben

--
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.eu.org/Linux-MM/