Memory overhead of sourcemapLocations is high

[mihaip]

We were profiling the memory use of our rollup builds, and a surprising amount is due to sourcemapLocations. As far as we can tell, each AST node ends up adding two locations (https://github.com/rollup/rollup/blob/121a7f41fb88a294d9680c3fa11f4f72ebf9e9ff/src/ast/nodes/shared/Node.ts#L113-L114). Here's a screenshot from heap dump from the rollup process:

sourcemapLocations is an object being used as a set, if it's changed to a real Set it becomes ~4x smaller (guessing this is because it avoids the implicit stringification of object keys):

@Rich-Harris is this something you're open to? If so, happy to send a PR.

[paulocoghi]

I am not a contributor to magic-string, but I believe that if your change doesn't alter how magic-string works and all the tests pass, providing at the same time less memory overhead, surely your PR is welcome!

[kzc]

@mihaip A bit set ought to use considerably less memory than a set. Could you profile this patch?

diff --git a/src/MagicString.js b/src/MagicString.js
index 18bf1f4..e138492 100644
--- a/src/MagicString.js
+++ b/src/MagicString.js
@@ -16,4 +16,21 @@ const warned = {
 };
 
+const BitSet_BITS = 32;
+
+class BitSet {
+	constructor(arg) {
+		this._bits = arg instanceof BitSet ? arg._bits.slice() : [];
+	}
+	clone() {
+		return new BitSet(this);
+	}
+	set(n) {
+		if (n >= 0) this._bits[Math.floor(n / BitSet_BITS)] |= 1 << (n % BitSet_BITS);
+	}
+	get(n) {
+		return !!(this._bits[Math.floor(n / BitSet_BITS)] & (1 << (n % BitSet_BITS)));
+	}
+}
+
 export default class MagicString {
 	constructor(string, options = {}) {
@@ -31,5 +48,5 @@ export default class MagicString {
 			filename:              { writable: true, value: options.filename },
 			indentExclusionRanges: { writable: true, value: options.indentExclusionRanges },
-			sourcemapLocations:    { writable: true, value: {} },
+			sourcemapLocations:    { writable: true, value: new BitSet },
 			storedNames:           { writable: true, value: {} },
 			indentStr:             { writable: true, value: guessIndent(string) }
@@ -44,6 +61,6 @@ export default class MagicString {
 	}
 
-	addSourcemapLocation(char) {
-		this.sourcemapLocations[char] = true;
+	addSourcemapLocation(pos) {
+		this.sourcemapLocations.set(pos);
 	}
 
@@ -122,7 +139,5 @@ export default class MagicString {
 		}
 
-		Object.keys(this.sourcemapLocations).forEach(loc => {
-			cloned.sourcemapLocations[loc] = true;
-		});
+		cloned.sourcemapLocations = this.sourcemapLocations.clone();
 
 		cloned.intro = this.intro;
diff --git a/src/utils/Mappings.js b/src/utils/Mappings.js
index 6026200..8bf3d21 100644
--- a/src/utils/Mappings.js
+++ b/src/utils/Mappings.js
@@ -29,5 +29,5 @@ export default class Mappings {
 
 		while (originalCharIndex < chunk.end) {
-			if (this.hires || first || sourcemapLocations[originalCharIndex]) {
+			if (this.hires || first || sourcemapLocations.get(originalCharIndex)) {
 				this.rawSegments.push([this.generatedCodeColumn, sourceIndex, loc.line, loc.column]);
 			}

[mihaip]

Thanks @kzc, that is a lot better. Opened a PR at #169