Next Version of Lua?

classic Classic list List threaded Threaded
143 messages Options
1 ... 45678
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Steven Johnson
> 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.)

VarOps.lua (7K) Download Attachment
Iterators.lua (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Niklas Frykholm
In reply to this post by Asko Kauppi
Yes, I know I've kind of reached a dead-end with lua 5.1 where none of
the options is really attractive (userdata generating lots of garbage,
increased TValue size inflating memory use, manual memory management
in pools which is hard to use). That's why I brought this up in a
thread discussing future changes to Lua. To say that this is something
that I'm missing.

C# has "structs" -- a variable-sized value type.

I'm not sure if variable sized value types are right for Lua. It might
be it requires so many choices to the core it destroys the attractive
simpleness of the language. It might be that these performance issues
would be better addressed with a fast and smart generational garbage
collector. It might also be that nobody but me cares about this
particular performance issue.

// Niklas


2009/6/11 Asko Kauppi <[hidden email]>:

>
> Well... Do you think you can both eat and save the pie?  :/
>
> Seriously, only the string type of the built-ins allows for variable length.
> If you don't want to grow Value, you'll need to do something similar to
> string. I bet it will make them immutable, as strings are.
>
> So why not just use strings to store the 3D values?  As binaries.  You'll
> make C side code to create them of course:
>
>        local v= vec3d( 0.123, 1.234, 2.345 )
>        print( v.x, v.y, v.z )          -- cannot be done since it's a string
>        print( v )                              -- would give binary garbage
>
> And you cannot override add and sub and mul and... either.   Meaning you
> want userdata.
>
> Case closed?  :))
>
>
> Niklas Frykholm kirjoitti 11.6.2009 kello 12:30:
>
>> Yes, that would work and wouldn't be too tricky. The drawback is that
>> you would have to increase the size of the Value union to have room
>> for the biggest value type you wanted to support. Support for Vector3
>> would triple the size of Value and double the size of TValue. Which
>> would mean close to doubling the memory footprint of a running lua
>> application.
>>
>> I'm targetting game consoles, where increasing the script memory from
>> 30 MB to 50 MB or even 40 MB is a big deal... so I can't really go
>> that path.
>>
>> // Niklas
>>
>> 2009/6/10 Asko Kauppi <[hidden email]>:
>>>
>>> About the complex type, LNUM patch allows all Lua numbers to be complex
>>> (compile with LNUM_COMPLEX defined; C99 required for C complex support).
>>>
>>> The approach could of course be extended to making a native 3D vector
>>> datatype, as well.
>>>
>>> -asko
>>>
>>>
>>> Niklas Frykholm kirjoitti 10.6.2009 kello 17:42:
>>>
>>>> 2009/6/10 Duncan Cross <[hidden email]>:
>>>>>
>>>>> On Wed, Jun 10, 2009 at 2:55 PM, Niklas Frykholm<[hidden email]>
>>>>> wrote:
>>>>>>
>>>>>> 2009/6/10 Olivier Hamel <[hidden email]>:
>>>>>> Currently, if you want to create Complex or Vector3 type you have to
>>>>>> do it as a table or a userdata. And if you do a serious ammount of
>>>>>> processing on them, the ammount of garbage generated by simple
>>>>>> arithmetic operations will soon put a significant strain on the
>>>>>> system. (You could use a pool of such objects, but that would mean
>>>>>> resorting to manual memory management with all its pains - especially
>>>>>> when you are using it for something as simple as numbers.)
>>>>>
>>>>> Perhaps I am misunderstanding, but if the pool is a table that has
>>>>> been set to have weak values (i.e. its metatable's __mode field is set
>>>>> to 'v'), you should not have to do any manual memory management -
>>>>> values that only exist in the pool will be eligible for garbage
>>>>> collection.
>>>>
>>>> My description was a bit short, but the whole point of having a pool
>>>> was to avoid generating garbage. (By using a free object from the
>>>> pool, rather than creating a new one, whenever a new object is
>>>> needed.) But this requires us to manually track which objects in the
>>>> pool are free or not (i.e., manual memory management).
>>>>
>>>> If the objects in the pool are eligible for garbage collection, then
>>>> the pool doesn't really buy us anything. We will generate the same
>>>> ammount of garbage with the pool as without it.
>>>>
>>>> // Niklas
>>>
>>>
>
>
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Niklas Frykholm
In reply to this post by steve donovan
2009/6/11 steve donovan <[hidden email]>:
> Thinking about 3D vectors as objects, I'm sure a C++ application would
> struggle with lots of tiny objects like that, and it would certainly
> cause a lot of allocation churn unless some clever reusing was going
> on.  Surely the userdata needed here is an _array_ of 3D vectors, to
> efficiently handle the storage and processing of many vectors?

Yes, if the 3D vectors were allocated on the heap using
run-of-the-mill malloc, then C++ would have problems too. (The memory
access patterns are often the bottleneck.) But in a normal C++
application the 3D vectors would be value types and live on the stack
rather than the heap and thus would be very quick to create and
destroy. But lua userdata must live on the heap, so in Lua we are
forced into the slow behavior.

Yes, for SIMD applications you could have a userdata representing an
"array of Vector3" and get very fast vectorized operations using a
library similar to NumPy. But in my case the issue is lots of small
computations that cannot be easily vectorized.

// Niklas
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

steve donovan
On Fri, Jun 12, 2009 at 12:30 PM, Niklas Frykholm<[hidden email]> wrote:
> destroy. But lua userdata must live on the heap, so in Lua we are
> forced into the slow behavior.

So some kind of guaranteed finalization would do the job, if one could
indicate that a particular object had to be collected when out of
scope. In fact, just having the ability to force __gc for such objects
would allow for a custom scheme, not so?

Whether this would impact on general performance, I don't know: such
objects would have to be specially marked for 'impatient disposal'.
RAII is the obvious goal for such a feature.

steve d.
Reply | Threaded
Open this post in threaded view
|

Re[2]: Next Version of Lua?

Bulat Ziganshin
Hello steve,

Friday, June 12, 2009, 2:51:33 PM, you wrote:

>> destroy. But lua userdata must live on the heap, so in Lua we are
>> forced into the slow behavior.

one more way to make gc faster - use allocation pools:

  pool = makePool()
  obj1 = pool:alloc(bytes1)
  obj2 = pool:alloc(bytes2)
  ...
  pool:destroy()



--
Best regards,
 Bulat                            mailto:[hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua? - Bitwise Ops & Enum/Flags

Olivier Hamel
In reply to this post by Henk Boom-2
Henk Boom wrote:

> 2009/6/11 Olivier Hamel <[hidden email]>:
>  
>> Olivier Hamel wrote:
>>    
>>> Note that it's not permitted to do:
>>>
>>> enum "Test"
>>> {
>>>   "Div",
>>>   "Multi",
>>>   "Add",
>>>   "Sub",
>>>   "Assign",
>>>   "Call"
>>> }
>>>      
>> Gah! I'm an idiot, Sorry! Here:
>>
>> function enum(strEnumSetName, tblEnumList)
>>   typecheck(strEnumSetName, "string")
>>   typecheck(tblEnumList, "table")
>>   return function()
>>       for k, v in ipairs(tblEnumList) do
>>          HackEnumCntr = HackEnumCntr + 1
>>         _G[k] = 2^HackEnumCntr -- Figure something for handling over
>> overflows?
>>          -- Is it even a possible concern? Never was in my experience...
>>       end
>>   end
>> end
>>    
>
> I'm guessing you meant to move "tblEnumList" into the internal
> function's args, right?
>
> function enum(strEnumSetName)
>   typecheck(strEnumSetName, "string")
>   typecheck(tblEnumList, "table")
>   return function(tblEnumList)
>       for k, v in ipairs(tblEnumList) do
>          HackEnumCntr = HackEnumCntr + 1
>         _G[k] = 2^HackEnumCntr -- Figure something for handling over
> overflows?
>          -- Is it even a possible concern? Never was in my experience...
>       end
>   end
> end
>
>  
Yah, you can drop the second parameter of the enum func entirely, since
it's not defined.
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua

Luiz Henrique de Figueiredo
In reply to this post by Patrick Donnelly
> >  if a = 1 then print() end
> >  --> stdin:1: '==' expected near '='
>
> I don't agree with this because it implies that Lua only expects the
> '==' token after 'a'. I think that could be more confusing.

No, the message would be issued only when Lua sees '='.
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua

Henk Boom-2
In reply to this post by Patrick Donnelly
2009/6/12 Patrick Donnelly <[hidden email]>:
> I don't agree with this because it implies that Lua only expects the
> '==' token after 'a'. I think that could be more confusing.

In the context, this makes more sense than the original error message,
which would imply that Lua only expects 'then' after 'a'.

    Henk
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Mark Hamburg
In reply to this post by Steven Johnson
Nice. As someone who routinely reaches for such caches, I don't know  
why I didn't think about doing so in this case.

Mark

Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua

David Manura
In reply to this post by Henk Boom-2
On Fri, Jun 12, 2009 at 10:42 AM, Henk Boom wrote:
> In the context, this makes more sense than the original error message,
> which would imply that Lua only expects 'then' after 'a'.

More generally, we might instead patch lparser.c:subexpr to suggest
"==" if an r-value sub-expression is followed by an "=" :

--- lua-5.1.4/src/lparser.c
+++ lua-5.1.4-better-errors/src/lparser.c
400
@@ -849,6 +849,8 @@
     op = nextop;
   }
   leavelevel(ls);
+  if (ls->t.token == '=')
+    error_expected(ls, TK_EQ);
   return op;  /* return first untreated operator */
 }

Tests (old and new errors respectively):

if x = y then end
--> stdin:1: 'then' expected near '='
--> stdin:1: '==' expected near '='

while x = f() do end
--> stdin:1: 'do' expected near '='
--> stdin:1: '==' expected near '='

repeat until x = y
--> stdin:1: unexpected symbol near '='
--> stdin:1: '==' expected near '='

x = y = z
--> stdin:1: unexpected symbol near '='
--> stdin:1: '==' expected near '='

x = w or (y = z)
--> stdin:1: ')' expected near '='
--> stdin:1: '==' expected near '='

if a b then end
--> stdin:1: 'then' expected near 'b'
--> stdin:1: 'then' expected near 'b'
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua

David Manura
In reply to this post by David Manura
On Thu, Jun 11, 2009 at 10:58 PM, David Manura wrote:

> On Thu, Jun 11, 2009 at 12:45 PM, Michael Newberry wrote:
>> Here's another one:
>>
>>   `=' expected near `ot'
>>
>> is thrown by
>>
>>   ifn ot CMyClass then
>
> ... You might do this patch on assignments: ...
>
>  ifn ot CMyClass then print() end
>  --> stdin:1: ',', '(', or '=' expected near 'ot'

This patch to lparser.c:assignment may more practical:

--- lua-5.1.4/src/lparser.c
+++ lua-5.1.4-better-errors-2/src/lparser.c
@@ -944,7 +944,9 @@
   }
   else {  /* assignment -> `=' explist1 */
     int nexps;
-    checknext(ls, '=');
+    if (ls->t.token != '=')
+      luaX_syntaxerror(ls, "unrecognized statement");
+    luaX_next(ls);
     nexps = explist1(ls, &e);
     if (nexps != nvars) {
       adjust_assign(ls, nvars, nexps, &e);

Tests (old and new errors respectively):

a b c
--> stdin:1: '=' expected near 'b'
--> stdin:1: unrecognized statement near 'b'

If x then end
--> stdin:1: '=' expected near 'x'
--> stdin:1: unrecognized statement near 'x'

> x[1][2] y
--> stdin:1: '=' expected near 'y'
--> stdin:1: unrecognized statement near 'y'

a,b c
--> stdin:1: '=' expected near 'c'
--> stdin:1: unrecognized statement near 'c'
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Ralph Hempel
In reply to this post by Olivier Hamel
Olivier Hamel wrote:
> Probably way pre-mature but I can resist asking, does anyone but Roberto
> know anything of what will be the next version of Lua? I'm interested
> because from what I've seen Lua has a (good?) peculiar tendency to
> radically change it's 'feel'/design radically at each iteration.

Besides the core changes that are proposed by the Lua developers, the
only wish I have is for the embedded hex values and to keep the
feature and code bloat to a minimum.

Libraries are preferrable (for me) to builtin features, and the only
thing I'd wish for there is a minimum set of approved core libraries. I
susupect that the defacto standards are (for me again)

luafilesystem
luasocket
luasql
luaexpat

Of course, this is my own private wish since I'm implementing
Lua on a very memory constrained system with 256K of FLASH and
64K of RAM.

The emergency garbage collection cycle will be a big help!

The current default garbage collector parameters request a doubling
of the current RAM usage when RAM runs out. Hopefully the new emergency
cycle does the collection and is happy with whatever it comes up
with :-)

My system has a fixed heap for allocations, so sbrk() is meaningless.

Ralph
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Enrico Colombini
Ralph Hempel wrote:
> The current default garbage collector parameters request a doubling
> of the current RAM usage when RAM runs out.

I may be wrong, but I interpret the manual description of 'pause' as
meaning that the collector merely doubles the allocation threshold where
a new collection will forcibly take place. I can't find sbrk() in the code.

Is there a check for failed allocation due to RAM exhaustion?

Anyway, as I said last week, I'm not sure I really understand how this
mechanism works. To avoid the risk of memory overrun in an embedded
system, I ended out checking allocation level periodically with 'count'
and forcing a gc at a fixed threshold, then later checking it again
(suggestions for a better way are welcome).

   Enrico
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Ralph Hempel
Enrico Colombini wrote:
> Ralph Hempel wrote:
>> The current default garbage collector parameters request a doubling
>> of the current RAM usage when RAM runs out.
>
> I may be wrong, but I interpret the manual description of 'pause' as
> meaning that the collector merely doubles the allocation threshold where
> a new collection will forcibly take place. I can't find sbrk() in the code.

Yes, you are correct. The call to sbrk() happens when your own heap gets
exhausted :-)

> Anyway, as I said last week, I'm not sure I really understand how this
> mechanism works. To avoid the risk of memory overrun in an embedded
> system, I ended out checking allocation level periodically with 'count'
> and forcing a gc at a fixed threshold, then later checking it again
> (suggestions for a better way are welcome).

A tunable parameter for the garbage coellctor that either works the
way it currently does (as a percentage) or as an absolute value would
be in interesting compromise.

Ralph
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Enrico Colombini
Ralph Hempel wrote:
> A tunable parameter for the garbage coellctor that either works the
> way it currently does (as a percentage) or as an absolute value would
> be in interesting compromise.

As I said in a previous post, I'm still trying to understand that "as a
percentage"... of what?

To avoid problems due to my limited understanding of the above point, I
coded my own poor man's emergency gc, using 'count' periodically and
keeping a margin for the (estimated) efficiency of the allocator I'm
using (keeping track of the exact amount of used memory or walking the
heap to compute it would cost too much). Luckily I'm only doing small
allocations.

Note that you'll still have the same problem with an absolute limit:
used heap > allocated memory, because of allocator's
efficiency/overhead, even not counting fragmentation.
So I'm afraid an absolute limit would not be a good subsitute for a real
emergency gc when an allocation fails.

   Enrico
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Enrico Colombini
Enrico Colombini wrote:
> Luckily I'm only doing small allocations.

(meaning that fragmentation is thus very low)

   Enrico
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Vaughan McAlley
In reply to this post by Philippe Lhoste
2009/6/11 Philippe Lhoste <[hidden email]>
> Perhaps I am abnormal, but I use both continue and do ... while (or repeat ... until) in languages that allow them. Not necessarily together...

It might be a bit of a hard sell to the Lua authors. If spotlight on
my Mac is to be trusted, there is only one 'continue' statement within
a loop in the whole of the Lua source (in ldblib.c). There are lots of
continues during the gigantic switch statement that is the main
interpreter loop (lvm.c).

Vaughan
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Hisham Muhammad
In reply to this post by Roberto Ierusalimschy
On Thu, Jun 11, 2009 at 11:30 AM, Roberto
Ierusalimschy<[hidden email]> wrote:

>> * Roberto Ierusalimschy:
>>
>> > Any comment about this?
>> >
>> >   http://lua-users.org/lists/lua-l/2005-09/msg00548.html
>>
>> "until" could have been "break if", and the "repeat ... until exp"
>> could have been "repeat ... break if exp end", where "repeat ... end"
>> is an endless loop.
>
> It is, and that is the problem. If you have repeat + continue, it
> becomes this:
>
>  repeat ... continue ... break if exp; end
>
> With this interpretation, the continue goes to the end of the loop,
> bypassing the "break if exp". This is not what most people expect
> from continue.

I confess I've never given too much thought to the exact semantics of
'continue', and have been using it for many years (and missing it in
Lua for a few, by now). Amazingly, I've always read it as "jump back
to the top of the loop", having never realized that it actually "jumps
back to the test" -- and have never been bitten by this error!
(Probably because every time I 'continue' in a repeat loop, I'm doing
it when I expect the loop to, well, continue running, and so my exit
conditions don't trigger anyway.)

So I'm guessing that my personal "expected" behavior for
continue-within-repeat would be Peter Cawley's alternative number 5:

> 5) A "continue" within a repeat ... until construct causes execution
> to jump back to the statement immediately following the "repeat", thus
> skipping the "until" clause entirely.

This would make 'continue' mean "jump to the top", and would be
consistent with 'while' and 'for'. Perhaps, as you said, "this is not
what most people expect from continue", but then again, I'd venture
that 'until' clause already has semantics that most people don't
expect, anyway. (It's just odd to see a variable being used in a lower
indentation level than it is declared.)

So, in short, my two-cents is that, given that repeat-until in Lua
doesn't work like other languages anyway, Cawley's option 5 would give
people continue with semantics that's consistent among looping
constructs and would have no weirdness for 'while' and 'for'.

-- Hisham
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Peter Cawley
On Fri, Jun 19, 2009 at 4:51 PM, Hisham<[hidden email]> wrote:
> This would make 'continue' mean "jump to the top", and would be
> consistent with 'while' and 'for'.

In C, in a 'while', 'continue' jumps the remainder of the loop body
and to the condition. The condition is at the top of the source, but
it's not the top of the loop body. Again, in C, in 'for', 'continue'
jumps to the counting expression and then onto the condition. I tend
to visualise the counting expression at the bottom of the loop body,
even though it is specified above the loop body. Thus the norm is for
'continue' to jump to the condition, and skipping the condition for a
'continue' in a 'repeat' would break this norm.
Reply | Threaded
Open this post in threaded view
|

Re: Next Version of Lua?

Hisham Muhammad
On Fri, Jun 19, 2009 at 1:00 PM, Peter Cawley <[hidden email]> wrote:

>
> On Fri, Jun 19, 2009 at 4:51 PM, Hisham<[hidden email]> wrote:
> > This would make 'continue' mean "jump to the top", and would be
> > consistent with 'while' and 'for'.
>
> In C, in a 'while', 'continue' jumps the remainder of the loop body
> and to the condition. The condition is at the top of the source, but
> it's not the top of the loop body. Again, in C, in 'for', 'continue'
> jumps to the counting expression and then onto the condition. I tend
> to visualise the counting expression at the bottom of the loop body,
> even though it is specified above the loop body. Thus the norm is for
> 'continue' to jump to the condition, and skipping the condition for a
> 'continue' in a 'repeat' would break this norm.

I understand. When I said "would be consistent with 'while' and 'for'"
I meant that a single rule could apply to *Lua's* 'repeat', 'while'
and 'for' consistently. We can't use C's 'continue' semantics anyway
due to Lua's 'repeat' weirdness, so I'd rather have something that
works without having to special-case 'repeat' -- I think the simple
semantics "jump to the top of the construct" (where the test is, in
'while' and 'for', and isn't in 'repeat') would satisfy that.

-- Hisham
1 ... 45678