Storing and sorting objects on my engine
I imagine that the list sort algorithm is merge sort which will also be O(n lg n) complexity for best/avg/worst.
If I was writing an engine or game in "native" C/C++, I would write my own memory manager. It can be very difficult and time-consuming to do, much less, do right...but it can offer some significant advantages. The default CRT memory manager isn't really made for games, mind you. Games often make tons of allocations and deallocations in rapid succession; many of them very "lean" objects. The default memory manager isn't really designed for that sort of thing. Fragmentation can muck up your memory playground and it can be darned slow. If your game isn't really memory intensive, then this may not be worth the time. But if your game is big, bad and needs every tick of performance and needs to be memory efficient to the byte, then you should consider rolling your own memory manager.
The basic idea is you allocate a large, but appropriately sized, block of contiguous memory right at the start. Through using "smart pointers" or your own self-invented reference system, your memory manager can even provide garbage collection and heap compaction (though compacting the heap and moving objects can be problematic; because what if you have to expand and/or move everything the next frame after compacting?). You can take advantage of "placement-new" in C++, or provide your own "malloc/calloc-like" functions to place objects into your managed heap. There are lots of different ways to go with it, and the only "right" way would be the way that works the most efficiently for your needs.
I'm not sure what sort of performance/memory demands your project makes, so you'll be the one to make the evaluation. But if I wasn't using C#, which has a built-in memory manager and garbage collector, I'd implement my own in my engine. I wrote a simple one in C++ a while back for a different type of project, and it was successful within the scope of my needs.
P.S. - What is up with the forums posting "C" instead of the symbolic C-plussign-plusign for the language called "C-PlusPlus"? Everywhere I typed it it put just "C" instead of C with two plus signs's.
The basic idea is you allocate a large, but appropriately sized, block of contiguous memory right at the start. Through using "smart pointers" or your own self-invented reference system, your memory manager can even provide garbage collection and heap compaction (though compacting the heap and moving objects can be problematic; because what if you have to expand and/or move everything the next frame after compacting?). You can take advantage of "placement-new" in C++, or provide your own "malloc/calloc-like" functions to place objects into your managed heap. There are lots of different ways to go with it, and the only "right" way would be the way that works the most efficiently for your needs.
I'm not sure what sort of performance/memory demands your project makes, so you'll be the one to make the evaluation. But if I wasn't using C#, which has a built-in memory manager and garbage collector, I'd implement my own in my engine. I wrote a simple one in C++ a while back for a different type of project, and it was successful within the scope of my needs.
P.S. - What is up with the forums posting "C" instead of the symbolic C-plussign-plusign for the language called "C-PlusPlus"? Everywhere I typed it it put just "C" instead of C with two plus signs's.
Quote:Original post by bregaSorry brega, I had a look at the code but there's a thing I have difficulties in getting. Is this the time to sort NumObjects = 5000; elements? When you say retail build, you mean that the time becomes list(.14s) and vector (.6s) (2.5 ratio or 2.5 reduction over debug)?list sort time: 0.300784svector sort time: 0.126097s
EDIT: this results are from Debug build, with Release (Full Optimization /Ox
and Favore Fast code /Ot) i got similar result where vector is almost 2.5x faster.
@Krohm
This is the number of elements.
I meant that sorting vector is about 2.5 times faster then sorting list
in my test be it release or debug .
Release build:
Debug build:
Quote:
Is this the time to sort NumObjects = 5000; elements?
This is the number of elements.
Quote:
When you say retail build, you mean that the time becomes list(.14s) and vector (.6s) (2.5 ratio or 2.5 reduction over debug)?
I meant that sorting vector is about 2.5 times faster then sorting list
in my test be it release or debug .
Release build:
list sort time: 0.00170832svector sort time: 0.000696737sDebug build:
list sort time: 0.292196svector sort time: 0.124949s
Damn, I seriously wished sorting 5000 elements would take far less nowadays... thankfully it's seldom needed for me.
You might consider profiling the sort just to see if anything funky is going on. I never tracked it down, but I did a sort on a vector once and found that it was doing a massive number of allocations during the sort, which was hugely unexpected. I switch algorithms implementations and got a handy speed up.
If you're doing a sqrt when calculating the distances, and if you're not using the distances for anything else, you can save some cycles by not doing the sqrt. The order will work out the same anyway.
Yes, this. In Windows you can just use VirtualAlloc to reserve about half a gig or a gig, and pull down from it as required (committing 64 k chunks at a time). No fragmentation, everything contiguous, a one-time only initial overhead, almost immune to "lots of small allocations" syndrome, and easy as pie to wipe all allocations without having to worry about leaks. You miss a lot of the nicer STL functionality, but much of it is replacable by CRT functions (qsort instead of std::sort, for example). It's not a silver bullet and you still need to do some management yourself, but for the type of allocation it's suited to, it's hard to beat.
I'm sure that there are Linux/OSX equivalents but I don't know them.
Quote:Original post by keinmann
If I was writing an engine or game in "native" C/C++, I would write my own memory manager. It can be very difficult and time-consuming to do, much less, do right...but it can offer some significant advantages. The default CRT memory manager isn't really made for games, mind you. Games often make tons of allocations and deallocations in rapid succession; many of them very "lean" objects. The default memory manager isn't really designed for that sort of thing. Fragmentation can muck up your memory playground and it can be darned slow. If your game isn't really memory intensive, then this may not be worth the time. But if your game is big, bad and needs every tick of performance and needs to be memory efficient to the byte, then you should consider rolling your own memory manager.
The basic idea is you allocate a large, but appropriately sized, block of contiguous memory right at the start. Through using "smart pointers" or your own self-invented reference system, your memory manager can even provide garbage collection and heap compaction (though compacting the heap and moving objects can be problematic; because what if you have to expand and/or move everything the next frame after compacting?). You can take advantage of "placement-new" in C++, or provide your own "malloc/calloc-like" functions to place objects into your managed heap. There are lots of different ways to go with it, and the only "right" way would be the way that works the most efficiently for your needs.
Yes, this. In Windows you can just use VirtualAlloc to reserve about half a gig or a gig, and pull down from it as required (committing 64 k chunks at a time). No fragmentation, everything contiguous, a one-time only initial overhead, almost immune to "lots of small allocations" syndrome, and easy as pie to wipe all allocations without having to worry about leaks. You miss a lot of the nicer STL functionality, but much of it is replacable by CRT functions (qsort instead of std::sort, for example). It's not a silver bullet and you still need to do some management yourself, but for the type of allocation it's suited to, it's hard to beat.
I'm sure that there are Linux/OSX equivalents but I don't know them.
I have another question.
Lets imagine that total number of object in scene is 5000 (like i used in my previous post). I don't need to sort all of them but just ones that are "visible" by "player" camera. Then (i imagine) i need two vectors, one witch holds all objects in the scenes/level and second that holds objects that should be rendered. So i need to fill second vector with that objects and then sort it. How do you people manage this problem?
EDIT: "fill" is the wrong word. i need second vector to store just pointers that point to objects in first vector that should be rendered.
[Edited by - brega on October 16, 2010 5:47:55 PM]
Lets imagine that total number of object in scene is 5000 (like i used in my previous post). I don't need to sort all of them but just ones that are "visible" by "player" camera. Then (i imagine) i need two vectors, one witch holds all objects in the scenes/level and second that holds objects that should be rendered. So i need to fill second vector with that objects and then sort it. How do you people manage this problem?
EDIT: "fill" is the wrong word. i need second vector to store just pointers that point to objects in first vector that should be rendered.
[Edited by - brega on October 16, 2010 5:47:55 PM]
You really can get the best of both worlds by writing your own allocator and then using it in conjunction with the STL containers. It's not even that difficult. It also allows you to customize smaller memory pools for different needs so that any one collection can remain contiguous for all elements.
To be honest, if sorting is your bottleneck then you're either doing something very badly wrong in your sort routine or doing something incredibly miraculously right everywhere else.
You might find that just sorting them all anyway and skipping over the ones you don't want to render has less overhead than using a second list.
You might find that just sorting them all anyway and skipping over the ones you don't want to render has less overhead than using a second list.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
