2
const map = {}

for (let i=0;i<10**5;i++) {
    map[i] = true
}


let ans = 0

for (let i in map) {
    for (let j in map) {
        ans += i+j
    }
}


console.log(ans)

The above code when run using node returns the following error -

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory 1: 0x100037ddb node::Abort() [/usr/local/bin/node]

Can someone explain the reason why? The map gets instantiated just fine. Only when I loop over the map keys and add them to my ans variable I get this issue?

However the following similar code works fine and prints ans - 

let ans = 0

for (let i=0;i<10**5;i++) {
    for (let j=0;j<10**5;j++) {
        ans += i+j
    }
}

console.log(ans)

What is the logic behind this. Why is looping over keys in map so bad?

Node version v10.7.0

Yash Agarwal
  • 955
  • 1
  • 13
  • 28

3 Answers3

6

The problem is your keys are strings, not numbers. You need to call parseInt() or Number() to convert them before adding:

for (let i in map) {
    for (let j in map) {
        ans += Number(i) + Number(j)
    }
}

The loop will still take a long time (you are iterating 10**10 times), but you won't accumulated a huge string that blows up memory usage.

UPDATE: succumbed to the primacy of using Number() instead of parseInt().

Jim B.
  • 4,512
  • 3
  • 25
  • 53
  • So you are saying the error is due to OP creating a string that is "too large"? FWIW, no need for `praseInt`. Use `Number(i)` or `+i`. – Felix Kling Nov 06 '18 at 19:15
  • 1
    Yep. The string was getting to be huge. And yes, there are other ways to convert a string to a Number. I didn't think that particular optimization was the point of the question. – Jim B. Nov 06 '18 at 19:16
  • *"I didn't think that particular optimization was the point of the question."* Sure. I would just use the simplest solution possible. `parseInt` is just unnecessary. The real optimization would be to move `i = parseInt` or whatever in the outer loop. – Felix Kling Nov 06 '18 at 19:19
  • 1
    and if you use parseInt, use it with a radix `parseInt(string, 10)` :) – japrescott Nov 06 '18 at 19:20
  • 1
    I'll add the option to the answer, but not sure why parseInt is meaningfully any better or worse than Number(). Maybe a topic for another question. :-) – Jim B. Nov 06 '18 at 19:20
  • *"not sure why parseInt is meaningfully any better or worse than Number()"* `parseInt` does "more", so that it can process strings that *start* with a number. E.g. `parseInt('123foobar')` returns `123`. But all strings in this example only contain digits so there is no need for such functionality. A simply "number cast" suffices. – Felix Kling Nov 06 '18 at 19:22
  • Wouldn't Number() effectively do that same thing? Again, the bug was treating strings as numbers. I'll bet a sandwich there's another SO post on what the most efficient way to convert a string to a number is. Oh, look: https://stackoverflow.com/questions/12862624/whats-the-fastest-way-to-convert-string-to-number-in-javascript . Where's my sandwich? :-) – Jim B. Nov 06 '18 at 19:24
  • The biggest difference is that `parseInt` essential creates a substring first up to the first charcter that is not part of a number. `Number` calls the number conversion algorithm directly. Spec:https://www.ecma-international.org/ecma-262/9.0/index.html#sec-parseint-string-radix , https://www.ecma-international.org/ecma-262/9.0/index.html#sec-number-constructor-number-value – Felix Kling Nov 06 '18 at 19:29
  • Thanks. Good to know. You are relieved of your sandwich debt. :-) – Jim B. Nov 06 '18 at 19:31
  • My point was only to use the minimal functionality to perform the task. `parseInt` is used too often where it is not necessary. Exaggerated example: You were using the `+` operator because that's the simplest way. You didn't define your own `add` function. I didn't want to start a lengthy discussion :-/ – Felix Kling Nov 06 '18 at 19:31
  • Indeed. Updated the answer to reflect comments. – Jim B. Nov 06 '18 at 19:32
0

when using for..in, you are iterating over all enumerable properties, including the inherited ones on the prototype chain (so for a Object, there are quite a few)

you need to shield your loop from inherited props with hasOwnProperty as it is outlined in the example on MDN

japrescott
  • 4,736
  • 3
  • 25
  • 37
  • 1
    While that is true, `Object.prototype` has like 20 properties or so. That's insignificant compared to the number of properties the OP creates. Plus all of these are non-enumerable, so not an issue. – Felix Kling Nov 06 '18 at 19:13
  • the problem is that those props are functions that become strings with the inferred toString() and add up to a concatenation which causes the memory leak – japrescott Nov 06 '18 at 19:21
  • No, that's not the problem. String concatenation is the problem, yes, but again, none of the properties in `Object.prototype` is included. Plus, property *names* are never functions. Proof: `var ans = 0; for (var i in {1: true, 2: true}) ans += i; console.log(ans);` – Felix Kling Nov 06 '18 at 19:25
0

The reason as mentioned in accepted answer was that I was adding strings. But also converting from string to int is a costly operation specially when looping over such large amount of numbers, it will take forever.

So for someone else who is reading this question and has to use map can use Javascript Map instead of Object as used in my example above because Map can support any type of key (not just strings). So the code for that will be - 

const map = new Map()

for (let i=0;i<10**5;i++) {
    map.set(i, true)
}

let ans = 0

for (const i of map.keys()) {
    for (const j of map.keys()) {
        ans += i + j
    }
}


console.log(ans)
Yash Agarwal
  • 955
  • 1
  • 13
  • 28