C++ timers

[degibson]

Originally posted by: stevf
one of the sorts I perform in this test is a merge sort based on an unordered list. The sort and list code was provided to me but it certainly is nothing special. That sort is slightly faster that the quick sort on an array. The data sorted is the same for each run as I loop through all the sorts 10 times and use the value of my loop counter for the seed. It is just the STL list that is horrible. I am going to try a few other things from the STL and see what happens. I have done far more than the assignment requires already but I am having fun throwing extra things in there and seeing what happens


Also, any suggestions for more tests? I was required to do a bubble, insertion, selection, quick, and merge using the code that was provided. I have added a gnome sort (just because of the silly name) and the STL sort. Was going to cast one set to double and run that through one or two of the sorts to see if that makes a difference. May add radix to it too. These should often be worst case scenarios as the data is random

If the values you are sorting are integers, try Radix sort.

As far as more experiments, consider trying each of your sorting algorithms with and without compiler optimizations.

Speaking of compiler optimizations, STL sort() would be slow if the comparison operator isn't inlined -- make sure it is declared in a header file somewhere as 'inline' and ensure that your compiler is properly inlining the call.

 

[stevf]

thanks for the suggestions - will try a few of them out. One question though. How do I inline something from the STL? Is it as simple as overloading the operator to make it inline?


Thanks

 

[Sc4freak]

Short answer is that you don't. The "inline" keyword is only a suggestion. Your compiler is free to ignore it. MSVC has the "__forceinline" keyword, which is a slightly stronger suggestion, but the compiler is still free to ignore it.

But I'd say that any compiler with half a brain will automatically inline trivial functions like a comparison operator. If you enable global optimisations, the compiler will be able to perform cross-module inlining so you don't need to fiddle about with header files. In a lot of cases, the compiler will have better judgement than you do.

 

[stevf]

thanks - that is what I thought - the compiler ignores inline whenever it feels like it

 

[degibson]

Originally posted by: Sc4freak
Short answer is that you don't. The "inline" keyword is only a suggestion. Your compiler is free to ignore it. MSVC has the "__forceinline" keyword, which is a slightly stronger suggestion, but the compiler is still free to ignore it.

But I'd say that any compiler with half a brain will automatically inline trivial functions like a comparison operator. If you enable global optimisations, the compiler will be able to perform cross-module inlining so you don't need to fiddle about with header files. In a lot of cases, the compiler will have better judgement than you do.

Like everything, this depends on the compiler. I predominately use gcc, so I know its inlining preferences well. The trick to get GCC to inline is to make sure you're on -O2 or better, and define the entire function in a header file -- don't expect GCC to inline a function from myFile1.C into myFile2.C.