2

Using LibGdx, I recently implemented a grid system(spatial partitioning) to optimize performance for collision detection. I spawned 2000 entities on the board, and had them move around, recalculating their new tile location on the grid, and transferring the entity to the correct Collection whenever necessary.

Problem:

GC_FOR_ALLOC freed 3068K (65765), 45% free 3925K/7124K, paused 36ms, total 36ms

occurs on Android around once a second, causing the rendering to stutter.

Code:

This is run by each entity:

if(newgridy!=currentgridy||newgridx!=currentgridy){ try { my_tile.remove(this); my_tile = grid[newgridy][newgridx]; my_tile.add(this); }catch (ArrayIndexOutOfBoundsException e){ } }

newgridy,newgridx,currentgridy,currentygridx are tile coordinates(not render coords)

my_tile is an ArrayList

grid is a 2D array of ArrayLists

My Attempts:

I know that this is the problematic block of code, because the GC calls go away when I comment it out.

I think that the repetitive remove and add calls results in fragmented memory, and the ArrayList grows too large to fit in any contiguous location in memory, so the GC has to compact when my Entities enter a new tile. I thought I should preallocate space for each tile, but each tile could potentially contain 1000+ ships at once, and sometimes be completely empty. Then I would have to allocate the 1000 to accommodate for when it is full, but then that would be an enormous waste when the tile is empty.

Questions

Is fragmented memory my issue? If so, is there a Collection in Java that can be non-contiguous? Or other ways to fix it?

Would switching to a Quadtree for optimization help?

Sorry for multiple questions and being a bit broad.

Improve this question

1 Answer 1

Reset to default
1

Reading http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.ensureCapacity%28int%29 (which might be the wrong implementation but is probably similar) suggests that it's not fragmentation. Remove just copies data down one space and add only increases memory when neccessary; there aren't fragments. The size is increased a lot on the way up to 1000 through with lots of cast-off arrays for the GC: could that be it?

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

So it's not fragmentation, thanks for clearing that up. What do you mean by cast-off arrays?
I'm not an expert on the details of Java memory management; this is just my best guess on reading the source. What I mean is that first the array is 10 long, then 15, 23, 36, ... items long, multiplying by 1.5 each time, and each array is discarded when it has been used. So, those discarded arrays are what I meant by cast offs.
Oh, alright, that makes sense. So the question for me has become how to have all these collections: 1. Be able to store 0-1000+ values without having to discard an array every time it expands. 2. Be able to have thousands of these collections(for the grid). Should I make a new question or edit this one?
No wait, how would this account for GC freeing 3000k bytes? Since ArrayLists are references, an arrayList of 1000 would be 4kb-ish on a 32 bit system, and 8k on 64 bit, right? And even though what's being freed are the multitudes of cast-offs, it shouldn't add up to that many.
I have no idea. I estimate 2700 x 4 = 10.8 kB per array raised to 1000, so unless you are raising 300 arrays to that size per second I must be wrong. You haven't been calling trimToSize, have you?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.