I put a patch in bug 96461, but should have filed a separate bug. Better patch coming right up. /be

This blocks 96461. I'd like to get the forthcoming patch ASAP. I'll have some measurements to share soon, too. /be

Comment on attachment 52863 [details] [diff] [review] proposed fix: provide SetAlphaBounds API, eliminate sizeLog2 (computable from hashShift), provide TABLE_SIZE macro instead Note to self: test-compile before attaching.

Except: increasing the maximum alpha from .75 to .875 made for longer hash chains and steps over collisions while searching. Running Mozilla with DEBUG_brendan defined, opening a browser window, and then the mail window, and massaging the resulting /tmp/*dhash.bigdump files produced with .75 (0xC0 maxAlphaFrac); and then recompiling with maximum alpha of .875 (0xE0 maxAlphaFrac) and rerunning; I then grepped for the mean steps per search, mean hash chain length, and maximum hash chain length. Given that grep output, I cut the last field of each line (awk '{print $NF}' or the cut commmand). I then sorted the six output files in reverse-numerical order (sort -nr). A little perl helped compare each line from the .75 and the .875 file, keeping score (smaller is better). The results are maximum alpha .75 .875 ----------------------------------- mean steps per search: 94 to 18 mean hash chain length: 44 to 1 maximum hash chain length: 13 to 8 So I'm going to play it safe and leave the default at .75. Final patch in a second. /be

Argh, that was unclear. My scoring counted wins, where the smaller average or maximum won. Ties aren't counted; there were many. Here are the full scores: maximum alpha .75 .875 (ties) ------------------------------------------ mean steps per search: 94 to 18 (312) mean hash chain length: 44 to 1 (379) maximum hash chain length: 13 to 8 (403) So the edge for .75 is not that great. Still, because we've used .75 for so long, I'm inclined to stick with it and let hard cases tune maxAlphaFrac higher via {JS,PL}_DHashTableSetAlphaBounds. Comments? /be

All you big brains, please comment! /be

Comment on attachment 53046 [details] [diff] [review] ok, so *this* is money! r=dbaron if you fix the comment changes that I already pointed out (the mentions of .875 rather than .75 and the change in the definition of the hashShift member).

Comment on attachment 53046 [details] [diff] [review] ok, so *this* is money! sr=waterson

Comments fixed (thanks, dbaron), patch checked in. /be

Marking Verified -

12 years later, it's not that unreasonable anymore to have a hashtable exceeding 16M... see bug 902922.