Demo: Over 50x slowdown on pointer arithmetic due to single branch

[lukego]

Here is a fun little program that demonstrates the problem of code doing 64-bit arithmetic (e.g. on pointers) being vulnerable to surprising performance problems. In this case adding a single branch causes a more than 50x slowdown by inhibiting allocation sinking optimization.

The problem is already described on #91 but I wanted to revisit it briefly because this is still the absolute most important problem that I want to solve in the compiler (see also #251.)

-- This program demonstrates that loading FFI pointers into local
-- variables is very cheap when allocations "sink" but much more
-- expensive when the pointer values escape from a trace.
--
-- The pointers are generated using arithmetic but the same principle
-- applies to other cases e.g. loading pointers from FFI structures.
--
-- Note: Allocation sinking can work even for values that escape into
-- a side trace, but not for values that escape into a new root trace,
-- or into the heap, or into the bytecode interpreter.
--
-- This program runs fast if the line "if i > 100" is commented out
-- (because it stays within a root trace) but slow if that line is
-- present (because in each iteration a new pointer value escapes from
-- a side-trace back into the root trace.)

local ffi = require("ffi")
local ptr = ffi.cast("char*", buf)

for i = 0, 1e8 do
   ptr = ptr + 1         -- store a new pointer in a local variable
   --if i > 100 then end   -- force exit to side trace
end

Here is a profile of the fast version with the branch commented out:

and here is a profile of the slow version with the branch included:

I don't think it's reasonable for application programmers to have to deal with the current behaviour of the compiler: the rules for sinking allocations have to be much simpler, or the overhead of unsunk allocations has to be much reduced, or both.