Skip to content
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

Enum/Switch Fusion #4386

Open
mandel59 opened this issue Jul 6, 2015 · 8 comments
Open

Enum/Switch Fusion #4386

mandel59 opened this issue Jul 6, 2015 · 8 comments
Assignees
Milestone

Comments

@mandel59
Copy link
Contributor

mandel59 commented Jul 6, 2015

It would be nice to add the Enum/Switch Fusion feature, which eliminates intermediate enum and switch. It is similar to inlining, which eliminates intermediate function call, and brings zero-cost abstraction.

Here is a sample code to show how enum and switch should be optimized.

http://try.haxe.org/#2b610

The original code:

enum Option<T> {
    None;
    Some(v : T);
}

class Test {
    static inline function sqrt(x:Float) {
        return if (x >= 0) Some(Math.sqrt(x)) else None;
    }
    static function trace_sqrt(x) {
        switch (sqrt(x)) {
        case None:
            trace("none");
        case Some(v):
            trace("sqrt($x) = $v");
        }
    }
    static function trace_sqrt_fused(x:Float) {
        if (x >= 0) {
            var v = Math.sqrt(x);
            trace("sqrt($x) = $v");
        } else {
            trace("none");
        }
    }
    static function main() {
        trace_sqrt(9.0);
        trace_sqrt_fused(9.0);
    }
}

In that program, the sqrt function generates Option<Float>. The function trace_sqrt uses sqrt and immediately decompose the enum with switch expression. trace_sqrt_fused is a comparison case that doesn"t use Option<Float>.

The following is the compiled code (with Full DCE and Analyzer options):

Test.trace_sqrt = function(x) {
    {
        var _g = x >= 0?Option.Some(Math.sqrt(x)):Option.None;
        switch(_g[1]) {
        case 0:
            console.log("none");
            break;
        case 1:
            console.log("sqrt(" + x + ") = " + _g[2]);
            break;
        }
    }
};
Test.trace_sqrt_fused = function(x) {
    if(x >= 0) {
        var v = Math.sqrt(x);
        console.log("sqrt(" + x + ") = " + v);
    } else console.log("none");
};

trace_sqrt uses intermediate data structures, so it looks less efficient than trace_sqrt_fused.

The fused version would be acquired like the following steps.

switch (if (x >= 0) Some(Math.sqrt(x)) else None) { case None: f(); case Some(v): g(v); }
=
if (x >= 0) (switch (Some(Math.sqrt(x))) { case None: f(); case Some(v): g(v); })
else (switch (None) { case None: f(); case Some(v): g(v); });
=
if (x >= 0) { var v = Math.sqrt(x); g(v); }
else { f(); }
@back2dos
Copy link
Member

Yes, yes, yes!

This bugs me quite a lot. Consider this: http://try.haxe.org/#e0EC4

Chrome: 

Test.hx:29: 0.0280001163482666s
Test.hx:30: 0.0019998550415039062s

Firefox:

Test.hx:29: 1.071000099182129s //yep, enums are veeeery sloooow on firefox
Test.hx:30: 0.002000093460083008s

IE11:
Test.hx:29: 0.06400012969970703s
Test.hx:30: 0.003000020980834961s

That"s over an order of magnitude.

I can live with having to optimize bottlenecks to not use enums, but if it can be fast out of the box, that"d be great.

@Simn
Copy link
Member

Simn commented Nov 22, 2015

It looks nice, but I have no idea how to implement that.

@nadako
Copy link
Member

nadako commented Nov 22, 2015

Could we somehow inline enum constructors similar to what we do with array and object declarations?

@Simn
Copy link
Member

Simn commented Nov 22, 2015

Perhaps, but that"s not really the issue here.

@Simn Simn modified the milestone: 3.4 Feb 23, 2016
@Simn
Copy link
Member

Simn commented Mar 27, 2016

Could someone post a practical example of this which makes sense in the real world?

@kevinresol
Copy link
Contributor

@Simn how about this?

function onKeyDown(key) {
  if(key == "up") walk(Up);
  if(key == "down") walk(Down);
  if(key == "left") walk(Left);
  if(key == "right") walk(Right);
}

function walk(direction:Direction) switch direction {
  case Up: player.y --;
  case Down: player.y ++;
  case Left: player.x --;
  case Right: player.x ++;
}

enum Direction {
  Up; Down; Left; Right;
}

This example is more or less extracted and modified from here. See how FlxWeaponFireMode is basically used only in one function, so I think I agree with @nadako that this is quite related to inline enum declaration.

@Simn
Copy link
Member

Simn commented Mar 28, 2016

That is not the same issue and already produces good output if you inline walk.

@Simn Simn modified the milestones: 3.4, 4.0 Jan 9, 2017
@frabbit
Copy link
Member

frabbit commented Jun 8, 2017

here is another example:

import haxe.ds.Option;

abstract Maybe<T>(Null<T>) {
	public function new (x:Null<T>) this = x;

	@:analyzer(optimize) public inline function match ():haxe.ds.Option<T> {
		return this != null ? Some(this) : None;
	}
}

class Test {
	@:analyzer(optimize) static function main () {
		var m = new Maybe(null);
		var x = switch (m.match()) {
			case None: 0;
			case Some(x): x;
		}

		trace(x);
	}
}

becomes

var x;
var _g = m != null?haxe_ds_Option.Some(m):haxe_ds_Option.None;
switch(_g[1]) {
case 0:
	x = _g[2];
	break;
case 1:
	x = 0;
	break;
}

instead of

var x = (m != null ? m : 0);

@Simn Simn modified the milestones: Release 4.0, Design Apr 17, 2018
@Simn Simn self-assigned this Apr 19, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

6 participants