fs/buffer.c

Peter Steiner (p.steiner@t-online.de)
Sun, 6 Jun 1999 16:31:28 +0200 (CEST)

Could someone please fix the buffer hash in 2.2.9? The current code
allocates one hash bucket for each kb of RAM. This is ridiculous high. But
that's not the worst thing of the current code. The real problem is that
most of the buckets are empty while others may contain up to 100 buffers at
the same time. e.g.:

: Buffer memory: 41600kB
: Buffer heads: 41616
: Buffer blocks: 41600
: Buffer hashed: 41599
: Longest list: 99
: List size : empty 1 2 3 4 5 6 7 8 >=9
: Num : 54534 6719 1907 832 424 196 141 71 76 636

Here 41599 buffers are hashed but only 11002 buckets are actually used, 636
buckets have >=9 entries (=23943 blocks --> more than 50%) and the fullest
bucket has 99 entries. These 23943 blocks are in buckets with an average
size of 37. That hurts.

Please, please. There were several patches on the list fixing that problem.
You can get equal/higher speed with just about 1/8 hashtable size by simply
using a sane _hashfn. If the multiplication scares you, here is a good
lightweight _hashfn:

#define _hashfn(dev,block) \
(((unsigned)((HASHDEV(dev)+block)+(block>>11))) & bh_hash_mask)

It reduces the "Longest List" of the example above to 9:

: Buffer hashed: 41508
: Longest list: 9
: List size : empty 1 2 3 4 5 6 7 8 >=9
: Num : 46735 7905 4290 3257 2031 910 298 91 18 1

Peter

-- 
   _   x    ___
  / \_/_\_ /,--'  p.steiner@t-online.de (Peter Steiner)
  \/>'~~~~//
    \_____/   signature V0.2 alpha


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/