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

17 messages
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?

 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
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?

 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. -- Gé
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?

 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
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?

 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
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?

 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
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?

 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.
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?

 > 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.
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?

 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.
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?

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?

 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.
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?

 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.
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?

 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.
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?

 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.
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?

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?

 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.