Re: Generate multidimensional tables

[David Kastrup <dak@...>]

steve donovan <steve.j.donovan@gmail.com> writes:

> On Tue, Oct 6, 2009 at 3:23 PM, Francesco Abbate
> <francesco.bbt@gmail.com> wrote:
>> Hi all,
>> as far as I know is better to use unidimensional table to implement
>> multidimensional array (like in C). Here an example that should do the
>> affair:
>
> I seriously doubt that all these function calls & arithmetic would
> beat a few table lookups!

"Numerical algorithms in C" is a translation of the original "Numerical
algorithms" written with Fortran.  Instead of Fortran's multidimensional
variable-size arrays something else had to be done.

The people doing that decided

a) to stay with index numbering with 1, and rather allocate additional
space in the arrays
b) to deal with the problem of passing runtime-sizes multidimensional
arrays into functions by having a be an array of pointers such that a[i]
points into one row in a contiguous array.

The result is that the allocation is a terrible mess incompatible with
any other library, that memory is wasted a lot, that stuff gets
allocated on the _heap_ rather than on the stack (which means garbage
collection costs), and most importantly, that the inner loops can't be
optimized.  When writing out everything in terms of explicit index
arithmetic, the compiler can use loop reversal, strength unfolding,
static overlap analysis and other things.  With the "row pointer"
"trick", all optimizations fail.  In addition, even without strength
reduction, on current computers about 10 complete index calculations can
be performed in the time that it takes to do a single memory access.

And of course, the row pointer accesses cause cache poisoning as well.

Now we are talking about Lua rather than C here, but the assumption for
Lua is that floating point arithmetic is fast compared to the
alternatives, and with fixed expected times.  Table accesses are more
complex in contrast.

-- 
David Kastrup