HaxeFoundation / HaxeFoundation/haxe

Exponential increase in generated code size due to array matching

Open
#11,145 1 comment 0 reactions 0 assignees View on GitHub
feature-pattern-matching
Dominant language
Haxe
Stars
6.9k
Forks
715
Avg merge
2d 2h
Merged PRs (30d)
11

Description

(Loose follow up to #6731)

Here's a (silly) way to find the winner of a tic-tac-toe board:

```haxe
class Main {
public static function main():Void {
trace(matchBoard([[X, O, X], [X, O, X], [X, O, X]]));
}

static function matchBoard(board:Array>):Tile {
return (switch (board) {
case [[X, X, X], _, _]: X; // line 8
case [_, [X, X, X], _]: X;
case [_, _, [X, X, X]]: X;
case [[X, _, _], [X, _, _], [X, _, _]]: X;
case [[_, X, _], [_, X, _], [_, X, _]]: X;
case [[_, _, X], [_, _, X], [_, _, X]]: X;
case [[X, _, _], [_, X, _], [_, _, X]]: X;
case [[_, _, X], [_, X, _], [X, _, _]]: X;
case [[O, O, O], _, _]: O;
case [_, [O, O, O], _]: O;
case [_, _, [O, O, O]]: O;
case [[O, _, _], [O, _, _], [O, _, _]]: O;
case [[_, O, _], [_, O, _], [_, O, _]]: O;
case [[_, _, O], [_, _, O], [_, _, O]]: O;
case [[O, _, _], [_, O, _], [_, _, O]]: O;
case [[_, _, O], [_, O, _], [O, _, _]]: O; // line 23
case _: N;
});
}
}

enum Tile {
X;
O;
N;
}
```

With the full example, the generated code *mostly* consists of that switch statement. I measured the size of the generated Javascript code (compiled with `--dce full`) when adding line 8 only, then line 8-9, then line 8-10, etc. The size increases very quickly:

```
0: 3077 out.js
1: 3468 out.js
2: 4612 out.js
3: 9524 out.js
4: 9524 out.js
5: 10517 out.js
6: 12717 out.js
7: 13489 out.js
8: 14266 out.js
9: 22991 out.js
10: 43741 out.js
11: 72983 out.js
12: 72983 out.js
13: 114628 out.js
14: 185129 out.js
15: 190342 out.js
16: 204627 out.js
```

Looking at the generated code I see unreasonable amounts of code like this:

```js
default:
if(_g2.length == 3) {
var _g6 = _g2[1];
var _g7 = _g2[2];
switch(_g2[0]._hx_index) {
case 0:
if(_g6._hx_index == 0) {
switch(_g7._hx_index) {
case 0:
return Tile.X;
case 1:
return Tile.X;
default:
return Tile.X;
}
} else {
return Tile.X;
}
break;
case 1:
if(_g6._hx_index == 1) {
if(_g7._hx_index == 1) {
return Tile.O;
} else {
return Tile.N;
}
} else if(_g7._hx_index == 1) {
if(_g5._hx_index == 1) {
return Tile.O;
} else {
return Tile.N;
}
} else {
return Tile.N;
}
break;
default:
if(_g7._hx_index == 1) {
if(_g5._hx_index == 1) {
return Tile.O;
} else {
return Tile.N;
}
} else {
return Tile.N;
}
```

Can we do better?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.