Jump to content
  • Advertisement
Sign in to follow this  
noodleBowl

C++ Vectors: Sorting and removing specific items

Recommended Posts

Just now, Hodgman said:

Don't remove things from the list. Throw the whole thing away after you've rendered it and build a new list from scratch next frame. 

Yeah, I wondered why the fascination with removing, then I thought maybe it's an occlusion culling pass after first adding everything in the frustum or something. (Personally I'd tackle that by using my occlusion cull to filter the first vector and add things that are not occluded to a new collection, but if @noodleBowl has a need to remove things from the vector then my advice is just do it and worry about performance if it's too slow.)

Share this post


Link to post
Share on other sites
Advertisement
1 hour ago, noodleBowl said:

Definitely there are trade offs everywhere. Originally I was thinking a map, because I could remove items really fast. But then (i'm pretty sure) that means I loose out on my sorting. Unless I do something crazy like copy the map into a vector. But doing that every frame sounds pretty bad.

std::map is sorted by key, however you would only use this if you need a sorted associative container (which you don't).

1 hour ago, noodleBowl said:

Not really sure why shifting a spot is such a hit to performance though

It's not that it's a hit to performance per se (especially if the items in the vector have move semantics), but rather that in certain cases you can avoid the shift completely, so why bother doing it?

24 minutes ago, Hodgman said:

Don't remove things from the list. Throw the whole thing away after you've rendered it and build a new list from scratch next frame. 

Agreed. And if you just clear the vector, you'll be able to re-use the memory too.

Share this post


Link to post
Share on other sites
21 hours ago, Hodgman said:

Don't remove things from the list. Throw the whole thing away after you've rendered it and build a new list from scratch next frame. 

Not to hijack this thread (hopefully this contributes to the discussion topic), but is that generally always the best option? I'm using a very similar system to OP (vector<Renderable*>), and sorting using insertion sort on every push_back() to enforce draw order. I thought about discarding and re-populating renderables every frame, but I assumed the cost of sorting the entire array every frame was much more expensive than insertion sort on insert + std::erase(std::remove_if()) on removal. I guess I'll just have to run some performance tests and see for myself.

Share this post


Link to post
Share on other sites
3 minutes ago, cmac said:

Not to hijack this thread (hopefully this contributes to the discussion topic), but is that generally always the best option? I'm using a very similar system to OP (vector<Renderable*>), and sorting using insertion sort on every push_back() to enforce draw order. I thought about discarding and re-populating renderables every frame, but I assumed the cost of sorting the entire array every frame was much more expensive than insertion sort on insert + std::erase(std::remove_if()) on removal. I guess I'll just have to run some performance tests and see for myself.

The performance differences will depend on your game and how many objects get created and destroyed all the time, as well as how much your camera moves.

In my engine I do exactly what @Hodgman says, I just build up the draw list from scratch each frame for each camera that renders.  Then I sort.  I dont assume that my draw list will stay mostly the same, in fact I optimize that stuff for worst cases, because those are the cases where you need most performance.  So I assume that the camera will be moving around and that there's a lot of stuff happening, i.e. a lot of objects being created and destroyed... which means that per-camera draw list will be changing a lot.

BTW I also keep my components in contiguous arrays, so iterating through all mesh components (for example) isnt so bad because the caches and prefetcher will help you out.  If you have stuff all over memory, with your rendering data intermingled with other stuff... then the performance will suffer.

Share this post


Link to post
Share on other sites
1 hour ago, cmac said:

but I assumed the cost of sorting the entire array every frame was much more expensive than insertion sort on insert + std::erase(std::remove_if()) on removal. I guess I'll just have to run some performance tests and see for myself.

This is what I was thinking! But I guess this makes sense if you are doing a lot of creating and destroying like @0r0d mentions

1 hour ago, 0r0d said:

BTW I also keep my components in contiguous arrays, so iterating through all mesh components (for example) isnt so bad because the caches and prefetcher will help you out.  If you have stuff all over memory, with your rendering data intermingled with other stuff... then the performance will suffer.

Can you elaborate more on this? The part about If you have stuff all over memory, with your rendering data intermingled with other stuff

Example if I have a set up roughly like this does this mean everything is all over?

//Vector of renderables. This is the list we will actually look at and traverse when rendering
cubeRenderable    | { pointerToShader: shapeShader, pointerToTexture: NULL }
truckRenderable   | { pointerToShader: truckShader, pointerToTexture: truckTexture }
enemyRenderable   | { pointerToShader: enemyShader, pointerToTexture: enemyTexture }
boatRenderable    | { pointerToShader: boatShader, pointerToTexture: boatTexture }

//Vector of created shaders. Used to keep track of the shaderes that have been created. Exists in a ShaderManager class
shapeShader | { comPointerVertexShader: 1, comPointerPixelShader: 2 }
truckShader | { comPointerVertexShader: 3, comPointerPixelShader: 4 }
enemyShader | { comPointerVertexShader: 5, comPointerPixelShader: 6 }
boatShader  | { comPointerVertexShader: 7, comPointerPixelShader: 8 }

//Vector of loaded textures. Used to keep track of the textures that have been created. Exists in a TextureManager class
truckTexture | { width: 64, height: 64, comPointer: 9 }
enemyTexture | { width: 64, height: 64, comPointer: 10 }
boatTexture  | { width: 64, height: 64, comPointer: 11 }

I kind of feel like it does, but I'm not really sure cause of the pointers and well I have never really taken a hard look at how memory management/cache works

Edited by noodleBowl

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!