"Javascript heap out of memory" using Lodash memoize

Question

I'm trying to solve LeetCode's longest palindromic subsequence problem using Javascript by applying memoization to a recursive solution. Here is the recursive solution, longestPalindromicSubsequence.js:

function longestPalindromicSubsequence(string, start = 0, end = string.length) {
  if (end < start) { return 0; }
  if (start === end) { return 1; }
  if (string[start] === string[end]) {
    return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
  }
  return Math.max(
    longestPalindromicSubsequence(string, start + 1, end),
    longestPalindromicSubsequence(string, start, end - 1),
  );
}

module.exports = longestPalindromicSubsequence;

Here are some Jest test cases for it, longestPalindromicSubsequence.test.js:

const longestPalindromicSubsequence = require('./longestPalindromicSubsequence');

describe('longest palindromic subsequence', () => {
  test('works for aab', () => {
    expect(longestPalindromicSubsequence('aab')).toBe(2);
  });

  test('works for long string', () => {
    expect(longestPalindromicSubsequence(`${'a'.repeat(50)}bcdef`)).toBe(50);
  });
});

This works, but is rather slow due to the exponential increase in the number of recursive calls. For example, for a string of length ~50 it takes 9 seconds:

$ jest longestPalindromicSubsequence.test.js
 PASS  ./longestPalindromicSubsequence.test.js (9.6s)
  longest palindromic subsequence
    ✓ works for aab (3ms)
    ✓ works for long string (9315ms)

Test Suites: 1 passed, 1 total
Tests:       2 passed, 2 total
Snapshots:   0 total
Time:        10.039s
Ran all test suites matching /longestPalindromicSubsequence.test.js/i.

To improve this performance, I tried using _.memoize in an updated module longestPalindromicSubsequence2.js:

const _ = require('lodash');

const longestPalindromicSubsequence = _.memoize(
  (string, start = 0, end = string.length) => {
    if (end < start) { return 0; }
    if (start === end) { return 1; }
    if (string[start] === string[end]) {
      return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
    }
    return Math.max(
      longestPalindromicSubsequence(string, start + 1, end),
      longestPalindromicSubsequence(string, start, end - 1),
    );
  },
  (string, start, end) => [string, start, end], // resolver function
);

module.exports = longestPalindromicSubsequence;

However, when I try to run the tests with this module, I get a "Javascript heap out of memory" error:

$ jest longestPalindromicSubsequence.test.js

 RUNS  ./longestPalindromicSubsequence.test.js

<--- Last few GCs --->
at[89308:0x104801e00]    15800 ms: Mark-sweep 1379.2 (1401.3) -> 1379.2 (1401.3) MB, 1720.4 / 0.0 ms  (+ 0.0 ms in 5 steps since start of marking, biggest step 0.0 ms, walltime since start of marking 1735 ms) (average mu = 0.128, current mu = 0.057) allocat[89308:0x104801e00]    17606 ms: Mark-sweep 1390.0 (1412.3) -> 1390.0 (1412.3) MB, 1711.7 / 0.0 ms  (+ 0.0 ms in 4 steps since start of marking, biggest step 0.0 ms, walltime since start of marking 1764 ms) (average mu = 0.091, current mu = 0.052) allocat

<--- JS stacktrace --->

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

    0: ExitFrame [pc: 0x20b000bdc01d]
Security context: 0x1c189571e549 <JSObject>
    1: /* anonymous */ [0x1c18f7682201] [/Users/kurtpeek/GoogleDrive/LeetCode/longestPalindromicSubsequence2.js:~14] [pc=0x20b0015cd091](this=0x1c18d38893a1 <JSGlobal Object>,string=0x1c18f7682271 <String[55]: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcdef>,start=45,end=45)
    2: memoized [0x1c18f7682309] [/Users/kurtpeek/GoogleDrive/LeetCode/node_...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
 1: 0x100037733 node::Abort() [/usr/local/bin/node]
 2: 0x1000378d6 node::FatalTryCatch::~FatalTryCatch() [/usr/local/bin/node]
 3: 0x10018e57b v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [/usr/local/bin/node]
 4: 0x10018e51c v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [/usr/local/bin/node]
 5: 0x1004682ee v8::internal::Heap::UpdateSurvivalStatistics(int) [/usr/local/bin/node]
 6: 0x100469ed7 v8::internal::Heap::CheckIneffectiveMarkCompact(unsigned long, double) [/usr/local/bin/node]
 7: 0x1004675cb v8::internal::Heap::PerformGarbageCollection(v8::internal::GarbageCollector, v8::GCCallbackFlags) [/usr/local/bin/node]
 8: 0x1004663e6 v8::internal::Heap::CollectGarbage(v8::internal::AllocationSpace, v8::internal::GarbageCollectionReason, v8::GCCallbackFlags) [/usr/local/bin/node]
 9: 0x10046eafc v8::internal::Heap::AllocateRawWithLigthRetry(int, v8::internal::AllocationSpace, v8::internal::AllocationAlignment) [/usr/local/bin/node]
10: 0x10046eb48 v8::internal::Heap::AllocateRawWithRetryOrFail(int, v8::internal::AllocationSpace, v8::internal::AllocationAlignment) [/usr/local/bin/node]
11: 0x10044eb7a v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationSpace) [/usr/local/bin/node]
12: 0x100634916 v8::internal::Runtime_AllocateInTargetSpace(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/local/bin/node]
13: 0x20b000bdc01d 
Abort trap: 6

As I understand from Node.js heap out of memory, the standard memory usage for Node is 1.7GB, which I reckon should be sufficient. Any ideas why the memoized version is not working, and on how to fix it?

Have you checked how many calls to `longestPalindromicSubsequence` would need to be memoized? You might also want to try providing a different resolver since IIRC it's the first argument that's used by default, which here I think would always be the same string, which might also cause a problem (but I'm just guessing on that one). — Dave Newton, Sep 28 '18 at 21:07
The function above actually does not use the default resolver function (which only takes into account the first argument), but defines its own one which takes all arguments (`string`, `start`, and `end`) into account. Apparently, though, it's more efficient to store a string as the key as illustrated in my answer below. — Kurt Peek, Sep 28 '18 at 21:14
Ugh, sorry, totally skipped over that. But yeah, I'd imagine a single string key would be more efficient than an array. My guess is that JS implementation would matter, e.g., how are arrays implemented, and what's the lookup cost. — Dave Newton, Sep 28 '18 at 21:20
@KurtPeek I am not familiar with memoize function, but giving it an array might be memoizing array reference, which is never the same — juvian, Sep 28 '18 at 21:20
@juvian Ah--because it compares strict reference, not values. — Dave Newton, Sep 28 '18 at 21:21
@KurtPeek That's worth exploring and shouldn't be difficult to catch out. — Dave Newton, Sep 28 '18 at 21:22
check this answer: https://stackoverflow.com/questions/38558989/node-js-heap-out-of-memory/66914674#66914674 — sidverma, Apr 02 '21 at 06:33

score 2 · Accepted Answer · answered Sep 28 '18 at 21:10

I managed to fix the problem by changing the resolver function from (string, start, end) => [string, start, end] to (string, start, end) => string + start + end:

const _ = require('lodash');

const longestPalindromicSubsequence = _.memoize(
  (string, start = 0, end = string.length) => {
    if (end < start) { return 0; }
    if (start === end) { return 1; }
    if (string[start] === string[end]) {
      return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
    }
    return Math.max(
      longestPalindromicSubsequence(string, start + 1, end),
      longestPalindromicSubsequence(string, start, end - 1),
    );
  },
  (string, start, end) => string + start + end, // resolver function
);

module.exports = longestPalindromicSubsequence;

Now the 'long string' test takes only 3ms:

$ jest longestPalindromicSubsequence.test.js
 PASS  ./longestPalindromicSubsequence.test.js
  longest palindromic subsequence
    ✓ works for aab (3ms)
    ✓ works for long string (3ms)

Test Suites: 1 passed, 1 total
Tests:       2 passed, 2 total
Snapshots:   0 total
Time:        1.004s, estimated 10s
Ran all test suites matching /longestPalindromicSubsequence.test.js/i.

It would appear that using a string as a key into the cache is much more memory-efficient than using an array - perhaps because strings are immutable in Javascript? Any explanations of this improvement would be welcome.

Each new array instance is treat as unique even having the same elements inside. In other words `['abcd', 4, 4] !== ['abcd', 4, 4]` and memoization for such keys just consumes memory but actually does not help at all. It's easy to check just by adding `console.log(string, start, end);` at the end of the function and by checking sequential calls actually made with the same arguments — skyboyer, Sep 28 '18 at 21:24
string + start + end is not really good either, (asd, 17, 3) would go to the same key as (asd, 1, 73) just use JSON.strigify([string, start, end]) — juvian, Sep 28 '18 at 21:28
@juvian I guess a delimiter would suffice? For example `asd:1:73`. — Alexander Azarov, Oct 01 '18 at 13:58
@AlexanderAzarov in this case yes, JSON.stringify is a more general solution — juvian, Oct 01 '18 at 15:39

score 2 · Answer 2 · answered Sep 28 '18 at 22:00

I know you posted the most optimal answer but wanted to add another clarification. The root issue is that using arrays is what was causing the bottleneck. Behind the scenes, lodash has their own MapCache they define which seems to assume strings will be passed.

However relooking at the documentation and comments, they do expose the Cache object for you to override assuming it has the same interface as their Map.

Creates a function that memoizes the result of func. If resolver is provided, it determines the cache key for storing the result based on the arguments provided to the memoized function. By default, the first argument provided to the memoized function is used as the map cache key. The func is invoked with the this binding of the memoized function.

Note: The cache is exposed as the cache property on the memoized function. Its creation may be customized by replacing the _.memoize.Cache constructor with one whose instances implement the Map method interface of clear, delete, get, has, and set.

I went in and tested your code because the actual Map you should use if you want to reference keys as objects/non-strings is a WeakMap. This is what I tested

const _ = require('lodash');

// override Cache and use WeakMap
_.memoize.Cache = WeakMap;

const longestPalindromicSubsequence = _.memoize(
  (string, start = 0, end = string.length) => {
    if (end < start) { return 0; }
    if (start === end) { return 1; }
    if (string[start] === string[end]) {
      return 2 + longestPalindromicSubsequence(string, start + 1, end - 1);
    }
    return Math.max(
      longestPalindromicSubsequence(string, start + 1, end),
      longestPalindromicSubsequence(string, start, end - 1),
    );
  },
  (string, start, end) => [string, start, end], // resolver function
);

module.exports = longestPalindromicSubsequence;

And while it does still take a long time, it does eventually end up passing without hitting the JavaScript Heap out of memory issue.

As you identified, the best solution is to simply stringify the key though :) (although consider @juvian comment regarding using JSON.stringify in cases where the final string could be the same if the parts of the string end up with collisions)

"Javascript heap out of memory" using Lodash memoize

2 Answers2