Quantcast

[ANN] Lua Fun - a functional programming library for tracing JIT compiler

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[ANN] Lua Fun - a functional programming library for tracing JIT compiler

Roman Tsisyk

I'm happy to announce the release of Lua Fun [1] - a high-performance functional
programming library designed for superb LuaJIT tracing just-in-time compiler.

The library provides a set of more than 50 programming primitives like `map`,
`filter`, `reduce`, `zip`, etc. to help you writing simple and efficient code.

Lua Fun takes the full advantage of the innovative tracing JIT compiler [2] to
achieve transcendental performance on functional compositions and high-order
functions. Functional expressions can be compiled into efficient asm code!

An example:

    require "fun" ()
    n = 100
    ans = sum(map(function(x) return x^2 end, take(n, tabulate(math.sin(x)))))
    -- calculate sum(sin(x)^2 for x in 0..n-1)
    print(ans)

LuaJIT 2.0 translates code above to:

    -- some initilization code --
    ->LOOP:
    394cffd0  movsd [rsp+0x8], xmm7
    394cffd6  addsd xmm4, xmm5
    394cffda  ucomisd xmm6, xmm1
    394cffde  jnb 0x394c0028        ->6
    394cffe4  addsd xmm6, xmm0
    394cffe8  addsd xmm7, xmm0
    394cffec  fld qword [rsp+0x8]
    394cfff0  fsin
    394cfff2  fstp qword [rsp]
    394cfff5  movsd xmm5, [rsp]
    394cfffa  mulsd xmm5, xmm5
    394cfffe  jmp 0x394cffd0        ->LOOP
    ---- TRACE 1 stop -> loop

Simple, Efficient and Functional.
In Lua. With JIT.

Lua Fun is fully documented [2] and tested. A Rockspec is available [3].
This is the first public release. Feedback is very welcome!

[1] https://github.com/rtsisyk/luafun
[2] http://luajit.org/luajit.html
[3] http://rtsisyk.github.io/luafun
[4] https://raw.github.com/rtsisyk/luafun/master/fun-scm-1.rockspec

Thank you for your attention!
Have Fun!

--
WBR,
  Roman Tsisyk <[hidden email]>
  http://tarantool.org/ - an efficient in-memory database and a Lua application server
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [ANN] Lua Fun - a functional programming library for tracing JIT compiler

Ico Doornekamp
* On 2013-11-20 19:41:51 +0100, Roman Tsisyk wrote:
 
> I'm happy to announce the release of Lua Fun [1] - a high-performance functional
> programming library designed for superb LuaJIT tracing just-in-time compiler.

Seems very usable to me, I will definitely check this out.

Just wondering: what makes this LuaJIT code, instead of just normal Lua
code?

--
:wq
^X^Cy^K^X^C^C^C^C

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [ANN] Lua Fun - a functional programming library for tracing JIT compiler

Greg Fitzgerald
In reply to this post by Roman Tsisyk
> sum(map(function(x) return x^2 end, take(n, tabulate(math.sin(x)))))

Wow, LuaJIT translates that to one loop?  amazing!  Does it implement
stream fusion?

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401


How general is this mechanism?  Will it fuse maps over trees?

Thanks,
Greg

On Wed, Nov 20, 2013 at 10:41 AM, Roman Tsisyk <[hidden email]> wrote:

>
> I'm happy to announce the release of Lua Fun [1] - a high-performance functional
> programming library designed for superb LuaJIT tracing just-in-time compiler.
>
> The library provides a set of more than 50 programming primitives like `map`,
> `filter`, `reduce`, `zip`, etc. to help you writing simple and efficient code.
>
> Lua Fun takes the full advantage of the innovative tracing JIT compiler [2] to
> achieve transcendental performance on functional compositions and high-order
> functions. Functional expressions can be compiled into efficient asm code!
>
> An example:
>
>     require "fun" ()
>     n = 100
>     ans = sum(map(function(x) return x^2 end, take(n, tabulate(math.sin(x)))))
>     -- calculate sum(sin(x)^2 for x in 0..n-1)
>     print(ans)
>
> LuaJIT 2.0 translates code above to:
>
>     -- some initilization code --
>     ->LOOP:
>     394cffd0  movsd [rsp+0x8], xmm7
>     394cffd6  addsd xmm4, xmm5
>     394cffda  ucomisd xmm6, xmm1
>     394cffde  jnb 0x394c0028        ->6
>     394cffe4  addsd xmm6, xmm0
>     394cffe8  addsd xmm7, xmm0
>     394cffec  fld qword [rsp+0x8]
>     394cfff0  fsin
>     394cfff2  fstp qword [rsp]
>     394cfff5  movsd xmm5, [rsp]
>     394cfffa  mulsd xmm5, xmm5
>     394cfffe  jmp 0x394cffd0        ->LOOP
>     ---- TRACE 1 stop -> loop
>
> Simple, Efficient and Functional.
> In Lua. With JIT.
>
> Lua Fun is fully documented [2] and tested. A Rockspec is available [3].
> This is the first public release. Feedback is very welcome!
>
> [1] https://github.com/rtsisyk/luafun
> [2] http://luajit.org/luajit.html
> [3] http://rtsisyk.github.io/luafun
> [4] https://raw.github.com/rtsisyk/luafun/master/fun-scm-1.rockspec
>
> Thank you for your attention!
> Have Fun!
>
> --
> WBR,
>   Roman Tsisyk <[hidden email]>
>   http://tarantool.org/ - an efficient in-memory database and a Lua application server

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re[2]: [ANN] Lua Fun - a functional programming library for tracing JIT compiler

Roman Tsisyk
I'm sorry, there was a type:

    n = 100
    ans = sum(map(function(x) return x^2 end, take(n, tabulate(math.sin))))  -- was sin(x)

Wednesday, November 20, 2013 11:05 AM -08:00 from :
> > sum(map(function(x) return x^2 end, take(n, tabulate(math.sin(x)))))
>
> Wow, LuaJIT translates that to one loop?  amazing!  Does it implement
> stream fusion?
>

The magic is done by the tracing compiler [1]. LuaJIT can trace entire loops
and optimize them wholly, instead of optimizing single functions.
The compiler unrolls compositions of functions, eliminates high-order functions
replaces recursions with loops and makes other sophisticated optimizations.

I have never seen such powerful JIT in any language. Seriously.
I think Mike Pall can provide more details.

The source code is fully compatibly with Lua 5.1. However,
this library was especially optimized to use tracing JIT at its full strength.

[1] http://en.wikipedia.org/wiki/Tracing_just-in-time_compilation

--
WBR,
  Roman Tsisyk <[hidden email]>
  http://tarantool.org/ - an efficient in-memory database and a Lua application server
Loading...