Memory complexity?

[jochem-brouwer]

After swapping functional-red-black-tree to js-sdsl in ethereumjs/ethereumjs-monorepo#2283, we now run into an out-of-memory exception in one of the unit tests which uses a big chunk of memory. This seems to imply that js-sdsl is worse in memory usage than functional-red-black-tree. Is there any theory of this memory complexity?

[jochem-brouwer]

Note: it might also have to do with how we handle the cache currently, so it might not be related to the inner workings of this package.

[ZLY201]

Could give me some examples or just tell me how to reproduce it? @jochem-brouwer

[jochem-brouwer]

Sure!

Clone the repository, then npm i in the root directory.

Now;

cd packages/vm
npm run test:blockchain -- --fork=Homestead --test=ShanghaiLove_Homestead

You can also git checkout cfa99af6ad7d78920aa9e3433466e9592fdea4e4 to rollback to the PR which introduced the js-sdsl package. Prior to that commit, i.e. 295deaa07ee8a45d7813e9f07971073652fafcb0 the above command succeeds.

Error log;

npm run test:blockchain -- --fork=Homestead --test=ShanghaiLove_Homestead

> @ethereumjs/vm@6.0.0 test:blockchain
> npm run tester -- --blockchain "--fork=Homestead" "--test=ShanghaiLove_Homestead"


> @ethereumjs/vm@6.0.0 tester
> ts-node ./tests/tester --stack-size=1500 "--blockchain" "--fork=Homestead" "--test=ShanghaiLove_Homestead"

+--------------------------------------------------+
| VM -> BlockchainTests                            |
|                                                  |
| TestGetterArgs                                   |
| skipTests           : 53                         |
| forkConfig          : Homestead                  |
| test                : ShanghaiLove_Homestead     |
|                                                  |
| RunnerArgs                                       |
| forkConfigVM        : homestead                  |
| forkConfigTestSuite : Homestead                  |
+--------------------------------------------------+

TAP version 13
# BlockchainTests
# file: ValidBlocks/bcExploitTest/ShanghaiLove.json test: ShanghaiLove_Homestead
ok 1 correct genesis RLP
ok 2 correct pre stateRoot

<--- Last few GCs --->

[1634670:0x63eefe0]    42002 ms: Scavenge 2042.7 (2085.9) -> 2039.3 (2085.9) MB, 2.5 / 0.0 ms  (average mu = 0.185, current mu = 0.072) allocation failure 
[1634670:0x63eefe0]    42011 ms: Scavenge 2042.7 (2085.9) -> 2039.7 (2086.4) MB, 3.5 / 0.0 ms  (average mu = 0.185, current mu = 0.072) allocation failure 
[1634670:0x63eefe0]    42019 ms: Scavenge 2043.2 (2086.4) -> 2040.2 (2086.9) MB, 3.0 / 0.0 ms  (average mu = 0.185, current mu = 0.072) allocation failure 


<--- JS stacktrace --->

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
 1: 0xb0a860 node::Abort() [node]
 2: 0xa1c193 node::FatalError(char const*, char const*) [node]
 3: 0xcf9a6e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [node]
 4: 0xcf9de7 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [node]
 5: 0xeb1685  [node]
 6: 0xeb2166  [node]
 7: 0xec068e  [node]
 8: 0xec10d0 v8::internal::Heap::CollectGarbage(v8::internal::AllocationSpace, v8::internal::GarbageCollectionReason, v8::GCCallbackFlags) [node]
 9: 0xec404e v8::internal::Heap::AllocateRawWithRetryOrFailSlowPath(int, v8::internal::AllocationType, v8::internal::AllocationOrigin, v8::internal::AllocationAlignment) [node]
10: 0xe8558a v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationType, v8::internal::AllocationOrigin) [node]
11: 0x11fe2d6 v8::internal::Runtime_AllocateInYoungGeneration(int, unsigned long*, v8::internal::Isolate*) [node]
12: 0x15f2d39  [node]
Aborted (core dumped)

[ZLY201]

Note: it might also have to do with how we handle the cache currently, so it might not be related to the inner workings of this package.

How large the test size is?

I insert nearly 3000000 elements to ordered-set and it works fine.

See:

https://github.com/js-sdsl/js-sdsl/actions/runs/3402812865/jobs/5658916877

[ZLY201]

Okay, I'll take a look later.

[jochem-brouwer]

OK, starting to get convinced the problem is on how we use it in the cache. If we checkpoint then we copy the entire OrderedMap and I am not sure if we did that before we switched packages.

The map size is 51300, but we keep creating copies of it, so that might be what causes this problem.

[jochem-brouwer]

Is it possible to take a "snapshot" of the OrderedMap and then use that later on to "rollback" to an "older version" of the OrderedMap? This copying seems to be the problem, we need a pointer to older versions of the map so we can rollback or commit to it later.

[ZLY201]

Is it possible to take a "snapshot" of the OrderedMap and then use that later on to "rollback" to an "older version" of the OrderedMap? This copying seems to be the problem, we need a pointer to older versions of the map so we can rollback or commit to it later.

For current version, the only way to roll back is to save the current copy.

Looks like you want to add a new feature to it in order to save the current state.

I'll give it a try, but there are no guarantees.

[ZLY201]

Maybe tell me more details about this feature?

I need some practical scenarios to think about this.

@jochem-brouwer

[ZLY201]

Source: ethereumjs/ethereumjs-monorepo#2406

[jochem-brouwer]

Sorry for not linking the "source issue" like you did above.

Essentially what you say here: ethereumjs/ethereumjs-monorepo#2406 (comment) seems to be exactly what we need. (i.e. space complexity like functional-red-black-tree)

[ZLY201]

I think the following data structure might be helpful in this case, but it's not suitable to add to js-sdsl, maybe create a new awesome-js-sdsl repo is a good idea.

class OrderedMapWithRollback<K, V> extends OrderedMap<K, V> {
  private isRecording = false;
  private recordNow: ([K, V] | K)[] = [];
  private recordAll: ([K, V] | K)[][] = [];
  setElement(key: K, value: V) {
    this.recordNow.push(key);
    super.setElement(key, value);
  }
  eraseElementByKey(key: K) {
    const value = super.getElementByKey(key);
    if (value === undefined) return;
    this.recordNow.push([key, value]);
    super.eraseElementByKey(key);
  }
  startRecord() {
    if (this.isRecording) return;
    this.isRecording = true;
    this.recordNow = [];
  }
  endRecord() {
    if (!this.isRecording) return;
    this.isRecording = false;
    this.recordAll.push(this.recordNow);
  }
  rollback(depth = 1) {
    if (depth <= 0 || this.recordAll.length < depth) {
      throw new RangeError();
    }
    while (depth--) {
      const record = this.recordAll.pop()!;
      for (const op of record) {
        if (Array.isArray(op)) {
          super.setElement(op[0], op[1]);
        } else super.eraseElementByKey(op);
      }
    }
  }
}