How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

孙世龙 sunshilong
Hi, list

As per the documentation(https://www.lua.org/pil/26.1.html), which says:

As a first example, let us see how to implement a simplified version
of a function that returns the sine of a given number (a more
professional implementation should check whether its argument is a
number):

    static int l_sin (lua_State *L) {
      double d = lua_tonumber(L, 1);  /* get argument */
      lua_pushnumber(L, sin(d));  /* push result */
      return 1;  /* number of results */
    }
From the point of view of C, a C function gets as its single argument
the Lua state and returns (in C) an integer with the number of values
it is returning (in Lua). Therefore, the function does not need to
clear the stack before pushing its results. After it returns, Lua
automatically removes whatever is in the stack below the results.

***
How to comprehend that Lua automatically removes whatever is in the
stack below the results after the function returned?
How does it achieve this goal?
Any explanation or document helps.
I would be grateful if you could shed some light on this matter.

Thank you for your attention to this matter.
Best regards.
Sunshilong
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Gé Weijers
On Tue, Sep 22, 2020 at 12:11 AM 孙世龙 sunshilong <[hidden email]> wrote:
> How to comprehend that Lua automatically removes whatever is in the
> stack below the results after the function returned?
> How does it achieve this goal?

The 'contract' between the interpreter and your code explicitly does
not require you to clean up the unneeded stack values when returning
from a C routine, how the interpreter manages that is an
implementation detail, which could change from version to version. It
could be that this stack is a chunk of memory allocated just before
the call and freed after, or that the interpreter just removes those
entries for you. I have never looked at those details because I don't
really need to know to write the code.



--

Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Dibyendu Majumdar
In reply to this post by 孙世龙 sunshilong
On Tue, 22 Sep 2020 at 08:11, 孙世龙 sunshilong <[hidden email]> wrote:


> How to comprehend that Lua automatically removes whatever is in the
> stack below the results after the function returned?
> How does it achieve this goal?
> Any explanation or document helps.
> I would be grateful if you could shed some light on this matter.
>

Lua's stack is a heap allocated structure. There is a pointer to the
top of the stack in each Lua State - this is simply reset after a
function call. Stack can also be reallocated to reduce or grow as
needed.

Regards
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

孙世龙 sunshilong
Hi, Dibyendu Majumdar

>Stack can also be reallocated to reduce or grow as needed.
I want to make Lua meet the soft real-time requirement.
So I do not want to dynamically increase or reduce the stack indeed.

Best Regards
Sunshilong


On Wed, Sep 23, 2020 at 5:34 AM Dibyendu Majumdar
<[hidden email]> wrote:

>
> On Tue, 22 Sep 2020 at 08:11, 孙世龙 sunshilong <[hidden email]> wrote:
>
>
> > How to comprehend that Lua automatically removes whatever is in the
> > stack below the results after the function returned?
> > How does it achieve this goal?
> > Any explanation or document helps.
> > I would be grateful if you could shed some light on this matter.
> >
>
> Lua's stack is a heap allocated structure. There is a pointer to the
> top of the stack in each Lua State - this is simply reset after a
> function call. Stack can also be reallocated to reduce or grow as
> needed.
>
> Regards
bel
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

bel
One key to reach real-time requirements is not to prevent Lua from dynamically allocating the stack (or any other object), but to provide an allocator function capable of providing memory in a fixed time. (Others are fine tuning garbage collection, preloading libraries and replacing/not using the io library after initializing, by the way).
This can be done using the official interface.
The allocator function is set using lua_newstate. Splitting allocation into a fixed size memory pool for frequently used small objects (basically everything but string), maybe <= 32 bytes (may depend on the Lua version), and another strategy for less frequently allocated larger objects seems to work. But the best strategy may depend on your system and should be verified experimentally.
In any case, you need to deal with Lua dynamically increasing and reducing not only the stack, but many other objects as well. Handle these allocations by a proper "special purpose" alloc/free implementation, instead of using the "general purpose" algorithms in a typical non-realtime standard C library.

On Wed, Sep 23, 2020 at 3:57 AM 孙世龙 sunshilong <[hidden email]> wrote:
Hi, Dibyendu Majumdar

>Stack can also be reallocated to reduce or grow as needed.
I want to make Lua meet the soft real-time requirement.
So I do not want to dynamically increase or reduce the stack indeed.

Best Regards
Sunshilong


On Wed, Sep 23, 2020 at 5:34 AM Dibyendu Majumdar
<[hidden email]> wrote:
>
> On Tue, 22 Sep 2020 at 08:11, 孙世龙 sunshilong <[hidden email]> wrote:
>
>
> > How to comprehend that Lua automatically removes whatever is in the
> > stack below the results after the function returned?
> > How does it achieve this goal?
> > Any explanation or document helps.
> > I would be grateful if you could shed some light on this matter.
> >
>
> Lua's stack is a heap allocated structure. There is a pointer to the
> top of the stack in each Lua State - this is simply reset after a
> function call. Stack can also be reallocated to reduce or grow as
> needed.
>
> Regards
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Gé Weijers


On Wed, Sep 23, 2020, 06:15 bel <[hidden email]> wrote:
One key to reach real-time requirements is not to prevent Lua from dynamically allocating the stack (or any other object), but to provide an allocator function capable of providing memory in a fixed time. (Others are fine tuning garbage collection, preloading libraries and replacing/not using the io library after initializing, by the way).

Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Some operations performed by the garbage collector may also not meet hard realtime requirements. It all depends on how much delay you can handle.



bel
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

bel
> Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.

You are definitely right when it comes to operations with large n, like concatenating lengthy strings ... so ... "don't do that " (or measure up to what length you can handle the resulting delay).

To clarify the recommendation: Write an allocator function where you can log the memory usage profile, recording what memory blocks your Lua program is actually using (for me the vast majority of blocks was < ~60 Bytes, in total some hundred blocks of this size, and after initialization it never needed a block with more than some hundred bytes, ... don't remember the exact numbers). Then preallocate ~1000 blocks * ~60 bytes, lock it in memory, and use this preallocated pool in your allocator function (if you use it for just one state, you can even drop mutexes there).

This way, you will not end up with a "general purpose real time Lua", but with a special purpose system ... that cannot handle lengthy strings, but work with numbers in real time.
From my experience, real time systems are always "special purpose" anyway - so this approach might work for you or not, depending on what the system is supposed to do.
Would you mind telling something about the purpose of the real time system and the role of Lua therein?


On Wed, Sep 23, 2020 at 5:32 PM Gé Weijers <[hidden email]> wrote:


On Wed, Sep 23, 2020, 06:15 bel <[hidden email]> wrote:
One key to reach real-time requirements is not to prevent Lua from dynamically allocating the stack (or any other object), but to provide an allocator function capable of providing memory in a fixed time. (Others are fine tuning garbage collection, preloading libraries and replacing/not using the io library after initializing, by the way).

Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Some operations performed by the garbage collector may also not meet hard realtime requirements. It all depends on how much delay you can handle.



Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Philippe Verdy-2
I do agree, and modern allocators already use pools of preallocated objects for common sizes, and maintain usage statistics to avoid freeing these pools too early.

Le mer. 23 sept. 2020 à 20:56, bel <[hidden email]> a écrit :
> Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.

You are definitely right when it comes to operations with large n, like concatenating lengthy strings ... so ... "don't do that " (or measure up to what length you can handle the resulting delay).

To clarify the recommendation: Write an allocator function where you can log the memory usage profile, recording what memory blocks your Lua program is actually using (for me the vast majority of blocks was < ~60 Bytes, in total some hundred blocks of this size, and after initialization it never needed a block with more than some hundred bytes, ... don't remember the exact numbers). Then preallocate ~1000 blocks * ~60 bytes, lock it in memory, and use this preallocated pool in your allocator function (if you use it for just one state, you can even drop mutexes there).

This way, you will not end up with a "general purpose real time Lua", but with a special purpose system ... that cannot handle lengthy strings, but work with numbers in real time.
From my experience, real time systems are always "special purpose" anyway - so this approach might work for you or not, depending on what the system is supposed to do.
Would you mind telling something about the purpose of the real time system and the role of Lua therein?


On Wed, Sep 23, 2020 at 5:32 PM Gé Weijers <[hidden email]> wrote:


On Wed, Sep 23, 2020, 06:15 bel <[hidden email]> wrote:
One key to reach real-time requirements is not to prevent Lua from dynamically allocating the stack (or any other object), but to provide an allocator function capable of providing memory in a fixed time. (Others are fine tuning garbage collection, preloading libraries and replacing/not using the io library after initializing, by the way).

Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Some operations performed by the garbage collector may also not meet hard realtime requirements. It all depends on how much delay you can handle.



Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

孙世龙 sunshilong
In reply to this post by bel
Hi, bel

>In any case, you need to deal with Lua dynamically increasing and reducing
>not only the stack, but many other objects as well. Handle these
>allocations by a proper "special purpose" alloc/free implementation,
>instead of using the "general purpose" algorithms in a typical non-realtime
>standard C library.
TLSF is a good choice. What do you think about it? Or any other
available choice?


>One key to reach real-time requirements is not to prevent Lua from
>dynamically allocating the stack (or any other object), but to provide an
>allocator function capable of providing memory in a fixed time.
And
>This way, you will not end up with a "general purpose real time Lua",
>but with a special purpose system ... that cannot handle lengthy strings,
>but work with numbers in real time.

I agree that the allocator function is the key factor. But as you said that
the "special" purpose real-time system that even cannot handle lengthy strings,
so I still think that dynamically growing the stack is a problem that should be
solved or avoided.

And another question, what do you think "real-time" really mean? Does it have
any relation with handling lengthy strings? I am really confused, though I have
been doing some development with real-time OS for half an year.

>Would you mind telling something about the purpose of the real time system
>and the role of Lua therein?
I want the Lua script can meet soft real-time requirement, which
controls a robot
arm to grab food(i.e cookies).

Thank you for your attention to my question.

Best regards
Sunshilong

On Thu, Sep 24, 2020 at 2:56 AM bel <[hidden email]> wrote:

>
> > Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.
>
> Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.
>
> You are definitely right when it comes to operations with large n, like concatenating lengthy strings ... so ... "don't do that " (or measure up to what length you can handle the resulting delay).
>
> To clarify the recommendation: Write an allocator function where you can log the memory usage profile, recording what memory blocks your Lua program is actually using (for me the vast majority of blocks was < ~60 Bytes, in total some hundred blocks of this size, and after initialization it never needed a block with more than some hundred bytes, ... don't remember the exact numbers). Then preallocate ~1000 blocks * ~60 bytes, lock it in memory, and use this preallocated pool in your allocator function (if you use it for just one state, you can even drop mutexes there).
>
> This way, you will not end up with a "general purpose real time Lua", but with a special purpose system ... that cannot handle lengthy strings, but work with numbers in real time.
> From my experience, real time systems are always "special purpose" anyway - so this approach might work for you or not, depending on what the system is supposed to do.
> Would you mind telling something about the purpose of the real time system and the role of Lua therein?
>
>
> On Wed, Sep 23, 2020 at 5:32 PM Gé Weijers <[hidden email]> wrote:
>>
>>
>>
>> On Wed, Sep 23, 2020, 06:15 bel <[hidden email]> wrote:
>>>
>>> One key to reach real-time requirements is not to prevent Lua from dynamically allocating the stack (or any other object), but to provide an allocator function capable of providing memory in a fixed time. (Others are fine tuning garbage collection, preloading libraries and replacing/not using the io library after initializing, by the way).
>>
>>
>> Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.
>>
>> Some operations performed by the garbage collector may also not meet hard realtime requirements. It all depends on how much delay you can handle.
>>
>>
>>>
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Gé Weijers
In reply to this post by bel


On Wed, Sep 23, 2020, 11:56 bel <[hidden email]> wrote:
> Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.

Growing a table is the operation that would cause significant delays when the table is large enough. You would have to keep sizes small or fixed to guarantee constant time operations.

Growing an array by doubling it's size when you run out of space has O(1) complexity, but that is amortized complexity which is not good enough for hard realtime work unless you limit the maximum array size.


bel
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

bel
Yes, all objects (strings, tables/arrays, ...) need to have a known maximum size. But that's by no means specific to Lua.
There are a lot of implicit assumptions on the type of real time system in my two short comments above - that's why I finally asked for some information on the kind of real time system you have in mind, because maybe all my attempts to explain could be a waste of time for both of us, if you have completely different requirements than I had and you are looking for something completely different.

By "real time" I mean some loop running in some fixed cycle (somewhere between 100 microseconds and 10 milliseconds) or event/interrupt driven. Every cycle starts with reading some input values (booleans and numbers) corresponding to sensor signals. Inputs could also be "messages" (data from serial communication, network packages, ...) - these are of type string but with a well known maximum length (the serial interface has a maximum baud rate, you know the cycle time --> you can calculate it). Within every cycle you need to process all (relevant) inputs, e.g. by filtering it and storing results in a log (data logger), by calculating outputs (closed loop control), probably updating some internal state machines, ... In any case, you must never miss any cycle, because the input data will be gone, the data logs incomplete, the outputs and state machines incorrect. However, the data processed in every cycle has a more or less constant, and limited size. There is no handling of "lengthy" (thousands of bytes) strings.
If you have something completely different in mind, all my suggestions above may not be helpful at all - so probably you should explain a little more on your use case (I don't want to bother you with irrelevant stuff).

On Thu, Sep 24, 2020 at 3:34 PM Gé Weijers <[hidden email]> wrote:


On Wed, Sep 23, 2020, 11:56 bel <[hidden email]> wrote:
> Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.

Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.

Growing a table is the operation that would cause significant delays when the table is large enough. You would have to keep sizes small or fixed to guarantee constant time operations.

Growing an array by doubling it's size when you run out of space has O(1) complexity, but that is amortized complexity which is not good enough for hard realtime work unless you limit the maximum array size.


Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Robert Burke
In reply to this post by Gé Weijers
On Thu, Sep 24, 2020 at 10:35 PM Gé Weijers <[hidden email]> wrote:
> Growing a table is the operation that would cause significant delays when the table is large enough. You would have to keep sizes small or fixed to guarantee constant time operations.

As discussed previously on the mailing list, you'll cause tables'
contents to be copied to a new backing array and rehashed just by
adding and removing elements while keeping the table a fixed size.
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

孙世龙 sunshilong
Hi,  Robert Burke

Thank you for your clarification.

>As discussed previously on the mailing list, you'll cause tables'
>contents to be copied to a new backing array and rehashed just by
>adding and removing elements while keeping the table a fixed size.
How to keep the table a fixed size?
I found that it seems that there are two related problems:
1. How to pre-allocate a fixed size table in Lua?
    I find it is only possible on the C side with this function:
    void lua_createtable (lua_State *L, int narr, int nrec);
    (for details, see
    https://stackoverflow.com/questions/124455/how-do-you-pre-size-an-array-in-lua)

2.There's no trivial way to get the size of a table(for details, see
https://stackoverflow.com/questions/2461932/is-there-a-simple-way-to-get-the-memory-usage-of-a-lua-table.)

Thank you for your attention to this matter.
Best regards
Sunshilong

On Fri, Sep 25, 2020 at 9:40 PM Robert Burke <[hidden email]> wrote:
>
> On Thu, Sep 24, 2020 at 10:35 PM Gé Weijers <[hidden email]> wrote:
> > Growing a table is the operation that would cause significant delays when the table is large enough. You would have to keep sizes small or fixed to guarantee constant time operations.
>
> As discussed previously on the mailing list, you'll cause tables'
> contents to be copied to a new backing array and rehashed just by
> adding and removing elements while keeping the table a fixed size.
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

孙世龙 sunshilong
In reply to this post by bel
>However, the data processed in every cycle has a more or less constant,
>and limited size. There is no handling of "lengthy" (thousands of bytes)
>strings.
If I understand correctly, all the objects should have a pre-known max
size to meet the soft real-time requirements.

>If you have something completely different in mind, all my suggestions
>above may not be helpful at all - so probably you should explain a little
>more on your use case (I don't want to bother you with irrelevant stuff).
I use Lua scripts to control the robot arm to grab cookies, plates, fruits
and etc. And move them from one point to another.
No damage or bad things may happen if the soft real-time requirement is
breaked occasionally.

Best regards.
Sunshilong



On Fri, Sep 25, 2020 at 5:57 AM bel <[hidden email]> wrote:

>
> Yes, all objects (strings, tables/arrays, ...) need to have a known maximum size. But that's by no means specific to Lua.
> There are a lot of implicit assumptions on the type of real time system in my two short comments above - that's why I finally asked for some information on the kind of real time system you have in mind, because maybe all my attempts to explain could be a waste of time for both of us, if you have completely different requirements than I had and you are looking for something completely different.
>
> By "real time" I mean some loop running in some fixed cycle (somewhere between 100 microseconds and 10 milliseconds) or event/interrupt driven. Every cycle starts with reading some input values (booleans and numbers) corresponding to sensor signals. Inputs could also be "messages" (data from serial communication, network packages, ...) - these are of type string but with a well known maximum length (the serial interface has a maximum baud rate, you know the cycle time --> you can calculate it). Within every cycle you need to process all (relevant) inputs, e.g. by filtering it and storing results in a log (data logger), by calculating outputs (closed loop control), probably updating some internal state machines, ... In any case, you must never miss any cycle, because the input data will be gone, the data logs incomplete, the outputs and state machines incorrect. However, the data processed in every cycle has a more or less constant, and limited size. There is no handling of "lengthy" (thousands of bytes) strings.
> If you have something completely different in mind, all my suggestions above may not be helpful at all - so probably you should explain a little more on your use case (I don't want to bother you with irrelevant stuff).
>
> On Thu, Sep 24, 2020 at 3:34 PM Gé Weijers <[hidden email]> wrote:
>>
>>
>>
>> On Wed, Sep 23, 2020, 11:56 bel <[hidden email]> wrote:
>>>
>>> > Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.
>>>
>>> Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.
>>
>>
>> Growing a table is the operation that would cause significant delays when the table is large enough. You would have to keep sizes small or fixed to guarantee constant time operations.
>>
>> Growing an array by doubling it's size when you run out of space has O(1) complexity, but that is amortized complexity which is not good enough for hard realtime work unless you limit the maximum array size.
>>
>>>
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Eretnek Hippi Messiás
In reply to this post by 孙世龙 sunshilong
hi all! :)

孙世龙 sunshilong:
> 1. How to pre-allocate a fixed size table in Lua?

1st:
get a fake `nil`, if too obvious, then jump to "2nd:" :D

so lets say
`NULL={}`
or
```
NULL=setmetatable(
  {},
  { __newindex=function() end,
    __metatable=true})
```
or
`NULL=function() end`

the point is to have a unique identity that differs from everything else (recently (in the version detection hack topic?) it was shown that in some cases u can get the same function more than once if it is cached and identical and i think if it comes from the same place, like a generator; and much earlier someone told that the plain empty table approach can leak data in a sandbox, and there was the suggestion for an empty function, but i think the metatable approach is the best for all cases...)


2nd:
make a `table.new()` (or anything like) that prefills ur table with these `NULL`s for the keys u want (with a hash part that has unknown keys, it is harder, but when they are known, then this initializer can get the keys). and give it a metatable where `__newindex` will insert a `NULL` instead of `nil`s and where `__index` will give back `nil`s instead of `NULL`s.

probably some implementation details could matter a bit (like the actual size could vary, while still being constant), but if either u dont change the number of the elements in the hash part or u dont cross a boundary for the size (to trigger a shrink/grow), then it shouldnt change. the former is more questionable if theres a way at all for removing and adding a key, in other words, change one to something else, either to consume a dummy placeholder or just to reuse a key slot...

bests, have fun! :)

Sent with ProtonMail Secure Email.
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

Robert Burke
On Sat, Sep 26, 2020 at 9:50 PM Eretnek Hippi Messiás
<[hidden email]> wrote:
> 2nd:
> make a `table.new()` (or anything like) that prefills ur table with these `NULL`s for the keys u want (with a hash part that has unknown keys, it is harder, but when they are known, then this initializer can get the keys). and give it a metatable where `__newindex` will insert a `NULL` instead of `nil`s and where `__index` will give back `nil`s instead of `NULL`s.
>
It is not necessary to use a NULL or a metatable, because values that
are set to some non-nil value then set to nil keep their entries in
the table. That is, the entry is not deleted by setting it to nil, it
would only be deleted in a rehash. This is why you can delete some
keys from a table while iterating over it.

So if you know your key set, it is sufficient to initialize your table
like this:

local all_keys = {"x", "y", "cow", "chicken", "duck"}
local function table_new()
  local t = {}
  for _,k in ipairs(all_keys) do
    t[k] = true
  end
  for _,k in ipairs(all_keys) do
    t[k] = nil
  end
  return t
end

> probably some implementation details could matter a bit (like the actual size could vary, while still being constant), but if either u dont change the number of the elements in the hash part or u dont cross a boundary for the size (to trigger a shrink/grow), then it shouldnt change. the former is more questionable if theres a way at all for removing and adding a key, in other words, change one to something else, either to consume a dummy placeholder or just to reuse a key slot...
In the implementation we have, if the key set changes over time, you
will trigger a rehash, even if you do not increase the size of the
table.
bel
Reply | Threaded
Open this post in threaded view
|

Re: How to comprehend that Lua automatically removes whatever is in the stack below the results after the function returned?

bel
In reply to this post by 孙世龙 sunshilong

 

> If I understand correctly, all the objects should have a pre-known max
> size to meet the soft real-time requirements.

Not exactly. The concept is to allow the Lua interpreter to allocate and free all objects, as it always does, but to not pass this memory dynamics to the operating system or glibc. You can effectively make most reallocations “zero cost” operations (at the cost of a small memory overhead). Probably some pseudo-code for the allocator function explains this more clearly:

if (nsize==0) {

} else if (!ptr) {
    nsize = get_better_quess_of_size_from_object_type(nsize, osize); /* osize is LUA_T*, see https://www.lua.org/manual/5.3/manual.html#lua_Alloc */
    if (nsize <= 64) return new_element_from_64_bytes_pool();
    if (nsize <= 256) return new_element_from_256_bytes_pool();
    if (nsize <= 4096) return new_element_from_4096_bytes_pool();
    if (we_are_in_initialization) return malloc(); /* can do this when loading program */
    else fatal_error(); /* but cannot during cyclic real-time … somebody should have tested before */
} else {
    if (is_in_64_bytes_pool(ptr)) {
        if (nsize <= 64) return ptr; /* resizing in the range [1..64] does “nothing” */
        else … /* move to a bigger block … happens rarely */
    } else if (is_in_256_bytes_pool(ptr)) {
        if (nsize <= 256) return ptr; /* … same as before */
   

Where the pools are basically arrays, like
static char my_64_bytes_pool[500][64], my_256_bytes_pool[100][256], my_4066_bytes_pool[20][4096];
except they are allocated page aligned and locked. The sizes 64, 256 and 4096 (and that there are 3 pools), the number of 500, 100 and 20 elements are just example numbers here. Actual numbers come from a lot of testing/profiling of real life programs made for exactly this context (if the numbers are not well chosen, the code will still work but it will waste some memory). This code assumes objects will tend to keep their sizes within a certain range – there is no theory predicting this (as to my knowledge), it is an experimental finding. Maybe this code expresses more clearly what I meant, than my attempts to explain it in English. Essentially Lua forwards all resizing operations to the allocator, but the allocator does not call malloc/realloc/free during real time processing. You need to know the maximum amount of memory used and pre-allocate it (with some reserve). But for real time you anyway need to keep memory consumption below some maximum, because when the system starts to swap data to disk due to low memory, even soft real time is definitely lost.

 

> I use Lua scripts to control the robot arm to grab cookies, plates, fruits
> and etc. And move them from one point to another.

I’m curious about the role of Lua in your application. Are you using Lua for the robot program (defining pick/place positions and sequences), object identification/tracking (camera, sensor, conveyor belt?), robot coordinate transformation and/or also for real time path trajectory generation (for servo drives)?

 

> No damage or bad things may happen if the soft real-time requirement is
> breaked occasionally.

I think there is no commonly agreed on clear definition of “soft” real time and no precise discrimination from “hard” real time – for an estimation of the real time capability of a system, you need a lot more information (cycle time, jitter of the underlying operating system and hardware, timing constraints of I/O devices and/or field busses, …). Missing a sensor signal or detecting the position of a moving object at the wrong time will yield to missed picks, discontinuities in motion profiles will cause undesirable dynamic stress for the robot mechanics or drop a grabbed cookie, …

Archiving real time capability of an interpreter is also just a small step on a long path towards a full robot control software ecosystem. In case you are interested in a professional, commercial hard real-time software system for robot control (including sensor/camera integration, path blending, events some milliseconds before a pick position is reached, …), I might be able to give you some recommendations, depending on your exact needs. Just write me an email (you have my email address?). Feel free to do so as well, for highly robotic specific topics (that might be too specific for the Lua mailing list). Probably you are trying to build something already existing.


On Sat, Sep 26, 2020 at 7:26 AM 孙世龙 sunshilong <[hidden email]> wrote:
>However, the data processed in every cycle has a more or less constant,
>and limited size. There is no handling of "lengthy" (thousands of bytes)
>strings.
If I understand correctly, all the objects should have a pre-known max
size to meet the soft real-time requirements.

>If you have something completely different in mind, all my suggestions
>above may not be helpful at all - so probably you should explain a little
>more on your use case (I don't want to bother you with irrelevant stuff).
I use Lua scripts to control the robot arm to grab cookies, plates, fruits
and etc. And move them from one point to another.
No damage or bad things may happen if the soft real-time requirement is
breaked occasionally.

Best regards.
Sunshilong



On Fri, Sep 25, 2020 at 5:57 AM bel <[hidden email]> wrote:
>
> Yes, all objects (strings, tables/arrays, ...) need to have a known maximum size. But that's by no means specific to Lua.
> There are a lot of implicit assumptions on the type of real time system in my two short comments above - that's why I finally asked for some information on the kind of real time system you have in mind, because maybe all my attempts to explain could be a waste of time for both of us, if you have completely different requirements than I had and you are looking for something completely different.
>
> By "real time" I mean some loop running in some fixed cycle (somewhere between 100 microseconds and 10 milliseconds) or event/interrupt driven. Every cycle starts with reading some input values (booleans and numbers) corresponding to sensor signals. Inputs could also be "messages" (data from serial communication, network packages, ...) - these are of type string but with a well known maximum length (the serial interface has a maximum baud rate, you know the cycle time --> you can calculate it). Within every cycle you need to process all (relevant) inputs, e.g. by filtering it and storing results in a log (data logger), by calculating outputs (closed loop control), probably updating some internal state machines, ... In any case, you must never miss any cycle, because the input data will be gone, the data logs incomplete, the outputs and state machines incorrect. However, the data processed in every cycle has a more or less constant, and limited size. There is no handling of "lengthy" (thousands of bytes) strings.
> If you have something completely different in mind, all my suggestions above may not be helpful at all - so probably you should explain a little more on your use case (I don't want to bother you with irrelevant stuff).
>
> On Thu, Sep 24, 2020 at 3:34 PM Gé Weijers <[hidden email]> wrote:
>>
>>
>>
>> On Wed, Sep 23, 2020, 11:56 bel <[hidden email]> wrote:
>>>
>>> > Growing an object requires copying, which can't be done in constant time. Most CPUs can copy very quickly but it's still an O(n) operation, however efficient you make the memory management.
>>>
>>> Even copying is only O(n) for a "larger" number of bytes n. For small n effects memory access, caching, ... (random effects) do have a much bigger effect on execution time than copying a byte more - making it effectively independent from n. The ~32 bytes mentioned before would be "small" from that point of view.
>>
>>
>> Growing a table is the operation that would cause significant delays when the table is large enough. You would have to keep sizes small or fixed to guarantee constant time operations.
>>
>> Growing an array by doubling it's size when you run out of space has O(1) complexity, but that is amortized complexity which is not good enough for hard realtime work unless you limit the maximum array size.
>>
>>>