https://searchvoidstar.tumblr.com/post/659634228574715904/an-amazing-error-message-if-you-put-more-than-2-24

 
Research endeavors
RSS    Archive
search(void *)  

Homepage  Twitter   Ask me anything  
August 15, 2021
An amazing error message if you put more than 2^24 items in a JS Map
object

One of the fun things about working with big data is that you can
often hit weird limits with a system.

I was personally trying to load every "common" single nucleotide
polymorphism for the human genome into memory (dbSNP), of which there
are over 37 million entries (there are many more uncommon ones)

Turns out, you may run into some hard limits. Note that these are all
V8-isms and may not apply to all browsers or engines (I was using
node.js for this)

const myObject = new Map();
for (let i = 0; i <= 50_000_000; i++) {
myObject.set(i,i);
if(i%100000==0) { console.log(i) }
}


This will crash after adding approx 16.7M elements and say



0
100000
200000
...
16400000
16500000
16600000
16700000

Uncaught RangeError: Value undefined out of range for undefined
options property undefined


That is a very weird error message. It says "undefined" three times!
Much better than your usual "TypeError: Can't find property 'lol' of
undefined". See https://bugs.chromium.org/p/v8/issues/detail?id=11852
for a bug filed to help improve the error message perhaps.

Now, also interestingly enough, if you use an Object instead of a Map


const myObject = {};
for (let i = 0; i <= 50_000_000; i++) {
myObject['myobj_'+i]=i;
if(i%100000==0) { console.log(i) }
}



Then it will print....

0
100000
200000
...
8000000
8100000
8200000
8300000

And it will actually just hang there...frozen...no error message though!
And it is failing at ~8.3M elements. Weird right? This is roughly
half the amount of elements as the 16.7M case

Turns out there is a precise hard limit for the Map case

For the Map: 2^24=16,777,216

For the Object it is around 2^23=8,388,608 HOWEVER, I can actually
add more than this, e.g. I can add 8,388,609 or 8,388,610 or even
more, but the operations start taking forever to run, e.g. 8,388,999
was taking many minutes


Very weird stuff! If you expected me to dig into this and explain it
in deep technical detail, well, you'd be wrong. I am lazy. However,
this helpful post on stackoverflow by a V8 js engine developer
clarifies the Map case!! https://stackoverflow.com/questions/54452896
/maximum-number-of-entries-in-node-js-map



V8 developer here. I can confirm that 2^24 is the maximum number of
entries in a Map. That's not a bug, it's just the
implementation-defined limit.

The limit is determined by:

  * The FixedArray backing store of the Map has a maximum size of 1GB
    (independent of the overall heap size limit)
  * On a 64-bit system that means 1GB / 8B = 2^30 / 2^3 = 2^27 ~=
    134M maximum elements per FixedArray
  * A Map needs 3 elements per entry (key, value, next bucket link),
    and has a maximum load factor of 50% (to avoid the slowdown
    caused by many bucket collisions), and its capacity must be a
    power of 2. 2^27 / (3 * 2) rounded down to the next power of 2 is
    2^24, which is the limit you observe.

FWIW, there are limits to everything: besides the maximum heap size,
there's a maximum String length, a maximum Array length, a maximum
ArrayBuffer length, a maximum BigInt size, a maximum stack size, etc.
Any one of those limits is potentially debatable, and sometimes it
makes sense to raise them, but the limits as such will remain. Off
the top of my head I don't know what it would take to bump this
particular limit by, say, a factor of two - and I also don't know
whether a factor of two would be enough to satisfy your expectations.


Great details there. It would also be good to know what the behavior
is for the Object, which has those 100% CPU stalls after ~8.3M, but
not the same error message....




Another fun note: if I modify the Object code to use only "integer
IDs" the code actually works fine, does not hit any errors, and is
"blazingly fast" as the kids call it


const myObject = {};
for (let i = 0; i <= 50_000_000; i++) {
myObject[i]=i;
if(i%100000==0) { console.log(i) }
}


I presume that this code works because it detects that I'm using it
like an array and it decides to transform how it is working
internally and not use a hash-map-style data structure, so does not
hit a limit. There is a slightly higher limit though, e.g. 1 billion
elements gives "Uncaught RangeError: Invalid array length"


const myObject = {};
for (let i = 0; i <= 1_000_000_000; i++) {
myObject[i]=i;
if(i%100000==0) { console.log(i) }
}


This has been another episode...of the twilight zone (other episodes
catalogued here) https://github.com/cmdcolin/technical_oddities/

9:10pm  |   URL: https://tmblr.co/Z7wt8tadVTO3ue00
(View comments) 
(Notes: 4)
  
Filed under: code 

 1. [octahedron]packu liked this
 2. [avatar_2b0]b8horpet liked this
 3. [avatar_196]wildberry-reblog reblogged this from searchvoidstar
 4. [avatar_42c]wildberry-art liked this
 5. [avatar_58c]searchvoidstar posted this

        One of the fun things about working with big data is that you
        can often hit weird limits with a system.

View the discussion thread
Blog comments powered by Disqus
RSS feed: https://searchvoidstar.tumblr.com/rss
Next post
[                    ] [Search]
Theme is The Atlantic by Peter Vidani for Tumblr.
[impixu][impixu]