-
-
Notifications
You must be signed in to change notification settings - Fork 61
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Memory complexity? #125
Comments
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. |
Could give me some examples or just tell me how to reproduce it? @jochem-brouwer |
Sure! Clone the repository, then Now;
You can also Error log;
|
How large the test size is? I insert nearly See: https://github.com/js-sdsl/js-sdsl/actions/runs/3402812865/jobs/5658916877 |
Okay, I'll take a look later. |
OK, starting to get convinced the problem is on how we use it in the cache. If we The map size is 51300, but we keep creating copies of it, so that might be what causes this problem. |
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. |
Maybe tell me more details about this feature? I need some practical scenarios to think about this. |
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 |
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 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);
}
}
}
} |
After swapping
functional-red-black-tree
tojs-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 thatjs-sdsl
is worse in memory usage thanfunctional-red-black-tree
. Is there any theory of this memory complexity?The text was updated successfully, but these errors were encountered: