HaxeFoundation / HaxeFoundation/haxe

Custom map implementations perform poorly at large sizes

Open
#9,994 6 comments 1 reaction 0 assignees View on GitHub
platform-cs platform-java platform-javascript
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.