Comments on: Want larger MAPs? Send me some primes.
Ticket #0001344 requests larger MAP (hashed dictionary) sizes.
MAPs auto-expand their hash tables as they grow. The method uses a prime number table, as defined here:
251,
509,
1021,
2039,
4093,
8191,
16381,
32749,
65521,
131071,
262139,
524287,
999983
Divide by two for maximum map values.
Want support for larger maps? If so, continue the prime number pattern of the table, and send it to me.
Oh, and I should note, there's no need to go beyond 2 ** 32.
9 Comments Comments:
Jerry Tsai
23-Nov-2009 22:00:37 |
When I first read your post on R3 Chat, talking about needing a bigger prime number for hash table entries,
I thought that was a scientist's bad joke. Now I know that prime numbers are something related to the hash algorithm that you are using. I realize that the joke is on me. | Jerry Tsai
23-Nov-2009 22:22:59 |
1999993 -> 3999971 -> 7999993 -> 15999989 -> 31999939 -> 63999979
| Jerry Tsai
23-Nov-2009 22:46:41 |
251 -> 509 -> 1021 -> 2039 -> 8191 -> 16381 -> 32749 ->
65521 -> 131071 -> 262139 -> 524287 -> 1048573 (this is different from yours, which is 999983) -> 2097143 -> 4194301 -> 8388593 -> 16777213 -> 33554393 -> 67108859 | Carl Sassenrath
23-Nov-2009 23:55:30 |
Thanks Jerry. The A95 build with those new values will be released soon. BTW, if you want to hit 60M entries, I'll need one more value (greater than 60M * 2.)
| Jerry Tsai
24-Nov-2009 0:08:51 |
-> 134217689 -> 268435399 -> 536870909 (< power 2 29)
| Carl Sassenrath
24-Nov-2009 0:16:22 |
Actually... one that large is going to be a problem. For each element of a MAP, there is storage for 1) the key value 2) the associated value, 3) the hash integer. For 60M elements, you'll need a couple GB of memory. | Jerry Tsai
24-Nov-2009 0:20:27 |
The 60M entries problem is not a problem for me anymore. I am running my REBOL code in a couple hardware servers now. But it's still nice to make REBOL have the ability of super large map! since the 64-bit world is right around the corner. | Maxim Olivier-Adlhoch
24-Nov-2009 8:02:59 |
and I've heard of desktop computers with over 500GB of RAM ! | Carl Sassenrath
24-Nov-2009 14:06:54 |
The change has been implemented in A95. See the note posted to the R3 change log about limits of memory, etc. |
Post a Comment:
You can post a comment here. Keep it on-topic.
|
