Re: Next Version of Lua?

[Steven Johnson <steve@...>]

> Even if for realistic numbers of
> arguments the quadratic complexity doesn't bite one, I feel dirty writing
> such code knowing it's there and on the other hand knowing that the linear
> algorithms carry extra cost is again annoying because it means that in the
> realistic case, they actually are less efficient (though not by much).
>
> I should probably just get over it (one way or the other).
>

I don't know how this compares speed-wise against the quadratic
version (for our purposes it's
been fast enough), and there are obviously more algorithms to
consider, but it's not too bad
making an apairs() iterator that's almost garbage-free.

This came up a while back in our project when we were getting
noticeable GC hits that proved
hard to rectify with mere tuning. Among other problems, several
stateful iterators had a habit
of churning out little helper tables which quite quickly piled up.

For iterators, what I did was build several on top of a pattern that
allows for recycling, consisting
basically of the following four operations:

(1 - iterator setup
(2 - is it done?
(3 - the standard iterator body that supplies the values we want
(4 - a cleanup function (which can also be called explicitly, say in
the middle of a loop we exit early)

These all get combined into one function that provides the interface.
When this function is called, it
first checks a cache. If the cache is empty, a new closure is built
that wraps the above four operations
and any state shared among them; if not empty, such a closure gets
extracted instead. The setup logic
then initializes its state, and your iterator is ready to go. When
it's done, the cleanup is called to clear
the state, and the closure puts itself back in the cache.

In the apairs() case, setup is the familar { n = select("#", ...), ...
}, but reusing the table; cleanup wipes
the table clean, so it's good for the next use. For "unrealistic"
numbers of arguments it might be best
to just throw the table away and grab another next time.

The cache approach also has a few helpful consequences:

(1 - You can nest the iterator without problems
(2 - You can save the closure for later without crippling the iterator
(3 - If an error occurs mid-iteration the closure just becomes garbage
without breaking the iterator

In the attachments:

VarOps.lua has CollectArgsInto(), which I use to stuff tables, and a
couple utilities. The Collect()
helper function is of course easily written in C if that option is available.

In Iterators.lua you can see CachedCallback() and APairs(), among others.

(License is MIT; these were in the demo I linked to in another recent thread.)

Attachment: VarOps.lua
Description: Binary data

Attachment: Iterators.lua
Description: Binary data