Messages in this thread | | | Date | Fri, 18 Jun 1999 13:27:28 +0200 | From | Peter Steiner <> | Subject | Re: 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/
| |