Node.js - Segfault: 11 With Quite Large Array

Question

Second post here and this one's really got me scratching my head. I have a function which processes an array to try to find similar data. The array contains 1410 elements which I consider to be a lot but nothing that Node or my computer shouldn't be able to handle.

My code is giving "Segmentation Fault: 11" error which I found was to do with memory access issues so I even want as far as to test my Mac's RAM but everything's fine. The segfault makes it very difficult to debug which is why I came here.

The code where something is going wrong is within here:

return matchings.map(matchArray => {
  const namesList = matchArray
    .map(matchItem => matchItem.name)
    .sort((a, b) => a.localeCompare(b))

  const symbolsList = matchArray
    .map(matchItem => matchItem.symbol)
    .sort((a, b) => a.localeCompare(b))

  return {
    name: common.getMode(namesList),
    symbol: common.getMode(symbolsList),
    matches: matchArray
  }
}).sort((a, b) => a.name.localeCompare(b.name))

Where matchings is the array I'm talking about. common.getMode(array) has this code:

array.sort()

const stats = {
  top: {
    name: '',
    freq: 0
  },
  current: {
    name: array[0],
    freq: 1
  }
}

for (let idxName = 1; idxName < array.length; idxName++) {
  const currentName = array[idxName]
  const lastName = array[idxName - 1]

  if (currentName === lastName) {
    stats.current.freq++
  } else {
    if (stats.current.freq > stats.top.freq) {
      stats.top.name = stats.current.name
      stats.top.freq = stats.current.freq
    }
    stats.current = {
      name: currentName,
      freq: 1
    }
  }
}

if (stats.current.freq > stats.top.freq) {
  stats.top.name = stats.current.name
  stats.top.freq = stats.current.freq
}

return stats.top.name

It's worth mentioning that when performed with an array of smaller size ~1000, the code works fine which leads me to believe it is not my code. There is also very little content online about Node's Segfault 11 which isn't helping.

Any ideas greatly appreciated!

Answer 1

TL;DR remove stress from the call stack by using tail call optimization.

Edit (with explanation)

See Understanding Javascript Functions Execution... to understand the difference between call stack, memory heap and queue. Whereas the objects and variables live in heap land, the function calls are referenced in the call stack, which your 2nd dataset depleted (16'000 stack frames) ; so your algorithm couldn't keep up because it had no way to continue allocating new function calls.

See this StackOverflow answer, which points to further information about the call stack and this one too, which points to ways to get data on the heap.

Original answer

I may be completely off, but I'm curious to see if converting your loops to recursion could help the memory cope. I'd try it on my box but setting everything up is a hassle.

Could you try this? It uses spread operator and array destructuring, so you may have to add babel-preset-stage-0 to your project and a .babelrc file too.

Javascript

let common = {};
common.getMode = (arr, compare_fn) => {
  const compare = !!compare_fn ? compare_fn : (a, b) => a.localeCompare(b)
  arr.sort(compare)

  const stats = {
    top: {
      name: '',
      freq: 0
    },
    current: {
      name: arr[0],
      freq: 1
    }
  }

  for (let i=1, imax = arr.length ; i < imax ; ++i) {
    const currentName = arr[i]
    const lastName = arr[i - 1]

    if (currentName === lastName) {
      stats.current.freq++
    } else {
      if (stats.current.freq > stats.top.freq) {
        stats.top.name = stats.current.name
        stats.top.freq = stats.current.freq
      }
      stats.current = {
        name: currentName,
        freq: 1
      }
    }
  }

  if (stats.current.freq > stats.top.freq) {
    stats.top.name = stats.current.name
    stats.top.freq = stats.current.freq
  }

  return stats.top.name
};

const build_prop_list = (prop, input_array, output_array = []) => {
  if(input_array.length == 0) return output_array;
  else {
    const [current, ...tail] = input_array;
    const new_array = [...output_array, current[prop]];
    return build_prop_list(prop, tail, new_array);
  }
}

const work = (input_array, output_array = []) => {
  if(input_array.length == 0) return output_array.sort((a, b) => a.name.localeCompare(b.name));
  else {
    const [matchArray, ...tail] = input_array;

    const namesList = build_prop_list("name", matchArray);
    const symbolsList = build_prop_list("symbol", matchArray);

    const new_element = {
      name: common.getMode(namesList),
      symbol: common.getMode(symbolsList),
      matches: matchArray
    };

    const new_array = [...output_array, new_element];
    return work(tail, new_array);
  }
}

let result = work(insert_your_json_here);

Edit

You may also apply tail call optimization to your for loop in common.getMode(...). The first iteration's behavior is different though, because lastName doesn't reference the last name of the array (index: -1), but the first one. See if it fits your needs and you'd optimize your code a bit more.
This should replace the for loop in common.getMode(...).

  const feed = (input_array) => {
    if(input_array.length == 0) return;
    const [lastName, currentName, ...tail] = input_array;

    if (currentName === lastName) {
      stats.current.freq++
    } else {
      if (stats.current.freq > stats.top.freq) {
        stats.top.name = stats.current.name
        stats.top.freq = stats.current.freq
      }
      stats.current = {
        name: currentName,
        freq: 1
      }
    }

    return feed(tail);
  }(arr);