Help with garbage collection?

Heres my problem.

I've got a game that creates an array in lua via a table, of size 500x500x10 or so, filling up data over the course of 10 seconds; one of the indexes is the frame #. So after 500 frames, it returns to the beginning, and starts overwriting old data; every time it loads an index, it erases the previous one

(so my code looks something like this:)
array[x] = [];
array[x][y][z] = ....;


My problem comes with lua's garbage collection scheme. Clearly, this array takes up a HUGE amount of RAM during the runtime. The game's memory usage will constantly increase; it starts at 18 megabytes at the start of the frame, and increases by about 1 megabyte per second up until it hits nearly 70 megabytes of memory. Then *BAM*, the garbage collection cycle runs, and it drops down to ~30 or so megabytes (The size of the data actually in use by the array).

However, when this cycle runs, the game takes a huge framerate drop. Killing those 30+ megabytes of allocated memory makes my game stutter every 40 seconds or so, dropping it from 50 FPS to 35 FPS, since that cycle took so long to process.

So letting the garbage run out of hand seems to overload it so terribly that I can't use it at the runtime without framerate drops. Now, my initial reaction was that I would simply have to run a garbage collection cycle frequently. However, something seems terribly wrong; by just modifying my code to run:

collectgarbage("collect");

every frame of gameplay, what happened was that the game took a huge constant hit of framerate; drastic, something like 50 --> 40 FPS.

Running the cycle once every 5 seconds or so caused the tiniest stutter ever 5 seconds. The only thing is; that doesn't make much sense. The game is only writing/freeing less than a megabyte per frame, something my computer should have no trouble handling. The game indeed caps out at ~32 megabytes of memory instead of constantly crawling upwards, which is good, but it appears that every time I run lua's garbage collection, even though the smallest changes to my table/array have been made, it freaks out.



Now, my suspicion would be this: That the way Lua has tables implemented, each time it frees up the memory from the table, it is doing something funky that involves the entire size of the table, like recreating it, or so on, due to an inefficient implementation. If this is true, or even if it isn't, does anyone know what kind of tactics I could use to make my project more efficient? Is there some issue with the means with which I am instantiating/destructing my table entries that would cause them to collect poorly, something that wouldn't surprise me? In the worst case scenario, I'm looking into the merits of using some alternative data storage technique like heck even LUASQL to interface with.

If it helps, my code looks like this (a section of it):
[spoiler]

Code:

---

--this is invoked once per frame before it updates
function clearTimeStep(timeStep)
 timeArray[timeStep] = {};
end

function update(timeStep)
 for k=1, maxObjects do
  updateObject(timeStep,k);
 end
end

function updateObject(timeStep,id)
 for i=timeStep,timeStep do
  for j=id,id do
  timeArray[i][j] = {};
  timeArray[i][j]["X"] = mmf.Object.GetX(id);
  timeArray[i][j]["Y"] =  mmf.Object.GetY(id);
  timeArray[i][j]["ValA"] = mmf.Object.GetValue(id,1);
  timeArray[i][j]["ValB"] = mmf.Object.GetValue(id,2);
  timeArray[i][j]["ValC"] = mmf.Object.GetValue(id,3);
  end
  end
 end
end

---

[/spoiler]

Garbage collection is an expensive process, even if there isn't a lot of garbage to clean up there is still a high overhead to calling the collector. That's why it tries to wait so it can amortize the cost. You could keep trying to find a suitable interval for calling the GC.

If worst comes to worst, you may want to look into writing a C Module where you can statically allocate a huge chunk of space for your data, which you would just keep overwriting rather than having to constantly recreate the data tables (as is the case with Lua - it's not because it's inefficient, it's just not tuned for that kind of use).

Actually, before you dive into any of that, you might be able to partially mitigate your problem by removing the line "timeArray[i][j] = {};", and either creating your table skeleton ahead of time or putting a check around it. You might reduce the amount of garbage you're producing because you'll at least retain the table rather than discarding it. Whether or not it can reuse the values, I'm really not sure. It depends if number values are treated as a primitive or not.

Hrmm I was looking at it and indeed, while the overhead on the GC is low in itself, the fact that its mark/sweep algorithm seems to count every single object sure seems to take a huge chunk of time like you said.

But yeah you might be right that I could just create a skeleton table and overwrite individual values instead of discarding the entire timestep entries, since they'll be overwritten with data of the same format. The problem with that is twofold; the data will start filling in the table somewhat randomly, leaving behind remnant data on later frames that doesn't actually exist in the array, so the logic might get difficult (If I had object ID 21 leased to an object on frame #31, it would write in that data, but if it doesn't exist on frame #531, the data would still be left idling in that entry, even though no such object existed). Another problem with this is that as the table gets more and more filled in, the amount of memory used by the array would only go up and up and up and approach the worst case scenario, since it would never be cleared out. And since 90% of the time I'll only be using 10% of the table, that could have a negative impact on gameplay in itself, but I'll try testing it. I don't like the thought of using up the full 500x500x8 size array worth of memory, but if it proves to be something a normal computer can field, I'll just use the skeleton approach


But yeah that might really help it if I can get the logic working, thanks. I suppose that writing a C Module that manually allocates the memory itself would create a workable solution if that doesn't work, so its definitely something I'll look into.

Hummm well! That appears to work!
My only problem is that I have to generate the 58 megabytes of array each time the player loads the game now :D Fortunately, I can have it instantiate the 3rd index of the array as it generates it; running a 500x500 loop when the lua loads instead of the 500x500x8 loop. But still... 58 megabytes of RAM constantly needed, minimum! Lordy lordy this is going to be one hog of an app. At least its stable now, thanks!

Humm I'll have to add something in there to control when the maximum cases are in, since without losing any size, worst case scenarios can make it look like this:
http://img56.imageshack.us/img56/9316/edrthell.png


I figure just some common sense code to free the unused memory whenever the game detects that the number of objects exceeds a number, then returns below it, ie whenever the number of particles on screen spikes. It would cause a little slowdown, but it could easily free 100+ megabytes of memory, which is a little ~_~

A C Module approach would cost you about 16Mb (same approach, the complete amount of data is allocated up front).

You could try selectively killing off dead objects, NILing out attributes, and maybe strike some sort of balance between size and GC time. CPU and memory are pretty much a universal trade-off in computing.

Yeah, what I'm looking at right now is running a selective garbage collection scheme inside of lua. Normally CPU and memory are so abundant that MMF never needs to worry about them but I guess I'll have to worry about that trade-off, ehehe.

I figure I'll create a switch that gives it the ability to run the delete/create version of the table for a little while, and then call a garbage collector via lua at the end of the cycle, in order to wipe it, whenever it exceeds whatever threshold. In effect it would be almost exactly what lua is doing in the first place, except instead of just being able to set a threshold like it would give the choice, it would also let me adjust how much it is deleting at a time to stagger it a little.

you could try changing how often the gc runs but apparently that's a touchy process and probably wouldn't improve your situation

lua does do some weird table things, like it won't shrink one if you nil most of it out, at least until you write a few values back into it; however i believe those only affect the hash part which you probably aren't using (unless for whatever reason it's wanting to throw your integer indices into the hash part

of course you could always disable the gc entirely (and re-run it when you can afford to), but obviously that's probably a really bad idea for what you're doing

Well I'm trying to run a bit of a balance between the two by defining the X/Y axes of the 3-dimensional array off the bat, and having it only destruct/collect array elements whenever the number of objects in the game spikes (by comparing the ratio of maximum to minimum objects, and activating it when it goes above 1.5 and then back below 1.25). My hope is that this would create a safety catch that would free up the memory whenever a worst case scenario comes along (the player shoots a million projectiles somehow), and recover from it by freeing up the memory. It would mean the game might spike above 200+ megabytes of RAM, which is pretty nasty.

Unfortanately the huge array size is a pretty crux part of the game. At best I can shrink it by maybe 60% by lowering the maximum object cap from 1000 to 500, and stacking a few variables on top of each other.

I think disabling the GC isn't so terrible here. As long as I'm only overwriting the array, I'm never actually giving lua any bytes to throw away in the first place, so it would never have to run. I figure the garbage collection should only run (and the game should only free up the array) whenever the active portion of the array spikes up and then down. Putting in a naive activation threshold might cause the collector to run nonstop on larger levels, and thus both use up more memory *and* slow down the game, whereas recovering from large memory usages could cause a momentary lag spike, but free up the majority of the memory.

My concern is this; would it really be worth freeing up the memory at all? If the game is going to use up 183 megabytes of RAM in the worst case, should I just allocate all that off the bat and never free it up at all, or will there be any tangible benefits to releasing it. Will there be some computers that will run slowly when the RAM becomes filled, and thus benefit from releasing the chunk? I mean it seems ridiculous and unstable for me to have an MMF app using up 200ish megabytes of RAM, but do I actually benefit more from releasing it than just hogging it all up? My program would be barely using an ounce more from anything else, so I'm not entirely sure.

I mean, what sort of brick walls DO I run into by using up that much RAM?

If you're always storing the same attributes, you should try using sequential integer indices instead of string keys. I did a little test with your code, and got huge memory savings (85MB down to 54MB. Given a 9MB overhead, that's 76 down to 45, or a ~40% reduction. When I used more attributes per table, my savings ratio was closer to 50%).

The reason lies in how Lua stores its tables. Contiguous integer indices are stored in a basic array, and string indices (and outlier indices) are stored in a hash table. The hash table itself, in order to have fast insert and lookup properties, has to reserve extra space and thus has a higher overhead. Each repeated string index also has a stiff memory overhead, compared to an integer index which in this case should be implicit (doesn't have to be stored at all).

I dont understand what problem you are having.
My map editor uses a lua array that can use up to 500x500x12 slots. My map size is variable though so the x and y will be dependent on the map size. I have no problem with writing and reading values to this array at all. Im not sure what you mean by garbage collection though. Is that a command you call from lua itself? Im just overwriting values in each slots, is that different to what your doing?

The problem is Pixelthief is creating and destroying that entire volume of data every 10 seconds (go run his example code, and you will see the memory consumption shoot up like a rocket). Your map would be far less volatile than that, so you wouldn't ever experience a problem. My map editor also stores a huge volume of data but realtime problems like this aren't even relevant to it.

The garbage collector is part of Lua. It runs without you even being aware of it. It's like Java or any other scripting language, it cleans up your memory for you without you ever needing to be conscious of memory management. That contrasts with C where you must explicitly allocate and free all memory.

The problem with the garbage collector is that it will cause "ticks" in your application if you give it too much work to do all at once, such as deleting thousands of tables per second, which is what is going on in this example.

Quote:

---

Originally Posted by Retriever2

If you're always storing the same attributes, you should try using sequential integer indices instead of string keys. I did a little test with your code, and got huge memory savings (85MB down to 54MB. Given a 9MB overhead, that's 76 down to 45, or a ~40% reduction. When I used more attributes per table, my savings ratio was closer to 50%).

The reason lies in how Lua stores its tables. Contiguous integer indices are stored in a basic array, and string indices (and outlier indices) are stored in a hash table. The hash table itself, in order to have fast insert and lookup properties, has to reserve extra space and thus has a higher overhead. Each repeated string index also has a stiff memory overhead, compared to an integer index which in this case should be implicit (doesn't have to be stored at all).

---

Well dang thats silly, I assumed it would use the same structure regardless of input. I'll definitely switch it over to integer keys 1,2,3... instead! Any string storage is entirely to facilitate the code, so its no harm at all, thanks!

One problem is that thats only ~54 MB with my array unfilled; thats using only 1x in the Z index. In my runtime, I'm getting approximately 30 MB from initializing my 'skeleton' array. In the apocalyptic scenario, when its all filled in, it would take 12x that! 260 MB! And if the game tried to release it by running a full 10 seconds and severing all data, yet repasting it all again, it would double to 520 MB before it was deleted. Thats scary

Quote:

---

Originally Posted by Retriever2

The problem is Pixelthief is creating and destroying that entire volume of data every 10 seconds (go run his example code, and you will see the memory consumption shoot up like a rocket). Your map would be far less volatile than that, so you wouldn't ever experience a problem.

---

Yep yep, and unfortunately thats simply a given in the code I'm working on; a 'time travel' engine opposed to a mere map editor, which needs to destruct its entire volume in such a short period. Garbage collection ticks can indeed be a problem with games using lua infrastructure, something I read about in this little blurb, which I found very novel:
http://lua-users.org/wiki/GarbageCollectionInRealTimeGames

I think I know what I could do;
I just could have the game simply wipe the array and collect the garbage whenever you change frames. That should be more than sufficient an answer, and wouldn't hamper gameplay.

You're going to run out of memory really fast unless you're changing frames constantly. For what you're trying to do, producing huge volumes of garbage isn't really a viable solution. You need to reuse your memory.

Thanks for the explanation retriever. I was aware Lua had garbage collection so I was confused for a while there thinking it was an additional call you had to make.
But I dont understand why the array size PixelTheif has is so big? I can have 500x500x12 values stored in an array and my application used like 20mb including MMF. Although mine are all integers and not strings in the table, is that why?

Well heres my think Retriever.
With my scheme, I'd be reusing memory, but it would require a large amount of base memory in use; I'd be using anywhere from 30 MB to 260 MB at a time. The key would be that it would never exceed 260 MB since that would be the maxed out amount. Now, it would only spike to that much memory when a large amount of objects are created, something that isn't likely to last very long. And I could either put in code to reduce the memory usage from 260 down to ~30 again, or let it hang onto 260 MB of RAM until the next frame.

Since its not leaking memory and its capped out, the only advantage of freeing up the memory again is sort of negated by the fact that if anyone was capped out on memory, it would be a moot point to begin with; any code that reduced memory usage from 260 to 30 MB wouldn't have much effect, since if they didn't have 260 to spare, the game would have crashed, and if they did, the gameplay would be unhindered.

So I'm trying to think; is there any situation where freeing up the memory would be useful? Like if someones computer would experience degraded performance as it runs drastically low on RAM, but wouldn't fully crash? Most people have 1-2 Gigabytes of RAM at the least, so I'm not forseeing a 200ish MB usage being a problem at all. And if thats the case, then yes, I'll just reuse my memory and tank along

Another thing. Like bigredron is saying, Lua seems to be very inefficient with its 'number' interface. How many bytes is it really allocating per number in a matrix? Because 1000x500x12 numbers should really only take up 23 megabytes of RAM if they were 4 byte integers. Is there any way to tell it to use a more efficient number scheme? I know theres some funkiness that goes on because it tries to use a single format of number for *everything*.

From what I understand, the table allocates 40 bytes for empty, and 16 bytes per index (allocated at an exponential rate). With 500x500x12, thats 91 megabytes simply for the array indexes, not even including the numbers. Is there any way to create a more efficient static array in lua? Or could I use some external interface to work with arrays like luasql or something, that might be more efficient.

Err, that is to say, I'd have to do something like build a C module for lua, right?

Numbers are all stored as doubles, so that's 8 bytes per number. That's basically non-negotiable.

However if you want to save on table and index overhead, you could do a flat array and calculate your indices, e.g. data[i*500+j][1] or even data[i*500+j*12+1] and then you have no other tables at all. As long as you use the numeric indices you'll be doing simple array-based lookups and not a hash table lookup, so you could get considerable space savings.

ok yeah I'll try just doing a singular 'bytewise' array instead of using the built in dimension lookups, that might help. But the 16 bytes per index is a little huge... I'm not sure if moving it into c code would be worthwhile.

Lemme think:
1000x500x12 = 6 million entries.
Lua = 24 bytes per entry = 137 megabytes
C = 8 bytes per entry = 46 megabytes

137 honestly isn't a bother at all. I'm guessing my table is only large because like you say, it must be hashing as a 3 dimensional array even though the indexes are numerical and integral

Thanks guys you have made me understand better.
My array is stored like this: map[i][j][k] so all indexes are number based. All my stored values are also numbers so I guess thats why its extremely fast and not using much ram?
I was considering string indexes so glad I opted out of that :)

Also Pixeltheif above, why 24bytes per entry and not 16 bytes?? Or are you saying 3 x indexes at bytes each?
Sorry for sounding a but dumb, I can udnerstand lua code pretty well and make it do what I want, I am just not good with memory managment so tis good to learn!

well 16 bytes for the index, 8 bytes for the number itself
so 24 overall. However, this doesn't seem entirely right, either. I tried out code that filled up a 6,000,000 size array for the single index, and it used up 300+ mb off the bat, when it should be 137. However, using the tricks we figured out over the past few pages, I've already got my program's memory usage down to manageable amount, even if its not perfect, so I think I'm good to go (I'm storing as array[i][j][k], too).

But I dont understand how you are getting such high memory usage when I have a table that is 500x500x12 in size in LUA, with this duplicated in an array in MMF and my memory usage is nowhere near that. Given that my array will never be completely full because empty slots I fill with 0 values, but that shouldnt make a difference? Are you still storing strings or only integers?

Quote:

---

Originally Posted by bigredron

But I dont understand how you are getting such high memory usage when I have a table that is 500x500x12 in size in LUA, with this duplicated in an array in MMF and my memory usage is nowhere near that. Given that my array will never be completely full because empty slots I fill with 0 values, but that shouldnt make a difference? Are you still storing strings or only integers?

---

lua uses sparse tables, so even if you do something like:

table[1] = 1
table[1000000] = 2

it's only going to use space for those two "cells" (although the second will use more than the first because it's thrown into the hash table)

mmf's array object allocates space for whatever you set your XYZ for, whether you're using all of it or not; however, a given cell in mmf will use less memory than one in lua (because lua's have various overheads)

also from what i've seen, mmf's arrays won't show their memory usage in the debugger; you'll have to use task manager to see it (for example a 1000x1000x30 mmf array uses ~120MB)

Yep, use the task manager to see your memory usage.
With my 3 dimensional, 'fill as I go' array[x][y][z] method of filling it with increasing integer indexes, I'm getting about 54 MB base usage on the array, spiking up to 200 MB in the worst case. Predefining a 1000x500x12 one dimensional array in lua took up 300 MB.

Interesting result. I'll have to some further testing myself, since that seems to buck common logic if your worst case scenario is storing the same amount of data as your flat array. Unless your pre-definitions are themselves discarded as garbage, which is possible.

Ah! I will have to check task manager, I have been checking the MMF debugger all this time! I will check it out when I get home and post back with my results. Nevertheless I have learnt a lot from this thread.

EDIT: OK, it seems a 500x500x12 array in LUA uses ~84mb of ram by using map[i][j][k] as my indexes. If I also add a value into an MMF array at the same x,y,z indexes, the total ram usage only goes up to about 100mb. This was figured out by a quick blank frame i just made using some code:

Code:

---

map={}
for i=1,500 do
 map[i]={}
 for j = 1,500 do
  map[i][j]={}
  for k=1,12 do
  map[i][j][k]=0
  DoCall("array",i,j,k)
  end
 end
end

---

So that means that the MMF array only uses about 16mb, compared to Lua which uses 3-4 times that ammount? Would I be better to store my map in one big flat array in LUA by multiplying the 3 indexes into one large integer instead of having 3 seperate indexes?

Nobodies gonna die from 84 MB of RAM usage, though, so its really not worth the hassle for you. Integer stacking is only really worthwhile if your data fulfills two qualities:
A) Its gotta be small numbers; low digits
B) It has to have a definitive size range

So storing 0-128 can be easily stacked, whereas 0-999999 is not worthwhile. Remember that you can stack numbers off any number, not just powers of 10- you could multiply it as: 16384x + 128y + z.

But yes retriever its an odd result, well above the projected amount of memory usage, for a single 'linear' array. If I had to guess, I'd say its possible that the exponential memory allocation is resulting in it allocating far more memory than the array actually needs? Perhaps I'll try it again, forcing garbage collection immediately after instantiating it, and see what happens. But I'm happy with the setup I have now.

Quote:

---

Originally Posted by Pixelthief

Nobodies gonna die from 84 MB of RAM usage, though, so its really not worth the hassle for you. Integer stacking is only really worthwhile if your data fulfills two qualities:
A) Its gotta be small numbers; low digits
B) It has to have a definitive size range

So storing 0-128 can be easily stacked, whereas 0-999999 is not worthwhile. Remember that you can stack numbers off any number, not just powers of 10- you could multiply it as: 16384x + 128y + z.

But yes retriever its an odd result, well above the projected amount of memory usage, for a single 'linear' array. If I had to guess, I'd say its possible that the exponential memory allocation is resulting in it allocating far more memory than the array actually needs? Perhaps I'll try it again, forcing garbage collection immediately after instantiating it, and see what happens. But I'm happy with the setup I have now.

---

Well most of the values are 0-16 range. Some values may be as high as about 4000 which is the reference to images within the background images object. That would be worst case scenario if I have to use that many images.
So stacking numbers would probably be a good idea in my case. I guess I can do a test and see what the difference is.
But either way, its much more than a MMF array. I understand it uses doubles so the memory will always be higher but I didnt realise it was that high.
Overall the RAM usage isnt that bad, but I still have to allow for all the potential images I want, plus character animations, pathfinding, etc I need to watch where I allocate resources to.

http://hocuspocus.taloncrossing.com/rii/fixedarray.zip

That's a link to a C library I just wrote for a generic fixed-size array of different storage types. It can create fixed-size storage for bytes, shorts, longs (ints), floats, or doubles. It stores 1000*500*12 doubles in 45MB, and as many shorts in 11MB. It avoids any problems with garbage collection.

Compared against native lua tables, averaged writes are anywhere between 15% - 400% faster, but reads are generally 50% - 80% slower. The library takes a hit on reads because of the C protocol it needs to return values (and the native table lookups conversely are very optimized).

To use it, add the line:
require "fixedarray"

to your source code, which will put the function "fixedarray" into the global table.

fixedarray can take 1 or 2 parameters. The first is the number of elements to allocate space for, and the second is the data type, which can be either numeric constant 0 - 4, or the strings "byte", "char", "short", "long", "int", "float", or "double". Any invalid type is automatically a double.

Calling fixedarray returns an object table, which contains 4 methods:

- at(index) [returns the value stored at the given index.]
- set(index, value) [saves value to the given index.]
- reset() [a fast operation to reset all elements to 0]
- destroy() [destroys the internal state, frees the memory, and empties the "self" table so you can't accidentally call functions on an invalid array]

Indexes are 1-based. Functions are tolerant of invalid indexes.

Usage example:

Code:

---

require "fixedarray"

data = fixedarray(500, "short")

-- Sets array to sequence 2, 4, 6, 8, ... 1000
for (i = 1, 500) do
  data.set(i * 2)
end

-- Prints sequence 4, 8, 12, 16, ... 40
for (i = 1, 10) do
  print(data.get(i * 2))
end

data.reset()

-- Prints sequence 0, 0, 0, 0, ... 0
for (i = 1, 10) do
  print(data.get(i * 2))
end

-- Prints contents of 'data' variable; 5 elements printed out
for k, v in pairs(data) do
  print(k, v)
end

data.destroy()

-- 'data' variable is now empty; 0 elements printed out
for k, v in pairs(data) do
  print(k, v)
end

---

The methods do not need to use the : operator, but it will tolerate the operator if you use it (just be a tad bit slower).

Oh oh! Thank you very much, that looks like exactly what I needed. You should definitely think about including that with your standard release, it could definitely prove useful to more than just the two of us. One problem- I don't quite understand how Lua's library loading thingy works. How do you load the library in the lua file? I know lua has some funkiness with file directories. Thought I just had to alter package.path to tell it to search the proper directory, but I seem to be having troubles

You could always load it with the appropriate action of the XLua object, and then you'd be able to include it into the exe.

Without modifying your package.path, that DLL would need to be in the same folder as your main exe, although if you stuck it in a subfolder, you should be able to require subfolder.fixedarray. Package loading is a fairly complex topic.

Oh 'doh, didn't see the open c module function. Thanks very much! I'm sure this will really streamline a lot of my work! Yeah trying to read up on how lua package loading worked made my head spin. Maybe a sticky post with compiled open release modules would be a neat addition for this little subforum :D love your work!

Thanks Retreiver I will check it out.
I might do some tests comparing this to a flat array in Lua and see what the differences are and work out if its worthwhile.

Oh and it works like a charm! 42 Megabytes of RAM for the full application, down from 300+ worst case. Thank you very much good sir!