Messages in this thread Patch in this message | | | Date | Sun, 25 Apr 1999 01:07:04 +0200 | From | Peter Steiner <> | Subject | Re: 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/
| |