iterating a big list of objects throws a memory issue

Question

I'm writing a function which iterate through a list of objects and should return: true if all the items have the attributes (cp and type). false if all the items haven't the attributes (cp and type). throw an error if one of the attribute is missed in the object.

const checkList = (list) => {
    if (list && !list.length) return false
    console.time('setCheckList')
    const dict = {
        withCpCount: 0,
        withoutCpCount: 0,
        total: 0
    }
    for (elem of list) {
        const {cp, type} = elem

        if((!cp && type) || (cp && !type)) {
            throw new Error('The cp/type is not exclusive')
        }

        if (cp && type && dict.withCpCount === dict.total) {
            dict.withCpCount += 1
        } 
        if (!cp && !type && dict.total === dict.withoutCpCount){
            dict.withoutCpCount += 1
        }
        dict.total += 1

        if ((dict.withCpCount > 0 && dict.total  !== dict.withCpCount) 
            || (dict.withoutCappingCount > 0 && dict.total  !== dict.withoutCpCount)) {
            throw new Error('All items should have the same shape')
        }
    }
    
     if (dict.withoutCpCount) return false
     console.timeEnd('checkList')
     return true;

}

The function works well but I'm trying to generate some data using this function:

const generateList  = (n) => {
    return Array.from({length: n}, (x, i) => ({
        lat: Number((Math.random() * 100).toFixed(5)),
        lon: Number((Math.random() * 100).toFixed(5)),
        rad: Number((Math.random() * 100).toFixed(5)),
        cp: parseInt(Math.random() * 10000 + 1),
        type: 'imp'
    }))
}

Then I tested with huge value like 10Exp7 and 10Exp8 but I got a heap out of memory, and I wonder if I should increase the memory using export NODE_OPTIONS=--max-old-space-size=8192 or the function should be moree optimized. I got this issue when I increase the number:

<--- Last few GCs --->
ca[12998:0x102d88000]    50019 ms: Mark-sweep 2047.7 (2050.4) -> 2046.7 (2050.4) MB, 741.7 / 0.0 ms  (+ 8.2 ms in 17 steps since start of marking, biggest step 6.0 ms, walltime since start of marking 810 ms) (average mu = 0.165, current mu = 0.074) allocati[12998:0x102d88000]    51104 ms: Mark-sweep 2048.0 (2050.7) -> 2047.0 (2050.7) MB, 1011.9 / 0.0 ms  (+ 12.6 ms in 17 steps since start of marking, biggest step 6.5 ms, walltime since start of marking 1085 ms) (average mu = 0.108, current mu = 0.056) alloc

<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x100a0d8d9]
Security context: 0x3506d33008d1 <JSObject>
    1: /* anonymous */ [0x3506baaf7d59] [/Users/xxx/projects/utils/index.js:~59] [pc=0x3231b97054d9](this=0x3506d787fe99 <JSGlobal Object>,0x350675d804b1 <undefined>,21011726)
    2: from [0x3506d331a659](this=0x3506d331a4b1 <JSFunction Array (sfi = 0x350622812af9)>,0x3506baaf7d91 <Object map = 0x350650b89949>,0x3506baaf7d59 <JSFunction (sfi = 0x3506618d4...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
 1: 0x101204d65 node::Abort() (.cold.1) [/usr/local/bin/node]
 2: 0x1000a5fd9 node::Abort() [/usr/local/bin/node]
 3: 0x1000a613f node::OnFatalError(char const*, char const*) [/usr/local/bin/node]
 4: 0x1001f0127 v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [/usr/local/bin/node]
xxxx@MacBook-Pro utils % node index.js
**************** Generate list *****************

<--- Last few GCs --->

[13738:0x102d88000]    33405 ms: Scavenge 2715.1 (2733.7) -> 2699.1 (2733.7) MB, 1.7 / 0.0 ms  (average mu = 0.988, current mu = 0.988) allocation failure 
[13738:0x102d88000]    33503 ms: Scavenge 2719.2 (2738.0) -> 2703.2 (2738.0) MB, 1.7 / 0.0 ms  (average mu = 0.988, current mu = 0.988) allocation failure 
[13738:0x102d88000]    33599 ms: Scavenge 2723.3 (2742.0) -> 2707.4 (2742.0) MB, 1.7 / 0.0 ms  (average mu = 0.988, current mu = 0.988) allocation failure 


<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x100a0d8d9]
Security context: 0x1362a92408d1 <JSObject>
    1: from [0x1362a925a659](this=0x1362a925a4b1 <JSFunction Array (sfi = 0x1362567d2af9)>,0x1362a37045d9 <Object map = 0x13628ca099e9>,0x1362a37045a1 <JSFunction (sfi = 0x13621754b531)>)
    2: generateList [0x1362a3704619] [/Users/xxx/projects/utils/index.js:59] [bytecode=0x13621754b5f1 offset=30](this=0x136275d3f759 <JSGlobal Object>,1000000000)
    3:...

FATAL ERROR: invalid table size Allocation failed - JavaScript heap out of memory
 1: 0x101204d65 node::Abort() (.cold.1) [/usr/local/bin/node]
 2: 0x1000a5fd9 node::Abort() [/usr/local/bin/node]
 3: 0x1000a613f node::OnFatalError(char const*, char const*) [/usr/local/bin/node]
 4: 0x1001f0127 v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [/usr/local/bin/node]
 5: 0x1001f00c7 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [/usr/local/bin/node]
 6: 0x100388e85 v8::internal::Heap::FatalProcessOutOfMemory(char const*) [/usr/local/bin/node]
 7: 0x10058df7f v8::internal::HashTable<v8::internal::NumberDictionary, v8::internal::NumberDictionaryShape>::EnsureCapacity(v8::internal::Isolate*, v8::internal::Handle<v8::internal::NumberDictionary>, int, v8::internal::AllocationType) [/usr/local/bin/node]
 8: 0x10058eef2 v8::internal::Dictionary<v8::internal::NumberDictionary, v8::internal::NumberDictionaryShape>::Add(v8::internal::Isolate*, v8::internal::Handle<v8::internal::NumberDictionary>, unsigned int, v8::internal::Handle<v8::internal::Object>, v8::internal::PropertyDetails, int*) [/usr/local/bin/node]
 9: 0x1004f6112 v8::internal::(anonymous namespace)::DictionaryElementsAccessor::AddImpl(v8::internal::Handle<v8::internal::JSObject>, unsigned int, v8::internal::Handle<v8::internal::Object>, v8::internal::PropertyAttributes, unsigned int) [/usr/local/bin/node]
10: 0x10055db56 v8::internal::JSObject::AddDataElement(v8::internal::Handle<v8::internal::JSObject>, unsigned int, v8::internal::Handle<v8::internal::Object>, v8::internal::PropertyAttributes) [/usr/local/bin/node]
11: 0x10059e71b v8::internal::Object::AddDataProperty(v8::internal::LookupIterator*, v8::internal::Handle<v8::internal::Object>, v8::internal::PropertyAttributes, v8::Maybe<v8::internal::ShouldThrow>, v8::internal::StoreOrigin) [/usr/local/bin/node]
12: 0x100551a08 v8::internal::JSObject::DefineOwnPropertyIgnoreAttributes(v8::internal::LookupIterator*, v8::internal::Handle<v8::internal::Object>, v8::internal::PropertyAttributes, v8::Maybe<v8::internal::ShouldThrow>, v8::internal::JSObject::AccessorInfoHandling) [/usr/local/bin/node]
13: 0x10054e074 v8::internal::JSObject::CreateDataProperty(v8::internal::LookupIterator*, v8::internal::Handle<v8::internal::Object>, v8::Maybe<v8::internal::ShouldThrow>) [/usr/local/bin/node]
14: 0x1006ccd10 v8::internal::Runtime_CreateDataProperty(int, unsigned long*, v8::internal::Isolate*) [/usr/local/bin/node]
15: 0x100a0d8d9 Builtins_CEntry_Return1_DontSaveFPRegs_ArgvOnStack_NoBuiltinExit [/usr/local/bin/node]
zsh: abort      node index.js

It's just a question related to performance when iterating on a list with huge number of items.

Answer 1

As @JaeBradley says, the out-of-memory error doesn't seem to have anything to do with the function you want to to have reviewed, so I'll just do a regular review, but I've added some words about this at the end.

Code style

Personally I'm not a big fan of using the lambda notation to define top-level functions. Using the function keyword makes the purpose of the code (to define a function) clearer to me.

I'm also not a big fan of leaving out the semicolons. This requires you to memorize the rules of automatic semicolon insertion in order to avoid formatting the code in a way, that accidentally a semicolon is inserted where you don't want one. I find it easier, just to use semicolons.

Generally it's considered a bad style to leave out the braces for single statement blocks (if (list && !list.length) return false).

You have a few inconsistencies in the spacing, e.g. sometimes missing a space after a keyword (if() or between ) and {.

Generally you may want to look into using a linter, maybe one that automatically inserts the semicolons for you.

Programming style

The condition if (list && !list.length) looks strange to me and is a potential bug. That condition explicitly allows an undefined/null list to continue only to generate a reference error when the for loop is reached.

Either your contract disallows passing in undefined or null in the first place, then in that case you can just as well leave out list &&, because it doesn't matter when the reference error is thrown. Or the condition should be !list || !list.length.

You are missing a let to declare elem in for (elem of list) { making elem a global variable. Make sure you are using strict mode and then you'll get an error in those cases.

The use of a (badly named) object (dict) instead of just three local variables (let withCpCount = 0; etc.) is strange and makes the code less readable.

The two if statements

if (cp && type && dict.withCpCount === dict.total) {
    dict.withCpCount += 1
} 
if (!cp && !type && dict.total === dict.withoutCpCount){
    dict.withoutCpCount += 1
}

could be combined with an else and in that case the part !cp && !type && can be left out, because that will always be true at that point:

if (cp && type && dict.withCpCount === dict.total) {
    dict.withCpCount += 1
} else if (dict.total === dict.withoutCpCount){
    dict.withoutCpCount += 1
}

You should be careful using JavaScript's truthy/falsy logic to validate cp and type. In my experience real life data rarely conforms to those conditions. You should at the very least extract that logic into two separate functions and then you only have one place to change:

function checkCp(cp) {
   return !!cp; // Or replace with an explicit check for zero, for example
}

function checkType(type) {
   return !!type; 
}

Finally the use of exceptions as a "return value" is not optimal, unless those cases never (or very seldom) occur. If it's a common occurrence you may want to look into alternatives.

Logic

The function is a bit over-engineered. There is no real need to count the items that validate. You can just look at the state of the first item and make sure the other items match that state. For example:

function checkItem(item) {
  const cpState = checkCp(item.cp);
  const typeState = checkType(item.type);
  if (cpState !== typeState) {
    throw new Error('The cp/type is not exclusive');
  }
  return cpState;
}

function checkList(list) {
  if (!list || !list.length) { return false; }
  const firstState = checkItem(list[0]);
  // This unnecessarily checks the first item again, however it is much
  // more work skipping the first item, than just repeating the check,
  // especially if the list is millions of items long anyway.
  if (!list.every(item => firstItem === checkItem(item))) {
    throw new Error('All items should have the same shape');
  }
  return firstState;
}

Memory problems

As suggested at the start, the memory problems have nothing to do with this function, but with the choice to keep all items in memory at once. If your real life scenario will be to actually work with that many items, then you'll need to find different solution. This depends on where the data is coming from. I would assume that it's a database. In that case you should consider either move this logic to the database itself, or implement a solution that reads the items lazily one by one from the database (usually using a "database cursor").