lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Hello, it may very well be my ignorance but provide the current FFI
cdata semantic, I tried a few ways to allocate and manage a variable
length 2d array .. and most of them seemed sub-optimal to me (either
in the sense of coding-style or actual outcome.)

First of all, since the pointers are not followed by GC, so obviously
you cannot write:

a ="int*[?]", height)
for i = 0, height - 1 do
  a[i] ="int[?]", width)

I failed miserably with this first attempt, since I didn't read the
documentation then. I then tried fixed length array to make sure that
I wasn't that dumb, and checked there wasn't any stupid mistake in
other parts of my testing code:

a ="int[10][10]")
-- then use a

This worked, however it's not variable length array. So I came up with this:

a ="int["..height.."]["..width.."]")
-- then use this variable-size a

It worked too, however the perfomance seemed sub-optimal. I run a
15x15 Conway's Game of Life for 100000 iterations on my i7 laptop, the
speed is roughly the same as not using FFI at all (with a 2d lua
table, JIT enabled.) And it even use up some more memory space ..
however I'm not sure about memory usage since all I have were just two
15x15 grid plus a few constants. The VM/Compiler itself probably was
the dominant factor.

So I modifed that code to simulate a 2d array with 1d array:

a ="int["..height*width.."]")
-- then use this variable-size a, accessing it's element via a[ i*h + j ]

Now the performance seemed good enough: it's about twice as fast as
using only tables with JIT compiler enabled but without FFI, and the
memory usages are indistinguishable between two methods.

But still.. is this the best way to implement a 2d array with FFI for
now? How about in the future? Or how about 3-dimensions and more? That
would be a pain to simulate through a 1d array. Any help or hint

I've got a C++ version of this Game of Life to compare with. Sometimes
the last method can almost break even with the C++ version; the worst
case is around 50%~100% slower than the C++ version. When not using
FFI cdata (only tables with JIT enabled), it's around 200% slower than
C++ version.

As a side note, I didn't bail out the situations where all the cells
on the grid are dead, but I don't think it matters since I still do
all the calculations and accesses every iteration. And I am not very
sure if my Lua version's implementation is near optimal or not.

My code can be found at these links:

Game of Life plain Lua version, can be run on any kind of Lua:

Game of Life LuaJIT FFI version, using 1d array to simulate 2d array:

Game of Life C++ version (it's pretty much C, I just used some templates):

Johnson Lin