Re: [PATCH] Decrease hash table memory overhead

From: Mark Hemment (
Date: Tue Aug 01 2000 - 08:42:50 EST


On Tue, 1 Aug 2000, Keith Owens wrote:
> On Tue, 1 Aug 2000 13:38:16 +0100 (BST),
> Mark Hemment <> wrote:
> > I've attached a patch (against 2.4.0-test5) for the page cache, which
> >demonstrates a technique to reduce the length of re-searching of a chain
> >after its guarding lock has been temporarily dropped (say, for a blocking
> >operation), and the re-search is expected to fail.
> >[snip]
> > By inserting a marker (cookie) as the first object (after the original
> >search and while the guarding lock is still held) gives a well known
> >point at which to terminate a subsequent search (assuming it doesn't match
> >before reaching the marker).
> >[snip]
> There is a method which may give almost the same performance boost but
> is much easier to use. Associate an update counter with each chain
> head. Every add or delete on that chain increments the counter, the
> lock is held so no need for atomic_t counters. If the chain head is
> being updated at the same time then the counter update is almost free,
> assuming the head and the counter are in the same cache line.
> [snip]

  Event counters are light, and should perform well on a chain which
doesn't have a very high frequency of updates.
  Their worse case is much heavier than inserting/removing cookies into a
chain when the chain is long, but that maybe offset by the cases they do
catch (and long chains should be considered a design bug anyway, and
fixed by increasing the size of the hash-table or the hashing algorithm).

  As you mentioned, the only objection is the extra (constantly wired
down) memory they consume.

  Depending on what events are of interest, the counter may only need to
be updated on an insert (and not on a delete).


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Aug 07 2000 - 21:00:05 EST