   Extreme slowdown when indexing into Vectors
  So currently I'm working on a simple 2D scrolling shooter in DirectX. I just have the very very early beginnings of it. A plane moves around the screen and I'm currently trying to finish off the map system.It seems such a simple program compared to an "actual" game that I couldn't help get completely thrown when my FPS went from around 65-75 to under 10 after putting in 4 statements to index into vectors.To store my map, I have a Tile class and a vector of Tile* vectors to represent the rows and columns. The Tile contains x, y coords and the usual basic things. To draw the tiles onto the screen I put in:tileMap.at(y).at(x)->getX()etc. but immediately the framerate about halves with just 1 of them. It's definitely just those statements because I put them there on their own and it happened as well.I know it's happening many times per second since it's part of the function to draw to the screen, but that's not normal behaviour is it? It's still a very small program and I thought vectors were good for indexing in like that?I'm finding it hard to believe this program could be bringing my computer down like that and I've been suspecting my game loop may be involved but it doesn't appear to be as far as I can see and it doesn't seem like that would make sense anyway. Viewing the load of my CPU's cores on CoreTemp doesn't show any significant difference between using those statements and not. So I'm trying to look for any other factor that might somehow be causing this.What's going wrong? Do vectors start costing terribly when they're 2 dimensional?UPDATE: I tried using the [] operator instead of at() and I found the whole problem just disappears. Why is that? Should you almost always use [] if you're doing repetitive operations?[Edited by - Sean_Seanston on June 11, 2009 1:35:54 PM]
  Vectors are a series of elements and are not necessarily placed sequential in memory. Therefore accessing via index is not simply a offset from start address.I would use fixed size arrays so you could index as arr[j].EDIT see:http://www.cppreference.com/wiki/stl/vector/atand:http://www.cppreference.com/wiki/stl/vector/vector_operatorsSays operator[] returns in constant time, I didn't know that my self :);Quote:Original post by Sean_SeanstonUPDATE: I tried using the [] operator instead of at() and I found the whole problem just disappears. Why is that? Should you almost always use [] if you're doing repetitive operations?at is range checked. [] is not. You should always use [] if you need performance and don't need range checking.   ;Quote:Original post by AnnoyedVectors are a series of elements and are not necessarily placed sequential in memory. That's not right; the standard states they must be contiguous in memory. Effectively Vector is a wrapper around an array, it's just a safer wrapper which manages it's own memory. In 99.9% of cases there isn't a good reason not to use it.When accessing a Vector via [] there is no speed penalty when compared to arrays (MS's secure Std. Lib not withstanding).The problem the OP is hitting is that .at() does bound checking on the vector so that if you go outside of it it will throw an exception. operator []() on the other hand doesn't do this range check (MS's does by default if you have the secure Std. lib active however).So;.at() is safer but sloweroperator[]() is faster but you can go beyond the array bounds if you aren't careful.   ;Quote:Original post by phantomQuote:Original post by AnnoyedVectors are a series of elements and are not necessarily placed sequential in memory. That's not right; the standard states they must be contiguous in memory.Whoops! that's the second time I've been told that >.<;  Right... cool.I'd always just assumed that since at() also works in constant time it was just as fast as [] and that [] was just some kind of shortcut.Still, scary how much of a difference it makes :/   ;Quote:Original post by Sean_SeanstonRight... cool.I'd always just assumed that since at() also works in constant time it was just as fast as [] and that [] was just some kind of shortcut.Still, scary how much of a difference it makes :/Nope, at() is bounds checked, while [] is not. More importantly, constant time is just a rough bounds for it. Do remember that the big-O timing ignores constants. So an O(1) can be fast or slow, just consistently so.   ;Quote:Original post by WashuQuote:Original post by Sean_SeanstonRight... cool.I'd always just assumed that since at() also works in constant time it was just as fast as [] and that [] was just some kind of shortcut.Still, scary how much of a difference it makes :/Nope, at() is bounds checked, while [] is not. More importantly, constant time is just a rough bounds for it. Do remember that the big-O timing ignores constants. So an O(1) can be fast or slow, just consistently so.To expand on that, constant time means that it takes roughly the same amount of time to access any element in the vector no matter how many elements there are total (cache misses and related issues notwithstanding).   ;  Although vectors in the vector-of-vectors are stored contiguously, and elements of each of the "row" vectors are contiguous, the elements are still not necessarily all in a contiguous block. Each "row" vector maintains its own dynamic allocation, which is at its own, not-necessarily-related location in memory.If your "grid" has an unknown size in both dimensions, but is always rectangular, use boost::multi_array instead.   