REBOL 3.0

Comments on: Want larger MAPs? Send me some primes.

Carl Sassenrath, CTO
REBOL Technologies
23-Nov-2009 0:45 GMT

Article #0295
Main page || Index || Prior Article [0294] || Next Article [0296] || 9 Comments || Send feedback

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.

Name:

Blog id:

R3-0295


Comment:


 Note: HTML tags allowed for: b i u li ol ul font span div a p br pre tt blockquote
 
 

This is a technical blog related to the above topic. We reserve the right to remove comments that are off-topic, irrelevant links, advertisements, spams, personal attacks, politics, religion, etc.

REBOL 3.0
Updated 24-Mar-2017 - Edit - Copyright REBOL Technologies - REBOL.net