diff options
Diffstat (limited to 'benchmark/source/BenchmarkSort.cpp')
| -rw-r--r-- | benchmark/source/BenchmarkSort.cpp | 1399 |
1 files changed, 0 insertions, 1399 deletions
diff --git a/benchmark/source/BenchmarkSort.cpp b/benchmark/source/BenchmarkSort.cpp deleted file mode 100644 index ccd2f43..0000000 --- a/benchmark/source/BenchmarkSort.cpp +++ /dev/null @@ -1,1399 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// Copyright (c) Electronic Arts Inc. All rights reserved. -///////////////////////////////////////////////////////////////////////////// - - -#include <EASTL/bonus/sort_extra.h> -#include <EASTL/sort.h> -#include <EASTL/vector.h> -#include <EAStdC/EAStopwatch.h> -#include "EASTLBenchmark.h" -#include "EASTLTest.h" - -EA_DISABLE_ALL_VC_WARNINGS() -#include <stdlib.h> -#include <algorithm> -#include <functional> -#include <vector> -EA_RESTORE_ALL_VC_WARNINGS() - - -using namespace EA; - - -namespace -{ - struct ValuePair - { - uint32_t key; - uint32_t v; - }; - - struct VPCompare - { - bool operator()(const ValuePair& vp1, const ValuePair& vp2) const - { - // return *(const uint64_t*)&vp1 < *(const uint64_t*)&vp2; - return (vp1.key == vp2.key) ? (vp1.v < vp2.v) : (vp1.key < vp2.key); - } - }; - - bool operator<(const ValuePair& vp1, const ValuePair& vp2) - { - // return *(const uint64_t*)&vp1 < *(const uint64_t*)&vp2; - return (vp1.key == vp2.key) ? (vp1.v < vp2.v) : (vp1.key < vp2.key); - } - - bool operator==(const ValuePair& vp1, const ValuePair& vp2) - { - // return *(const uint64_t*)&vp1 == *(const uint64_t*)&vp2; - return (vp1.key == vp2.key) && (vp1.v == vp2.v); - } -} - -// VPCompareC -// Useful for testing the the C qsort function. -int VPCompareC(const void* elem1, const void* elem2) -{ - return (int)(*(const uint64_t*)elem1 - *(const uint64_t*)elem2); -} - - -typedef std::vector<ValuePair> StdVectorVP; -typedef eastl::vector<ValuePair> EaVectorVP; - -typedef std::vector<uint32_t> StdVectorInt; -typedef eastl::vector<uint32_t> EaVectorInt; - -typedef std::vector<TestObject> StdVectorTO; -typedef eastl::vector<TestObject> EaVectorTO; - - -namespace -{ - #ifndef EA_PREFIX_NO_INLINE - #ifdef _MSC_VER - #define EA_PREFIX_NO_INLINE EA_NO_INLINE - #define EA_POSTFIX_NO_INLINE - #else - #define EA_PREFIX_NO_INLINE - #define EA_POSTFIX_NO_INLINE EA_NO_INLINE - #endif - #endif - - EA_PREFIX_NO_INLINE void TestQuickSortStdVP (EA::StdC::Stopwatch& stopwatch, StdVectorVP& stdVectorVP) EA_POSTFIX_NO_INLINE; - EA_PREFIX_NO_INLINE void TestQuickSortEaVP (EA::StdC::Stopwatch& stopwatch, EaVectorVP& eaVectorVP) EA_POSTFIX_NO_INLINE; - EA_PREFIX_NO_INLINE void TestQuickSortStdInt(EA::StdC::Stopwatch& stopwatch, StdVectorInt& stdVectorInt) EA_POSTFIX_NO_INLINE; - EA_PREFIX_NO_INLINE void TestQuickSortEaInt (EA::StdC::Stopwatch& stopwatch, EaVectorInt& eaVectorInt) EA_POSTFIX_NO_INLINE; - EA_PREFIX_NO_INLINE void TestQuickSortStdTO (EA::StdC::Stopwatch& stopwatch, StdVectorTO& stdVectorTO) EA_POSTFIX_NO_INLINE; - EA_PREFIX_NO_INLINE void TestQuickSortEaTO (EA::StdC::Stopwatch& stopwatch, EaVectorTO& eaVectorTO) EA_POSTFIX_NO_INLINE; - - - - void TestQuickSortStdVP(EA::StdC::Stopwatch& stopwatch, StdVectorVP& stdVectorVP) - { - stopwatch.Restart(); - std::sort(stdVectorVP.begin(), stdVectorVP.end()); - stopwatch.Stop(); - sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)stdVectorVP[0].key); - } - - - void TestQuickSortEaVP(EA::StdC::Stopwatch& stopwatch, EaVectorVP& eaVectorVP) - { - stopwatch.Restart(); - eastl::quick_sort(eaVectorVP.begin(), eaVectorVP.end()); - stopwatch.Stop(); - sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)eaVectorVP[0].key); - } - - - void TestQuickSortStdInt(EA::StdC::Stopwatch& stopwatch, StdVectorInt& stdVectorInt) - { - stopwatch.Restart(); - std::sort(stdVectorInt.begin(), stdVectorInt.end()); - stopwatch.Stop(); - sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)stdVectorInt[0]); - } - - - void TestQuickSortEaInt(EA::StdC::Stopwatch& stopwatch, EaVectorInt& eaVectorInt) - { - stopwatch.Restart(); - eastl::quick_sort(eaVectorInt.begin(), eaVectorInt.end()); - stopwatch.Stop(); - sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)eaVectorInt[0]); - } - - - void TestQuickSortStdTO(EA::StdC::Stopwatch& stopwatch, StdVectorTO& stdVectorTO) - { - stopwatch.Restart(); - std::sort(stdVectorTO.begin(), stdVectorTO.end()); - stopwatch.Stop(); - sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)stdVectorTO[0].mX); - } - - - void TestQuickSortEaTO(EA::StdC::Stopwatch& stopwatch, EaVectorTO& eaVectorTO) - { - stopwatch.Restart(); - eastl::quick_sort(eaVectorTO.begin(), eaVectorTO.end()); - stopwatch.Stop(); - sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)eaVectorTO[0].mX); - } - -} // namespace - - -namespace -{ - enum SortFunctionType - { - sf_qsort, // C qsort - sf_shell_sort, // eastl::shell_sort. - sf_heap_sort, // eastl::heap_sort - sf_merge_sort, // eastl::merge_sort - sf_merge_sort_buffer, // eastl::merge_sort_buffer - sf_comb_sort, // eastl::comb_sort - sf_bubble_sort, // eastl::bubble_sort - sf_selection_sort, // eastl::selection_sort - sf_shaker_sort, // eastl::shaker_sort - sf_quick_sort, // eastl::quick_sort - sf_tim_sort, // eastl::tim_sort - sf_insertion_sort, // eastl::insertion_sort - sf_std_sort, // std::sort - sf_std_stable_sort, // std::stable_sort - sf_radix_sort, // eastl::radix_sort (unconventional sort) - sf_count // - }; - - const char* GetSortFunctionName(int sortFunctionType) - { - switch (sortFunctionType) - { - case sf_quick_sort: - return "eastl::sort"; - - case sf_tim_sort: - return "eastl::tim_sort"; - - case sf_insertion_sort: - return "eastl::insertion_sort"; - - case sf_shell_sort: - return "eastl::shell_sort"; - - case sf_heap_sort: - return "eastl::heap_sort"; - - case sf_merge_sort: - return "eastl::merge_sort"; - - case sf_merge_sort_buffer: - return "eastl::merge_sort_buffer"; - - case sf_comb_sort: - return "eastl::comb_sort"; - - case sf_bubble_sort: - return "eastl::bubble_sort"; - - case sf_selection_sort: - return "eastl::selection_sort"; - - case sf_shaker_sort: - return "eastl::shaker_sort"; - - case sf_radix_sort: - return "eastl::radix_sort"; - - case sf_qsort: - return "qsort"; - - case sf_std_sort: - return "std::sort"; - - case sf_std_stable_sort: - return "std::stable_sort"; - - default: - return "unknown"; - } - } - - - enum RandomizationType - { - kRandom, // Completely random data. - kRandomSorted, // Random values already sorted. - kOrdered, // Already sorted. - kMostlyOrdered, // Partly sorted already. - kRandomizationTypeCount - }; - - const char* GetRandomizationTypeName(int randomizationType) - { - switch (randomizationType) - { - case kRandom: - return "random"; - - case kRandomSorted: - return "random sorted"; - - case kOrdered: - return "ordered"; - - case kMostlyOrdered: - return "mostly ordered"; - - default: - return "unknown"; - } - } - - template <typename ElementType, typename RandomType> - void Randomize(eastl::vector<ElementType>& v, EA::UnitTest::RandGenT<RandomType>& rng, RandomizationType type) - { - typedef RandomType value_type; - - switch (type) - { - default: - case kRandomizationTypeCount: // We specify this only to avoid a compiler warning about not testing for it. - case kRandom: - { - eastl::generate(v.begin(), v.end(), rng); - break; - } - - case kRandomSorted: - { - // This randomization type differs from kOrdered because the set of values is random (but sorted), in the kOrdered - // case the set of values is contiguous (i.e. 0, 1, ..., n) which can have different performance characteristics. - // For example, radix_sort performs poorly for kOrdered. - eastl::generate(v.begin(), v.end(), rng); - eastl::sort(v.begin(), v.end()); - break; - } - - case kOrdered: - { - for(eastl_size_t i = 0; i < v.size(); ++i) - v[i] = value_type((value_type)i); // Note that value_type may be a struct and not an integer. Thus the casting and construction here. - break; - } - - case kMostlyOrdered: - { - for(eastl_size_t i = 0; i < v.size(); ++i) - v[i] = value_type((value_type)i); // Note that value_type may be a struct and not an integer. Thus the casting and construction here. - - // We order random segments. - // The algorithm below in practice will make slightly more than kPercentOrdered be ordered. - const eastl_size_t kPercentOrdered = 80; // In actuality, due to statistics, the actual ordered percent will be about 82-85%. - - for(eastl_size_t n = 0, s = v.size(), nEnd = ((s < (100 - kPercentOrdered)) ? 1 : (s / (100 - kPercentOrdered))); n < nEnd; n++) - { - eastl_size_t i = rng.mRand.RandLimit((uint32_t)s); - eastl_size_t j = rng.mRand.RandLimit((uint32_t)s); - - eastl::swap(v[i], v[j]); - } - - break; - } - } - } - - - char gSlowAssignBuffer1[256] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 /* ... */}; - char gSlowAssignBuffer2[256] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 /* ... */}; - - - // SlowAssign - // Implements an object which has slow assign performance. - template <typename T> - struct SlowAssign - { - typedef T key_type; - T x; - - static int nAssignCount; - - SlowAssign() - { x = 0; memcpy(gSlowAssignBuffer1, gSlowAssignBuffer2, sizeof(gSlowAssignBuffer1)); } - - SlowAssign(const SlowAssign& sa) - { ++nAssignCount; x = sa.x; memcpy(gSlowAssignBuffer1, gSlowAssignBuffer2, sizeof(gSlowAssignBuffer1)); } - - SlowAssign& operator=(const SlowAssign& sa) - { ++nAssignCount; x = sa.x; memcpy(gSlowAssignBuffer1, gSlowAssignBuffer2, sizeof(gSlowAssignBuffer1)); return *this; } - - SlowAssign& operator=(int a) - { x = (T)a; return *this; } - - static void Reset() - { nAssignCount = 0; } - }; - - template<> int SlowAssign<uint32_t>::nAssignCount = 0; - - template <typename T> - bool operator <(const SlowAssign<T>& a, const SlowAssign<T>& b) - { return a.x < b.x; } - - - // SlowCompare - // Implements a compare which is N time slower than a simple integer compare. - template <typename T> - struct SlowCompare - { - static int nCompareCount; - - bool operator()(T a, T b) - { - ++nCompareCount; - - return (a < b) && // It happens that gSlowAssignBuffer1 is always zeroed. - (gSlowAssignBuffer1[0] == 0) && (gSlowAssignBuffer1[1] == 0) && (gSlowAssignBuffer1[1] == 0) && - (gSlowAssignBuffer1[2] == 0) && (gSlowAssignBuffer1[4] == 0) && (gSlowAssignBuffer1[5] == 0); - } - - static void Reset() { nCompareCount = 0; } - }; - - template <> - int SlowCompare<int32_t>::nCompareCount = 0; - - - // qsort callback functions - // qsort compare function returns negative if b > a and positive if a > b. - template <typename T> - int CompareInteger(const void* a, const void* b) - { - // Even though you see the following in Internet example code, it doesn't work! - // The reason is that it works only if a and b are both >= 0, otherwise large - // values can cause integer register wraparound. A similar kind of problem happens - // if you try to do the same thing with floating point value compares. - // See http://www.akalin.cx/2006/06/23/on-the-qsort-comparison-function/ - // Internet exmaple code: - // return *(const int32_t*)a - *(const int32_t*)b; - - // This double comparison might seem like it's crippling qsort against the - // STL-based sorts which do a single compare. But consider that the returning - // of -1, 0, +1 gives qsort more information, and its logic takes advantage - // of that. - if (*(const T*)a < *(const T*)b) - return -1; - if (*(const T*)a > *(const T*)b) - return +1; - return 0; - } - - - int SlowCompareInt32(const void* a, const void* b) - { - ++SlowCompare<int32_t>::nCompareCount; - - // This code is similar in performance to the C++ SlowCompare template functor above. - if((gSlowAssignBuffer1[0] == 0) && (gSlowAssignBuffer1[1] == 0) && - (gSlowAssignBuffer1[1] == 0) && (gSlowAssignBuffer1[2] == 0) && - (gSlowAssignBuffer1[4] == 0) && (gSlowAssignBuffer1[5] == 0)) - { - if (*(const int32_t*)a < *(const int32_t*)b) - return -1; - if (*(const int32_t*)a > *(const int32_t*)b) - return +1; - } - - return 0; - } - - template <typename slow_assign_type> - struct slow_assign_extract_radix_key - { - typedef typename slow_assign_type::key_type radix_type; - - const radix_type operator()(const slow_assign_type& obj) const - { - return obj.x; - } - }; - - template <typename integer_type> - struct identity_extract_radix_key - { - typedef integer_type radix_type; - - const radix_type operator()(const integer_type& x) const - { - return x; - } - }; -} // namespace - - -struct BenchmarkResult -{ - uint64_t mTime; - uint64_t mCompareCount; - uint64_t mAssignCount; - - BenchmarkResult() : mTime(0), mCompareCount(0), mAssignCount(0) {} -}; - - -int CompareSortPerformance() -{ - // Sizes of arrays to be sorted. - const eastl_size_t kSizes[] = { 10, 100, 1000, 10000 }; - const eastl_size_t kSizesCount = EAArrayCount(kSizes); - static BenchmarkResult sResults[kRandomizationTypeCount][kSizesCount][sf_count]; - int nErrorCount = 0; - - EA::UnitTest::ReportVerbosity(2, "Sort comparison\n"); - EA::UnitTest::ReportVerbosity(2, "Random seed = %u\n", (unsigned)EA::UnitTest::GetRandSeed()); - - EA::UnitTest::RandGenT<int32_t> rng(EA::UnitTest::GetRandSeed()); - EA::StdC::Stopwatch stopwatch(EA::StdC::Stopwatch::kUnitsCPUCycles); - EA::StdC::Stopwatch stopwatchGlobal(EA::StdC::Stopwatch::kUnitsSeconds); - const eastl_size_t kArraySizeMax = *eastl::max_element(eastl::begin(kSizes), eastl::end(kSizes)); - const int kRunCount = 4; - - #if !defined(EA_DEBUG) - EA::UnitTest::SetHighThreadPriority(); - #endif - - eastl::vector<SortFunctionType> allSortFunctions; - for (int i = 0; i < sf_count; i++) - { - allSortFunctions.push_back(SortFunctionType(i)); - } - - { - auto& sortFunctions = allSortFunctions; - - // Regular speed test. - // In this case we test the sorting of integral values. - // This is probably the most common type of comparison. - EA::UnitTest::ReportVerbosity(2, "Sort comparison: Regular speed test\n"); - - typedef uint32_t ElementType; - typedef eastl::less<ElementType> CompareFunction; - - eastl::string sOutput; - sOutput.set_capacity(100000); - ElementType* pBuffer = new ElementType[kArraySizeMax]; - - memset(sResults, 0, sizeof(sResults)); - - stopwatchGlobal.Restart(); - - for (int c = 0; c < kRunCount; c++) - { - for (int i = 0; i < kRandomizationTypeCount; i++) - { - for (size_t sizeType = 0; sizeType < EAArrayCount(kSizes); sizeType++) - { - const eastl_size_t size = kSizes[sizeType]; - - for (SortFunctionType sortFunction : sortFunctions) - { - eastl::vector<ElementType> v(size); - - rng.SetSeed(EA::UnitTest::GetRandSeed()); - Randomize(v, rng, (RandomizationType)i); - - switch (sortFunction) - { - case sf_quick_sort: - stopwatch.Restart(); - eastl::quick_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_tim_sort: - stopwatch.Restart(); - eastl::tim_sort_buffer(v.begin(), v.end(), pBuffer, CompareFunction()); - stopwatch.Stop(); - break; - - case sf_insertion_sort: - stopwatch.Restart(); - eastl::insertion_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_shell_sort: - stopwatch.Restart(); - eastl::shell_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_heap_sort: - stopwatch.Restart(); - eastl::heap_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_merge_sort: - stopwatch.Restart(); - eastl::merge_sort(v.begin(), v.end(), *get_default_allocator((EASTLAllocatorType*)NULL), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_merge_sort_buffer: - stopwatch.Restart(); - eastl::merge_sort_buffer(v.begin(), v.end(), pBuffer, CompareFunction()); - stopwatch.Stop(); - break; - - case sf_comb_sort: - stopwatch.Restart(); - eastl::comb_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_bubble_sort: - stopwatch.Restart(); - eastl::bubble_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_selection_sort: - stopwatch.Restart(); - eastl::selection_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_shaker_sort: - stopwatch.Restart(); - eastl::shaker_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_radix_sort: - stopwatch.Restart(); - eastl::radix_sort<ElementType*, identity_extract_radix_key<ElementType>>(v.begin(), v.end(), pBuffer); - stopwatch.Stop(); - break; - - case sf_qsort: - stopwatch.Restart(); - qsort(&v[0], (size_t)v.size(), sizeof(ElementType), CompareInteger<ElementType>); - stopwatch.Stop(); - break; - - case sf_std_sort: - stopwatch.Restart(); - std::sort(v.data(), v.data() + v.size(), std::less<ElementType>()); - stopwatch.Stop(); - break; - - case sf_std_stable_sort: - stopwatch.Restart(); - std::stable_sort(v.data(), v.data() + v.size(), std::less<ElementType>()); - stopwatch.Stop(); - break; - - case sf_count: - default: - // unsupported - break; - } - - const uint64_t elapsedTime = (uint64_t)stopwatch.GetElapsedTime(); - - // If this result was faster than a previously fastest result, record this one instead. - if ((c == 0) || (elapsedTime < sResults[i][sizeType][sortFunction].mTime)) - sResults[i][sizeType][sortFunction].mTime = elapsedTime; - - VERIFY(eastl::is_sorted(v.begin(), v.end())); - - } // for each sort function... - - } // for each size type... - - } // for each randomization type... - - } // for each run - - EA::UnitTest::ReportVerbosity(2, "Total time: %.2f s\n", stopwatchGlobal.GetElapsedTimeFloat()); - - delete[] pBuffer; - - // Now print the results. - for (int i = 0; i < kRandomizationTypeCount; i++) - { - for (size_t sizeType = 0; sizeType < EAArrayCount(kSizes); sizeType++) - { - const eastl_size_t size = kSizes[sizeType]; - - for (SortFunctionType sortFunction : sortFunctions) - { - sOutput.append_sprintf("%25s, %14s, Size: %8u, Time: %14" PRIu64 " ticks %0.2f ticks/elem\n", - GetSortFunctionName(sortFunction), GetRandomizationTypeName(i), - (unsigned)size, sResults[i][sizeType][sortFunction].mTime, - float(sResults[i][sizeType][sortFunction].mTime)/float(size)); - } - sOutput.append("\n"); - } - } - - EA::UnitTest::ReportVerbosity(2, "%s\n\n", sOutput.c_str()); - } - - { - // Do a speed test for the case of slow compares. - // By this we mean to compare sorting speeds when the comparison of elements is slow. - // Sort functions use element comparison to tell where elements go and use element - // movement to get them there. But some sorting functions accomplish sorting performance by - // minimizing the amount of movement, some minimize the amount of comparisons, and the - // best do a good job of minimizing both. - auto sortFunctions = allSortFunctions; - // We can't test this radix_sort because what we need isn't exposed. - sortFunctions.erase(eastl::remove(sortFunctions.begin(), sortFunctions.end(), sf_radix_sort), sortFunctions.end()); - EA::UnitTest::ReportVerbosity(2, "Sort comparison: Slow compare speed test\n"); - - typedef int32_t ElementType; - typedef SlowCompare<ElementType> CompareFunction; - - eastl::string sOutput; - sOutput.set_capacity(100000); - ElementType* pBuffer = new ElementType[kArraySizeMax]; - - memset(sResults, 0, sizeof(sResults)); - - stopwatchGlobal.Restart(); - - for (int c = 0; c < kRunCount; c++) - { - for (int i = 0; i < kRandomizationTypeCount; i++) - { - for (size_t sizeType = 0; sizeType < EAArrayCount(kSizes); sizeType++) - { - const eastl_size_t size = kSizes[sizeType]; - - for (SortFunctionType sortFunction : sortFunctions) - { - eastl::vector<ElementType> v(size); - - rng.SetSeed(EA::UnitTest::GetRandSeed()); - Randomize(v, rng, (RandomizationType)i); - CompareFunction::Reset(); - - switch (sortFunction) - { - case sf_quick_sort: - stopwatch.Restart(); - eastl::quick_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_tim_sort: - stopwatch.Restart(); - eastl::tim_sort_buffer(v.begin(), v.end(), pBuffer, CompareFunction()); - stopwatch.Stop(); - break; - - case sf_insertion_sort: - stopwatch.Restart(); - eastl::insertion_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_shell_sort: - stopwatch.Restart(); - eastl::shell_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_heap_sort: - stopwatch.Restart(); - eastl::heap_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_merge_sort: - stopwatch.Restart(); - eastl::merge_sort(v.begin(), v.end(), *get_default_allocator((EASTLAllocatorType*)NULL), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_merge_sort_buffer: - stopwatch.Restart(); - eastl::merge_sort_buffer(v.begin(), v.end(), pBuffer, CompareFunction()); - stopwatch.Stop(); - break; - - case sf_comb_sort: - stopwatch.Restart(); - eastl::comb_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_bubble_sort: - stopwatch.Restart(); - eastl::bubble_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_selection_sort: - stopwatch.Restart(); - eastl::selection_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_shaker_sort: - stopwatch.Restart(); - eastl::shaker_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_qsort: - stopwatch.Restart(); - qsort(&v[0], (size_t)v.size(), sizeof(ElementType), SlowCompareInt32); - stopwatch.Stop(); - break; - - case sf_std_sort: - stopwatch.Restart(); - std::sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_std_stable_sort: - stopwatch.Restart(); - std::stable_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_radix_sort: - case sf_count: - default: - // unsupported - break; - } - - const uint64_t elapsedTime = (uint64_t)stopwatch.GetElapsedTime(); - - // If this result was faster than a previously fastest result, record this one instead. - if ((c == 0) || (elapsedTime < sResults[i][sizeType][sortFunction].mTime)) - { - sResults[i][sizeType][sortFunction].mTime = elapsedTime; - sResults[i][sizeType][sortFunction].mCompareCount = (uint64_t)CompareFunction::nCompareCount; - } - - VERIFY(eastl::is_sorted(v.begin(), v.end())); - } // for each sort function... - - } // for each size type... - - } // for each randomization type... - - } // for each run - - EA::UnitTest::ReportVerbosity(2, "Total time: %.2f s\n", stopwatchGlobal.GetElapsedTimeFloat()); - - delete[] pBuffer; - - // Now print the results. - for (int i = 0; i < kRandomizationTypeCount; i++) - { - for (size_t sizeType = 0; sizeType < EAArrayCount(kSizes); sizeType++) - { - const eastl_size_t size = kSizes[sizeType]; - - for (SortFunctionType sortFunction : sortFunctions) - { - sOutput.append_sprintf("%25s, %14s, Size: %6u, Time: %11" PRIu64 " ticks, Compares: %11" PRIu64 "\n", - GetSortFunctionName(sortFunction), GetRandomizationTypeName(i), - (unsigned)size, sResults[i][sizeType][sortFunction].mTime, - sResults[i][sizeType][sortFunction].mCompareCount); - } - - sOutput.append("\n"); - } - } - - EA::UnitTest::ReportVerbosity(2, "%s\n\n", sOutput.c_str()); - } - - { - // Do a speed test for the case of slow assignment. - // By this we mean to compare sorting speeds when the movement of elements is slow. - // Sort functions use element comparison to tell where elements go and use element - // movement to get them there. But some sorting functions accomplish sorting performance by - // minimizing the amount of movement, some minimize the amount of comparisons, and the - // best do a good job of minimizing both. - auto sortFunctions = allSortFunctions; - // Can't implement this for qsort because the C standard library doesn't expose it. - // We could implement it by copying and modifying the source code. - sortFunctions.erase(eastl::remove(sortFunctions.begin(), sortFunctions.end(), sf_qsort), sortFunctions.end()); - - EA::UnitTest::ReportVerbosity(2, "Sort comparison: Slow assignment speed test\n"); - - typedef SlowAssign<uint32_t> ElementType; - typedef eastl::less<ElementType> CompareFunction; - - eastl::string sOutput; - sOutput.set_capacity(100000); - ElementType* pBuffer = new ElementType[kArraySizeMax]; - - memset(sResults, 0, sizeof(sResults)); - - stopwatchGlobal.Restart(); - - for (int c = 0; c < kRunCount; c++) - { - for (int i = 0; i < kRandomizationTypeCount; i++) - { - for (size_t sizeType = 0; sizeType < EAArrayCount(kSizes); sizeType++) - { - const eastl_size_t size = kSizes[sizeType]; - - for (SortFunctionType sortFunction : sortFunctions) - { - eastl::vector<ElementType> v(size); - - Randomize<ElementType>(v, rng, (RandomizationType)i); - ElementType::Reset(); - - switch (sortFunction) - { - case sf_quick_sort: - stopwatch.Restart(); - eastl::quick_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_tim_sort: - stopwatch.Restart(); - eastl::tim_sort_buffer(v.begin(), v.end(), pBuffer, CompareFunction()); - stopwatch.Stop(); - break; - - case sf_insertion_sort: - stopwatch.Restart(); - eastl::insertion_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_shell_sort: - stopwatch.Restart(); - eastl::shell_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_heap_sort: - stopwatch.Restart(); - eastl::heap_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_merge_sort: - stopwatch.Restart(); - eastl::merge_sort(v.begin(), v.end(), *get_default_allocator((EASTLAllocatorType*)NULL), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_merge_sort_buffer: - stopwatch.Restart(); - eastl::merge_sort_buffer(v.begin(), v.end(), pBuffer, CompareFunction()); - stopwatch.Stop(); - break; - - case sf_comb_sort: - stopwatch.Restart(); - eastl::comb_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_bubble_sort: - stopwatch.Restart(); - eastl::bubble_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_selection_sort: - stopwatch.Restart(); - eastl::selection_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_shaker_sort: - stopwatch.Restart(); - eastl::shaker_sort(v.begin(), v.end(), CompareFunction()); - stopwatch.Stop(); - break; - - case sf_radix_sort: - stopwatch.Restart(); - eastl::radix_sort<ElementType*, slow_assign_extract_radix_key<ElementType>>(v.begin(), v.end(), pBuffer); - stopwatch.Stop(); - break; - - case sf_std_sort: - stopwatch.Restart(); - std::sort(v.begin(), v.end(), std::less<ElementType>()); - stopwatch.Stop(); - break; - - case sf_std_stable_sort: - stopwatch.Restart(); - std::stable_sort(v.begin(), v.end(), std::less<ElementType>()); - stopwatch.Stop(); - break; - - case sf_qsort: - case sf_count: - default: - // unsupported - break; - } - - const uint64_t elapsedTime = (uint64_t)stopwatch.GetElapsedTime(); - - // If this result was faster than a previously fastest result, record this one instead. - if ((c == 0) || (elapsedTime < sResults[i][sizeType][sortFunction].mTime)) - { - sResults[i][sizeType][sortFunction].mTime = elapsedTime; - sResults[i][sizeType][sortFunction].mAssignCount = (uint64_t)ElementType::nAssignCount; - } - - VERIFY(eastl::is_sorted(v.begin(), v.end())); - - } // for each sort function... - - } // for each size type... - - } // for each randomization type... - - } // for each run - - EA::UnitTest::ReportVerbosity(2, "Total time: %.2f s\n", stopwatchGlobal.GetElapsedTimeFloat()); - - delete[] pBuffer; - - // Now print the results. - for (int i = 0; i < kRandomizationTypeCount; i++) - { - for (size_t sizeType = 0; sizeType < EAArrayCount(kSizes); sizeType++) - { - const eastl_size_t size = kSizes[sizeType]; - - for (SortFunctionType sortFunction : sortFunctions) - { - sOutput.append_sprintf("%25s, %14s, Size: %6u, Time: %11" PRIu64 " ticks, Assignments: %11" PRIu64 "\n", - GetSortFunctionName(sortFunction), GetRandomizationTypeName(i), - (unsigned)size, sResults[i][sizeType][sortFunction].mTime, - sResults[i][sizeType][sortFunction].mAssignCount); - } - - sOutput.append("\n"); - } - } - EA::UnitTest::ReportVerbosity(2, "%s\n", sOutput.c_str()); - } - - #if !defined(EA_DEBUG) - EA::UnitTest::SetNormalThreadPriority(); - #endif - - return nErrorCount; -} - -typedef eastl::function<void(eastl::string &output, const char* sortFunction, const char* randomizationType, size_t size, size_t numSubArrays, const BenchmarkResult &result)> OutputResultCallback; -typedef eastl::function<void(BenchmarkResult &result)> PostExecuteCallback; -typedef eastl::function<void()> PreExecuteCallback; - - -template<class ElementType, class CompareFunction> -static int CompareSmallInputSortPerformanceHelper(eastl::vector<eastl_size_t> &arraySizes, eastl::vector<SortFunctionType> &sortFunctions, const PreExecuteCallback &preExecuteCallback, const PostExecuteCallback &postExecuteCallback, const OutputResultCallback &outputResultCallback) -{ - int nErrorCount = 0; - - EA::UnitTest::RandGenT<int32_t> rng(EA::UnitTest::GetRandSeed()); - EA::StdC::Stopwatch stopwatch(EA::StdC::Stopwatch::kUnitsCPUCycles); - EA::StdC::Stopwatch stopwatchGlobal(EA::StdC::Stopwatch::kUnitsSeconds); - const eastl_size_t kArraySizeMax = *eastl::max_element(eastl::begin(arraySizes), eastl::end(arraySizes)); - const int kRunCount = 4; - const int numSubArrays = 128; - - eastl::string sOutput; - sOutput.set_capacity(100000); - ElementType* pBuffer = new ElementType[kArraySizeMax]; - - stopwatchGlobal.Restart(); - - for (int i = 0; i < kRandomizationTypeCount; i++) - { - for (size_t size : arraySizes) - { - for (SortFunctionType sortFunction : sortFunctions) - { - BenchmarkResult bestResult{}; - - for (int c = 0; c < kRunCount; c++) - { - eastl::vector<ElementType> v(size * numSubArrays); - - rng.SetSeed(EA::UnitTest::GetRandSeed()); - Randomize(v, rng, (RandomizationType)i); - preExecuteCallback(); - - switch (sortFunction) - { - case sf_quick_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::quick_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_tim_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::tim_sort_buffer(begin, begin + size, pBuffer, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_insertion_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::insertion_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_shell_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::shell_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_heap_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::heap_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_merge_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::merge_sort(begin, begin + size, *get_default_allocator((EASTLAllocatorType*)NULL), CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_merge_sort_buffer: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::merge_sort_buffer(begin, begin + size, pBuffer, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_comb_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::comb_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_bubble_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::bubble_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_selection_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::selection_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_shaker_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - eastl::shaker_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_std_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - std::sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_std_stable_sort: - stopwatch.Restart(); - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - std::stable_sort(begin, begin + size, CompareFunction()); - } - stopwatch.Stop(); - break; - - case sf_qsort: - case sf_radix_sort: - case sf_count: - default: - EATEST_VERIFY_F(false, "Missing case statement for sort function %s.", GetSortFunctionName(sortFunction)); - break; - } - - BenchmarkResult result {}; - result.mTime = (uint64_t)stopwatch.GetElapsedTime(); - postExecuteCallback(result); - - // If this result was faster than a previously fastest result, record this one instead. - if ((c == 0) || (result.mTime < bestResult.mTime)) - bestResult = result; - - for (auto begin = v.begin(); begin != v.end(); begin += size) - { - VERIFY(eastl::is_sorted(begin, begin + size)); - } - } // for each run - - outputResultCallback(sOutput, GetSortFunctionName(sortFunction), GetRandomizationTypeName(i), size, numSubArrays, bestResult); - - } // for each sort function... - sOutput.append("\n"); - - } // for each size type... - - } // for each randomization type... - - EA::UnitTest::ReportVerbosity(2, "Total time: %.2f s\n", stopwatchGlobal.GetElapsedTimeFloat()); - EA::UnitTest::ReportVerbosity(2, "%s\n", sOutput.c_str()); - - delete[] pBuffer; - return nErrorCount; -} - -static int CompareSmallInputSortPerformance() -{ - int nErrorCount = 0; - eastl::vector<eastl_size_t> arraySizes{1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 64, 128, 256}; - // Test quick sort and merge sort to provide a "base line" for performance. The other sort algorithms are mostly - // O(n^2) and they are benchmarked to determine what sorts are ideal for sorting small arrays or sub-arrays. (i.e. - // this is useful to determine good algorithms to choose as a base case for some of the recursive sorts). - eastl::vector<SortFunctionType> sortFunctions{sf_quick_sort, sf_merge_sort_buffer, sf_bubble_sort, sf_comb_sort, - sf_insertion_sort, sf_selection_sort, sf_shell_sort, sf_shaker_sort}; - - EA::UnitTest::ReportVerbosity(2, "Small Sub-array Sort comparison: Regular speed test\n"); - nErrorCount += CompareSmallInputSortPerformanceHelper<uint32_t, eastl::less<uint32_t>>( - arraySizes, sortFunctions, PreExecuteCallback([]() {}), PostExecuteCallback([](BenchmarkResult&) {}), - OutputResultCallback([](eastl::string& output, const char* sortFunction, const char* randomizationType, - size_t size, size_t numSubArrays, const BenchmarkResult& result) { - output.append_sprintf("%25s, %14s, Size: %8u, Time: %0.1f ticks %0.2f ticks/elem\n", sortFunction, - randomizationType, (unsigned)size, float(result.mTime) / float(numSubArrays), - float(result.mTime) / float(size * numSubArrays)); - })); - - EA::UnitTest::ReportVerbosity(2, "Small Sub-array Sort comparison: Slow compare speed test\n"); - nErrorCount += CompareSmallInputSortPerformanceHelper<int32_t, SlowCompare<int32_t>>( - arraySizes, sortFunctions, PreExecuteCallback([]() { SlowCompare<int32_t>::Reset(); }), - PostExecuteCallback( - [](BenchmarkResult& result) { result.mCompareCount = (uint64_t)SlowCompare<int32_t>::nCompareCount; }), - OutputResultCallback([](eastl::string& output, const char* sortFunction, const char* randomizationType, - size_t size, size_t numSubArrays, const BenchmarkResult& result) { - output.append_sprintf("%25s, %14s, Size: %6u, Time: %0.2f ticks, Compares: %0.2f\n", sortFunction, - randomizationType, (unsigned)size, float(result.mTime) / float(numSubArrays), - float(result.mCompareCount) / float(numSubArrays)); - })); - - EA::UnitTest::ReportVerbosity(2, "Small Sub-array Sort comparison: Slow assignment speed test\n"); - nErrorCount += CompareSmallInputSortPerformanceHelper<SlowAssign<uint32_t>, eastl::less<SlowAssign<uint32_t>>>( - arraySizes, sortFunctions, PreExecuteCallback([]() { SlowAssign<uint32_t>::Reset(); }), - PostExecuteCallback([](BenchmarkResult& result) { - result.mCompareCount = (uint64_t)SlowCompare<int32_t>::nCompareCount; - result.mAssignCount = (uint64_t)SlowAssign<uint32_t>::nAssignCount; - }), - OutputResultCallback([](eastl::string& output, const char* sortFunction, const char* randomizationType, - size_t size, size_t numSubArrays, const BenchmarkResult& result) { - output.append_sprintf("%25s, %14s, Size: %6u, Time: %0.2f ticks, Assignments: %0.2f\n", sortFunction, - randomizationType, (unsigned)size, float(result.mTime) / float(numSubArrays), - float(result.mAssignCount) / float(numSubArrays)); - })); - - return nErrorCount; -} - - -void BenchmarkSort() -{ - EASTLTest_Printf("Sort\n"); - - EA::UnitTest::RandGenT<uint32_t> rng(12345678); // For debugging sort code we should use 12345678, for normal testing use EA::UnitTest::GetRandSeed(). - EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); - EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); - - if (EA::UnitTest::GetVerbosity() >= 3) - { - CompareSortPerformance(); - CompareSmallInputSortPerformance(); - } - - { // Exercise some declarations - int nErrorCount = 0; - - ValuePair vp1 = {0, 0}, vp2 = {0, 0}; - VPCompare c1, c2; - - VERIFY(c1.operator()(vp1, vp2) == c2.operator()(vp1, vp2)); - VERIFY((vp1 < vp2) || (vp1 == vp2) || !(vp1 == vp2)); - } - - { - eastl::vector<uint32_t> intVector(10000); - eastl::generate(intVector.begin(), intVector.end(), rng); - - for (int i = 0; i < 2; i++) - { - /////////////////////////////// - // Test quick_sort/vector/ValuePair - /////////////////////////////// - - StdVectorVP stdVectorVP(intVector.size()); - EaVectorVP eaVectorVP(intVector.size()); - - for (eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) - { - const ValuePair vp = {intVector[j], intVector[j]}; - stdVectorVP[j] = vp; - eaVectorVP[j] = vp; - } - - TestQuickSortStdVP(stopwatch1, stdVectorVP); - TestQuickSortEaVP (stopwatch2, eaVectorVP); - - if(i == 1) - Benchmark::AddResult("sort/q_sort/vector<ValuePair>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - - // Benchmark the sorting of something that is already sorted. - TestQuickSortStdVP(stopwatch1, stdVectorVP); - TestQuickSortEaVP (stopwatch2, eaVectorVP); - - if(i == 1) - Benchmark::AddResult("sort/q_sort/vector<ValuePair>/sorted", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - - - - /////////////////////////////// - // Test quick_sort/vector/Int - /////////////////////////////// - - StdVectorInt stdVectorInt(intVector.size()); - EaVectorInt eaVectorInt (intVector.size()); - - for(eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) - { - stdVectorInt[j] = intVector[j]; - eaVectorInt[j] = intVector[j]; - } - - TestQuickSortStdInt(stopwatch1, stdVectorInt); - TestQuickSortEaInt (stopwatch2, eaVectorInt); - - if(i == 1) - Benchmark::AddResult("sort/q_sort/vector<uint32>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - - // Benchmark the sorting of something that is already sorted. - TestQuickSortStdInt(stopwatch1, stdVectorInt); - TestQuickSortEaInt (stopwatch2, eaVectorInt); - - if(i == 1) - Benchmark::AddResult("sort/q_sort/vector<uint32>/sorted", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - - - - /////////////////////////////// - // Test quick_sort/vector/TestObject - /////////////////////////////// - - StdVectorTO stdVectorTO(intVector.size()); - EaVectorTO eaVectorTO(intVector.size()); - - for (eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) - { - stdVectorTO[j] = TestObject(intVector[j]); - eaVectorTO[j] = TestObject(intVector[j]); - } - - TestQuickSortStdTO(stopwatch1, stdVectorTO); - TestQuickSortEaTO(stopwatch2, eaVectorTO); - - if (i == 1) - Benchmark::AddResult("sort/q_sort/vector<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - - // Benchmark the sorting of something that is already sorted. - TestQuickSortStdTO(stopwatch1, stdVectorTO); - TestQuickSortEaTO(stopwatch2, eaVectorTO); - - if (i == 1) - Benchmark::AddResult("sort/q_sort/vector<TestObject>/sorted", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - - - - /////////////////////////////// - // Test quick_sort/TestObject[] - /////////////////////////////// - - // Reset the values back to the unsorted state. - for(eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) - { - stdVectorTO[j] = TestObject(intVector[j]); - eaVectorTO[j] = TestObject(intVector[j]); - } - - TestQuickSortStdTO(stopwatch1, stdVectorTO); - TestQuickSortEaTO (stopwatch2, eaVectorTO); - - if(i == 1) - Benchmark::AddResult("sort/q_sort/TestObject[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - - // Benchmark the sorting of something that is already sorted. - TestQuickSortStdTO(stopwatch1, stdVectorTO); - TestQuickSortEaTO (stopwatch2, eaVectorTO); - - if(i == 1) - Benchmark::AddResult("sort/q_sort/TestObject[]/sorted", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); - } - } -} - - - - - |