Single Array or Multi Array for Tiles?
Author
I've tried both ways of drawing tiles and I didn't really notice any difference. I did read up on how single arrays are faster to draw. I've setup my Editor to draw like that but it required a ton of code because you need to draw for every row. I know that multidimensional arrays are easier to draw because you just do it once for x and y, however is there any real advantage for me drawing from single arrays instead?
I am not totally sure why (or how) 1D would be "faster to draw", but would the possible slight speed increase be worth the added complexity? The answer is more than likely no, so I would just use a 2D array...
I found that an array of array is easier to manage. In C# here's how I handle tiles :
/// <summary> /// Contain all the tile of the layer /// </summary> List<List<int>> Tiles;
A 1D array is going to be much better for memory access.
1) a 2d array means accessing an element is pointer->pointer->value
a 1D array is pointer->value
over items that you are going to want access to all the time(drawing, pathing, line of sight) the one less level of indirection is paramount (this is the same reason many consoles warn against virtual functions, the pointer->pointer-> lookup can be very slow, not to mention they are bad on the instruction cache of some consoles)
2) Why can it be really slow? 1, the memory is not coherent so it means reading two very non-local blocks of memory, and that means one may be in the cache while the other isn't. and it also means that one may be in the cache and the lookup of the other evicts the first one, so you thrash the cache as you swap back and forth between the two sets of pointers.
The 1D array is going to be much nicer on your memory fragmentation as it is ONE block instead of many small blocks.
I have no idea what you mean here.
Assuming C++.
Sorry, I'm not a C# guy. But in C++ a std::list<> is a linked list.
A linked list makes no sense for a map unless you constantly stream in tiles along the edges or something. The random access is going to be terrible, the cache locality is terrible, and thus it is going to be far slower than an array.
[Edited by - KulSeran on January 14, 2009 3:26:43 AM]
1) a 2d array means accessing an element is pointer->pointer->value
a 1D array is pointer->value
over items that you are going to want access to all the time(drawing, pathing, line of sight) the one less level of indirection is paramount (this is the same reason many consoles warn against virtual functions, the pointer->pointer-> lookup can be very slow, not to mention they are bad on the instruction cache of some consoles)
2) Why can it be really slow? 1, the memory is not coherent so it means reading two very non-local blocks of memory, and that means one may be in the cache while the other isn't. and it also means that one may be in the cache and the lookup of the other evicts the first one, so you thrash the cache as you swap back and forth between the two sets of pointers.
The 1D array is going to be much nicer on your memory fragmentation as it is ONE block instead of many small blocks.
Quote:I've setup my Editor to draw like that but it required a ton of code because you need to draw for every row.
I have no idea what you mean here.
Assuming C++.
std::vector<Tile> mapTiles;mapTiles.resize(height * width);for ( int y = 0; y < height; ++y ){ for ( int x = 0; x < width; ++x ) { mapTiles[ x + y*width ].Draw(); }}// ORfor ( std::vector<Tile>::iterator i = mapTiles.begin(); i != mapTiles.end(); ++i ){i->Draw();}Quote:
List<List<int>> Tiles;
Sorry, I'm not a C# guy. But in C++ a std::list<> is a linked list.
A linked list makes no sense for a map unless you constantly stream in tiles along the edges or something. The random access is going to be terrible, the cache locality is terrible, and thus it is going to be far slower than an array.
[Edited by - KulSeran on January 14, 2009 3:26:43 AM]
Quote:Original post by KulSeranIn C#, a list is a container with constant-time random access.
Sorry, I'm not a C# guy. But in C++ a std::list<> is a linked list.
A linked list makes no sense for a map unless you constantly stream in tiles along the edges or something. The random access is going to be terrible, the cache locality is terrible, and thus it is going to be far slower than an array.
Quote:Original post by KulSeran
A 1D array is going to be much better for memory access.
1) a 2d array means accessing an element is pointer->pointer->value
a 1D array is pointer->value
It depends if your array is jagged or not. A regular old statically-allocated 2D array should perform identically to a 1D array, except the compiler will handle the pointer arithmetic for you.
But for arrays-of-arrays, yes, that might make a difference.
In C++, use boost::multi_array. It provides resizable storage with all the semantics you'd expect for a multidimensional array, but also stores elements in a single contiguous block (the same as a statically sized primitive multidimensional array) and thus allows for efficient iteration.
Author
I should of made it clear in my post. I'm not using C#, I'm using C++.
How I drew for every row was easy. Just too much code to write.
KulSeran, I would make an Array for each row of my map, then draw on after another. They would all start at the same x value, I would just have to change the y value +32 for each row.
Thanks for all of the replies.
How I drew for every row was easy. Just too much code to write.
KulSeran, I would make an Array for each row of my map, then draw on after another. They would all start at the same x value, I would just have to change the y value +32 for each row.
Thanks for all of the replies.
Do you have any data that demonstrates that using this approach actually yields better results?
Im kinda skeptic because such task should be easy to handle for today cpu's and you will benefit from cleaner code than from minimal perf gains
Im kinda skeptic because such task should be easy to handle for today cpu's and you will benefit from cleaner code than from minimal perf gains
Author
Quote:Original post by EvilNando
Do you have any data that demonstrates that using this approach actually yields better results?
Im kinda skeptic because such task should be easy to handle for today cpu's and you will benefit from cleaner code than from minimal perf gains
I didn't make any claim that it runs faster. I was asking if any knew.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
