LRUCache throws "Invalid Array length" error on Node.js 12.22.1 for capacity=4294967295

[trivikr]

Describe the issue

This is a different issue from #165

LRUCache throws "Invalid array length" error on Node.js 12.22.1 for capacity=4294967295

Steps to reproduce

Run the following code with [email protected]

const LRUCache = require("mnemonist/lru-cache");

new LRUCache(Math.pow(2, 32) - 1);

Observed behavior

No error is thrown on Node.js v14.17.0

On Node.js v12.22.1, the following error is thrown:

/Users/trivikr/workspace/test-lru-cache/node_modules/mnemonist/lru-cache.js:45
  this.forward = new PointerArray(capacity);
                 ^

RangeError: Invalid typed array length: 4294967295
    at new Uint32Array (<anonymous>)
    at new LRUCache (/Users/trivikr/workspace/lru-cache/node_modules/mnemonist/lru-cache.js:45:18)
    at Object.<anonymous> (/Users/trivikr/workspace/lru-cache/index.js:3:1)
    at Module._compile (internal/modules/cjs/loader.js:999:30)
    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1027:10)
    at Module.load (internal/modules/cjs/loader.js:863:32)
    at Function.Module._load (internal/modules/cjs/loader.js:708:14)
    at Function.executeUserEntryPoint [as runMain] (internal/modules/run_main.js:60:12)
    at internal/main/run_main_module.js:17:47

Expected behavior

No error should be thrown for Node.js 12.22.1

[trivikr]

This appears to be limitation put forward by the runtime version.

When capacity= Math.pow(2, 32) LRUCache needs to use Float64Array as per:

mnemonist/utils/typed-arrays.js

Lines 26 to 39 in 825538a

	exports.getPointerArray = function(size) {
	var maxIndex = size - 1;
	if (maxIndex <= MAX_8BIT_INTEGER)
	return Uint8Array;
	if (maxIndex <= MAX_16BIT_INTEGER)
	return Uint16Array;
	if (maxIndex <= MAX_32BIT_INTEGER)
	return Uint32Array;
	return Float64Array;
	};

But it throws error on Node.js 14.x as follows:

Code

const LRUCache = require("mnemonist/lru-cache");

new LRUCache(Math.pow(2, 32));

Output

/Users/trivikr/workspace/lru-cache/node_modules/mnemonist/lru-cache.js:45
  this.forward = new PointerArray(capacity);
                 ^

RangeError: Invalid typed array length: 4294967296
    at new Uint32Array (<anonymous>)
    at new LRUCache (/Users/trivikr/workspace/lru-cache/node_modules/mnemonist/lru-cache.js:45:18)
    at Object.<anonymous> (/Users/trivikr/workspace/lru-cache/index.js:3:1)
    at Module._compile (internal/modules/cjs/loader.js:1068:30)
    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1097:10)
    at Module.load (internal/modules/cjs/loader.js:933:32)
    at Function.Module._load (internal/modules/cjs/loader.js:774:14)
    at Function.executeUserEntryPoint [as runMain] (internal/modules/run_main.js:72:12)
    at internal/main/run_main_module.js:17:47

[trivikr]

According to ECMAScript Spec on TypedArray Objects:

If it is impossible to create such a Data Block, throw a RangeError exception.

From StackOverflow answer on Do ArrayBuffers have a maximum length?

[trivikr]

Should LRUCache fall back to using an Array if PointerArray for provided capacity throws RangeError?

Verified that Array of size 4294967295 can be created in Node.js v12.22.1:

$ node
Welcome to Node.js v12.22.1.
Type ".help" for more information.
> new Uint32Array(4294967295);
Uncaught RangeError: Invalid typed array length: 4294967295
    at new Uint32Array (<anonymous>)
> new Array(4294967295);
[ <4294967295 empty items> ]

[trivikr]

Should LRUCache add 4294967295 as upper limit for capacity?

Array of size 4294967296 can't be created in Node.js v14.17.0:

$ node
Welcome to Node.js v14.17.0.
Type ".help" for more information.
> new Float64Array(4294967296);
Uncaught RangeError: Invalid typed array length: 4294967296
    at new Float64Array (<anonymous>)
> new Array(4294967296);
Uncaught RangeError: Invalid array length

[Yomguithereal]

Yes unfortunately JS cannot handle indices > 32 bits. Sometimes we can cheat using the 53 bits of the float mantissa but not here. So I guess you can add an upper limit to capacity indeed. If I was cheeky I could also tell you it feels weird to be attempting to create such a large LRU cache since usually they are used to save memory :)

It is possible to create composite arrays to index up to 53 bits but the perf cost will start becoming very high to support this.

I am wondering whether throwing the error could be thrown from here instead of returning a Float64Array since it seems this function is overly optimistic :)

[trivikr]

I am wondering whether throwing the error could be thrown from here instead of returning a Float64Array since it seems this function is overly optimistic :)

Yup, any suggestion on what the error message should be?

throw new Error('mnemonist: Pointer Array of size > 4294967295 is not supported.');

Should LRUCache just rethrow the same error, or throw a different custom error like this?

throw new Error('mnemonist/lru-cache: LRUCache of size > 4294967295 is not supported.');

[Yomguithereal]

Yup, any suggestion on what the error message should be?

Your message looks good to me. It could be maybe tell that JavaScript is the culprit :)

Should LRUCache just rethrow the same error, or throw a different custom error like this?

It would be nice, but it will be a drag to rethrow as a custom error in every class that needs it I think. I guess a generic error would be less hassle in this particular case.

[trivikr]

PR to throw error if array size > 4294967295 in getPointerArray is posted at #168

I'll keep this issue open to discuss solution if the platform doesn't support array length for TypedArrays.

Should LRUCache fall back to using an Array if PointerArray for provided capacity throws RangeError?

Verified that Array of size 4294967295 can be created in Node.js v12.22.1:

$ node
Welcome to Node.js v12.22.1.
Type ".help" for more information.
> new Uint32Array(4294967295);
Uncaught RangeError: Invalid typed array length: 4294967295
    at new Uint32Array (<anonymous>)
> new Array(4294967295);
[ <4294967295 empty items> ]

[Yomguithereal]

I'll keep this issue open to discuss solution if the platform doesn't support array length for TypedArrays.

It's right that we could try and use regular arrays in this case. In which case I suspect they are limited to 53 bits indices? One issue here though is obviously that the array should usually be zeroed completely before being used in most use cases to remain transparent with typed array usage. Another issue is of course performance. For full precisions floats, JS arrays on V8 display roughly the same performance as a static preallocated JS dynamic array (but this might change if the number of items is greater than 32 bits). So I think I would be against having this Array fallback without proprer documentation explicitly describing the caveats.

Another way to discuss this issue is: do you have actual use cases where you would need one of the lib structure to hold an amount of data that overflows JS TypedArrays capacity? In which case, maybe it could be useful to scale only some of the data structures to support up to 53 bits of indexing (I don't think we can use BigInt to index arrays in JS yet?) using typed arrays (by splitting the data layer in 2 separate arrays).