diff options
Diffstat (limited to 'EASTL/benchmark/source/BenchmarkAlgorithm.cpp')
| -rw-r--r-- | EASTL/benchmark/source/BenchmarkAlgorithm.cpp | 1241 |
1 files changed, 1241 insertions, 0 deletions
diff --git a/EASTL/benchmark/source/BenchmarkAlgorithm.cpp b/EASTL/benchmark/source/BenchmarkAlgorithm.cpp new file mode 100644 index 0000000..57e155e --- /dev/null +++ b/EASTL/benchmark/source/BenchmarkAlgorithm.cpp @@ -0,0 +1,1241 @@ +///////////////////////////////////////////////////////////////////////////// +// BenchmarkAlgorithm.cpp +// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EAStdC/EAMemory.h> +#include <EASTL/algorithm.h> +#include <EASTL/sort.h> +#include <EASTL/vector.h> +#include <EASTL/slist.h> +#include <EASTL/list.h> +#include <EASTL/string.h> +#include <EASTL/random.h> + +EA_DISABLE_ALL_VC_WARNINGS() +#include <stdio.h> +#include <stdlib.h> +#include <string> +#include <vector> +#include <list> +#include <algorithm> +EA_RESTORE_ALL_VC_WARNINGS() + +#ifdef _MSC_VER + #pragma warning(disable: 4996) // Function call with parameters that may be unsafe +#endif + + +using namespace EA; + + +typedef std::vector<unsigned char> StdVectorUChar; +typedef eastl::vector<unsigned char> EaVectorUChar; + +typedef std::vector<signed char> StdVectorSChar; +typedef eastl::vector<signed char> EaVectorSChar; + +typedef std::vector<uint32_t> StdVectorUint32; +typedef eastl::vector<uint32_t> EaVectorUint32; + +typedef std::vector<uint64_t> StdVectorUint64; +typedef eastl::vector<uint64_t> EaVectorUint64; + +typedef std::vector<TestObject> StdVectorTO; +typedef eastl::vector<TestObject> EaVectorTO; + + +// We make a fake version of C++11 std::next, as some C++ compilers don't currently +// provide the C++11 next algorithm in their standard libraries. +namespace std__ +{ + template<typename InputIterator> + inline InputIterator + next(InputIterator it, typename std::iterator_traits<InputIterator>::difference_type n = 1) + { + std::advance(it, n); + return it; + } +} + + +namespace +{ + void TestFindEndStd(EA::StdC::Stopwatch& stopwatch, const std::string& sTest, const char* pSearchStringBegin, const char* pSearchStringEnd) + { + stopwatch.Restart(); + std::string::const_iterator it = std::find_end(sTest.begin(), sTest.end(), pSearchStringBegin, pSearchStringEnd); + stopwatch.Stop(); + if(it != sTest.end()) + sprintf(Benchmark::gScratchBuffer, "%c", *it); + } + + void TestFindEndEa(EA::StdC::Stopwatch& stopwatch, const eastl::string& sTest, const char* pSearchStringBegin, const char* pSearchStringEnd) + { + stopwatch.Restart(); + eastl::string::const_iterator it = eastl::find_end(sTest.begin(), sTest.end(), pSearchStringBegin, pSearchStringEnd); + stopwatch.Stop(); + if(it != sTest.end()) + sprintf(Benchmark::gScratchBuffer, "%c", *it); + } + + + + void TestSearchStd(EA::StdC::Stopwatch& stopwatch, const std::string& sTest, const char* pSearchStringBegin, const char* pSearchStringEnd) + { + stopwatch.Restart(); + std::string::const_iterator it = std::search(sTest.begin(), sTest.end(), pSearchStringBegin, pSearchStringEnd); + stopwatch.Stop(); + if(it != sTest.end()) + sprintf(Benchmark::gScratchBuffer, "%c", *it); + } + + void TestSearchEa(EA::StdC::Stopwatch& stopwatch, const eastl::string& sTest, const char* pSearchStringBegin, const char* pSearchStringEnd) + { + stopwatch.Restart(); + eastl::string::const_iterator it = eastl::search(sTest.begin(), sTest.end(), pSearchStringBegin, pSearchStringEnd); + stopwatch.Stop(); + if(it != sTest.end()) + sprintf(Benchmark::gScratchBuffer, "%c", *it); + } + + + + void TestSearchNStd(EA::StdC::Stopwatch& stopwatch, const std::string& sTest, int n, char c) + { + stopwatch.Restart(); + std::string::const_iterator it = std::search_n(sTest.begin(), sTest.end(), n, c); + stopwatch.Stop(); + if(it != sTest.end()) + sprintf(Benchmark::gScratchBuffer, "%c", *it); + } + + void TestSearchNEa(EA::StdC::Stopwatch& stopwatch, const eastl::string& sTest, int n, char c) + { + stopwatch.Restart(); + eastl::string::const_iterator it = eastl::search_n(sTest.begin(), sTest.end(), n, c); + stopwatch.Stop(); + if(it != sTest.end()) + sprintf(Benchmark::gScratchBuffer, "%c", *it); + } + + + + template <typename Container> + void TestUniqueStd(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + typename Container::iterator it = std::unique(c.begin(), c.end()); + stopwatch.Stop(); + c.erase(it, c.end()); + } + + template <typename Container> + void TestUniqueEa(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + typename Container::iterator it = eastl::unique(c.begin(), c.end()); + stopwatch.Stop(); + c.erase(it, c.end()); + } + + + + template <typename Container> + void TestMinElementStd(EA::StdC::Stopwatch& stopwatch, const Container& c) + { + stopwatch.Restart(); + const typename Container::const_iterator it = std::min_element(c.begin(), c.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &it); + } + + template <typename Container> + void TestMinElementEa(EA::StdC::Stopwatch& stopwatch, const Container& c) + { + stopwatch.Restart(); + const typename Container::const_iterator it = eastl::min_element(c.begin(), c.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &it); + } + + + + template <typename Container> + void TestCountStd(EA::StdC::Stopwatch& stopwatch, const Container& c) + { + stopwatch.Restart(); + const typename Container::difference_type n = std::count(c.begin(), c.end(), (typename Container::value_type)999999); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", (int)n); + } + + template <typename Container> + void TestCountEa(EA::StdC::Stopwatch& stopwatch, const Container& c) + { + stopwatch.Restart(); + const typename Container::difference_type n = eastl::count(c.begin(), c.end(), (typename Container::value_type)999999); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", (int)n); + } + + + + template <typename Container> + void TestAdjacentFindStd(EA::StdC::Stopwatch& stopwatch, const Container& c) + { + stopwatch.Restart(); + const typename Container::const_iterator it = std::adjacent_find(c.begin(), c.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &it); + } + + template <typename Container> + void TestAdjacentFindEa(EA::StdC::Stopwatch& stopwatch, const Container& c) + { + stopwatch.Restart(); + const typename Container::const_iterator it = eastl::adjacent_find(c.begin(), c.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &it); + } + + + + template <typename Container> + void TestLowerBoundStd(EA::StdC::Stopwatch& stopwatch, const Container& c, const typename Container::value_type* pBegin, const typename Container::value_type* pEnd) + { + + stopwatch.Restart(); + while(pBegin != pEnd) + { + typename Container::const_iterator it = std::lower_bound(c.begin(), c.end(), *pBegin++); + Benchmark::DoNothing(&it); + } + stopwatch.Stop(); + } + + template <typename Container> + void TestLowerBoundEa(EA::StdC::Stopwatch& stopwatch, Container& c, const typename Container::value_type* pBegin, const typename Container::value_type* pEnd) + { + stopwatch.Restart(); + while(pBegin != pEnd) + { + typename Container::const_iterator it = eastl::lower_bound(c.begin(), c.end(), *pBegin++); + Benchmark::DoNothing(&it); + } + stopwatch.Stop(); + } + + + + template <typename Container> + void TestUpperBoundStd(EA::StdC::Stopwatch& stopwatch, const Container& c, const typename Container::value_type* pBegin, const typename Container::value_type* pEnd) + { + stopwatch.Restart(); + while(pBegin != pEnd) + { + typename Container::const_iterator it = std::upper_bound(c.begin(), c.end(), *pBegin++); + Benchmark::DoNothing(&it); + } + stopwatch.Stop(); + } + + template <typename Container> + void TestUpperBoundEa(EA::StdC::Stopwatch& stopwatch, Container& c, const typename Container::value_type* pBegin, const typename Container::value_type* pEnd) + { + stopwatch.Restart(); + while(pBegin != pEnd) + { + typename Container::const_iterator it = eastl::upper_bound(c.begin(), c.end(), *pBegin++); + Benchmark::DoNothing(&it); + } + stopwatch.Stop(); + } + + + + template <typename Container> + void TestEqualRangeStd(EA::StdC::Stopwatch& stopwatch, const Container& c, const typename Container::value_type* pBegin, const typename Container::value_type* pEnd) + { + stopwatch.Restart(); + while(pBegin != pEnd) + { + std::pair<const typename Container::const_iterator, + const typename Container::const_iterator> itPair = std::equal_range(c.begin(), c.end(), *pBegin++); + + Benchmark::DoNothing(&itPair); + } + stopwatch.Stop(); + } + + template <typename Container> + void TestEqualRangeEa(EA::StdC::Stopwatch& stopwatch, Container& c, const typename Container::value_type* pBegin, const typename Container::value_type* pEnd) + { + stopwatch.Restart(); + while(pBegin != pEnd) + { + eastl::pair<const typename Container::const_iterator, + const typename Container::const_iterator> itPair = eastl::equal_range(c.begin(), c.end(), *pBegin++); + Benchmark::DoNothing(&itPair); + } + stopwatch.Stop(); + } + + + + template <typename Iterator1, typename Iterator2> + void TestLexicographicalCompareStd(EA::StdC::Stopwatch& stopwatch, Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) + { + stopwatch.Restart(); + const bool bResult = std::lexicographical_compare(first1, last1, first2, last2); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", bResult ? (int)1 : (int)0); + } + + template <typename Iterator1, typename Iterator2> + void TestLexicographicalCompareEa(EA::StdC::Stopwatch& stopwatch, Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) + { + stopwatch.Restart(); + const bool bResult = eastl::lexicographical_compare(first1, last1, first2, last2); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", bResult ? (int)1 : (int)0); + } + + + + template <typename Iterator, typename OutputIterator> + void TestCopyStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, OutputIterator result) + { + stopwatch.Restart(); + std::copy(first, last, result); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", (int)*first); + } + + template <typename Iterator, typename OutputIterator> + void TestCopyEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, OutputIterator result) + { + stopwatch.Restart(); + eastl::copy(first, last, result); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", (int)*first); + } + + + + template <typename Iterator, typename OutputIterator> + void TestCopyBackwardStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, OutputIterator result) + { + stopwatch.Restart(); + std::copy_backward(first, last, result); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", (int)*first); + } + + template <typename Iterator, typename OutputIterator> + void TestCopyBackwardEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, OutputIterator result) + { + stopwatch.Restart(); + eastl::copy_backward(first, last, result); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%d", (int)*first); + } + + + + template <typename Iterator, typename Value> + void TestFillStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, const Value& v) + { + stopwatch.Restart(); + std::fill(first, last, v); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + template <typename Iterator, typename Value> + void TestFillEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, const Value& v) + { + stopwatch.Restart(); + eastl::fill(first, last, v); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + + + template <typename Iterator, typename Value> + void TestFillNStd(EA::StdC::Stopwatch& stopwatch, Iterator first, int n, const Value& v) + { + stopwatch.Restart(); + std::fill_n(first, n, v); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + template <typename Iterator, typename Value> + void TestFillNEa(EA::StdC::Stopwatch& stopwatch, Iterator first, int n, const Value& v) + { + stopwatch.Restart(); + eastl::fill_n(first, n, v); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + + + template <typename Iterator> + void TestReverseStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + std::reverse(first, last); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + template <typename Iterator> + void TestReverseEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + eastl::reverse(first, last); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + + + template <typename Iterator> + void TestRotateStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator middle, Iterator last) + { + stopwatch.Restart(); + std::rotate(first, middle, last); // C++11 specifies that rotate has a return value, but not all std implementations return it. + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + template <typename Iterator> + void TestRotateEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator middle, Iterator last) + { + stopwatch.Restart(); + eastl::rotate(first, middle, last); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + template <typename Iterator> + void TestMergeStd(EA::StdC::Stopwatch& stopwatch, Iterator firstIn1, Iterator lastIn1, Iterator firstIn2, Iterator lastIn2, Iterator out) + { + stopwatch.Restart(); + std::merge(firstIn1, lastIn1, firstIn2, lastIn2, out); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*out); + } + + template <typename Iterator> + void TestMergeEa(EA::StdC::Stopwatch& stopwatch, Iterator firstIn1, Iterator lastIn1, Iterator firstIn2, Iterator lastIn2, Iterator out) + { + stopwatch.Restart(); + eastl::merge(firstIn1, lastIn1, firstIn2, lastIn2, out); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*out); + } +} // namespace + + + + +void BenchmarkAlgorithm1(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + std::string sTestStd; + eastl::string sTestEa; + const char* pSearchString1Begin = "AAA"; + const char* pSearchString1End = pSearchString1Begin + strlen(pSearchString1Begin); + const char* pSearchString2Begin = "BBB"; // This is something that doesn't exist searched string. + const char* pSearchString2End = pSearchString2Begin + strlen(pSearchString2Begin); + const char* pSearchString3Begin = "CCC"; + const char* pSearchString3End = pSearchString3Begin + strlen(pSearchString3Begin); + + for(int i = 0; i < 10000; i++) + sTestStd += "This is a test of the find_end algorithm. "; + sTestEa.assign(sTestStd.data(), (eastl_size_t)sTestStd.length()); + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test find_end + /////////////////////////////// + + sTestStd.insert(sTestStd.size() * 15 / 16, pSearchString1Begin); + sTestEa.insert (sTestEa.size() * 15 / 16, pSearchString1Begin); + TestFindEndStd(stopwatch1, sTestStd, pSearchString1Begin, pSearchString1End); + TestFindEndEa (stopwatch2, sTestEa, pSearchString1Begin, pSearchString1End); + + if(i == 1) + Benchmark::AddResult("algorithm/find_end/string/end", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + sTestStd.insert(sTestStd.size() / 2, pSearchString2Begin); + sTestEa.insert (sTestEa.size() / 2, pSearchString2Begin); + TestFindEndStd(stopwatch1, sTestStd, pSearchString2Begin, pSearchString2End); + TestFindEndEa (stopwatch2, sTestEa, pSearchString2Begin, pSearchString2End); + + if(i == 1) + Benchmark::AddResult("algorithm/find_end/string/middle", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFindEndStd(stopwatch1, sTestStd, pSearchString3Begin, pSearchString3End); + TestFindEndEa (stopwatch2, sTestEa, pSearchString3Begin, pSearchString3End); + + if(i == 1) + Benchmark::AddResult("algorithm/find_end/string/none", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test search + /////////////////////////////// + TestSearchStd(stopwatch1, sTestStd, pSearchString1Begin, pSearchString1End); + TestSearchEa (stopwatch2, sTestEa, pSearchString1Begin, pSearchString1End); + + if(i == 1) + Benchmark::AddResult("algorithm/search/string<char>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test search_n + /////////////////////////////// + TestSearchNStd(stopwatch1, sTestStd, 3, 'A'); + TestSearchNEa (stopwatch2, sTestEa, 3, 'A'); + + if(i == 1) + Benchmark::AddResult("algorithm/search_n/string<char>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test adjacent_find + /////////////////////////////// + + } + } +} + + +void BenchmarkAlgorithm2(EASTLTest_Rand& rng, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + StdVectorUint32 stdVectorUint32; + EaVectorUint32 eaVectorUint32; + + StdVectorUint64 stdVectorUint64; + EaVectorUint64 eaVectorUint64; + + StdVectorTO stdVectorTO; + EaVectorTO eaVectorTO; + + for(int i = 0; i < 2; i++) + { + stdVectorUint32.clear(); + eaVectorUint32.clear(); + + for(int j = 0; j < 100000; j++) + { + stdVectorUint32.push_back(j); + eaVectorUint32.push_back(j); + stdVectorUint64.push_back(j); + eaVectorUint64.push_back(j); + stdVectorTO.push_back(TestObject(j)); + eaVectorTO.push_back(TestObject(j)); + + if((rng() % 16) == 0) + { + stdVectorUint32.push_back(i); + eaVectorUint32.push_back(i); + stdVectorUint64.push_back(j); + eaVectorUint64.push_back(j); + stdVectorTO.push_back(TestObject(j)); + eaVectorTO.push_back(TestObject(j)); + + if((rng() % 16) == 0) + { + stdVectorUint32.push_back(i); + eaVectorUint32.push_back(i); + stdVectorUint64.push_back(j); + eaVectorUint64.push_back(j); + stdVectorTO.push_back(TestObject(j)); + eaVectorTO.push_back(TestObject(j)); + } + } + } + + + /////////////////////////////// + // Test unique + /////////////////////////////// + + TestUniqueStd(stopwatch1, stdVectorUint32); + TestUniqueEa (stopwatch2, eaVectorUint32); + + if(i == 1) + Benchmark::AddResult("algorithm/unique/vector<uint32_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestUniqueStd(stopwatch1, stdVectorUint64); + TestUniqueEa (stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("algorithm/unique/vector<uint64_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestUniqueStd(stopwatch1, stdVectorTO); + TestUniqueEa (stopwatch2, eaVectorTO); + + if(i == 1) + Benchmark::AddResult("algorithm/unique/vector<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test min_element + /////////////////////////////// + + TestMinElementStd(stopwatch1, stdVectorTO); + TestMinElementEa (stopwatch2, eaVectorTO); + + if(i == 1) + Benchmark::AddResult("algorithm/min_element/vector<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test count + /////////////////////////////// + + TestCountStd(stopwatch1, stdVectorUint64); + TestCountEa (stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("algorithm/count/vector<uint64_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test adjacent_find + /////////////////////////////// + + // Due to the above unique testing, the container should container unique elements. Let's change that. + stdVectorTO[stdVectorTO.size() - 2] = stdVectorTO[stdVectorTO.size() - 1]; + eaVectorTO[eaVectorTO.size() - 2] = eaVectorTO[eaVectorTO.size() - 1]; + TestAdjacentFindStd(stopwatch1, stdVectorTO); + TestAdjacentFindEa (stopwatch2, eaVectorTO); + + if(i == 1) + Benchmark::AddResult("algorithm/adj_find/vector<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test lower_bound + /////////////////////////////// + + // Sort the containers for the following tests. + std::sort(stdVectorTO.begin(), stdVectorTO.end()); + eaVectorTO.assign(&stdVectorTO[0], &stdVectorTO[0] + stdVectorTO.size()); + + TestLowerBoundStd(stopwatch1, stdVectorTO, &stdVectorTO[0], &stdVectorTO[0] + stdVectorTO.size()); + TestLowerBoundEa (stopwatch2, eaVectorTO, &eaVectorTO[0], &eaVectorTO[0] + eaVectorTO.size()); + + if(i == 1) + Benchmark::AddResult("algorithm/lower_bound/vector<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test upper_bound + /////////////////////////////// + + std::sort(stdVectorUint32.begin(), stdVectorUint32.end()); + eaVectorUint32.assign(&stdVectorUint32[0], &stdVectorUint32[0] + stdVectorUint32.size()); + + TestUpperBoundStd(stopwatch1, stdVectorUint32, &stdVectorUint32[0], &stdVectorUint32[0] + stdVectorUint32.size()); + TestUpperBoundEa (stopwatch2, eaVectorUint32, &eaVectorUint32[0], &eaVectorUint32[0] + eaVectorUint32.size()); + + if(i == 1) + Benchmark::AddResult("algorithm/upper_bound/vector<uint32_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test equal_range + /////////////////////////////// + + // VS2010 (and later versions?) is extremely slow executing this in debug builds. It can take minutes for a + // single TestEqualRangeStd call to complete. It's so slow that it's nearly pointless to execute. + #if !defined(_MSC_VER) || (_MSC_VER < 1600) || !defined(_ITERATOR_DEBUG_LEVEL) || (_ITERATOR_DEBUG_LEVEL < 2) + std::sort(stdVectorUint64.begin(), stdVectorUint64.end()); + eaVectorUint64.assign(&stdVectorUint64[0], &stdVectorUint64[0] + stdVectorUint64.size()); + + TestEqualRangeStd(stopwatch1, stdVectorUint64, &stdVectorUint64[0], &stdVectorUint64[0] + stdVectorUint64.size()); + TestEqualRangeEa (stopwatch2, eaVectorUint64, &eaVectorUint64[0], &eaVectorUint64[0] + eaVectorUint64.size()); + + if(i == 1) + Benchmark::AddResult("algorithm/equal_range/vector<uint64_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + #endif + } + } +} + + +void BenchmarkAlgorithm3(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + StdVectorUChar stdVectorUChar1(100000); + StdVectorUChar stdVectorUChar2(100000); + EaVectorUChar eaVectorUChar1(100000); + EaVectorUChar eaVectorUChar2(100000); + + StdVectorSChar stdVectorSChar1(100000); + StdVectorSChar stdVectorSChar2(100000); + EaVectorSChar eaVectorSChar1(100000); + EaVectorSChar eaVectorSChar2(100000); + + StdVectorTO stdVectorTO1(100000); + StdVectorTO stdVectorTO2(100000); + EaVectorTO eaVectorTO1(100000); + EaVectorTO eaVectorTO2(100000); + + // All these containers should have values of zero in them. + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test lexicographical_compare + /////////////////////////////// + + TestLexicographicalCompareStd(stopwatch1, stdVectorUChar1.begin(), stdVectorUChar1.end(), stdVectorUChar2.begin(), stdVectorUChar2.end()); + TestLexicographicalCompareEa (stopwatch2, eaVectorUChar1.begin(), eaVectorUChar2.end(), eaVectorUChar2.begin(), eaVectorUChar2.end()); + + if(i == 1) + Benchmark::AddResult("algorithm/lex_cmp/vector<uchar>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestLexicographicalCompareStd(stopwatch1, &stdVectorSChar1[0], &stdVectorSChar1[0] + stdVectorSChar1.size(), &stdVectorSChar2[0], &stdVectorSChar2[0] + stdVectorSChar2.size()); + TestLexicographicalCompareEa (stopwatch2, &eaVectorSChar1[0], &eaVectorSChar1[0] + eaVectorSChar1.size(), &eaVectorSChar2[0], &eaVectorSChar2[0] + eaVectorSChar2.size()); + + if(i == 1) + Benchmark::AddResult("algorithm/lex_cmp/schar[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestLexicographicalCompareStd(stopwatch1, stdVectorTO1.begin(), stdVectorTO1.end(), stdVectorTO2.begin(), stdVectorTO2.end()); + TestLexicographicalCompareEa (stopwatch2, eaVectorTO1.begin(), eaVectorTO1.end(), eaVectorTO2.begin(), eaVectorTO2.end()); + + if(i == 1) + Benchmark::AddResult("algorithm/lex_cmp/vector<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } + +} + + +void BenchmarkAlgorithm4(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + std::vector<uint32_t> stdVectorUint321(10000); + std::vector<uint32_t> stdVectorUint322(10000); + eastl::vector<uint32_t> eaVectorUint321(10000); + eastl::vector<uint32_t> eaVectorUint322(10000); + + std::vector<uint64_t> stdVectorUint64(100000); + eastl::vector<uint64_t> eaVectorUint64(100000); + + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test copy + /////////////////////////////// + + TestCopyStd(stopwatch1, stdVectorUint321.begin(), stdVectorUint321.end(), stdVectorUint322.begin()); + TestCopyEa (stopwatch2, eaVectorUint321.begin(), eaVectorUint321.end(), eaVectorUint322.begin()); + + if(i == 1) + Benchmark::AddResult("algorithm/copy/vector<uint32_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test copy_backward + /////////////////////////////// + + TestCopyBackwardStd(stopwatch1, stdVectorUint321.begin(), stdVectorUint321.end(), stdVectorUint322.end()); + TestCopyBackwardEa (stopwatch2, eaVectorUint321.begin(), eaVectorUint321.end(), eaVectorUint322.end()); + + if(i == 1) + Benchmark::AddResult("algorithm/copy_backward/vector<uint32_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test fill + /////////////////////////////// + + TestFillStd(stopwatch1, stdVectorUint64.begin(), stdVectorUint64.end(), UINT64_C(37)); + TestFillEa (stopwatch2, eaVectorUint64.begin(), eaVectorUint64.end(), UINT64_C(37)); + TestFillStd(stopwatch1, stdVectorUint64.begin(), stdVectorUint64.end(), UINT64_C(37)); // Intentionally do this a second time, as we are finding + TestFillEa (stopwatch2, eaVectorUint64.begin(), eaVectorUint64.end(), UINT64_C(37)); // the results are inconsistent otherwise. + if(EA::StdC::Memcheck64(&eaVectorUint64[0], UINT64_C(37), eaVectorUint64.size())) + EA::UnitTest::Report("eastl algorithm 64 bit fill failure."); + + if(i == 1) + Benchmark::AddResult("algorithm/fill/vector<uint64_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test fill_n + /////////////////////////////// + + TestFillNStd(stopwatch1, stdVectorUint64.begin(), (int)stdVectorUint64.size(), UINT64_C(37)); + TestFillNEa (stopwatch2, eaVectorUint64.begin(), (int) eaVectorUint64.size(), UINT64_C(37)); + TestFillNStd(stopwatch1, stdVectorUint64.begin(), (int)stdVectorUint64.size(), UINT64_C(37)); // Intentionally do this a second time, as we are finding + TestFillNEa (stopwatch2, eaVectorUint64.begin(), (int) eaVectorUint64.size(), UINT64_C(37)); // the results are inconsistent otherwise. + + if(i == 1) + Benchmark::AddResult("algorithm/fill_n/vector<uint64_t>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } +} + + +void BenchmarkAlgorithm5(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + std::vector<void*> stdVectorVoid(100000); + eastl::vector<void*> eaVectorVoid(100000); + + std::vector<char> stdVectorChar(100000); + eastl::vector<char> eaVectorChar(100000); + + std::vector<bool> stdVectorBool(100000); + eastl::vector<bool> eaVectorBool(100000); + + for(int i = 0; i < 2; i++) + { + TestFillStd(stopwatch1, stdVectorVoid.begin(), stdVectorVoid.end(), (void*)NULL); + TestFillEa (stopwatch2, eaVectorVoid.begin(), eaVectorVoid.end(), (void*)NULL); + + if(i == 1) + Benchmark::AddResult("algorithm/fill/vector<void*>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFillStd(stopwatch1, &stdVectorChar[0], &stdVectorChar[0] + stdVectorChar.size(), 'd'); // Intentionally use ' ' and not casted to any type. + TestFillEa (stopwatch2, eaVectorChar.data(), eaVectorChar.data() + eaVectorChar.size(), 'd'); + TestFillStd(stopwatch1, &stdVectorChar[0], &stdVectorChar[0] + stdVectorChar.size(), 'd'); // Intentionally do this a second time, as we are finding + TestFillEa (stopwatch2, eaVectorChar.data(), eaVectorChar.data() + eaVectorChar.size(), 'd'); // the results are inconsistent otherwise. + + if(i == 1) + Benchmark::AddResult("algorithm/fill/char[]/'d'", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFillStd(stopwatch1, stdVectorChar.begin(), stdVectorChar.end(), (char)'d'); + TestFillEa (stopwatch2, eaVectorChar.begin(), eaVectorChar.end(), (char)'d'); + TestFillStd(stopwatch1, stdVectorChar.begin(), stdVectorChar.end(), (char)'d'); // Intentionally do this a second time, as we are finding + TestFillEa (stopwatch2, eaVectorChar.begin(), eaVectorChar.end(), (char)'d'); // the results are inconsistent otherwise. + + if(i == 1) + Benchmark::AddResult("algorithm/fill/vector<char>/'d'", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFillStd(stopwatch1, stdVectorChar.begin(), stdVectorChar.end(), (char)0); + TestFillEa (stopwatch2, eaVectorChar.begin(), eaVectorChar.end(), (char)0); + TestFillStd(stopwatch1, stdVectorChar.begin(), stdVectorChar.end(), (char)0); // Intentionally do this a second time, as we are finding + TestFillEa (stopwatch2, eaVectorChar.begin(), eaVectorChar.end(), (char)0); // the results are inconsistent otherwise. + + if(i == 1) + Benchmark::AddResult("algorithm/fill/vector<char>/0", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFillStd(stopwatch1, eaVectorBool.data(), eaVectorBool.data() + eaVectorBool.size(), false); // Intentionally use eaVectorBool for the array. + TestFillEa (stopwatch2, eaVectorBool.data(), eaVectorBool.data() + eaVectorBool.size(), false); + TestFillStd(stopwatch1, eaVectorBool.data(), eaVectorBool.data() + eaVectorBool.size(), false); + TestFillEa (stopwatch2, eaVectorBool.data(), eaVectorBool.data() + eaVectorBool.size(), false); + + if(i == 1) + Benchmark::AddResult("algorithm/fill/bool[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test fill_n + /////////////////////////////// + + TestFillNStd(stopwatch1, eaVectorChar.data(), (int) eaVectorChar.size(), 'd'); // Intentionally use eaVectorBool for the array. + TestFillNEa (stopwatch2, eaVectorChar.data(), (int) eaVectorChar.size(), 'd'); + TestFillNStd(stopwatch1, eaVectorChar.data(), (int) eaVectorChar.size(), 'd'); // Intentionally do this a second time, as we are finding + TestFillNEa (stopwatch2, eaVectorChar.data(), (int) eaVectorChar.size(), 'd'); // the results are inconsistent otherwise. + + if(i == 1) + Benchmark::AddResult("algorithm/fill_n/char[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFillNStd(stopwatch1, eaVectorBool.data(), (int) eaVectorBool.size(), false); // Intentionally use eaVectorBool for the array. + TestFillNEa (stopwatch2, eaVectorBool.data(), (int) eaVectorBool.size(), false); + TestFillNStd(stopwatch1, eaVectorBool.data(), (int) eaVectorBool.size(), false); // Intentionally do this a second time, as we are finding + TestFillNEa (stopwatch2, eaVectorBool.data(), (int) eaVectorBool.size(), false); // the results are inconsistent otherwise. + + if(i == 1) + Benchmark::AddResult("algorithm/fill_n/bool[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } +} + + +void BenchmarkAlgorithm6(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + // We allocate this on the heap because some platforms don't always have enough stack space for this. + std::vector<LargePOD>* pstdVectorLP1 = new std::vector<LargePOD>(100); + std::vector<LargePOD>* pstdVectorLP2 = new std::vector<LargePOD>(100); + eastl::vector<LargePOD>* peaVectorLP1 = new eastl::vector<LargePOD>(100); + eastl::vector<LargePOD>* peaVectorLP2 = new eastl::vector<LargePOD>(100); + + // Aliases. + std::vector<LargePOD>& stdVectorLP1 = *pstdVectorLP1; + std::vector<LargePOD>& stdVectorLP2 = *pstdVectorLP2; + eastl::vector<LargePOD>& eaVectorLP1 = *peaVectorLP1; + eastl::vector<LargePOD>& eaVectorLP2 = *peaVectorLP2; + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test copy + /////////////////////////////// + + TestCopyStd(stopwatch1, stdVectorLP1.begin(), stdVectorLP1.end(), stdVectorLP2.begin()); + TestCopyEa (stopwatch2, eaVectorLP1.begin(), eaVectorLP1.end(), eaVectorLP2.begin()); + + if(i == 1) + Benchmark::AddResult("algorithm/copy/vector<LargePOD>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test copy_backward + /////////////////////////////// + + TestCopyBackwardStd(stopwatch1, stdVectorLP1.begin(), stdVectorLP1.end(), stdVectorLP2.end()); + TestCopyBackwardEa (stopwatch2, eaVectorLP1.begin(), eaVectorLP1.end(), eaVectorLP2.end()); + + if(i == 1) + Benchmark::AddResult("algorithm/copy_backward/vector<LargePOD>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + + delete pstdVectorLP1; + delete pstdVectorLP2; + delete peaVectorLP1; + delete peaVectorLP2; +} + + +void BenchmarkAlgorithm7(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + std::list<TestObject> stdListTO(10000); + eastl::list<TestObject> eaListTO(10000); + + std::vector<TestObject> stdVectorTO(10000); + eastl::vector<TestObject> eaVectorTO(10000); + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test reverse + /////////////////////////////// + + TestReverseStd(stopwatch1, stdListTO.begin(), stdListTO.end()); + TestReverseEa (stopwatch2, eaListTO.begin(), eaListTO.end()); + + if(i == 1) + Benchmark::AddResult("algorithm/reverse/list<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestReverseStd(stopwatch1, stdVectorTO.begin(), stdVectorTO.end()); + TestReverseEa (stopwatch2, eaVectorTO.begin(), eaVectorTO.end()); + + if(i == 1) + Benchmark::AddResult("algorithm/reverse/vector<TestObject>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } + + { + // Create some containers and seed them with incremental values (i.e. 0, 1, 2, 3...). + eastl::slist<int32_t> eaSlistIntLarge(10000); + eastl::generate(eaSlistIntLarge.begin(), eaSlistIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + + std::vector< SizedPOD<32> > stdVectorLargePod32(10000); + for(std::vector< SizedPOD<32> >::iterator it = stdVectorLargePod32.begin(); it != stdVectorLargePod32.end(); ++it) + memset(&*it, 0, sizeof(SizedPOD<32>)); + eastl::vector< SizedPOD<32> > eaVectorLargePod32(10000); + for(eastl::vector< SizedPOD<32> >::iterator it = eaVectorLargePod32.begin(); it != eaVectorLargePod32.end(); ++it) + memset(&*it, 0, sizeof(SizedPOD<32>)); + + std::list<int32_t> stdListIntLarge(10000); + eastl::generate(stdListIntLarge.begin(), stdListIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + eastl::list<int32_t> eaListIntLarge(10000); + eastl::generate(eaListIntLarge.begin(), eaListIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + + std::vector<int32_t> stdVectorIntLarge(10000); + eastl::generate(stdVectorIntLarge.begin(), stdVectorIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + eastl::vector<int32_t> eaVectorIntLarge(10000); + eastl::generate(eaVectorIntLarge.begin(), eaVectorIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + + std::list<int32_t> stdListIntSmall(10); + eastl::generate(stdListIntLarge.begin(), stdListIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + eastl::list<int32_t> eaListIntSmall(10); + eastl::generate(eaListIntLarge.begin(), eaListIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + + std::vector<int32_t> stdVectorIntSmall(10); + eastl::generate(stdVectorIntLarge.begin(), stdVectorIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + eastl::vector<int32_t> eaVectorIntSmall(10); + eastl::generate(eaVectorIntLarge.begin(), eaVectorIntLarge.end(), GenerateIncrementalIntegers<int32_t>()); + + + + std::list<TestObject> stdListTOLarge(10000); + eastl::generate(stdListTOLarge.begin(), stdListTOLarge.end(), GenerateIncrementalIntegers<TestObject>()); + + eastl::list<TestObject> eaListTOLarge(10000); + eastl::generate(eaListTOLarge.begin(), eaListTOLarge.end(), GenerateIncrementalIntegers<TestObject>()); + + + std::vector<TestObject> stdVectorTOLarge(10000); + eastl::generate(stdVectorTOLarge.begin(), stdVectorTOLarge.end(), GenerateIncrementalIntegers<TestObject>()); + + eastl::vector<TestObject> eaVectorTOLarge(10000); + eastl::generate(eaVectorTOLarge.begin(), eaVectorTOLarge.end(), GenerateIncrementalIntegers<TestObject>()); + + + std::list<TestObject> stdListTOSmall(10); + eastl::generate(stdListTOSmall.begin(), stdListTOSmall.end(), GenerateIncrementalIntegers<TestObject>()); + + eastl::list<TestObject> eaListTOSmall(10); + eastl::generate(eaListTOSmall.begin(), eaListTOSmall.end(), GenerateIncrementalIntegers<TestObject>()); + + + std::vector<TestObject> stdVectorTOSmall(10); + eastl::generate(stdVectorTOSmall.begin(), stdVectorTOSmall.end(), GenerateIncrementalIntegers<TestObject>()); + + eastl::vector<TestObject> eaVectorTOSmall(10); + eastl::generate(eaVectorTOSmall.begin(), eaVectorTOSmall.end(), GenerateIncrementalIntegers<TestObject>()); + + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test reverse + /////////////////////////////// + + // There is no guaranteed Standard Library forward_list or slist. + TestRotateEa (stopwatch2, eaSlistIntLarge.begin(), eastl::next( eaSlistIntLarge.begin(), (eaSlistIntLarge.size() / 2) - 1), eaSlistIntLarge.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/slist<int32_t> large", stopwatch1.GetUnits(), 0 /* untested */, stopwatch2.GetElapsedTime()); + + + + TestRotateStd(stopwatch1, stdVectorLargePod32.begin(), std__::next(stdVectorLargePod32.begin(), (stdVectorLargePod32.size() / 2) - 1), stdVectorLargePod32.end()); + TestRotateEa (stopwatch2, eaVectorLargePod32.begin(), eastl::next( eaVectorLargePod32.begin(), (eaVectorLargePod32.size() / 2) - 1), eaVectorLargePod32.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/vector<SizedPOD<32>> large", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + TestRotateStd(stopwatch1, stdListIntLarge.begin(), std__::next(stdListIntLarge.begin(), (stdListIntLarge.size() / 2) - 1), stdListIntLarge.end()); + TestRotateEa (stopwatch2, eaListIntLarge.begin(), eastl::next( eaListIntLarge.begin(), (eaListIntLarge.size() / 2) - 1), eaListIntLarge.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/list<int32_t> large", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestRotateStd(stopwatch1, stdVectorIntLarge.begin(), std__::next(stdVectorIntLarge.begin(), (stdVectorIntLarge.size() / 2) - 1), stdVectorIntLarge.end()); + TestRotateEa (stopwatch2, eaVectorIntLarge.begin(), eastl::next( eaVectorIntLarge.begin(), (eaVectorIntLarge.size() / 2) - 1), eaVectorIntLarge.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/vector<int32_t large>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + TestRotateStd(stopwatch1, stdListIntSmall.begin(), std__::next(stdListIntSmall.begin(), (stdListIntSmall.size() / 2) - 1), stdListIntSmall.end()); + TestRotateEa (stopwatch2, eaListIntSmall.begin(), eastl::next( eaListIntSmall.begin(), (eaListIntSmall.size() / 2) - 1), eaListIntSmall.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/list<int32_t> small", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestRotateStd(stopwatch1, stdVectorIntSmall.begin(), std__::next(stdVectorIntSmall.begin(), (stdVectorIntSmall.size() / 2) - 1), stdVectorIntSmall.end()); + TestRotateEa (stopwatch2, eaVectorIntSmall.begin(), eastl::next( eaVectorIntSmall.begin(), (eaVectorIntSmall.size() / 2) - 1), eaVectorIntSmall.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/vector<int32_t small>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + TestRotateStd(stopwatch1, stdListTOLarge.begin(), std__::next(stdListTOLarge.begin(), (stdListTOLarge.size() / 2) - 1), stdListTOLarge.end()); + TestRotateEa (stopwatch2, eaListTOLarge.begin(), eastl::next( eaListTOLarge.begin(), (eaListTOLarge.size() / 2) - 1), eaListTOLarge.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/list<TestObject large>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestRotateStd(stopwatch1, stdVectorTOLarge.begin(), std__::next(stdVectorTOLarge.begin(), (stdVectorTOLarge.size() / 2) - 1), stdVectorTOLarge.end()); + TestRotateEa (stopwatch2, eaVectorTOLarge.begin(), eastl::next( eaVectorTOLarge.begin(), (eaVectorTOLarge.size() / 2) - 1), eaVectorTOLarge.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/vector<TestObject large>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + TestRotateStd(stopwatch1, stdListTOSmall.begin(), std__::next(stdListTOSmall.begin(), (stdListTOSmall.size() / 2) - 1), stdListTOSmall.end()); + TestRotateEa (stopwatch2, eaListTOSmall.begin(), eastl::next( eaListTOSmall.begin(), (eaListTOSmall.size() / 2) - 1), eaListTOSmall.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/list<TestObject small>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestRotateStd(stopwatch1, stdVectorTOSmall.begin(), std__::next(stdVectorTOSmall.begin(), (stdVectorTOSmall.size() / 2) - 1), stdVectorTOSmall.end()); + TestRotateEa (stopwatch2, eaVectorTOSmall.begin(), eastl::next( eaVectorTOSmall.begin(), (eaVectorTOSmall.size() / 2) - 1), eaVectorTOSmall.end()); + if(i == 1) + Benchmark::AddResult("algorithm/rotate/vector<TestObject small>", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } +} + +void BenchmarkAlgorithm8(EASTLTest_Rand& rng, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + const uint32_t ElementCount = 10000; + + eastl::vector<int> srcVecA(ElementCount); + eastl::vector<int> srcVecB(ElementCount); + + std::vector<int> stdVecAInt(ElementCount); + std::vector<int> stdVecBInt(ElementCount); + std::vector<int> stdVecOutInt(2 * ElementCount); + std::vector<TestObject> stdVecATestObject(ElementCount); + std::vector<TestObject> stdVecBTestObject(ElementCount); + std::vector<TestObject> stdVecOutTestObject(2 * ElementCount); + + eastl::vector<int> eaVecAInt(ElementCount); + eastl::vector<int> eaVecBInt(ElementCount); + eastl::vector<int> eaVecOutInt(2 * ElementCount); + eastl::vector<TestObject> eaVecATestObject(ElementCount); + eastl::vector<TestObject> eaVecBTestObject(ElementCount); + eastl::vector<TestObject> eaVecOutTestObject(2 * ElementCount); + + // Note: + // In some cases the compiler may generate branch free code for the loop body of merge. + // In this situation the performance of merging data that has a random merge selection (i.e. the chance that the smallest + // element is taken from the first or second list is essentially random) is the same as merging data where the choice of + // which list has the smallest element is predictable. + // However, if the compiler doesn't generate branch free code, then the performance of merge will suffer from branch + // misprediction when merging random data and will benefit greatly when misprediction is rare. + // This benchmark is aimed at highlighting what sort of code is being generated, and also showing the impact of + // predictability of the comparisons performed during merge. The branch predictablity /can/ have a large impact + // on merge sort performance. + + // 'unpred' is the case where the comparison is unpredictable + // 'pred' is the case where the comparison is mostly predictable + const char* patternDescriptions[][2] = + { + { + "algorithm/merge/vector<int> (unpred)", + "algorithm/merge/vector<int> (pred)", + }, + { + "algorithm/merge/vector<TestObject> (unpred)", + "algorithm/merge/vector<TestObject> (pred)", + }, + }; + + enum Pattern + { + P_Random, + P_Predictable, + P_Count + }; + + for (int pattern = 0; pattern < P_Count; pattern++) + { + if (pattern == P_Random) + { + eastl::generate(srcVecA.begin(), srcVecA.end(), [&]{ return int(rng()); }); + eastl::sort(srcVecA.begin(), srcVecA.end()); + eastl::generate(srcVecB.begin(), srcVecB.end(), [&] { return int(rng()); }); + eastl::sort(srcVecB.begin(), srcVecB.end()); + } + else if (pattern == P_Predictable) + { + // The data pattern means that a simple/naive algorithm will select 'runLen' values + // from one list, and then 'runLen' values from the other list (alternating back and forth). + // Of course, a merge algorithm that is more complicated might have a different order of + // comparison. + const int runLen = 32; + for (int i = 0; i < ElementCount; i++) + { + int baseValue = ((i / runLen) * 2 * runLen) + (i % (runLen)); + srcVecA[i] = baseValue; + srcVecB[i] = baseValue + runLen; + } + } + + /////////////////////////////// + // Test merge + /////////////////////////////// + for (int i = 0; i < 2; i++) + { + eastl::copy(srcVecA.begin(), srcVecA.end(), stdVecAInt.begin()); + eastl::copy(srcVecB.begin(), srcVecB.end(), stdVecBInt.begin()); + eastl::copy(srcVecA.begin(), srcVecA.end(), eaVecAInt.begin()); + eastl::copy(srcVecB.begin(), srcVecB.end(), eaVecBInt.begin()); + TestMergeStd(stopwatch1, stdVecAInt.begin(), stdVecAInt.end(), stdVecBInt.begin(), stdVecBInt.end(), stdVecOutInt.begin()); + TestMergeEa(stopwatch2, eaVecAInt.begin(), eaVecAInt.end(), eaVecBInt.begin(), eaVecBInt.end(), eaVecOutInt.begin()); + + if (i == 1) + { + Benchmark::AddResult(patternDescriptions[0][pattern], stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + + for (int j = 0; j < ElementCount; j++) + { + stdVecATestObject[j] = TestObject(srcVecA[j]); + stdVecBTestObject[j] = TestObject(srcVecB[j]); + eaVecATestObject[j] = TestObject(srcVecA[j]); + eaVecBTestObject[j] = TestObject(srcVecB[j]); + } + TestMergeStd(stopwatch1, stdVecATestObject.begin(), stdVecATestObject.end(), stdVecBTestObject.begin(), stdVecBTestObject.end(), stdVecOutTestObject.begin()); + TestMergeEa(stopwatch2, eaVecATestObject.begin(), eaVecATestObject.end(), eaVecBTestObject.begin(), eaVecBTestObject.end(), eaVecOutTestObject.begin()); + + if (i == 1) + { + Benchmark::AddResult(patternDescriptions[1][pattern], stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } + } + +} + + + +void BenchmarkAlgorithm() +{ + EASTLTest_Printf("Algorithm\n"); + + EASTLTest_Rand rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + BenchmarkAlgorithm1(rng, stopwatch1, stopwatch2); + BenchmarkAlgorithm2(rng, stopwatch1, stopwatch2); + BenchmarkAlgorithm3(rng, stopwatch1, stopwatch2); + BenchmarkAlgorithm4(rng, stopwatch1, stopwatch2); + BenchmarkAlgorithm5(rng, stopwatch1, stopwatch2); + BenchmarkAlgorithm6(rng, stopwatch1, stopwatch2); + BenchmarkAlgorithm7(rng, stopwatch1, stopwatch2); + BenchmarkAlgorithm8(rng, stopwatch1, stopwatch2); +} + + + + + + + + + + + + + + + + |