Vertex array - HUGE memory usage and bad performance

[FRex]

Hmm yeah forgot that sf::VertexArray needlessly duplicates vertices position data... oh well don't use them myself anyways . Using indexed VBOs you could slash so much off that requirement...

But.. OpenGL programming... it's hard like OpenGL
I've never seen anyone color their maps so the glColorPointer call and the 4 bytes from your own specialized sf::Vertex could be scrapped for 20% instant size cut... I think. I don't know OpenGL at all. Most people here(ie. me) probably don't know assembly, OpenGL and c++ at all or as good as you do.

(typically it's not 2 in STL implementations).

GCC and its STL like to troll apparently, not only operator[] does not assert at all(!!), the vector new length is calculated like: size + max(size,1) so it goes from 0 to 1and then keeps doubling... and netrick is on Linux so.. yeah, it's actually exactly 80 mbs allocated for 4 million pushed vertices. It probably could sum up and the virtual memory, minor page faults from stl structures that grow in advance, dlls and so on might make it seem worse: http://www.frogatto.com/?p=3

[Nexus]

To explain why the factor 2 is a particularly bad choice: It represents exactly the threshold that inhibits the usage of previously allocated memory. Growing by a factor of 2 is the worst possible allocation strategy.

Consider the scenario where a vector grows multiple times in a row (no other allocations occur in between).  Typically, there may be a large block of memory, at the beginning of which the vector is placed initially. # denotes an allocated and - an unusable byte.

When the vector grows by a factor of 2, the sum of the previous blocks is always a single byte too small for the new vector. As a consequence, the memory of all of its previous allocations cannot be used again, and the vector wanders continuously forward in memory.

Round     Allocated     Memory Usage
  1.          1         #
  2.          2         -##
  3.          4         ---####
  4.          8         -------########
  5.         16         ---------------################

As a result, a vector of capacity N uses 2N-1 bytes while growing. In the worst case, only slightly more than 50% of the elements are actually used, resulting in an effective usage of 25% of the memory, while 75% are wasted. Even though 50% can be used for future allocations, the growing process itself requires an overly big amount of memory.

The Dinkumware STL implementation of MSVC uses a factor 1.5 and therefore avoids this issue. After 4 allocations, old blocks can be used again.

Round     Allocated     Memory Usage
  1.          1         #
  2.          2         -##
  3.          3         ---###
  4.          4         ------####
  5.          6         ######----

[FRex]

I know , I just forgot gcc uses 2, I knew visuals 1.5.
That's also what folly tried to leverage in its favor: https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md
And then you wonder why people reimplement STL while gcc uses 2x and doesn't check [].
Who knows what other semi-witchcraft code sits in some STL implementation of some compiler.

[netrick]

Is there any good STL implementation out there that I can use with gcc? In some aspects gcc generates really bad code compared to other compilers...

[Silvah]

GCC and its STL like to troll apparently, not only operator[] does not assert at all(!!)

Have you tried enabling the debug mode? If you don't enable it, the debug checks are disabled, obviously.

To explain why the factor 2 is a particularly bad choice: It represents exactly the threshold that inhibits the usage of previously allocated memory. Growing by a factor of 2 is the worst possible allocation strategy.

It's a tradeoff. Factor of 1.5 copies more often, factor of 2 wastes more memory.

Of course, if you think that a factor of 2 is egregiously bad, you should file a bug in libstdc++. Still, the developers are aware of potential drawbacks, but they have some evidence that for real world code factor of 2 is faster.

At any rate, if you think that a smaller factor will benefit your case, you can implement it. if(vector.size() + itemsToAdd > vector.capacity()) vector.reserve(getNewCapacity(vector.capacity(), itemsToAdd)); is not exactly rocket science. And while reserve guarantees merely that capacity >= N, not capacity == N, on most if not all real implementations it'll grow to N.

[FRex]

The debug mode is 'enabled' as in NDEBUG is not defined so asserts happen.
It's 'disabled' as in _GLIBCXX_DEBUG is not defined and without it glibc++ doesn't have even asserts in vector.
And _GLIBCXX_DEBUG is "Undefined by default" (because it might mess up badly if a stl class is passed between units that are not both compiled with same debug switch because the sizes of stl classes change in debug) so there's a nasty surprise waiting to happen.

[netrick]

Going back to orginal topic, now I make a new vertex array from visible tiles every frame. I get constant 800fps and very low memory usage even when map is 1000 x 1000 tiles (40mb in that case).

[Ancurio]

Hmm yeah forgot that sf::VertexArray needlessly duplicates vertices position data... oh well don't use them myself anyways . Using indexed VBOs you could slash so much off that requirement...

Can you explain to me where these redundant vertices could be slashed off? Having recently implemented a tmx loader in openGL using indexed VBOs, I came to the conclusion that it's not really very viable, because the only cullable vertices would be those where two adjacent tiles on the screen were also adjacent in the tileset, in which case you'd safe 2 vertices per occurance, which IMO doesn't happen that often (as compared to eg. the same ground tile repeated over huge parts of the map).

Also, on the topic of the wasted std::vector memory: If the amount of vertices per tile and the amount of tiles is known before hand, why not just call vector.reserve(count) at the beginning (avoiding all reallocations) and avoid the waster memory?

[binary1248]

Can you explain to me where these redundant vertices could be slashed off? Having recently implemented a tmx loader in openGL using indexed VBOs, I came to the conclusion that it's not really very viable, because the only cullable vertices would be those where two adjacent tiles on the screen were also adjacent in the tileset, in which case you'd safe 2 vertices per occurance, which IMO doesn't happen that often (as compared to eg. the same ground tile repeated over huge parts of the map).

The idea is that you use indexing, yes... but you don't advance all attributes at the same pace, i.e. glVertexAttribDivisor. As you probably noticed, there is no way of going around newer OpenGL if you want all the performance you can get . If you use your own VBO for tile rendering you can already drop the redundant color data (-20%). If you are really crazy, you could write your own shader to render the tiles with minimal data. Think about it, you are just iterating through a grid and changing the texture that is applied to each quad along the way. You don't have to provide much besides basic information about the grid structure and the type data at each tile. Haven't done this myself, however it seems theoretically possible (maybe something I might try when I get really bored ).

Also, on the topic of the wasted std::vector memory: If the amount of vertices per tile and the amount of tiles is known before hand, why not just call vector.reserve(count) at the beginning (avoiding all reallocations) and avoid the waster memory?

You can do this already by using sf::VertexArray::reserve() and just indexing the data instead of constantly appending, or even better just specifying at construction how large the sf::VertexArray should be, however many beginners haven't had the privilege of being part of this discussion yet .

[Ancurio]

The idea is that you use indexing, yes... but you don't advance all attributes at the same pace, i.e. glVertexAttribDivisor. As you probably noticed, there is no way of going around newer OpenGL if you want all the performance you can get . If you use your own VBO for tile rendering you can already drop the redundant color data (-20%). If you are really crazy, you could write your own shader to render the tiles with minimal data. Think about it, you are just iterating through a grid and changing the texture that is applied to each quad along the way. You don't have to provide much besides basic information about the grid structure and the type data at each tile. Haven't done this myself, however it seems theoretically possible (maybe something I might try when I get really bored ).

Ah... Yes, yes, I see. You would provide the raw tile index data, set the attrib divisor to 4 so packs of 4 vertices describing one tile/quad get the same tile index (or is it based on indices, ie. 6 because 6 indices per tile?), and the rest of all the vertex pos and texpos data could be generated on the fly based on the provided vertex id in the shader. For a map with eg. 100x100 tiles, you would only specify a 100x100 big ushort buffer and that's all.

That would be an interesting space/computation trade off (you'd be calculating the same exact data 60 times per second), but for huge maps it might indeed help with memory concerns. Interesting.

[FRex]

If you are really crazy, you could write your own shader to render the tiles with minimal data. Think about it, you are just iterating through a grid and changing the texture that is applied to each quad along the way. You don't have to provide much besides basic information about the grid structure and the type data at each tile. Haven't done this myself, however it seems theoretically possible (maybe something I might try when I get really bored ).

Like Dbug's shader that I improved or even more minimal?

[binary1248]

What... there was someone who already did it? Man... now what will I do when I get bored ... I had a look, it looks pretty minimal. Doubt I can beat that without a few months worth of thinking .

[FRex]

I had a look, it looks pretty minimal. Doubt I can beat that without a few months worth of thinking .

I feel flattered, I probably shouldn't because I written it based on dbug's comments and code but I do.

Man... now what will I do when I get bored ...

SFGU.. I dunno, hex or isometric tile shader?