JavaScript C HTML D Python Shell CSS
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
asmjs
expl
lib
misc/d_dynamic_loading
prettify
test
try
.gitignore
.hgignore
LICENSE.TXT
README.md
asmjs.html
btn_anchor.js
c.html
contents_ul.js
d.html
examples.js
examples_c.js
expl.js
flatorize.js
flatorize_asmjs.js
flatorize_c.js
flatorize_d.js
flatorize_type_util.js
ga.js
index.html
log.js
modifsplitradix.js
simple_server.py
speed_test.js
style.css

README.md

flatorize

Generate fast implementations of mathematical expressions.

Idea

Think like this:

Matrix multiplication a * b: Each row of a with each column of b

...write code like you think, without caring about performance...

# Python   c = a * b
c = [[ sum(x*y for x,y in zip(ra,cb)) for cb in zip(*b) ] for ra in a ]
// JavaScript
function matmulrows_zip( a, b )
{
    return a.map( function (ra) { 
        return zip.apply( null, b ).map( function (cb) {
            return sum( 
                zip( ra, cb )
                    .map( function (xy) { return xy[ 0 ] * xy[ 1 ]; } )
            );
        } );
    } );
}

// --> Well encapsulated code, but slow due to function call overhead.

...and let flatorize transform the above into very fast JavaScript code:

// Generated "flatorized" code == factorized + flattened
// 
// - factorized: avoid repeating computations.
// - flattened:  no function call.

function anonymous(a, b) {
/* function (a,b) { return symbol_matmulrows_zip_gen( a, b, 3, 4, 2 ); } */
var
  _0 = a[0]
, _1 = _0[0]
, _2 = _0[1]
, _3 = _0[2]
, _4 = _0[3]
, _5 = a[1]
, _6 = _5[0]
, _7 = _5[1]
, _8 = _5[2]
, _9 = _5[3]
, _a = a[2]
, _b = _a[0]
, _c = _a[1]
, _d = _a[2]
, _e = _a[3]
, _f = b[0]
, _g = _f[0]
, _h = _f[1]
, _i = b[1]
, _j = _i[0]
, _k = _i[1]
, _l = b[2]
, _m = _l[0]
, _n = _l[1]
, _o = b[3]
, _p = _o[0]
, _q = _o[1]
;
return [ [ (_1 * _g) + (_2 * _j) + (_3 * _m) + (_4 * _p), (_1 * _h) + (_2 * _k) + (_3 * _n) + (_4 * _q) ], [ (_6 * _g) + (_7 * _j) + (_8 * _m) + (_9 * _p), (_6 * _h) + (_7 * _k) + (_8 * _n) + (_9 * _q) ], [ (_b * _g) + (_c * _j) + (_d * _m) + (_e * _p), (_b * _h) + (_c * _k) + (_d * _n) + (_e * _q) ] ];

}

Speedups exceed +1000% in many cases, including matrix multiplication and the Discrete Fourier Transform (full results).

A plugin permits to generate even faster JavaScript code using TypedArray, in an asm.js-compatible way. For usage explanations, see the live page.

A plugin permits to generate fast C code as well. For usage explanations, see the live page.

A plugin permits to generate fast D code as well. For usage explanations, see the live page.

More

For more details read the article:

See also the slides and video from the Budapest 2014 nodebp/bpjs meetup.