GC Parameters & Emergency Collection
Locked
 
|
jbsnyder |
GC Parameters & Emergency Collection
|
Hi -
I was wondering whether there might be any objection to adjusting the LUAI_GCPAUSE variable, decreasing the value from 200 to 110? This will cause GC to run after a 10% increase in memory allocated by Lua as opposed to a doubling. I'm not sure where I'm spinning off objects, but I've recently been finding that for running my ADC example scripts over long periods of time they will sometimes bail out when Lua is unable to allocate more memory. If I have the scripts periodically run a full GC however, they never bail. This particular GCPAUSE value is what Ralph Hempel is using in pbLua (just got a copy of Lua Gems). One case that this made me think about was that if I have 32k of RAM, and I've just allocated more than 16k of that already, I won't GC until I exceed available memory? Of course, since we don't have emergency GC, this just means that we get an "out of memory" error and get dumped to the prompt. Additionally: I've looked at the emergency GC patch minimally, and it looks fairly extensive. I suppose this wouldn't work in all cases (presumably since GC may sometimes require memory to grow a bit before shrinking), but would it not be useful to attempt a GC when a new allocation fails? I've thought about attempting to apply the emergency GC patch to eLua, but I've not bothered because 5.2 is intended to include some sort of emergency GC. Another thought: One of the reasons we don't have determinism in execution times is because of GC. I've not dug into how the Lua GC works, but is there some way that we could have it operate in some sort of fixed execution time mode where with debug hooks where we could run it for a fixed length of time at that frequency to control latency? Just some thoughts... :-) -- James Snyder Biomedical Engineering Northwestern University [hidden email] http://fanplastic.org/key.txt ph: (847) 448-0386 _______________________________________________ Elua-dev mailing list [hidden email] https://lists.berlios.de/mailman/listinfo/elua-dev |
PGP.sig (201 bytes) |
|
Robert G. Jakabosky |
Re: GC Parameters & Emergency Collection
|
|
Hello eLua list,
I am the creator of the Emergency Garbage Collection (EGC) patch for Lua 5.1.x. I joined this list because I have interest in using Lua VM with a very low memory limit and I think that over laps with embedded systems. Attached is a version of the EGC patch for eLua SVN revision 281. I just had to updated line numbers so it would apply cleanly to eLua without any warnings. I have only done minimal testing. Had problems with getting newlib compiled on my 32bit Gentoo linux box so that I could test eLua standalone inside Vmware. So I ended up only testing eLua's modified copy of Lua as a linux app. and only tested life.lua and bisect.lua (I just pick two from the romfs folder). life.lua was able to run with the memory limit set to 60Kbytes. The attched 'linux_host.patch' file are the changes I made to eLua so I could test it. For testing & debugging what tools do other people use? Remote gdb over serial? I might be able to do more testing tomorrow, right now I am to tired. On Friday 08, James Snyder wrote: > Additionally: I've looked at the emergency GC patch minimally, and it > looks fairly extensive. I suppose this wouldn't work in all cases > (presumably since GC may sometimes require memory to grow a bit before > shrinking), but would it not be useful to attempt a GC when a new > allocation fails? I've thought about attempting to apply the > emergency GC patch to eLua, but I've not bothered because 5.2 is > intended to include some sort of emergency GC. About 2/3 of the EGC patch is to make the resizing of the internal string table & hashpart of Lua table use less memory. That is done by doing an in-place resize of those tables. If the table is shrinking then the nodes are moved to the start of the table then realloc is called to shrink the table. If the table is growing then the realloc is done first before the nodes are moved. All of these changes are in lstring.c & ltable.c and I don't see any conflict with the change eLua made to vanilla Lua. The only place where the GC needed to grow memory usage before shrinking usage is when it is trying to shrink the internal string table or the hashpart of Lua tables. > Another thought: One of the reasons we don't have determinism in > execution times is because of GC. I've not dug into how the Lua GC > works, but is there some way that we could have it operate in some > sort of fixed execution time mode where with debug hooks where we > could run it for a fixed length of time at that frequency to control > latency? I think you could improve the determinism of the GC by changing the luaC_step() function to limit each incremental GC step to some fixed length of time (or cpu cycles if that is cheap to test). This should be a simple change to the luaC_step() function, since it already calls the singlestep() function multiple times until X number of bytes have been freed or the end of the current GC cycle has been reached. I still think that low memory systems should use the EGC to fully utilize the limited memory they have. -- Robert G. Jakabosky _______________________________________________ Elua-dev mailing list [hidden email] https://lists.berlios.de/mailman/listinfo/elua-dev |
|
|
BogdanM |
Re: GC Parameters & Emergency Collection
|
|
|
|
jbsnyder |
Re: GC Parameters & Emergency Collection
|
|
|
|
Robert G. Jakabosky |
Re: GC Parameters & Emergency Collection
|
|
I finally got a working i686-elf toolchain compiled and eLua to boot in a VirualBox instance. Also I found out that eLua will not start when using the Lilo boot loader. I was trying Lilo first since it is smaller then grub and I thought it would be easier to install eLua on a floppy. Turned out that it was much easier to install grub on a floppy and there was enough room for eLua too. On Saturday 09, jbsnyder@fanplastic.org wrote: > > <[hidden email]> wrote: > > > > Many, many thanks for this !!! I wanted to do this for quite a while > > now, but didn't find the time to do it. Your patch is excellent for > > eLua and its goals, so it's a Great Thing to have it running on our > > targets. Thanks again. > > Ditto. Thanks for getting this up and going. I will do some testing > with this, this weekend if I get a chance. I'm curious if this might > allow pushing limits a bit more where we would previously run out of > memory where the problem could be helped by emergency gc. With the patch you can now set a memory limit when starting a Lua script from the eLua shell. eLua# lua -m 51 /rom/life.lua The '-m' option lets you set the memory limit in Kbytes. 51Kbytes was the lowwest I was able to get life.lua to run at with eLua. On my linux host vanilla Lua with the EGC patch can only run life.lua with a minimal memory limit of 60Kbytes. Looks like the ROTables in eLua saved about 9Kbytes here. The attached patch is for stress testing the EGC only. It forces a full GC cycle on every allocation, so it is very slow (life.lua required over 30 minutes to run, compared to 4 minutes). I was able to run all the Lua scripts that eLua includes by default with that stress testing enabled. Normally I would also run the stress testing under valgrind to test for any bad memory accesses, but that is only possible if eLua is run as an app. under a host OS. > > And I couldn't agree with you more, and this why I feel so excited > > for having EGC in eLua. I'll have to think of a good batch of tests > > for making your patch shine in its full potential :) > > Would the torture tests for the egc patch work in really low memory > conditions like with 64k of SRAM? > > I think we should also have a general test suite for to simplify the > verification of builds across our multiple platforms. I think I may > start after luarpc is working with eLua. It should be possible to pick torture tests that will work with just 64k of memory. I normally run the Lua scripts from: http://shootout.alioth.debian.org/ when stress testing the EGC patch. Some of those scripts will require more then 64k for that dataset that they process. -- Robert G. Jakabosky _______________________________________________ Elua-dev mailing list [hidden email] https://lists.berlios.de/mailman/listinfo/elua-dev |
|
|
BogdanM |
Re: GC Parameters & Emergency Collection
|
|
|
|
jbsnyder |
Re: GC Parameters & Emergency Collection
|
|
In reply to this post by Robert G. Jakabosky
Minimal testing seems to show it working and surviving through conditions where previously it would run out of memory on STM32 w/ 64k SRAM. -jsnyder On May 10, 2009, at 5:48 AM, Robert G. Jakabosky wrote:
-- James Snyder Biomedical Engineering Northwestern University ph: (847) 448-0386 _______________________________________________ Elua-dev mailing list [hidden email] https://lists.berlios.de/mailman/listinfo/elua-dev |
|
|
BogdanM |
Re: GC Parameters & Emergency Collection
|
|
|
|
jbsnyder |
Re: GC Parameters & Emergency Collection
|
|
On May 11, 2009, at 12:54 AM, Bogdan Marinescu wrote:
I agree. Does the performance hit only show up during a GC (emergency or no)? I've not clocked any of this yet. In practice I would say since we have a fixed amount of memory, it's really undesirable to fail simply because a garbage collection event wasn't called in time. The other side is that if the penalty is only at GC time, people could disable collection during time-critical operations. I haven't taken a deep look to understand how every part of the patch works yet, but I see that it does provide a configurable of a memory limit. Maybe another interesting tunable might be how many GC steps to take when an emergency GC is called (i.e.: just enough for the allocation pending, full gc, or something else?) I'm also still curious about the idea of running GC in fixed timesteps, In the interests of pragmatism, I don't think I'd pursue anything more detailed here unless I run up against some situation where it doesn't work as desired. I think, overall, a default of sane incremental collection (maybe with the GCPAUSE set to 110) and a backstop emergency GC should be a good solution for most cases. -- James Snyder Biomedical Engineering Northwestern University ph: (847) 448-0386 _______________________________________________ Elua-dev mailing list [hidden email] https://lists.berlios.de/mailman/listinfo/elua-dev |
|
|
BogdanM |
Re: GC Parameters & Emergency Collection
|
|
|
|
BogdanM |
Re: GC Parameters & Emergency Collection
|
|
|
|
jbsnyder |
Re: GC Parameters & Emergency Collection
|
|
On May 11, 2009, at 5:17 PM, Bogdan Marinescu wrote: OK, this is what I was talking about: I see. The performance implications are pretty extreme as well. I guess some other tests that I'd like to cook up would be how LUAI_GCPAUSE affects those numbers as well, and also something showing the variability in loop timings depending on which is in use. If I get some time I'll run some numbers there, since I've been doing a bit of testing around memory growth when running scripts like adcscope. OT: My next major goal, though, is getting RPC working (should be pretty easy once I finish a bit more refactoring). I'll talk about it a bit more soon. I suppose I should also clean it up a little and see what the folks on the Lua list think once it's working with the generic transport layer. -- James Snyder Biomedical Engineering Northwestern University ph: (847) 448-0386 _______________________________________________ Elua-dev mailing list [hidden email] https://lists.berlios.de/mailman/listinfo/elua-dev |
|
|
Robert G. Jakabosky |
Re: GC Parameters & Emergency Collection
|
|
In reply to this post by BogdanM
On Monday 11, Bogdan Marinescu wrote:
> > I agree. Does the performance hit only show up during a GC (emergency or > > no)? I've not clocked any of this yet. > > Yes, the performance hit happens only during GC, which becomes a visible > problem when GC is called too often. But hey, at least your program is > running :) The only performance hit during a normal GC is the in-place resizing. During an emergency (out of memory) you can choice between throwing an error or taking a performance hit and calling the GC. The in-place resizing should be the only change in EGC that can cause slow downs (I wasn't able to messure any slow downs on my desktop, maybe the in-place resizing was helped by the L2 cache). Also only the hashpart resizing will require extra cpu work (it is also the most complex part of the EGC patch). Re-ordering the strings into the correct hash bucket was easy for the string table, since the buckets are normal linked lists. The hashpart of tables are more difficult to resize since the chain of nodes for each bucket are nodes from a single array instead of each node being allocated as a seperate block of memory. The other 1/3 of the EGC patch is just bug fixes to make it safe to call the GC from any place in Lua (i.e. on any allocation). Those changes were mostly moving code arround and not adding more work. Basically you just have to make sure the GC can find all GC'able objects, this means keeping atleast a reference to them on the Lua stack and not just the C-stack. > > The other side is that if the penalty is only at GC time, people could > > disable collection during time-critical operations. > > Definitely, part II :) You can disable the GC from happening durimg time-critical ops and it will also stop it from happening during an emergency. You could override the default Lua allocator and tune it to your needs. One way would be to reserve some memory for use when the GC is blocked. Use the memlimit as a softmark, that will call the GC during allocations only if the memory usage is above the memory limit but not throw an error if the GC can't free enough memory to lower the usage to below the softmark. Then during time-critical ops the GC will be blocked and there should still be some free memory to handle allocations during that time. > > I haven't taken a deep look to understand how every part of the patch > > works yet, but I see that it does provide a configurable of a memory > > limit. Maybe another interesting tunable might be how many GC steps to > > take when an emergency GC is called (i.e.: just enough for the allocation > > pending, full gc, or something else?) I'm also still curious about the > > idea of running GC in fixed timesteps, > > I did quite a few tests with Robert's patch a while ago, I really need to > look for my messages related to this subject on the Lua list and repost > them here. They're quite interesting. untill just enough memory was freed to handle the current allocation or untill atleast one full GC cycle is completed. That is if the memory usage + allocation size is greater then the set memory limit. If realloc() returns NULL, then a real emergency full GC cycle is done. A fixed timestep based GC would be very easy to do with a count debug hook. You could call the singlestep() from lgc.c once every X Lua ops. looking at the luaC_step() function again, it looks like it might be doing to much work to be used from the Lua allocator. I might look into creating a more flexible/simple GC step function. > > In the interests of pragmatism, I don't think I'd pursue anything more > > detailed here unless I run up against some situation where it doesn't > > work as desired. I think, overall, a default of sane incremental > > collection (maybe with the GCPAUSE set to 110) and a backstop emergency > > GC should be a good solution for most cases. > > I'd say a configurable emergency GC should be a good solution for most > cases. That is, the user should be able to define how the emergency GC will > run, which will give him a choice between speed and memory usage. Not hard > to do, fortunately. Again, things will probably be more clear after I post > the results of Robert's patch here. Another place to tune Lua's memory usage is the size of the internal string table. Right now the table will grow to twice the old size when the number of unique strings equals the old table size. This is not required for the string table since it uses buckets that chain together nodes that are allocated seperately (unlike the hashpart of Lua tables). The string tables bucket array can be many times smaller then the total number of unique strings. Having a smaller number of buckets will only slow down new string creation. Once strings are internalized they don't touch the string table. some quiuck tests with life.lua: 1Mbyte of memory without EGC patch: str count = 257, max buckets 512 1Mbyte of memory with EGC: str count = 256, max buckets 512 64Kbyte of memory with EGC: str count = 128, max buckets 256 1Mbyte of memory with EGC and allow bucket count < 2 * str count: str count = 273, max buckets 256 64Kbyte of memory with EGC and allow bucket count < 2 * str count: str count = 145, max buckets 128 1Mbyte of memory with EGC and allow bucket count < 4 * str count: str count = 273, max buckets 128 64Kbyte of memory with EGC and allow bucket count < 4 * str count: str count = 145, max buckets 64 Each bucket is a pointer so 512 buckets would equal 2Kbytes with 32bit pointers. I only timed two tests to see the difference in speed: 64Kbyte of memory with EGC: str count = 128, max buckets 256 real time = 11.035 seconds 64Kbyte of memory with EGC and allow bucket count < 4 * str count: str count = 145, max buckets 64 real time = 8.832 seconds I was very surpised to see that the run time decrease with a smaller number of buckets, I guess the EGC didn't have to run as many times since there was an extra 768 bytes of memory. Also notice that the string count is higher on the faster test, life.lua creates a lot of temp strings to render the output, so with more memory available to hold the string it doesn't have to recreate them as much. The attached patch has the changes to allow bucket count < 4 * str count and the fprintf I used to get the above string & bucket counts. I think it would be good to add support for tunning the low & high water marks for shrinking/growing the string table. Atleast this shows that it is possible to squeeze more memory out of the Lua core. -- Robert G. Jakabosky _______________________________________________ Elua-dev mailing list [hidden email] https://lists.berlios.de/mailman/listinfo/elua-dev |
| Free forum by Nabble | Edit this page |