Re: Allocation sinking in git HEAD

  • From: Mike Pall <mike-1207@xxxxxxxxxx>
  • To: luajit@xxxxxxxxxxxxx
  • Date: Wed, 4 Jul 2012 01:22:40 +0200

David Given wrote:
> On 03/07/12 13:21, Mike Pall wrote:
> [...]
> >  140.0  Lua
> >   26.9  LuaJIT -O-sink
> >    0.20 LuaJIT -O+sink *** 700x faster than Lua ***
> Very impressive! Don't suppose you have an equivalent benchmark in C++,
> do you?

  #include <iostream>

  class Point {
    Point(double x, double y) : x(x), y(y) {}
    Point operator+(const Point &b) const { return Point(x+b.x, y+b.y); }
    double x, y;

  int main()
    int i;
    Point a(1.5, 2.5), b(3.25, 4.75);
    for (i = 0; i < 100000000; i++)
      a = (a + b) + b;
    std::cout << a.x << ' ' << a.y << '\n';
    return 0;

 0.20 GCC 4.4.3 -O2 (or -O3)

Same speed as LuaJIT. C++ ain't so bad. ;-)

Whether this is equivalent is debatable, though. The C++ code is
passing around value objects and not actually allocating anything.
Feel free to convert it to something using 'new Point()' and check
whether the C++ compiler is able to eliminate the heap allocations.

> How does it determine whether the allocation can be sunk or not? How
> much work can we do with a new object before the JIT gives up and
> allocates it off the heap?

The rules are rather tricky in detail. Basically: when there's no
need to actually create the object, because all loads can be
forwarded from the corresponding stores. This is the case when
alias analysis is 'perfect', e.g. there are no loads/stores with
variable keys (t[1]=x; y=t[1] is ok, t[1]=x; y=t[k] is not ok).

You can do almost anything with a new object before it cannot be
sunk, except store it anywhere else or keep it across more than
one loop iteration.

Use -jdump to see whether the optimization works. Sunk allocations
and stores show a "}" in the left column.

> (For example, passing the object to a leaf function vs passing it to a
> non-leaf function vs passing it to an FFI function...)

Passing values around between Lua functions doesn't matter to the
compiler. OTOH passing new objects into or out of loops does matter.

Passing a pointer to an allocation to a C function via the FFI
means the allocation cannot be eliminated at all.

Please note this does _elimination_ of allocations. It does not
_transform_ heap allocations to stack allocations. See also:


Other related posts: