HaxeFoundation / HaxeFoundation/haxe
Custom map implementations perform poorly at large sizes
- Dominant language
- Haxe
- Stars
- 6.9k
- Forks
- 715
- Avg merge
- 2d 2h
- Merged PRs (30d)
- 11
Description
The following Advent of Code puzzle seems to be poision for the Haxe std map implementations, while the native counterparts don't seem to have too much trouble:
| | JS | JVM | C# |
|-------------|------|--------|-------|
| `haxe.ds.Map` | 2.6s | 101.0s | 91.0s |
| native | 0.1s | 0.2s | 0.1s |
On JS, this should improve with https://github.com/HaxeFoundation/haxe/pull/9303.
Compile with `-D native` to use the native map:
```haxe
function main() {
haxe.Timer.measure(() -> {
final map = new BenchmarkMap();
final n = 2000000;
final startingNumbers = [1, 20, 11, 6, 12, 0];
var lastSpoken = startingNumbers.pop();
for (i => n in startingNumbers) {
map.set(n, i);
}
var lastTurn = startingNumbers.length;
while (lastTurn + 1 < n) {
final number = if (map.exists(lastSpoken)) {
lastTurn - map.get(lastSpoken);
} else {
0;
}
map.set(lastSpoken, lastTurn);
lastSpoken = number;
lastTurn++;
}
trace(lastSpoken);
});
}
#if (js && native)
@:forward(get, set)
abstract BenchmarkMap(js.lib.Map) {
public function new()
this = new js.lib.Map();
public function exists(k)
return this.has(k);
}
#elseif (java && native)
@:forward(get)
abstract BenchmarkMap(java.util.HashMap) {
public function new()
this = new java.util.HashMap();
public function set(k, v)
return this.put(k, v);
public function exists(k)
return this.containsKey(k);
}
#elseif (cs && native)
abstract BenchmarkMap(cs.system.collections.generic.Dictionary_2) {
public function new()
this = new cs.system.collections.generic.Dictionary_2();
public function get(k)
return this.get_Item(k);
public function set(k, v)
return this.set_Item(k, v);
public function exists(k)
return this.ContainsKey(k);
}
#else
@:forward(get, set, exists)
abstract BenchmarkMap(haxe.ds.Map) {
public function new()
this = new haxe.ds.Map();
}
#end
```
Note that `n` is still much smaller here than originally.
Contributor guide
Research direction
The issue provides an inline Haxe benchmark using BenchmarkMap and compares it with native maps across JS, JVM, and C# targets. Start by reproducing the benchmark with and without -D native; no implementation files, tests, target fix, or definition of done are identified, so maintainer guidance would be needed before starting.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- csharp, java, javascript
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100