domingo, 5 de febrero de 2012

Fastruby 0.0.18 released: more performance improvements

Fastruby is a gem which allows to execute ruby code much faster than normal, currently in a state of transition between a spike and a usable gem, it is released when possible with incremental improvements.

The main improvemens on fastruby v0.0.18 are the optimizations:
  • Method inlining, with the following limitations: no inline of iter calls (blocks), no inline of methods with iter calls and only one level of inlining for now
  • Refactor of cache to do not make use of the code snippet as key, instead caching is applied at other level using the syntax tree and other data as key
And bug fixes:
  • Fixed replacements of methods by redesigning the cache

Install

You can clone the repository at github:
git clone git://github.com/tario/fastruby.git
git checkout v0.0.18

Or install it using gem install:
gem install fastruby

Inlining in Ruby

Inlining is a technique very very common and popular on static compiled languages like C, C++ and even on managed static languages as Java or .NET. It basically consists on replacing a method call with their implementation to save the overhead cost of calling to a separated method.
On C programs this means avoid having to execute call instructions, allocating a de-allocating function frames, etc... In the ruby world, while the concept of inlining turns a little more complex, inlining implies saving creations of ruby frames (surely much more expensive than C frames) and lookup on method tables which have the same cost as accessing a associative hash.

Many can realize that making use of inlining technique on dynamic languages such as Javascript, Python or Ruby on this case is very complicated. If you do not realize this, look at the following example:

Suppose that you have this ruby code:
class X
def foo(a,b)
a+b
end
end

class Y
def bar(x)
i = 100000
ret = 0
while (i > 0)
ret = x.foo(ret,i)
i = i - 1
end
ret
end
end

p Y.new.bar(X.new) # 50005000

For now, avoid paying attention to the loop code on bar, so, if we apply the inline logic to X#foo, the code will be converted to:
class Y
def bar(x)
i = 100000
ret = 0
while (i > 0)
ret = (
a = ret
b = ret
a+b
) # x.foo(ret,i)
i = i - 1
end
ret
end
end

p Y.new.bar(X.new) # 50005000

But there is a problem on this picture, what happens if we call the same bar method passing a object of other type than X?:
class X2
def foo(a,b)
a*b
end
end
p Y.new.bar(X2.new) # ?
The result will not be correct, the implementation of bar method with inlined foo is only valid while the implementation of the method being called is the same used at the moment of inlining it

Transparent multimethod and inlining

From earliest released versions of fastruby the base concept of multimethods was applied, this means that for a given method will be as many implementations as possible signatures (signatures given by arguments types including type of receiver object) , by example, the method Y#bar is implemented using two functions, one for X class and the other for X2 class

When the method is implemented in that way, we can know the type of arguments in a given function and use this information to inline the correct method being called.

Will be a version of Y#bar for X:
class Y
def bar(x) # we know the type of x is X
i = 100000
ret = 0
while (i > 0)
ret = (
a = ret
b = ret
a+b
) # x.foo(ret,i) # we know the implementation of X#foo
i = i - 1
end
ret
end
end
Will be a version of Y#bar for X2:
class Y
def bar(x) # we know the type of x is X2
i = 100000
ret = 0
while (i > 0)
ret = (
a = ret
b = ret
a*b
) # x.foo(ret,i) # we know the implementation of X2#foo
i = i - 1
end
ret
end
end
And this is correct, because the dispatcher calls the version of X or X2 depending on the type of the argument. The only problem with this is that the change of implementations of inlined methods (such as X#foo), when somebody do something like that:
class X
def foo(a,b)
a + b % 5
end
end

Open Classes: Observers

The solution to the problem described in the previous paragraph is to rebuild methods with inlined calls each time the implementation of inlined methods changes. To acchive this I have implemented a observer method on fastruby method object .
Each time a method is build, observers are created for each inlined method to rebuild when any of these observers are triggered, and each time a method changes all related observers are triggered.




No hay comentarios:

Publicar un comentario