Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


#ActualCornstalks

Posted 17 May 2013 - 07:06 PM

The standard does not state what algorithm must be used for either std::sort or std::list::sort. It does say, however, that both must complete in O(nlogn) (on average; I'm unsure if the standard states their maximum complexity on worst case execution). From what I've heard, std::sort typically uses intro-sort (which is O(nlogn) in both the average and worst cases). std::list::sort often uses mergesort. Implementations might do some clever modifications to these general algorithms, though, so they may not just be straight implementations of well known algorithms.

 

There are several things that might contribute to your big discrepancy:

  • Bad compiler options for timing code. If you didn't test "release" code (and instead tested "debug" code), the standard containers might be doing a lot of error checking and validating of iterators. Also, you should consider turning on your compiler's optimization flags so it doesn't generate "dumb" machine code (but if it's too smart, it could optimize too much of your code away and make your timings meaningless).
  • Cache misses. This one can be huge, and it's hard to say exactly when and if it's occurring. Tools like valgrind (if you're not on Windows) can help detect cache misses. std::list doesn't necessarily store the elements in a contiguous array, which could result in some extra cache misses (and in terms of CPU cycles, a cache miss is a big slow down).
  • Usage of std::clock(). std::clock() does not measure "wall clock" time (i.e. what your watch says). It measures "CPU time," which is completely different. While it should work in theory (the difference of two std::clock() calls is supposedly meaningful, compared to the actual value of an individual call), it's not the best way to really profile your code (CPU sampling with a proper profiler (like Visual Studio's) is far more effective).

#2Cornstalks

Posted 17 May 2013 - 07:04 PM

The standard does not state what algorithm must be used for either std::sort or std::list::sort. It does say, however, that both must complete in O(nlogn) (on average; I'm unsure if the standard states their maximum complexity on worst case execution). From what I've heard, std::sort typically uses intro-sort (which is O(nlogn) in both the average and worst cases). std::list::sort often uses mergesort. Implementations might do some clever modifications to these general algorithms, though, so they may not just be straight implementations of well known algorithms.

 

There are several things that might contribute to your big discrepancy:

  • Bad compiler options for timing code. If you didn't test "release" code (and instead tested "debug" code), the standard containers might be doing a lot of error checking, validating iterators. Also, you should consider turning on your compiler's optimization flags so it doesn't generate "dumb" machine code (but if it's too smart, it could optimize too much of your code away and make your timings meaningless).
  • Cache misses. This one can be huge, and it's hard to say exactly when and if it's occurring. Tools like valgrind (if you're not on Windows) can help detect cache misses. std::list doesn't necessarily store the elements in a contiguous array, which could result in some extra cache misses (and in terms of CPU cycles, a cache miss is a big slow down).
  • Usage of std::clock(). std::clock() does not measure "wall clock" time (i.e. what your watch says). It measures "CPU time," which is completely different. While it should work in theory (the difference of two std::clock() calls is supposedly meaningful, compared to the actual value of an individual call), it's not the best way to really profile your code (CPU sampling with a proper profiler (like Visual Studio's) is far more effective).

#1Cornstalks

Posted 17 May 2013 - 06:59 PM

The standard does not state what algorithm must be used for either std::sort or std::list::sort. It does say, however, that both must complete in O(nlogn) (on average; I'm unsure if the standard states their maximum complexity on worst case execution).

 

There are several things that might contribute to your big discrepancy:

  • Bad compiler options for timing code. If you didn't test "release" code (and instead tested "debug" code), the standard containers might be doing a lot of error checking, validating iterators. Also, you should consider turning on your compiler's optimization flags so it doesn't generate "dumb" machine code (but if it's too smart, it could optimize too much of your code away and make your timings meaningless).
  • Cache misses. This one can be huge, and it's hard to say exactly when and if it's occurring. Tools like valgrind (if you're not on Windows) can help detect cache misses. std::list doesn't necessarily store the elements in a contiguous array, which could result in some extra cache misses (and in terms of CPU cycles, a cache miss is a big slow down).
  • Usage of std::clock(). std::clock() does not measure "wall clock" time (i.e. what your watch says). It measures "CPU time," which is completely different. While it should work in theory (the difference of two std::clock() calls is supposedly meaningful, compared to the actual value of an individual call), it's not the best way to really profile your code (CPU sampling with a proper profiler (like Visual Studio's) is far more effective).

PARTNERS