lkml.org 
[lkml]   [1999]   [Jun]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: dynamic hash table allocation
>so, in summary, i don't think any exact calculation will always generate
>an optimal buffer hash table size. guessing is all we can do.

But it makes it easy to estimate how the size of the hashtable will be.
Especially when testing dozens of _hashfn's it's nice to have a
BUF_MEAN_BUFFERS_PER_BUCKET (MBPB). You can simply vary it from 1 to 8
and note down the results. With your patch it get's kind of "shift 11",
"shift 12" or "shift 10" which is not very descriptive. Using different
block sizes makes the results of all current methods bogus anyway.


Anyway... Chuck, did my last mail reach you? It seems some of my latest
mails went to nowhere. According to my benchmarks with various hash
table sizes (1, 2, 4 and 8) a shift value of 6 is about 3-6% faster
than the '>>bh_hash_bits' hashfn in the raw cache performance (du
test).

Typical distribution with >>10 - >>15 (including >>bh_hash_bits), MBPB=2:

Buffer hashed: 14718
Bucket size : empty 1 2 3 4 5 6 7 8 >=9
Num : 24311 5245 1634 708 433 293 126 16 2 0

With >>6, MBPB=2:

Buffer hashed: 14572
Bucket size : empty 1 2 3 4 5 6 7 8 >=9
Num : 20406 10338 1845 172 7 0 0 0 0 0

Golden Ratio, MBPB=2:

Buffer hashed: 14518
Bucket size : empty 1 2 3 4 5 6 7 8 >=9
Num : 20209 10721 1721 113 4 0 0 0 0 0


With >>6, MBPB=1:

Buffer hashed: 14540
Bucket size : empty 1 2 3 4 5 6 7 8 >=9
Num : 51968 12653 859 55 1 0 0 0 0 0

With >>6, MBPB=8:

Buffer hashed: 14675
Bucket size : empty 1 2 3 4 5 6 7 8 >=9
Num : 835 2949 2425 1308 495 123 45 9 3 0

With >>6, MBPB=16:

Buffer hashed: 14528
Longest list: 12
Bucket size : empty 1 2 3 4 5 6 7 8 >=9
Num : 9 393 748 954 904 598 323 121 36 1

Golden Ratio, MBPB=16:

Buffer hashed: 14515
Longest list: 10
Bucket size : empty 1 2 3 4 5 6 7 8 >=9
Num : 39 347 828 949 822 562 339 161 38 11


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/

\
 
 \ /
  Last update: 2005-03-22 13:52    [from the cache]
©2003-2011 Jasper Spaans. Advertise on this site