lkml.org 
[lkml]   [1999]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: random table-driven hash benchmarked
>here's the multiplicative hash, for comparison:
>
>/* this is 40499 * 65543 - both are prime; the result is ~0.68*(2^32) */
>#define MULTIPLIER 2654425957UL
>
>#define _hashfn(dev,block) \
> ((((unsigned long) (block) * MULTIPLIER) >> 11) & bh_hash_mask)

Here is an improved version of the multiplicative hash. It includes
some statistics (alt-SysRq-m). The size of the hash buffer can be
adjusted by changeing HASHBITS in the range of 10-15. On my system with
64MB RAM a hash table size of 4096 entries is big enough
(#define HASHBITS 12). It's tested on 32 bit x86 processors, but I
tried to make it working on 64 bit systems too.

The patch is against 2.2.6.

Peter


--- fs/buffer.c.ori Sun Apr 25 00:11:15 1999
+++ fs/buffer.c Sun Apr 25 00:45:07 1999
@@ -54,7 +54,13 @@
#define NR_RESERVED (2*MAX_BUF_PER_PAGE)
#define MAX_UNUSED_BUFFERS NR_RESERVED+20 /* don't ever have more than this
number of unused buffer heads */
+/*
+ * hash table size
+ * valid range for Intel PCs: 10-15
+ */

+#define HASHBITS 14
+
/*
* Hash table mask..
*/
@@ -420,7 +426,8 @@
}
}

-#define _hashfn(dev,block) (((unsigned)(HASHDEV(dev)^block)) & bh_hash_mask)
+#define _hashfn(dev,block) ( \
+ ( (((unsigned) (block)* 0x9E3779B1 )>>(32-HASHBITS))^HASHDEV(dev) ) & bh_hash_mask)
#define hash(dev,block) hash_table[_hashfn(dev,block)]

static inline void remove_from_hash_queue(struct buffer_head * bh)
@@ -1484,6 +1491,7 @@
{
struct buffer_head * bh;
int found = 0, locked = 0, dirty = 0, used = 0, lastused = 0;
+ int uc[10], umax = 0;
int protected = 0;
int nlist;
static char *buf_types[NR_LIST] = {"CLEAN","LOCKED","DIRTY"};
@@ -1492,7 +1500,31 @@
printk("Buffer heads: %6d\n",nr_buffer_heads);
printk("Buffer blocks: %6d\n",nr_buffers);
printk("Buffer hashed: %6d\n",nr_hashed_buffers);
-
+
+ uc[0] = uc[1] = uc[2] = uc[3] = uc[4] = 0;
+ uc[5] = uc[6] = uc[7] = uc[8] = uc[9] = 0;
+
+ for(nlist = 0; nlist <= bh_hash_mask; nlist++) {
+ struct buffer_head * next;
+
+ next = hash_table[nlist];
+ used=0;
+ while (next) {
+ used++;
+ next = next->b_next;
+ }
+ if (umax < used) umax = used;
+ if (used > 9) used = 9;
+ uc[used]++;
+ }
+ printk("Longest list: %6d\n", umax);
+ printk(" List size : empty 1 2 3 4 5 6 7 8 >=9\n");
+ printk(" Num : ");
+ for(nlist = 0; nlist <= 9; nlist++) {
+ printk("%6d ", uc[nlist]);
+ }
+ printk("\n");
+
for(nlist = 0; nlist < NR_LIST; nlist++) {
found = locked = dirty = used = lastused = protected = 0;
bh = lru_list[nlist];
@@ -1527,10 +1559,13 @@
*/
void __init buffer_init(void)
{
- int order = 5; /* Currently maximum order.. */
+ int order;
unsigned int nr_hash;

- nr_hash = (1UL << order) * PAGE_SIZE / sizeof(struct buffer_head *);
+ /* is this ok on 64 bit systems? */
+ order = HASHBITS - PAGE_SHIFT +
+ ((sizeof(struct buffer_head *) == 4) ? 2 : 3);
+ nr_hash = (1UL << HASHBITS);
hash_table = (struct buffer_head **) __get_free_pages(GFP_ATOMIC, order);

if (!hash_table)
-
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/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.070 / U:0.476 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site