Re: New array type? (was: 'table' as fallback for tables)

[William Ahern <william@...>]

On Thu, Jul 07, 2016 at 01:21:46PM -0300, Soni L. wrote:
> On 07/07/16 01:15 PM, Joseph Manning wrote:
> >On 2016-Jul-07 (Thu) at 09:08 (+0200), steve donovan wrote:
> >
> >>>It would be cool if #t was O(1), however.
> >Steve,
> >
> >    In theory, yes indeed, this would be nice and neat and clean.
> >
> >    In practice, however, computing #t is blazingly fast.  In tests
> >    that I did some time ago ( Lua 5.2 ), with t being a sequence of
> >    10,000 elements, #t was computed 1,000,000 time in just 0.1 seconds.
> >
> >    And that was on my little 2008-era netbook.
> >
> >    Fast enough for me :-)
> >
> I don't think ppl see the true power of logn.
> To put it simply, I don't think ppl see that log2(10000) = 14-ish. (14 ops
> for 10000 elements)

For large arrays the real penalty is memory latency. I was researching using
SIMD instructions to optimize the binary search and found this post which
explains the problem very well:

  http://databasearchitects.blogspot.com/2015/09/trying-to-speed-up-binary-search.html

TL;DR: For larger arrays the fixed costs go up; in the above experiments, by
a factor of 4. A project could theoretically end up with bifurcated behavior
where evaluating #t on large arrays can be much slower than would be
expected given the performance on smaller arrays.

I don't think it's much of a deal for interpreted Lua, though. I think it'd
only be a worthwhile concern if the operation were JITd, but notably LuaJIT
doesn't bother (AFAICT) with memoization. Frameworks like Torch don't keep
large arrays in Lua tables. And simplicity has significant performance
benefits.