Adding std::stable_sort to Torque

#1 Did you profile before trying to optimize? I too abhor qsort and would prefer having it replaced by std::sort and std::stable_sort (according to the specific need). However, my preliminary profile tests show that very little time is lost doing sorting so I gave up trying to optimize that. Anyway, I have bad news for you: if you wrap std::stable_sort you won't get any significant improvement! The performance boost of stable_sort over qsort comes from the fact that the former inlines the comparison function, while the latter have to call it through a pointer to function. So in order to get any gain you must replace every single use of dQsort with a direct call to stable_sort and possibly rewrite the comparison function into a functor. Seems a lot of work to me!
About using STL, I use it regularly. There is a resource that shows how to do that, although I found it unsatisfactory and so I came up with a different approach.

#2 Wow... you've made a giant leap of assumption here. Not sure why, but you seem to think i'm after std::stable_sort for performance reasons... that is not the case at all.

A stable sort in CS terms maintains the relative order of items with equal comparisons. I need this to avoid some flickering between equally distant overlapping items i'm rendering in TGB. If anything a stable sort will be equal or slower in performance to a standard quicksort.

The reason for a wrapper around it is to specifically avoid injecting any STL into Torque. This wrapper should have a similar interface as dQsort() to keep things consistent in the API and almost make the algorithms interchangeable.

Maybe this clears up my original question.

#3 Yes, that greatly clarifies the context.

What I did, mainly, is the following: in file platorm.h, just before the declaration of the Memory namespace, add this code:

#include <new>
#include <memory>
#ifdef _MSC_VER
#include <xdebug>
#endif

then remove from file winMemory.cc the definition of the function

void* FN_CDECL operator new(dsize_t, void* ptr)

That's it. In my code I also added Torque debug support for new/delete, in a way similar (but not identical) to the resource I quoted above, but you should not need that if all you use of the STL is stable_sort.

#4 Here's a few links that might help you, Tom. At least they helped me.

Torque Memory Manager
STL and the TGE memory manager
Link errors when using std::string

#5 @Alberto - This seems like a very simple change. How does it effect the function of the Torque memory manager?

#6 We have been running tests at work with TSE. Disabling the TMM yields small performance benefits in some situtations, but for some reason the profiler goes wacky. We ended up using the TMM for our internal builds and disabling it for Release builds.

Reading the threads I posted gives some more details on the issue about the Profiler.

Edit: Grammar.

#7 @Tom: it doesn't affect the TMM at all. Simply all memory allocated by an STL container or algorithm won't be allocated through the TMM, while the engine will keep using the TMM. That other "half" of the change that I have omitted for brevity lets the STL use the TMM also, but in both cases the TMM is left unmodified.

#8 Humm... thanks for the responses guys. I have to agree with Mark in the other threads that having two memory managers hanging around is generally a bad thing.

This is all too much change for just a simple stable sort... I'm just going to implement my own. ;)

#9 @Tom: I don't understand your concern. With my approach (well, with my "full" approach, composed of what I posted here plus the "half" I omitted) you will end up using only one memory manager, that is Torque's. If you use just what I post here, you would still be playing quite safe, though. The only problem is that stable_sort is one of the very few STL algorithms that requires extra memory, but you can safely assume that whatever stable_sort allocates is also freed upon exit from the algorithm, so in the end you don't really have to worry about it.
Just my opinion.

#10 @Alberto - The problem is what i'm working on will (most likely) be added to the official code base. Using an STL algorithm was a borderline change, but using a second memory manager... even if it was temporarily... is enough of a downside that i consider rolling my own stable sort a better alternative.