using array nature for microoptimization

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

using array nature for microoptimization

Jay Carlson
Just a little note for micro-optimizers:

In Lua 5, tables are implemented as having two parts: an array part, consisting of integer-keyed values, and a general hash table part. A key is a candidate for the array part if the array part is mostly consecutive. (This way assigning to t[20000] will not allocate a 20000 element array part, unless t[1]...t[19999] is already mostly used.)

The array part seems much faster.

I had an event queue that looked like this:

  {next=3, n=4, nil, nil, {...}, {...}}

As each event was consumed, I nil'd out the old event from the table. When I ran out of events, I'd just table.insert more on the end. So eventually, the table would look like:

  {next=20000, n=20001, [20000]={...}, [20001]={...}}

which I think was entirely stored as a hash table.

I changed my "get more events" strategy to reset t.n and t.next to near 0 when I went to get more, thus keeping the events in the array part of the table. This sped up my *whole* *program* by 3-5%.

Also, if you plan on doing a lot of unpack() calls on prepared tables you construct, add an "n=3" to your {"start", "b", {}, n=3} tables. That was good for another 5% speedup....

Jay

Reply | Threaded
Open this post in threaded view
|

Re: using array nature for microoptimization

Reuben Thomas-5
> In Lua 5, tables are implemented as having two parts: an array part,
> consisting of integer-keyed values, and a general hash table part.  A
> key is a candidate for the array part if the array part is mostly
> consecutive.  (This way assigning to t[20000] will not allocate a 20000
> element array part, unless t[1]...t[19999] is already mostly used.)

What happens is that the array part is used for numeric indices 1..n such
that at least half the entries in 1..n are non-nil.

> The array part seems much faster.

It should be, there's no hash function to call nor chains to follow.

> which I think was entirely stored as a hash table.

> Also, if you plan on doing a lot of unpack() calls on prepared tables
> you construct, add an "n=3" to your {"start", "b", {}, n=3} tables.
> That was good for another 5% speedup....

Interesting.

Have you put this on the Wiki?

-- 
http://www.mupsych.org/~rrt/ | perfect, a.  unsatirizable

Reply | Threaded
Open this post in threaded view
|

Re: using array nature for microoptimization

RLak-2
In reply to this post by Jay Carlson


> Also, if you plan on doing a lot of unpack() calls on prepared tables
> you construct, add an "n=3" to your {"start", "b", {}, n=3} tables.
> That was good for another 5% speedup....

That is generally true of table-as-vector functions. If you don't specify
n, either as a key or with a call to table.setn(), the library has to
do a complete scan of all keys to find the largest integer index. This
is different from functions (like table.foreachi) which don't attempt
to deal with sparse arrays, and only scan up to the first nil value.

Note that the varargs semantics add the "n" key, so if you have

function foo(a1, a2, ...)

then arg will already have an "n" key and you don't have to worry about it.

(Although I understand that the implementation of ... is due to change in 5.1)


Reply | Threaded
Open this post in threaded view
|

Re: using array nature for microoptimization

John Belmonte
 > Also, if you plan on doing a lot of unpack() calls on prepared tables
 > you construct, add an "n=3" to your {"start", "b", {}, n=3} tables.
 > That was good for another 5% speedup....

That is generally true of table-as-vector functions. If you don't specify
n, either as a key or with a call to table.setn(), the library has to
do a complete scan of all keys to find the largest integer index. This
is different from functions (like table.foreachi) which don't attempt
to deal with sparse arrays, and only scan up to the first nil value.

Doesn't this suggest that there should be some syntactic sugar for "list" literals, such that "n" is set for you at compile time?

-John


--
http:// if  ile.org/

Reply | Threaded
Open this post in threaded view
|

Re: using array nature for microoptimization

Jamie Webb-3
On Friday 12 March 2004 16:49, John Belmonte wrote:
> >  > Also, if you plan on doing a lot of unpack() calls on prepared tables
> >  > you construct, add an "n=3" to your {"start", "b", {}, n=3} tables.
> >  > That was good for another 5% speedup....
> >
> > That is generally true of table-as-vector functions. If you don't specify
> > n, either as a key or with a call to table.setn(), the library has to
> > do a complete scan of all keys to find the largest integer index. This
> > is different from functions (like table.foreachi) which don't attempt
> > to deal with sparse arrays, and only scan up to the first nil value.
>
> Doesn't this suggest that there should be some syntactic sugar for
> "list" literals, such that "n" is set for you at compile time?

It's not at compile time, but what's wrong with:

function array(...)
	return arg
end

a = array(1, 2, 3, 4)

I presume the case where there is a speed issue is far too rare to warrant 
language support.

-- Jamie Webb