diff options
Diffstat (limited to 'benchmark/source')
| -rw-r--r-- | benchmark/source/BenchmarkAlgorithm.cpp | 1241 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkBitset.cpp | 366 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkDeque.cpp | 342 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkHash.cpp | 469 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkHeap.cpp | 238 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkList.cpp | 382 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkMap.cpp | 382 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkSet.cpp | 353 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkSort.cpp | 1399 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkString.cpp | 531 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkTupleVector.cpp | 667 | ||||
| -rw-r--r-- | benchmark/source/BenchmarkVector.cpp | 452 | ||||
| -rw-r--r-- | benchmark/source/EASTLBenchmark.cpp | 291 | ||||
| -rw-r--r-- | benchmark/source/EASTLBenchmark.h | 228 | ||||
| -rw-r--r-- | benchmark/source/main.cpp | 194 |
15 files changed, 7535 insertions, 0 deletions
diff --git a/benchmark/source/BenchmarkAlgorithm.cpp b/benchmark/source/BenchmarkAlgorithm.cpp new file mode 100644 index 0000000..57e155e --- /dev/null +++ b/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); +} + + + + + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkBitset.cpp b/benchmark/source/BenchmarkBitset.cpp new file mode 100644 index 0000000..680622b --- /dev/null +++ b/benchmark/source/BenchmarkBitset.cpp @@ -0,0 +1,366 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#ifdef _MSC_VER + // Microsoft STL generates warnings. + #pragma warning(disable: 4267) // 'initializing' : conversion from 'size_t' to 'const int', possible loss of data +#endif + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/bitset.h> + + +EA_DISABLE_ALL_VC_WARNINGS() +#include <bitset> +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +namespace +{ + template <typename Bitset> + void TestSet(EA::StdC::Stopwatch& stopwatch, Bitset& b) + { + stopwatch.Restart(); + for(int i = 0; i < 100000; i++) + { + b.set(); + Benchmark::DoNothing(&b); + } + stopwatch.Stop(); + } + + + template <typename Bitset> + void TestSetIndex(EA::StdC::Stopwatch& stopwatch, Bitset& b, size_t index) + { + stopwatch.Restart(); + for(int i = 0; i < 100000; i++) + { + b.set(index); + Benchmark::DoNothing(&b); + } + stopwatch.Stop(); + } + + + template <typename Bitset> + void TestReset(EA::StdC::Stopwatch& stopwatch, Bitset& b) + { + stopwatch.Restart(); + for(int i = 0; i < 100000; i++) + { + b.reset(); + Benchmark::DoNothing(&b); + } + stopwatch.Stop(); + } + + + template <typename Bitset> + void TestFlip(EA::StdC::Stopwatch& stopwatch, Bitset& b) + { + stopwatch.Restart(); + for(int i = 0; i < 100000; i++) + { + b.flip(); + Benchmark::DoNothing(&b); + } + stopwatch.Stop(); + } + + + template <typename Bitset> + void TestTest(EA::StdC::Stopwatch& stopwatch, Bitset& b, unsigned nANDValue) + { + stopwatch.Restart(); + for(unsigned i = 0; i < 100000; i++) + Benchmark::DoNothing(b.test(i & nANDValue)); // We use & instead of % because the former is always fast due to forced power of 2. + stopwatch.Stop(); + } + + + template <typename Bitset> + void TestCount(EA::StdC::Stopwatch& stopwatch, Bitset& b) + { + size_t temp = 0; + stopwatch.Restart(); + for(int i = 0; i < 100000; i++) + { + temp += b.count(); + Benchmark::DoNothing(&temp); + } + stopwatch.Stop(); + } + + + template <typename Bitset> + void TestRightShift(EA::StdC::Stopwatch& stopwatch, Bitset& b, size_t n) + { + size_t temp = 0; + stopwatch.Restart(); + for(int i = 0; i < 100000; i++) + { + b >>= n; + Benchmark::DoNothing(&temp); + } + stopwatch.Stop(); + } + +} // namespace + + + +void BenchmarkBitset() +{ + EASTLTest_Printf("Bitset\n"); + + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + std::bitset<15> stdBitset15; + eastl::bitset<15> eaBitset15; + + std::bitset<35> stdBitset35; + eastl::bitset<35> eaBitset35; + + std::bitset<75> stdBitset75; + eastl::bitset<75> eaBitset75; + + std::bitset<1500> stdBitset1500; + eastl::bitset<1500> eaBitset1500; + + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test set() + /////////////////////////////// + + TestSet(stopwatch1, stdBitset15); + TestSet(stopwatch2, eaBitset15); + + if(i == 1) + Benchmark::AddResult("bitset<15>/set()", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSet(stopwatch1, stdBitset35); + TestSet(stopwatch2, eaBitset35); + + if(i == 1) + Benchmark::AddResult("bitset<35>/set()", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSet(stopwatch1, stdBitset75); + TestSet(stopwatch2, eaBitset75); + + if(i == 1) + Benchmark::AddResult("bitset<75>/set()", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSet(stopwatch1, stdBitset1500); + TestSet(stopwatch2, eaBitset1500); + + if(i == 1) + Benchmark::AddResult("bitset<1500>/set()", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test set(index) + /////////////////////////////// + + TestSetIndex(stopwatch1, stdBitset15, 13); + TestSetIndex(stopwatch2, eaBitset15, 13); + + if(i == 1) + Benchmark::AddResult("bitset<15>/set(i)", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSetIndex(stopwatch1, stdBitset35, 33); + TestSetIndex(stopwatch2, eaBitset35, 33); + + if(i == 1) + Benchmark::AddResult("bitset<35>/set(i)", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSetIndex(stopwatch1, stdBitset75, 73); + TestSetIndex(stopwatch2, eaBitset75, 73); + + if(i == 1) + Benchmark::AddResult("bitset<75>/set(i)", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSetIndex(stopwatch1, stdBitset1500, 730); + TestSetIndex(stopwatch2, eaBitset1500, 730); + + if(i == 1) + Benchmark::AddResult("bitset<1500>/set(i)", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test reset() + /////////////////////////////// + + TestReset(stopwatch1, stdBitset15); + TestReset(stopwatch2, eaBitset15); + + if(i == 1) + Benchmark::AddResult("bitset<15>/reset", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestReset(stopwatch1, stdBitset35); + TestReset(stopwatch2, eaBitset35); + + if(i == 1) + Benchmark::AddResult("bitset<35>/reset", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestReset(stopwatch1, stdBitset75); + TestReset(stopwatch2, eaBitset75); + + if(i == 1) + Benchmark::AddResult("bitset<75>/reset", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestReset(stopwatch1, stdBitset1500); + TestReset(stopwatch2, eaBitset1500); + + if(i == 1) + Benchmark::AddResult("bitset<1500>/reset", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test flip + /////////////////////////////// + + TestFlip(stopwatch1, stdBitset15); + TestFlip(stopwatch2, eaBitset15); + + if(i == 1) + Benchmark::AddResult("bitset<15>/flip", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFlip(stopwatch1, stdBitset35); + TestFlip(stopwatch2, eaBitset35); + + if(i == 1) + Benchmark::AddResult("bitset<35>/flip", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFlip(stopwatch1, stdBitset75); + TestFlip(stopwatch2, eaBitset75); + + if(i == 1) + Benchmark::AddResult("bitset<75>/flip", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFlip(stopwatch1, stdBitset1500); + TestFlip(stopwatch2, eaBitset1500); + + if(i == 1) + Benchmark::AddResult("bitset<1500>/flip", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test test + /////////////////////////////// + + TestTest(stopwatch1, stdBitset15, 7); + TestTest(stopwatch2, eaBitset15, 7); + + if(i == 1) + Benchmark::AddResult("bitset<15>/test", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestTest(stopwatch1, stdBitset35, 31); + TestTest(stopwatch2, eaBitset35, 31); + + if(i == 1) + Benchmark::AddResult("bitset<35>/test", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestTest(stopwatch1, stdBitset75, 63); + TestTest(stopwatch2, eaBitset75, 63); + + if(i == 1) + Benchmark::AddResult("bitset<75>/test", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestTest(stopwatch1, stdBitset1500, 1023); + TestTest(stopwatch2, eaBitset1500, 1023); + + if(i == 1) + Benchmark::AddResult("bitset<1500>/test", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test count + /////////////////////////////// + + TestCount(stopwatch1, stdBitset15); + TestCount(stopwatch2, eaBitset15); + + if(i == 1) + Benchmark::AddResult("bitset<15>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestCount(stopwatch1, stdBitset35); + TestCount(stopwatch2, eaBitset35); + + if(i == 1) + Benchmark::AddResult("bitset<35>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestCount(stopwatch1, stdBitset75); + TestCount(stopwatch2, eaBitset75); + + if(i == 1) + Benchmark::AddResult("bitset<75>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestCount(stopwatch1, stdBitset1500); + TestCount(stopwatch2, eaBitset1500); + + if(i == 1) + Benchmark::AddResult("bitset<1500>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test >>= + /////////////////////////////// + + TestRightShift(stopwatch1, stdBitset15, 1); + TestRightShift(stopwatch2, eaBitset15, 1); + + if(i == 1) + Benchmark::AddResult("bitset<15>/>>=/1", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime(), + GetStdSTLType() == kSTLPort ? "STLPort is broken, neglects wraparound check." : NULL); + + TestRightShift(stopwatch1, stdBitset35, 1); + TestRightShift(stopwatch2, eaBitset35, 1); + + if(i == 1) + Benchmark::AddResult("bitset<35>/>>=/1", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime(), + GetStdSTLType() == kSTLPort ? "STLPort is broken, neglects wraparound check." : NULL); + + TestRightShift(stopwatch1, stdBitset75, 1); + TestRightShift(stopwatch2, eaBitset75, 1); + + if(i == 1) + Benchmark::AddResult("bitset<75>/>>=/1", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime(), + GetStdSTLType() == kSTLPort ? "STLPort is broken, neglects wraparound check." : NULL); + + TestRightShift(stopwatch1, stdBitset1500, 1); + TestRightShift(stopwatch2, eaBitset1500, 1); + + if(i == 1) + Benchmark::AddResult("bitset<1500>/>>=/1", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime(), + GetStdSTLType() == kSTLPort ? "STLPort is broken, neglects wraparound check." : NULL); + } + } +} + + + + + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkDeque.cpp b/benchmark/source/BenchmarkDeque.cpp new file mode 100644 index 0000000..d3c69de --- /dev/null +++ b/benchmark/source/BenchmarkDeque.cpp @@ -0,0 +1,342 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/algorithm.h> +#include <EASTL/deque.h> +#include <EASTL/vector.h> +#include <EASTL/sort.h> + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) // behavior change: X called instead of Y +#endif +#include <algorithm> +#include <vector> +#include <deque> +#include <stdio.h> +#include <stdlib.h> +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; + + +namespace +{ + struct ValuePair + { + uint32_t key; + uint32_t v; + }; + + struct VPCompare + { + bool operator()(const ValuePair& vp1, const ValuePair& vp2) const + { + return (vp1.key == vp2.key) ? (vp1.v < vp2.v) : (vp1.key < vp2.key); + } + }; + + bool operator<(const ValuePair& vp1, const ValuePair& vp2) + { + return (vp1.key == vp2.key) ? (vp1.v < vp2.v) : (vp1.key < vp2.key); + } + + bool operator==(const ValuePair& vp1, const ValuePair& vp2) + { + return (vp1.key == vp2.key) && (vp1.v == vp2.v); + } +} + + +EASTL_DECLARE_POD(ValuePair) +EASTL_DECLARE_TRIVIAL_CONSTRUCTOR(ValuePair) +EASTL_DECLARE_TRIVIAL_COPY(ValuePair) +EASTL_DECLARE_TRIVIAL_ASSIGN(ValuePair) +EASTL_DECLARE_TRIVIAL_DESTRUCTOR(ValuePair) +EASTL_DECLARE_TRIVIAL_RELOCATE(ValuePair) + + + +typedef std::deque<ValuePair> StdDeque; +typedef eastl::deque<ValuePair, EASTLAllocatorType, 128> EaDeque; // What value do we pick for the subarray size to make the comparison fair? Using the default isn't ideal because it results in this test measuring speed efficiency and ignoring memory efficiency. + + + +namespace +{ + template <typename Container> + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector<uint32_t>& intVector) + { + stopwatch.Restart(); + for(eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) + { + const ValuePair vp = { intVector[j], intVector[j] }; + c.push_back(vp); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestPushFront(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector<uint32_t>& intVector) + { + stopwatch.Restart(); + for(eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) + { + const ValuePair vp = { intVector[j], intVector[j] }; + c.push_front(vp); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestBracket(EA::StdC::Stopwatch& stopwatch, Container& c) + { + uint64_t temp = 0; + stopwatch.Restart(); + for(typename Container::size_type j = 0, jEnd = c.size(); j < jEnd; j++) + temp += c[j].key; + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(temp & 0xffffffff)); + } + + + template <typename Container> + void TestIteration(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::iterator it = c.begin(), itEnd = c.end(); + stopwatch.Restart(); + while(it != itEnd) + ++it; + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(*it).key); + + /* Alternative way to measure: + const eastl_size_t n = c.size(); + stopwatch.Restart(); + for(eastl_size_t i = 0; i < n; ++i) + ++it; + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(*it).key); + */ + } + + + template <typename Container> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c) + { + // Intentionally use eastl find in order to measure just + // vector access speed and not be polluted by sort speed. + const ValuePair vp = { 0xffffffff, 0 }; + stopwatch.Restart(); + typename Container::iterator it = eastl::find(c.begin(), c.end(), vp); + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(*it).key); + } + + + template <typename Container> + void TestSort(EA::StdC::Stopwatch& stopwatch, Container& c) + { + // Intentionally use eastl sort in order to measure just + // vector access speed and not be polluted by sort speed. + VPCompare vpCompare; + stopwatch.Restart(); + eastl::quick_sort(c.begin(), c.end(), vpCompare); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c[0].key); + } + + + template <typename Container> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c) + { + const ValuePair vp = { 0xffffffff, 0 }; + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = 2000, it = c.begin(); j < jEnd; ++j) + { + it = c.insert(it, vp); + + if(it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestErase(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = 2000, it = c.begin(); j < jEnd; ++j) + { + it = c.erase(it); + + if(it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + +} // namespace + + + +void BenchmarkDeque() +{ + EASTLTest_Printf("Deque\n"); + + EA::UnitTest::RandGenT<uint32_t> rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { // 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(100000); + eastl::generate(intVector.begin(), intVector.end(), rng); + + for(int i = 0; i < 2; i++) + { + StdDeque stdDeque; + EaDeque eaDeque; + + + /////////////////////////////// + // Test push_back + /////////////////////////////// + + TestPushBack(stopwatch1, stdDeque, intVector); + TestPushBack(stopwatch2, eaDeque, intVector); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test push_front + /////////////////////////////// + + TestPushFront(stopwatch1, stdDeque, intVector); + TestPushFront(stopwatch2, eaDeque, intVector); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/push_front", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[] + /////////////////////////////// + + TestBracket(stopwatch1, stdDeque); + TestBracket(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration + /////////////////////////////// + + TestIteration(stopwatch1, stdDeque); + TestIteration(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find() + /////////////////////////////// + + TestFind(stopwatch1, stdDeque); + TestFind(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test sort + /////////////////////////////// + + // Currently VC++ complains about our sort function decrementing std::iterator that is already at begin(). In the strictest sense, + // that's a valid complaint, but we aren't testing std STL here. We will want to revise our sort function eventually. + #if !defined(_MSC_VER) || !defined(_ITERATOR_DEBUG_LEVEL) || (_ITERATOR_DEBUG_LEVEL < 2) + TestSort(stopwatch1, stdDeque); + TestSort(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + #endif + + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestInsert(stopwatch1, stdDeque); + TestInsert(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestErase(stopwatch1, stdDeque); + TestErase(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque<ValuePair>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } +} + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkHash.cpp b/benchmark/source/BenchmarkHash.cpp new file mode 100644 index 0000000..35470e7 --- /dev/null +++ b/benchmark/source/BenchmarkHash.cpp @@ -0,0 +1,469 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/vector.h> +#include <EASTL/hash_map.h> +#include <EASTL/string.h> +#include <EASTL/algorithm.h> + + + +EA_DISABLE_ALL_VC_WARNINGS() +#include <unordered_map> +#include <string> +#include <algorithm> +#include <stdio.h> +EA_RESTORE_ALL_VC_WARNINGS() + + + +using namespace EA; + + +// HashString8 +// +// We define a string +// +template <typename String> +struct HashString8 +{ + // Defined for EASTL, STLPort, SGI, etc. and Metrowerks-related hash tables: + size_t operator()(const String& s) const + { + const uint8_t* p = (const uint8_t*) s.c_str(); + uint32_t c, stringHash = UINT32_C(2166136261); + while((c = *p++) != 0) + stringHash = (stringHash * 16777619) ^ c; + return stringHash; + } + + // Defined for Dinkumware-related (e.g. MS STL) hash tables: + bool operator()(const String& s1, const String& s2) const + { + return s1 < s2; + } + + // Defined for Dinkumware-related (e.g. MS STL) hash tables: + enum { + bucket_size = 7, + min_buckets = 8 + }; +}; + + +using StdMapUint32TO = std::unordered_map<uint32_t, TestObject>; +using StdMapStrUint32 = std::unordered_map<std::string, uint32_t, HashString8<std::string>>; + +using EaMapUint32TO = eastl::hash_map<uint32_t, TestObject>; +using EaMapStrUint32 = eastl::hash_map<eastl::string, uint32_t, HashString8<eastl::string>>; + + +namespace +{ + template <typename Container, typename Value> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + c.insert(pArrayBegin, pArrayEnd); + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestIteration(EA::StdC::Stopwatch& stopwatch, const Container& c, const Value& findValue) + { + stopwatch.Restart(); + typename Container::const_iterator it = eastl::find(c.begin(), c.end(), findValue); // It shouldn't matter what find implementation we use here, as it merely iterates values. + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%p", &*it); + } + + + template <typename Container, typename Value> + void TestBracket(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(&c[pArrayBegin->first]); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + typename Container::iterator it = c.find(pArrayBegin->first); + Benchmark::DoNothing(&it); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestFindAsStd(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + typename Container::iterator it = c.find(pArrayBegin->first.c_str()); + Benchmark::DoNothing(&it); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestFindAsEa(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + typename Container::iterator it = c.find_as(pArrayBegin->first.c_str()); + Benchmark::DoNothing(&it); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestCount(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + typename Container::size_type temp = 0; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + temp += c.count(pArrayBegin->first); + ++pArrayBegin; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container, typename Value> + void TestEraseValue(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + c.erase(pArrayBegin->first); + ++pArrayBegin; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + + template <typename Container> + void TestErasePosition(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = c.size() / 3, it = c.begin(); j < jEnd; ++j) + { + // The erase fucntion is supposed to return an iterator, but the C++ standard was + // not initially clear about it and some STL implementations don't do it correctly. + #if (defined(_MSC_VER) || defined(_CPPLIB_VER)) // _CPPLIB_VER is something defined by Dinkumware STL. + it = c.erase(it); + #else + // This pathway may execute at a slightly different speed than the + // standard behaviour, but that's fine for the benchmark because the + // benchmark is measuring the speed of erasing while iterating, and + // however it needs to get done by the given STL is how it is measured. + const typename Container::iterator itErase(it++); + c.erase(itErase); + #endif + + ++it; + ++it; + } + + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p %p", &c, &it); + } + + + template <typename Container> + void TestEraseRange(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it1 = c.begin(); + typename Container::iterator it2 = c.begin(); + + for(j = 0, jEnd = c.size() / 3; j < jEnd; ++j) + ++it2; + + stopwatch.Restart(); + c.erase(it1, it2); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p %p %p", &c, &it1, &it2); + } + + + template <typename Container> + void TestClear(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + c.clear(); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + +} // namespace + + + +void BenchmarkHash() +{ + EASTLTest_Printf("HashMap\n"); + + EA::UnitTest::Rand rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector< std::pair<uint32_t, TestObject> > stdVectorUT(10000); + eastl::vector< eastl::pair<uint32_t, TestObject> > eaVectorUT(10000); + + eastl::vector< std::pair< std::string, uint32_t> > stdVectorSU(10000); + eastl::vector< eastl::pair<eastl::string, uint32_t> > eaVectorSU(10000); + + for(eastl_size_t i = 0, iEnd = stdVectorUT.size(); i < iEnd; i++) + { + const uint32_t n1 = rng.RandLimit((uint32_t)(iEnd / 2)); + const uint32_t n2 = rng.RandValue(); + + stdVectorUT[i] = std::pair<uint32_t, TestObject>(n1, TestObject(n2)); + eaVectorUT[i] = eastl::pair<uint32_t, TestObject>(n1, TestObject(n2)); + + char str_n1[32]; + sprintf(str_n1, "%u", (unsigned)n1); + + stdVectorSU[i] = std::pair< std::string, uint32_t>( std::string(str_n1), n2); + eaVectorSU[i] = eastl::pair<eastl::string, uint32_t>(eastl::string(str_n1), n2); + } + + for(int i = 0; i < 2; i++) + { + StdMapUint32TO stdMapUint32TO; + EaMapUint32TO eaMapUint32TO; + + StdMapStrUint32 stdMapStrUint32; + EaMapStrUint32 eaMapStrUint32; + + + /////////////////////////////// + // Test insert(const value_type&) + /////////////////////////////// + + TestInsert(stopwatch1, stdMapUint32TO, stdVectorUT.data(), stdVectorUT.data() + stdVectorUT.size()); + TestInsert(stopwatch2, eaMapUint32TO, eaVectorUT.data(), eaVectorUT.data() + eaVectorUT.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestInsert(stopwatch1, stdMapStrUint32, stdVectorSU.data(), stdVectorSU.data() + stdVectorSU.size()); + TestInsert(stopwatch2, eaMapStrUint32, eaVectorSU.data(), eaVectorSU.data() + eaVectorSU.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration + /////////////////////////////// + + TestIteration(stopwatch1, stdMapUint32TO, StdMapUint32TO::value_type(9999999, TestObject(9999999))); + TestIteration(stopwatch2, eaMapUint32TO, EaMapUint32TO::value_type(9999999, TestObject(9999999))); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestIteration(stopwatch1, stdMapStrUint32, StdMapStrUint32::value_type( std::string("9999999"), 9999999)); + TestIteration(stopwatch2, eaMapStrUint32, EaMapStrUint32::value_type(eastl::string("9999999"), 9999999)); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[] + /////////////////////////////// + + TestBracket(stopwatch1, stdMapUint32TO, stdVectorUT.data(), stdVectorUT.data() + stdVectorUT.size()); + TestBracket(stopwatch2, eaMapUint32TO, eaVectorUT.data(), eaVectorUT.data() + eaVectorUT.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestBracket(stopwatch1, stdMapStrUint32, stdVectorSU.data(), stdVectorSU.data() + stdVectorSU.size()); + TestBracket(stopwatch2, eaMapStrUint32, eaVectorSU.data(), eaVectorSU.data() + eaVectorSU.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find + /////////////////////////////// + + TestFind(stopwatch1, stdMapUint32TO, stdVectorUT.data(), stdVectorUT.data() + stdVectorUT.size()); + TestFind(stopwatch2, eaMapUint32TO, eaVectorUT.data(), eaVectorUT.data() + eaVectorUT.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFind(stopwatch1, stdMapStrUint32, stdVectorSU.data(), stdVectorSU.data() + stdVectorSU.size()); + TestFind(stopwatch2, eaMapStrUint32, eaVectorSU.data(), eaVectorSU.data() + eaVectorSU.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find_as + /////////////////////////////// + + TestFindAsStd(stopwatch1, stdMapStrUint32, stdVectorSU.data(), stdVectorSU.data() + stdVectorSU.size()); + TestFindAsEa(stopwatch2, eaMapStrUint32, eaVectorSU.data(), eaVectorSU.data() + eaVectorSU.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/find_as/char*", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test count + /////////////////////////////// + + TestCount(stopwatch1, stdMapUint32TO, stdVectorUT.data(), stdVectorUT.data() + stdVectorUT.size()); + TestCount(stopwatch2, eaMapUint32TO, eaVectorUT.data(), eaVectorUT.data() + eaVectorUT.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestCount(stopwatch1, stdMapStrUint32, stdVectorSU.data(), stdVectorSU.data() + stdVectorSU.size()); + TestCount(stopwatch2, eaMapStrUint32, eaVectorSU.data(), eaVectorSU.data() + eaVectorSU.size()); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(const key_type& key) + /////////////////////////////// + + TestEraseValue(stopwatch1, stdMapUint32TO, stdVectorUT.data(), stdVectorUT.data() + (stdVectorUT.size() / 2)); + TestEraseValue(stopwatch2, eaMapUint32TO, eaVectorUT.data(), eaVectorUT.data() + (eaVectorUT.size() / 2)); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/erase val", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestEraseValue(stopwatch1, stdMapStrUint32, stdVectorSU.data(), stdVectorSU.data() + (stdVectorSU.size() / 2)); + TestEraseValue(stopwatch2, eaMapStrUint32, eaVectorSU.data(), eaVectorSU.data() + (eaVectorSU.size() / 2)); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/erase val", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(iterator position) + /////////////////////////////// + + TestErasePosition(stopwatch1, stdMapUint32TO); + TestErasePosition(stopwatch2, eaMapUint32TO); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/erase pos", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestErasePosition(stopwatch1, stdMapStrUint32); + TestErasePosition(stopwatch2, eaMapStrUint32); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/erase pos", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(iterator first, iterator last) + /////////////////////////////// + + TestEraseRange(stopwatch1, stdMapUint32TO); + TestEraseRange(stopwatch2, eaMapUint32TO); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/erase range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestEraseRange(stopwatch1, stdMapStrUint32); + TestEraseRange(stopwatch2, eaMapStrUint32); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/erase range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test clear() + /////////////////////////////// + + // Clear the containers of whatever they happen to have. We want the containers to have full data. + TestClear(stopwatch1, stdMapUint32TO); + TestClear(stopwatch2, eaMapUint32TO); + TestClear(stopwatch1, stdMapStrUint32); + TestClear(stopwatch2, eaMapStrUint32); + + // Re-set the containers with full data. + TestInsert(stopwatch1, stdMapUint32TO, stdVectorUT.data(), stdVectorUT.data() + stdVectorUT.size()); + TestInsert(stopwatch2, eaMapUint32TO, eaVectorUT.data(), eaVectorUT.data() + eaVectorUT.size()); + TestInsert(stopwatch1, stdMapStrUint32, stdVectorSU.data(), stdVectorSU.data() + stdVectorSU.size()); + TestInsert(stopwatch2, eaMapStrUint32, eaVectorSU.data(), eaVectorSU.data() + eaVectorSU.size()); + + // Now clear the data again, this time measuring it. + TestClear(stopwatch1, stdMapUint32TO); + TestClear(stopwatch2, eaMapUint32TO); + + if(i == 1) + Benchmark::AddResult("hash_map<uint32_t, TestObject>/clear", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestClear(stopwatch1, stdMapStrUint32); + TestClear(stopwatch2, eaMapStrUint32); + + if(i == 1) + Benchmark::AddResult("hash_map<string, uint32_t>/clear", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + } + } +} + + + + + + + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkHeap.cpp b/benchmark/source/BenchmarkHeap.cpp new file mode 100644 index 0000000..635cf31 --- /dev/null +++ b/benchmark/source/BenchmarkHeap.cpp @@ -0,0 +1,238 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/heap.h> +#include <EASTL/vector.h> +#include <EASTL/algorithm.h> + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) // behavior change: X called instead of Y +#endif +#include <algorithm> +#include <vector> +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; + + +namespace +{ + template <typename Iterator> + void TestMakeHeapStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + std::make_heap(first, last); + stopwatch.Stop(); + } + + template <typename Iterator> + void TestMakeHeapEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + eastl::make_heap(first, last); + stopwatch.Stop(); + } + + + + template <typename Iterator1, typename Iterator2> + void TestPushHeapStd(EA::StdC::Stopwatch& stopwatch, Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) + { + stopwatch.Restart(); + while(first2 != last2) + { + *last1++ = *first2++; + std::push_heap(first1, last1); + } + stopwatch.Stop(); + } + + template <typename Iterator1, typename Iterator2> + void TestPushHeapEa(EA::StdC::Stopwatch& stopwatch, Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) + { + stopwatch.Restart(); + while(first2 != last2) + { + *last1++ = *first2++; + eastl::push_heap(first1, last1); + } + stopwatch.Stop(); + } + + + + template <typename Iterator> + void TestPopHeapStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, Iterator popEnd) + { + stopwatch.Restart(); + while(last != popEnd) + std::pop_heap(first, last--); + stopwatch.Stop(); + } + + template <typename Iterator> + void TestPopHeapEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last, Iterator popEnd) + { + stopwatch.Restart(); + while(last != popEnd) + eastl::pop_heap(first, last--); + stopwatch.Stop(); + } + + + + template <typename Iterator> + void TestSortHeapStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + std::sort_heap(first, last); + stopwatch.Stop(); + } + + template <typename Iterator> + void TestSortHeapEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + eastl::sort_heap(first, last); + stopwatch.Stop(); + } + +} // namespace + + + +void BenchmarkHeap() +{ + EASTLTest_Printf("Heap (Priority Queue)\n"); + + EA::UnitTest::RandGenT<uint32_t> rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + const int kArraySize = 100000; + + // uint32[] + uint32_t* const pIntArrayS = new uint32_t[kArraySize * 2]; // * 2 because we will be adding more items via push_heap. + uint32_t* const pIntArrayE = new uint32_t[kArraySize * 2]; // S means Std; E means EA. + uint32_t* const pIntArray2 = new uint32_t[kArraySize]; // This will be used for pop_heap. + + eastl::generate(pIntArrayS, pIntArrayS + kArraySize, rng); + eastl::copy(pIntArrayS, pIntArrayS + kArraySize, pIntArrayE); + eastl::copy(pIntArrayS, pIntArrayS + kArraySize, pIntArray2); + + + // vector<TestObject> + std::vector<TestObject> stdVectorTO(kArraySize * 2); + std::vector<TestObject> stdVectorTO2(kArraySize); + eastl::vector<TestObject> eaVectorTO(kArraySize * 2); + eastl::vector<TestObject> eaVectorTO2(kArraySize); + + for(int k = 0; k < kArraySize; k++) + { + stdVectorTO[k] = TestObject(pIntArrayS[k]); + stdVectorTO2[k] = TestObject(pIntArrayS[k]); + eaVectorTO[k] = TestObject(pIntArrayS[k]); + eaVectorTO2[k] = TestObject(pIntArrayS[k]); + } + + + for(int i = 0; i < 2; i++) + { + /////////////////////////////// + // Test make_heap + /////////////////////////////// + + TestMakeHeapStd(stopwatch1, pIntArrayS, pIntArrayS + kArraySize); + TestMakeHeapEa (stopwatch2, pIntArrayE, pIntArrayE + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (uint32_t[])/make_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestMakeHeapStd(stopwatch1, stdVectorTO.begin(), stdVectorTO.begin() + kArraySize); + TestMakeHeapEa (stopwatch2, eaVectorTO.begin(), eaVectorTO.begin() + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (vector<TestObject>)/make_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test push_heap + /////////////////////////////// + + TestPushHeapStd(stopwatch1, pIntArrayS, pIntArrayS + kArraySize, pIntArray2, pIntArray2 + kArraySize); + TestPushHeapEa (stopwatch2, pIntArrayE, pIntArrayE + kArraySize, pIntArray2, pIntArray2 + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (uint32_t[])/push_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestPushHeapStd(stopwatch1, stdVectorTO.begin(), stdVectorTO.begin() + kArraySize, stdVectorTO2.begin(), stdVectorTO2.begin() + kArraySize); + TestPushHeapEa (stopwatch2, eaVectorTO.begin(), eaVectorTO.begin() + kArraySize, eaVectorTO2.begin(), eaVectorTO2.begin() + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (vector<TestObject>)/push_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test pop_heap + /////////////////////////////// + + TestPopHeapStd(stopwatch1, pIntArrayS, pIntArrayS + (kArraySize * 2), pIntArrayS + kArraySize); // * 2 because we used push_heap above to add more items. + TestPopHeapEa (stopwatch2, pIntArrayE, pIntArrayE + (kArraySize * 2), pIntArrayE + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (uint32_t[])/pop_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestPopHeapStd(stopwatch1, stdVectorTO.begin(), stdVectorTO.begin() + (kArraySize * 2), stdVectorTO.begin() + kArraySize); // * 2 because we used push_heap above to add more items. + TestPopHeapEa (stopwatch2, eaVectorTO.begin(), eaVectorTO.begin() + (kArraySize * 2), eaVectorTO.begin() + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (vector<TestObject>)/pop_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test sort_heap + /////////////////////////////// + + TestSortHeapStd(stopwatch1, pIntArrayS, pIntArrayS + kArraySize); + TestSortHeapEa (stopwatch2, pIntArrayE, pIntArrayE + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (uint32_t[])/sort_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSortHeapStd(stopwatch1, stdVectorTO.begin(), stdVectorTO.begin() + kArraySize); + TestSortHeapEa (stopwatch2, eaVectorTO.begin(), eaVectorTO.begin() + kArraySize); + + if(i == 1) + Benchmark::AddResult("heap (vector<TestObject>)/sort_heap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + + delete[] pIntArrayS; + delete[] pIntArrayE; + delete[] pIntArray2; + } +} + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkList.cpp b/benchmark/source/BenchmarkList.cpp new file mode 100644 index 0000000..1d22ad8 --- /dev/null +++ b/benchmark/source/BenchmarkList.cpp @@ -0,0 +1,382 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/list.h> +#include <EASTL/vector.h> +#include <EASTL/algorithm.h> +#include <EASTL/random.h> + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4555) // expression has no effect; expected expression with side-effect + #pragma warning(disable: 4350) // behavior change: X called instead of Y +#endif +#include <list> +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; +using namespace eastl; + + + +typedef std::list<TestObject> StdListTO; +typedef eastl::list<TestObject> EaListTO; + + + +namespace +{ + void DoNothing(void*) + { + // Empty + } + + + template <typename ContainerSource, typename Container> + void TestCtorIterator(EA::StdC::Stopwatch& stopwatch, const ContainerSource& cs, Container*) // Dummy Container argument because of GCC 2.X limitations. + { + stopwatch.Restart(); + Container c(cs.begin(), cs.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + + + template <typename Container> + void TestCtorN(EA::StdC::Stopwatch& stopwatch, Container*) // Dummy Container argument because of GCC 2.X limitations. + { + stopwatch.Restart(); + Container c(10000); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + + + template <typename Container> + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c, const TestObject* pTOBegin, const TestObject* const pTOEnd) + { + stopwatch.Restart(); + while(pTOBegin != pTOEnd) + c.push_back(*pTOBegin++); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + + + template <typename Container> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c, const TestObject* pTOBegin, const TestObject* const pTOEnd) + { + typename Container::iterator it = c.begin(); + stopwatch.Restart(); + while(pTOBegin != pTOEnd) + { + it = c.insert(it, *pTOBegin++); + + if(++it == c.end()) // Try to safely increment the iterator a couple times + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + + + template <typename Container> + void TestSize(EA::StdC::Stopwatch& stopwatch, Container& c, void (*pFunction)(...)) + { + stopwatch.Restart(); + for(int i = 0; (i < 10000) && c.size(); i++) + (*pFunction)(&c); + stopwatch.Stop(); + } + + + template <typename Container> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c, const TestObject& to) + { + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + stopwatch.Restart(); + typename Container::iterator it = eastl::find(c.begin(), c.end(), to); + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%d", (*it).mX); + } + + + template <typename Container> + void TestReverse(EA::StdC::Stopwatch& stopwatch, Container& c) + { + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + stopwatch.Restart(); + c.reverse(); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + + + template <typename Container> + void TestRemove(EA::StdC::Stopwatch& stopwatch, Container& c, const TestObject* pTOBegin, const TestObject* const pTOEnd) + { + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + stopwatch.Restart(); + while(pTOBegin != pTOEnd) + c.remove(*pTOBegin++); + stopwatch.Stop(); + if(!c.empty()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + + + template <typename Container> + void TestSplice(EA::StdC::Stopwatch& stopwatch, Container& c, Container& cSource) + { + typename Container::iterator it = c.begin(); + int i = 0, iEnd = (int)cSource.size() - 5; + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + stopwatch.Restart(); + while(i++ != iEnd) + c.splice(it, cSource, cSource.begin()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + + + template <typename Container> + void TestErase(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::iterator it = c.begin(); + int i = 0, iEnd = (int)c.size() - 5; + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + stopwatch.Restart(); + while(i++ != iEnd) + { + it = c.erase(it); + + if(it == c.end()) // Try to safely increment the iterator a couple times + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.back().mX); + } + +} // namespace + + + + +void BenchmarkList() +{ + EASTLTest_Printf("List\n"); + + EASTLTest_Rand rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + EaListTO eaListTO_1(1); + EaListTO eaListTO_10(10); + EaListTO eaListTO_100(100); + StdListTO stdListTO_1(1); + StdListTO stdListTO_10(10); + StdListTO stdListTO_100(100); + + { + char buffer[32]; + sprintf(buffer, "%p", &DoNothing); + } + + { + eastl::vector<TestObject> toVector(100000); + for(eastl_size_t i = 0, iEnd = toVector.size(); i < iEnd; ++i) + toVector[i] = TestObject((int)i); + random_shuffle(toVector.begin(), toVector.end(), rng); + + + for(int i = 0; i < 2; i++) + { + StdListTO stdListTO; + EaListTO eaListTO; + + + /////////////////////////////// + // Test list(InputIterator first, InputIterator last) + /////////////////////////////// + + TestCtorIterator(stopwatch1, toVector, &stdListTO); + TestCtorIterator(stopwatch2, toVector, &eaListTO); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/ctor(it)", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test list(size_type n) + /////////////////////////////// + + TestCtorN(stopwatch1, &stdListTO); + TestCtorN(stopwatch2, &eaListTO); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/ctor(n)", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test push_back() + /////////////////////////////// + + TestPushBack(stopwatch1, stdListTO, toVector.data(), toVector.data() + toVector.size()); + TestPushBack(stopwatch2, eaListTO, toVector.data(), toVector.data() + toVector.size()); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test insert() + /////////////////////////////// + + TestInsert(stopwatch1, stdListTO, toVector.data(), toVector.data() + toVector.size()); + TestInsert(stopwatch2, eaListTO, toVector.data(), toVector.data() + toVector.size()); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test size() + /////////////////////////////// + + TestSize(stopwatch1, stdListTO_1, Benchmark::DoNothing); + TestSize(stopwatch2, eaListTO_1, Benchmark::DoNothing); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/size/1", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSize(stopwatch1, stdListTO_10, Benchmark::DoNothing); + TestSize(stopwatch2, eaListTO_10, Benchmark::DoNothing); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/size/10", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime() + #if !EASTL_LIST_SIZE_CACHE + , "EASTL is configured to not cache the list size." + #endif + ); + + TestSize(stopwatch1, stdListTO_100, Benchmark::DoNothing); + TestSize(stopwatch2, eaListTO_100, Benchmark::DoNothing); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/size/100", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime() + #if !EASTL_LIST_SIZE_CACHE + , "EASTL is configured to not cache the list size." + #endif + ); + + + + /////////////////////////////// + // Test find() + /////////////////////////////// + + TestFind(stopwatch1, stdListTO, TestObject(99999999)); + TestFind(stopwatch2, eaListTO, TestObject(99999999)); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test reverse() + /////////////////////////////// + + TestReverse(stopwatch1, stdListTO); + TestReverse(stopwatch2, eaListTO); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/reverse", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test remove() + /////////////////////////////// + + random_shuffle(toVector.begin(), toVector.end(), rng); + TestRemove(stopwatch1, stdListTO, &toVector[0], &toVector[20]); + TestRemove(stopwatch2, eaListTO, &toVector[0], &toVector[20]); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/remove", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test splice() + /////////////////////////////// + StdListTO listCopyStd(stdListTO); + EaListTO listCopyEa(eaListTO); + + TestSplice(stopwatch1, stdListTO, listCopyStd); + TestSplice(stopwatch2, eaListTO, listCopyEa); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/splice", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test erase() + /////////////////////////////// + + TestErase(stopwatch1, stdListTO); + TestErase(stopwatch2, eaListTO); + + if(i == 1) + Benchmark::AddResult("list<TestObject>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } +} + + + + + + + + + + + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkMap.cpp b/benchmark/source/BenchmarkMap.cpp new file mode 100644 index 0000000..d2fc35e --- /dev/null +++ b/benchmark/source/BenchmarkMap.cpp @@ -0,0 +1,382 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/map.h> +#include <EASTL/vector.h> +#include <EASTL/algorithm.h> + +EA_DISABLE_ALL_VC_WARNINGS() +#include <map> +#include <algorithm> +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +typedef std::map<TestObject, uint32_t> StdMapTOUint32; +typedef eastl::map<TestObject, uint32_t> EaMapTOUint32; + + +namespace +{ + template <typename Container, typename Value> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd, const Value& highValue) + { + stopwatch.Restart(); + c.insert(pArrayBegin, pArrayEnd); + stopwatch.Stop(); + c.insert(highValue); + } + + + template <typename Container, typename Value> + void TestIteration(EA::StdC::Stopwatch& stopwatch, const Container& c, const Value& findValue) + { + stopwatch.Restart(); + typename Container::const_iterator it = eastl::find(c.begin(), c.end(), findValue); // It shouldn't matter what find implementation we use here, as it merely iterates values. + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%p", &*it); + } + + + template <typename Container, typename Value> + void TestBracket(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c[pArrayBegin->first]); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.find(pArrayBegin->first)->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestCount(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + typename Container::size_type temp = 0; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + temp += c.count(pArrayBegin->first); + ++pArrayBegin; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container, typename Value> + void TestLowerBound(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.lower_bound(pArrayBegin->first)->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestUpperBound(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.upper_bound(pArrayBegin->first)->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestEqualRange(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.equal_range(pArrayBegin->first).second->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestEraseValue(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + c.erase(pArrayBegin->first); + ++pArrayBegin; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + + template <typename Container> + void TestErasePosition(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = c.size() / 3, it = c.begin(); j < jEnd; ++j) + { + // The erase fucntion is supposed to return an iterator, but the C++ standard was + // not initially clear about it and some STL implementations don't do it correctly. + #if (((defined(_MSC_VER) || defined(_CPPLIB_VER)) && !defined(_HAS_STRICT_CONFORMANCE))) // _CPPLIB_VER is something defined by Dinkumware STL. + it = c.erase(it); // Standard behavior. + #else + // This pathway may execute at a slightly different speed than the + // standard behaviour, but that's fine for the benchmark because the + // benchmark is measuring the speed of erasing while iterating, and + // however it needs to get done by the given STL is how it is measured. + const typename Container::iterator itErase(it++); + c.erase(itErase); + #endif + + ++it; + ++it; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p %p", &c, &it); + } + + + template <typename Container> + void TestEraseRange(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it1 = c.begin(); + typename Container::iterator it2 = c.begin(); + + for(j = 0, jEnd = c.size() / 3; j < jEnd; ++j) + ++it2; + + stopwatch.Restart(); + c.erase(it1, it2); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p %p %p", &c, &it1, &it2); + } + + + template <typename Container> + void TestClear(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + c.clear(); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + +} // namespace + + + +void BenchmarkMap() +{ + EASTLTest_Printf("Map\n"); + + EA::UnitTest::Rand rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector< std::pair<TestObject, uint32_t> > stdVector(10000); + eastl::vector< eastl::pair<TestObject, uint32_t> > eaVector(10000); + + for(eastl_size_t i = 0, iEnd = stdVector.size(); i < iEnd; i++) + { + const uint32_t n1 = rng.RandLimit(((uint32_t)iEnd / 2)); + const uint32_t n2 = rng.RandValue(); + + stdVector[i] = std::pair<TestObject, uint32_t>(TestObject(n1), n2); + eaVector[i] = eastl::pair<TestObject, uint32_t>(TestObject(n1), n2); + } + + for(int i = 0; i < 2; i++) + { + StdMapTOUint32 stdMapTOUint32; + EaMapTOUint32 eaMapTOUint32; + + + /////////////////////////////// + // Test insert(const value_type&) + /////////////////////////////// + const std::pair<TestObject, uint32_t> stdHighValue(TestObject(0x7fffffff), 0x7fffffff); + const eastl::pair<TestObject, uint32_t> eaHighValue(TestObject(0x7fffffff), 0x7fffffff); + + TestInsert(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size(), stdHighValue); + TestInsert(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size(), eaHighValue); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration + /////////////////////////////// + + TestIteration(stopwatch1, stdMapTOUint32, StdMapTOUint32::value_type(TestObject(9999999), 9999999)); + TestIteration(stopwatch2, eaMapTOUint32, EaMapTOUint32::value_type(TestObject(9999999), 9999999)); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[] + /////////////////////////////// + + TestBracket(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestBracket(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find + /////////////////////////////// + + TestFind(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestFind(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test count + /////////////////////////////// + + TestCount(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestCount(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test lower_bound + /////////////////////////////// + + TestLowerBound(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestLowerBound(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/lower_bound", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test upper_bound + /////////////////////////////// + + TestUpperBound(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestUpperBound(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/upper_bound", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test equal_range + /////////////////////////////// + + TestEqualRange(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestEqualRange(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/equal_range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(const key_type& key) + /////////////////////////////// + + TestEraseValue(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + (stdVector.size() / 2)); + TestEraseValue(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + (eaVector.size() / 2)); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/erase/key", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(iterator position) + /////////////////////////////// + + TestErasePosition(stopwatch1, stdMapTOUint32); + TestErasePosition(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/erase/pos", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime(), + GetStdSTLType() == kSTLMS ? "MS uses a code bloating implementation of erase." : NULL); + + + /////////////////////////////// + // Test erase(iterator first, iterator last) + /////////////////////////////// + + TestEraseRange(stopwatch1, stdMapTOUint32); + TestEraseRange(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/erase/range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test clear() + /////////////////////////////// + + TestClear(stopwatch1, stdMapTOUint32); + TestClear(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/clear", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + } + } +} + + + + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkSet.cpp b/benchmark/source/BenchmarkSet.cpp new file mode 100644 index 0000000..4a58b1a --- /dev/null +++ b/benchmark/source/BenchmarkSet.cpp @@ -0,0 +1,353 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/set.h> +#include <EASTL/vector.h> +#include <EASTL/algorithm.h> + +EA_DISABLE_ALL_VC_WARNINGS() +#include <set> +#include <algorithm> +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +typedef std::set<uint32_t> StdSetUint32; +typedef eastl::set<uint32_t> EaSetUint32; + + +namespace +{ + template <typename Container> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c, const uint32_t* pArrayBegin, const uint32_t* pArrayEnd) + { + stopwatch.Restart(); + c.insert(pArrayBegin, pArrayEnd); + stopwatch.Stop(); + + // Intentionally push back a high uint32_t value. We do this so that + // later upper_bound, lower_bound and equal_range never return end(). + c.insert(0xffffffff); + } + + + template <typename Container> + void TestIteration(EA::StdC::Stopwatch& stopwatch, const Container& c) + { + stopwatch.Restart(); + typename Container::const_iterator it = eastl::find(c.begin(), c.end(), uint32_t(9999999)); + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)*it); + } + + + template <typename Container> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c, const uint32_t* pArrayBegin, const uint32_t* pArrayEnd) + { + uint32_t temp = 0; + typename Container::iterator it; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + it = c.find(*pArrayBegin++); + temp += *it; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container> + void TestCount(EA::StdC::Stopwatch& stopwatch, Container& c, const uint32_t* pArrayBegin, const uint32_t* pArrayEnd) + { + typename Container::size_type temp = 0; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + temp += c.count(*pArrayBegin++); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container> + void TestLowerBound(EA::StdC::Stopwatch& stopwatch, Container& c, const uint32_t* pArrayBegin, const uint32_t* pArrayEnd) + { + uint32_t temp = 0; + typename Container::iterator it; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + it = c.lower_bound(*pArrayBegin++); + temp += *it; // We know that it != end because earlier we inserted 0xffffffff. + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container> + void TestUpperBound(EA::StdC::Stopwatch& stopwatch, Container& c, const uint32_t* pArrayBegin, const uint32_t* pArrayEnd) + { + uint32_t temp = 0; + typename Container::iterator it; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + it = c.upper_bound(*pArrayBegin++); + temp += *it; // We know that it != end because earlier we inserted 0xffffffff. + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container> + void TestEqualRange(EA::StdC::Stopwatch& stopwatch, Container& c, const uint32_t* pArrayBegin, const uint32_t* pArrayEnd) + { + uint32_t temp = 0; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + temp += *(c.equal_range(*pArrayBegin++).first); // We know that it != end because earlier we inserted 0xffffffff. + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container> + void TestEraseValue(EA::StdC::Stopwatch& stopwatch, Container& c, const uint32_t* pArrayBegin, const uint32_t* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + c.erase(*pArrayBegin++); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + + template <typename Container> + void TestErasePosition(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = c.size() / 3, it = c.begin(); j < jEnd; ++j) + { + // The erase fucntion is supposed to return an iterator, but the C++ standard was + // not initially clear about it and some STL implementations don't do it correctly. + #if (((defined(_MSC_VER) || defined(_CPPLIB_VER)) && !defined(_HAS_STRICT_CONFORMANCE))) // _CPPLIB_VER is something defined by Dinkumware STL. + it = c.erase(it); + #else + // This pathway may execute at a slightly different speed than the + // standard behaviour, but that's fine for the benchmark because the + // benchmark is measuring the speed of erasing while iterating, and + // however it needs to get done by the given STL is how it is measured. + const typename Container::iterator itErase(it++); + c.erase(itErase); + #endif + + ++it; + ++it; + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestEraseRange(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it1 = c.begin(); + typename Container::iterator it2 = c.begin(); + + for(j = 0, jEnd = c.size() / 3; j < jEnd; ++j) + ++it2; + + stopwatch.Restart(); + c.erase(it1, it2); + stopwatch.Stop(); + } + + + template <typename Container> + void TestClear(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + c.clear(); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + +} // namespace + + + +void BenchmarkSet() +{ + EASTLTest_Printf("Set\n"); + + EA::UnitTest::Rand rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector<uint32_t> intVector(10000); + for(eastl_size_t i = 0, iEnd = intVector.size(); i < iEnd; i++) + intVector[i] = (uint32_t)rng.RandLimit(((uint32_t)iEnd / 2)); // This will result in duplicates and even a few triplicates. + + for(int i = 0; i < 2; i++) + { + StdSetUint32 stdSetUint32; + EaSetUint32 eaSetUint32; + + + /////////////////////////////// + // Test insert(const value_type&) + /////////////////////////////// + + TestInsert(stopwatch1, stdSetUint32, intVector.data(), intVector.data() + intVector.size()); + TestInsert(stopwatch2, eaSetUint32, intVector.data(), intVector.data() + intVector.size()); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration + /////////////////////////////// + + TestIteration(stopwatch1, stdSetUint32); + TestIteration(stopwatch2, eaSetUint32); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find + /////////////////////////////// + + TestFind(stopwatch1, stdSetUint32, intVector.data(), intVector.data() + intVector.size()); + TestFind(stopwatch2, eaSetUint32, intVector.data(), intVector.data() + intVector.size()); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test count + /////////////////////////////// + + TestCount(stopwatch1, stdSetUint32, intVector.data(), intVector.data() + intVector.size()); + TestCount(stopwatch2, eaSetUint32, intVector.data(), intVector.data() + intVector.size()); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test lower_bound + /////////////////////////////// + + TestLowerBound(stopwatch1, stdSetUint32, intVector.data(), intVector.data() + intVector.size()); + TestLowerBound(stopwatch2, eaSetUint32, intVector.data(), intVector.data() + intVector.size()); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/lower_bound", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test upper_bound + /////////////////////////////// + + TestUpperBound(stopwatch1, stdSetUint32, intVector.data(), intVector.data() + intVector.size()); + TestUpperBound(stopwatch2, eaSetUint32, intVector.data(), intVector.data() + intVector.size()); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/upper_bound", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test equal_range + /////////////////////////////// + + TestEqualRange(stopwatch1, stdSetUint32, intVector.data(), intVector.data() + intVector.size()); + TestEqualRange(stopwatch2, eaSetUint32, intVector.data(), intVector.data() + intVector.size()); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/equal_range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(const key_type& key) + /////////////////////////////// + + TestEraseValue(stopwatch1, stdSetUint32, &intVector[0], &intVector[intVector.size() / 2]); + TestEraseValue(stopwatch2, eaSetUint32, &intVector[0], &intVector[intVector.size() / 2]); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/erase/val", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(iterator position) + /////////////////////////////// + + TestErasePosition(stopwatch1, stdSetUint32); + TestErasePosition(stopwatch2, eaSetUint32); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/erase/pos", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime(), + GetStdSTLType() == kSTLMS ? "MS uses a code bloating implementation of erase." : NULL); + + + /////////////////////////////// + // Test erase(iterator first, iterator last) + /////////////////////////////// + + TestEraseRange(stopwatch1, stdSetUint32); + TestEraseRange(stopwatch2, eaSetUint32); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/erase range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test clear() + /////////////////////////////// + + TestClear(stopwatch1, stdSetUint32); + TestClear(stopwatch2, eaSetUint32); + + if(i == 1) + Benchmark::AddResult("set<uint32_t>/clear", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + } + } +} + + + + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkSort.cpp b/benchmark/source/BenchmarkSort.cpp new file mode 100644 index 0000000..ccd2f43 --- /dev/null +++ b/benchmark/source/BenchmarkSort.cpp @@ -0,0 +1,1399 @@ +///////////////////////////////////////////////////////////////////////////// +// 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()); + } + } +} + + + + + diff --git a/benchmark/source/BenchmarkString.cpp b/benchmark/source/BenchmarkString.cpp new file mode 100644 index 0000000..5dfefbc --- /dev/null +++ b/benchmark/source/BenchmarkString.cpp @@ -0,0 +1,531 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/algorithm.h> +#include <EASTL/string.h> +#include <EASTL/sort.h> + +EA_DISABLE_ALL_VC_WARNINGS() +#include <algorithm> +#include <string> +#include <stdio.h> +#include <stdlib.h> +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +namespace +{ + template <typename Container> + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + for(int i = 0; i < 100000; i++) + c.push_back((typename Container::value_type)(i & ((typename Container::value_type)~0))); + stopwatch.Stop(); + } + + + template <typename Container, typename T> + void TestInsert1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p) + { + const typename Container::size_type s = c.size(); + stopwatch.Restart(); + for(int i = 0; i < 100; i++) + c.insert(s - (typename Container::size_type)(i * 317), p); + stopwatch.Stop(); + } + + + template <typename Container> + void TestErase1(EA::StdC::Stopwatch& stopwatch, Container& c) + { + const typename Container::size_type s = c.size(); + stopwatch.Restart(); + for(int i = 0; i < 100; i++) + c.erase(s - (typename Container::size_type)(i * 339), 7); + stopwatch.Stop(); + } + + + template <typename Container, typename T> + void TestReplace1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p, int n) + { + const typename Container::size_type s = c.size(); + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + c.replace(s - (typename Container::size_type)(i * 5), ((n - 2) + (i & 3)), p, n); // The second argument rotates through n-2, n-1, n, n+1, n-2, etc. + stopwatch.Stop(); + } + + + template <typename Container> + void TestReserve(EA::StdC::Stopwatch& stopwatch, Container& c) + { + const typename Container::size_type s = c.capacity(); + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + c.reserve((s - 2) + (i & 3)); // The second argument rotates through n-2, n-1, n, n+1, n-2, etc. + stopwatch.Stop(); + } + + + template <typename Container> + void TestSize(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, c.size()); + stopwatch.Stop(); + } + + + template <typename Container> + void TestBracket(EA::StdC::Stopwatch& stopwatch, Container& c) + { + int32_t temp = 0; + stopwatch.Restart(); + for(typename Container::size_type j = 0, jEnd = c.size(); j < jEnd; j++) + temp += c[j]; + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, *eastl::find(c.begin(), c.end(), (typename Container::value_type)~0)); + stopwatch.Stop(); + } + + + template <typename Container, typename T> + void TestFind1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p, int pos, int n) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, c.find(p, (typename Container::size_type)pos, (typename Container::size_type)n)); + stopwatch.Stop(); + } + + + template <typename Container, typename T> + void TestRfind1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p, int pos, int n) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, c.rfind(p, (typename Container::size_type)pos, (typename Container::size_type)n)); + stopwatch.Stop(); + } + + template <typename Container, typename T> + void TestFirstOf1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p, int pos, int n) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, c.find_first_of(p, (typename Container::size_type)pos, (typename Container::size_type)n)); + stopwatch.Stop(); + } + + template <typename Container, typename T> + void TestLastOf1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p, int pos, int n) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, c.find_last_of(p, (typename Container::size_type)pos, (typename Container::size_type)n)); + stopwatch.Stop(); + } + + template <typename Container, typename T> + void TestFirstNotOf1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p, int pos, int n) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, c.find_first_not_of(p, (typename Container::size_type)pos, (typename Container::size_type)n)); + stopwatch.Stop(); + } + + template <typename Container, typename T> + void TestLastNotOf1(EA::StdC::Stopwatch& stopwatch, Container& c, T* p, int pos, int n) + { + stopwatch.Restart(); + for(int i = 0; i < 1000; i++) + Benchmark::DoNothing(&c, c.find_last_not_of(p, (typename Container::size_type)pos, (typename Container::size_type)n)); + stopwatch.Stop(); + } + + + template <typename Container> + void TestCompare(EA::StdC::Stopwatch& stopwatch, Container& c1, Container& c2) // size() + { + stopwatch.Restart(); + for(int i = 0; i < 500; i++) + Benchmark::DoNothing(&c1, c1.compare(c2)); + stopwatch.Stop(); + } + + + template <typename Container> + void TestSwap(EA::StdC::Stopwatch& stopwatch, Container& c1, Container& c2) // size() + { + stopwatch.Restart(); + for(int i = 0; i < 10000; i++) // Make sure this is an even count so that when done things haven't changed. + { + c1.swap(c2); + Benchmark::DoNothing(&c1); + } + stopwatch.Stop(); + } + +} // namespace + + + + +void BenchmarkString() +{ + EASTLTest_Printf("String\n"); + + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + for(int i = 0; i < 2; i++) + { + std::basic_string<char8_t> ss8(16, 0); // We initialize to size of 16 because different implementations may make + eastl::basic_string<char8_t> es8(16, 0); // different tradeoffs related to startup size. Initial operations are faster + // when strings start with a higher reserve, but they use more memory. + std::basic_string<char16_t> ss16(16, 0); // We try to nullify this tradeoff for the tests below by starting all at + eastl::basic_string<char16_t> es16(16, 0); // the same baseline allocation. + + + /////////////////////////////// + // Test push_back + /////////////////////////////// + + TestPushBack(stopwatch1, ss8); + TestPushBack(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestPushBack(stopwatch1, ss16); + TestPushBack(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test insert(size_type position, const value_type* p) + /////////////////////////////// + + const char8_t pInsert1_8[] = { 'a', 0 }; + TestInsert1(stopwatch1, ss8, pInsert1_8); + TestInsert1(stopwatch2, es8, pInsert1_8); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/insert/pos,p", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + const char16_t pInsert1_16[] = { 'a', 0 }; + TestInsert1(stopwatch1, ss16, pInsert1_16); + TestInsert1(stopwatch2, es16, pInsert1_16); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/insert/pos,p", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(size_type position, size_type n) + /////////////////////////////// + + TestErase1(stopwatch1, ss8); + TestErase1(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/erase/pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestErase1(stopwatch1, ss16); + TestErase1(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/erase/pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test replace(size_type position, size_type n1, const value_type* p, size_type n2) + /////////////////////////////// + + const int kReplace1Size = 8; + const char8_t pReplace1_8[kReplace1Size] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' }; + + TestReplace1(stopwatch1, ss8, pReplace1_8, kReplace1Size); + TestReplace1(stopwatch2, es8, pReplace1_8, kReplace1Size); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/replace/pos,n,p,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + const char16_t pReplace1_16[kReplace1Size] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' }; + + TestReplace1(stopwatch1, ss16, pReplace1_16, kReplace1Size); + TestReplace1(stopwatch2, es16, pReplace1_16, kReplace1Size); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/replace/pos,n,p,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test reserve(size_type) + /////////////////////////////// + + TestReserve(stopwatch1, ss8); + TestReserve(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/reserve", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestReserve(stopwatch1, ss16); + TestReserve(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/reserve", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test size() + /////////////////////////////// + + TestSize(stopwatch1, ss8); + TestSize(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/size", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSize(stopwatch1, ss16); + TestSize(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/size", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestBracket(stopwatch1, ss8); + TestBracket(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestBracket(stopwatch1, ss16); + TestBracket(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration via find(). + /////////////////////////////// + + TestFind(stopwatch1, ss8); + TestFind(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFind(stopwatch1, ss16); + TestFind(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find(const value_type* p, size_type position, size_type n) + /////////////////////////////// + + const int kFind1Size = 7; + const char8_t pFind1_8[kFind1Size] = { 'p', 'a', 't', 't', 'e', 'r', 'n' }; + + ss8.insert(ss8.size() / 2, pFind1_8); + es8.insert(es8.size() / 2, pFind1_8); + + TestFind1(stopwatch1, ss8, pFind1_8, 15, kFind1Size); + TestFind1(stopwatch2, es8, pFind1_8, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/find/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + const char16_t pFind1_16[kFind1Size] = { 'p', 'a', 't', 't', 'e', 'r', 'n' }; + + #if !defined(EA_PLATFORM_IPHONE) && (!defined(EA_COMPILER_CLANG) && defined(EA_PLATFORM_MINGW)) // Crashes on iPhone. + ss16.insert(ss8.size() / 2, pFind1_16); + #endif + es16.insert(es8.size() / 2, pFind1_16); + + TestFind1(stopwatch1, ss16, pFind1_16, 15, kFind1Size); + TestFind1(stopwatch2, es16, pFind1_16, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/find/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test rfind(const value_type* p, size_type position, size_type n) + /////////////////////////////// + + TestRfind1(stopwatch1, ss8, pFind1_8, 15, kFind1Size); + TestRfind1(stopwatch2, es8, pFind1_8, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/rfind/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestRfind1(stopwatch1, ss16, pFind1_16, 15, kFind1Size); + TestRfind1(stopwatch2, es16, pFind1_16, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/rfind/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + //NOTICE (RASHIN): + //FindFirstOf variants are incredibly slow on palm pixi debug builds. + //Disabling for now... + #if !defined(EA_DEBUG) + /////////////////////////////// + // Test find_first_of(const value_type* p, size_type position, size_type n + /////////////////////////////// + + const int kFindOf1Size = 7; + const char8_t pFindOf1_8[kFindOf1Size] = { '~', '~', '~', '~', '~', '~', '~' }; + + TestFirstOf1(stopwatch1, ss8, pFindOf1_8, 15, kFindOf1Size); + TestFirstOf1(stopwatch2, es8, pFindOf1_8, 15, kFindOf1Size); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/find_first_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + const char16_t pFindOf1_16[kFindOf1Size] = { '~', '~', '~', '~', '~', '~', '~' }; + + TestFirstOf1(stopwatch1, ss16, pFindOf1_16, 15, kFindOf1Size); + TestFirstOf1(stopwatch2, es16, pFindOf1_16, 15, kFindOf1Size); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/find_first_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find_last_of(const value_type* p, size_type position, size_type n + /////////////////////////////// + + TestLastOf1(stopwatch1, ss8, pFindOf1_8, 15, kFindOf1Size); + TestLastOf1(stopwatch2, es8, pFindOf1_8, 15, kFindOf1Size); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/find_last_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestLastOf1(stopwatch1, ss16, pFindOf1_16, 15, kFindOf1Size); + TestLastOf1(stopwatch2, es16, pFindOf1_16, 15, kFindOf1Size); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/find_last_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find_first_not_of(const value_type* p, size_type position, size_type n + /////////////////////////////// + + TestFirstNotOf1(stopwatch1, ss8, pFind1_8, 15, kFind1Size); + TestFirstNotOf1(stopwatch2, es8, pFind1_8, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/find_first_not_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFirstNotOf1(stopwatch1, ss16, pFind1_16, 15, kFind1Size); + TestFirstNotOf1(stopwatch2, es16, pFind1_16, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/find_first_not_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find_last_of(const value_type* p, size_type position, size_type n + /////////////////////////////// + + TestLastNotOf1(stopwatch1, ss8, pFind1_8, 15, kFind1Size); + TestLastNotOf1(stopwatch2, es8, pFind1_8, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/find_last_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestLastNotOf1(stopwatch1, ss16, pFind1_16, 15, kFind1Size); + TestLastNotOf1(stopwatch2, es16, pFind1_16, 15, kFind1Size); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/find_last_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + #endif + + /////////////////////////////// + // Test compare() + /////////////////////////////// + + std::basic_string<char8_t> ss8X(ss8); + eastl::basic_string<char8_t> es8X(es8); + std::basic_string<char16_t> ss16X(ss16); + eastl::basic_string<char16_t> es16X(es16); + + TestCompare(stopwatch1, ss8, ss8X); + TestCompare(stopwatch2, es8, es8X); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/compare", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestCompare(stopwatch1, ss16, ss16X); + TestCompare(stopwatch2, es16, es16X); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/compare", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test swap() + /////////////////////////////// + + TestSwap(stopwatch1, ss8, ss8X); + TestSwap(stopwatch2, es8, es8X); + + if(i == 1) + Benchmark::AddResult("string<char8_t>/swap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSwap(stopwatch1, ss16, ss16X); + TestSwap(stopwatch2, es16, es16X); + + if(i == 1) + Benchmark::AddResult("string<char16_t>/swap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + } + } + +} + + + + + + + + + diff --git a/benchmark/source/BenchmarkTupleVector.cpp b/benchmark/source/BenchmarkTupleVector.cpp new file mode 100644 index 0000000..3a8e79d --- /dev/null +++ b/benchmark/source/BenchmarkTupleVector.cpp @@ -0,0 +1,667 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/algorithm.h> +#include <EASTL/bonus/tuple_vector.h> +#include <EASTL/sort.h> + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) +#endif +#include <algorithm> +#include <vector> +#include <stdio.h> +#include <stdlib.h> +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; + + +typedef std::vector<uint64_t> StdVectorUint64; +typedef eastl::tuple_vector<uint64_t> EaTupleVectorUint64; + + struct PaddingStruct +{ + char padding[56] = { 0 }; +}; +static const PaddingStruct DefaultPadding; +typedef eastl::tuple<uint64_t, PaddingStruct> PaddedTuple; +typedef std::vector<PaddedTuple> StdVectorUint64Padded; +typedef eastl::tuple_vector<uint64_t, PaddingStruct> EaTupleVectorUint64Padded; + +namespace +{ + + + ////////////////////////////////////////////////////////////////////////////// + // MovableType + // + struct MovableType + { + int8_t* mpData; + enum { kDataSize = 128 }; + + MovableType() : mpData(new int8_t[kDataSize]) + { memset(mpData, 0, kDataSize); } + + MovableType(const MovableType& x) : mpData(new int8_t[kDataSize]) + { memcpy(mpData, x.mpData, kDataSize); } + + MovableType& operator=(const MovableType& x) + { + if(!mpData) + mpData = new int8_t[kDataSize]; + memcpy(mpData, x.mpData, kDataSize); + return *this; + } + + #if EASTL_MOVE_SEMANTICS_ENABLED + MovableType(MovableType&& x) EA_NOEXCEPT : mpData(x.mpData) + { x.mpData = NULL; } + + MovableType& operator=(MovableType&& x) + { + eastl::swap(mpData, x.mpData); // In practice it may not be right to do a swap, depending on the case. + return *this; + } + #endif + + ~MovableType() + { delete[] mpData; } + }; + + + ////////////////////////////////////////////////////////////////////////////// + // AutoRefCount + // + // Basic ref-counted object. + // + template <typename T> + class AutoRefCount + { + public: + T* mpObject; + + public: + AutoRefCount() EA_NOEXCEPT : mpObject(NULL) + {} + + AutoRefCount(T* pObject) EA_NOEXCEPT : mpObject(pObject) + { + if(mpObject) + mpObject->AddRef(); + } + + AutoRefCount(T* pObject, int) EA_NOEXCEPT : mpObject(pObject) + { + // Inherit the existing refcount. + } + + AutoRefCount(const AutoRefCount& x) EA_NOEXCEPT : mpObject(x.mpObject) + { + if(mpObject) + mpObject->AddRef(); + } + + AutoRefCount& operator=(const AutoRefCount& x) + { + return operator=(x.mpObject); + } + + AutoRefCount& operator=(T* pObject) + { + if(pObject != mpObject) + { + T* const pTemp = mpObject; // Create temporary to prevent possible problems with re-entrancy. + if(pObject) + pObject->AddRef(); + mpObject = pObject; + if(pTemp) + pTemp->Release(); + } + return *this; + } + + #if EASTL_MOVE_SEMANTICS_ENABLED + AutoRefCount(AutoRefCount&& x) EA_NOEXCEPT : mpObject(x.mpObject) + { + x.mpObject = NULL; + } + + AutoRefCount& operator=(AutoRefCount&& x) + { + if(mpObject) + mpObject->Release(); + mpObject = x.mpObject; + x.mpObject = NULL; + return *this; + } + #endif + + ~AutoRefCount() + { + if(mpObject) + mpObject->Release(); + } + + T& operator *() const EA_NOEXCEPT + { return *mpObject; } + + T* operator ->() const EA_NOEXCEPT + { return mpObject; } + + operator T*() const EA_NOEXCEPT + { return mpObject; } + + }; // class AutoRefCount + + + struct RefCounted + { + int mRefCount; + static int msAddRefCount; + static int msReleaseCount; + + RefCounted() : mRefCount(1) {} + + int AddRef() + { ++msAddRefCount; return ++mRefCount; } + + int Release() + { + ++msReleaseCount; + if(mRefCount > 1) + return --mRefCount; + delete this; + return 0; + } + }; + + int RefCounted::msAddRefCount = 0; + int RefCounted::msReleaseCount = 0; + +} // namespace + + +namespace +{ + template <typename Container> + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector<uint32_t>& intVector) + { + stopwatch.Restart(); + for(eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) + c.push_back((uint64_t)intVector[j]); + stopwatch.Stop(); + } + + + template <typename Container> + void TestBracket(EA::StdC::Stopwatch& stopwatch, Container& c) + { + uint64_t temp = 0; + stopwatch.Restart(); + for(typename Container::size_type j = 0, jEnd = c.size(); j < jEnd; j++) + temp += c[j]; + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(temp & 0xffffffff)); + } + + void TestBracket(EA::StdC::Stopwatch& stopwatch, EaTupleVectorUint64& c) + { + uint64_t temp = 0; + stopwatch.Restart(); + for (typename EaTupleVectorUint64::size_type j = 0, jEnd = c.size(); j < jEnd; j++) + temp += eastl::get<0>(c[j]); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(temp & 0xffffffff)); + } + + template <typename Container> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + typedef typename Container::iterator iterator_t; // This typedef is required to get this code to compile on RVCT + iterator_t it = eastl::find(c.begin(), c.end(), UINT64_C(0xffffffffffff)); + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)*it); + } + + void TestFind(EA::StdC::Stopwatch& stopwatch, EaTupleVectorUint64& c) + { + eastl::tuple<uint64_t> val(0xffffffffffff); + stopwatch.Restart(); + EaTupleVectorUint64::iterator it = eastl::find(c.begin(), c.end(), val); + stopwatch.Stop(); + if (it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)eastl::get<0>(*it)); + } + + template <typename Container> + void TestSort(EA::StdC::Stopwatch& stopwatch, Container& c) + { + // Intentionally use eastl sort in order to measure just + // vector access speed and not be polluted by sort speed. + stopwatch.Restart(); + eastl::quick_sort(c.begin(), c.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(c[0] & 0xffffffff)); + } + + void TestSort(EA::StdC::Stopwatch& stopwatch, EaTupleVectorUint64& c) + { + // Intentionally use eastl sort in order to measure just + // vector access speed and not be polluted by sort speed. + stopwatch.Restart(); + eastl::quick_sort(c.begin(), c.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(eastl::get<0>(c[0]) & 0xffffffff)); + } + + + template <typename Container> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = 100, it = c.begin(); j < jEnd; ++j) + { + it = c.insert(it, UINT64_C(0xffffffffffff)); + + if(it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestErase(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = 100, it = c.begin(); j < jEnd; ++j) + { + it = c.erase(it); + + if(it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestMoveReallocate(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + while(c.size() < 8192) + c.resize(c.capacity() + 1); + stopwatch.Stop(); + } + + + template <typename Container> + void TestMoveErase(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + while(!c.empty()) + c.erase(c.begin()); + stopwatch.Stop(); + } + + ////////////////////////////////////////////////////////////////////////// + // Variations of test functions for the Padded structures + template <typename Container> + void TestTuplePushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector<uint32_t>& intVector) + { + stopwatch.Restart(); + for (eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) + { + PaddedTuple tup((uint64_t)intVector[j], DefaultPadding); + c.push_back(tup); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestTupleBracket(EA::StdC::Stopwatch& stopwatch, Container& c) + { + uint64_t temp = 0; + stopwatch.Restart(); + for (typename Container::size_type j = 0, jEnd = c.size(); j < jEnd; j++) + temp += eastl::get<0>(c[j]); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(temp & 0xffffffff)); + } + + + template <typename Container> + void TestTupleFind(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + typedef typename Container::iterator iterator_t; // This typedef is required to get this code to compile on RVCT + iterator_t it = eastl::find_if(c.begin(), c.end(), [](auto tup) { return eastl::get<0>(tup) == 0xFFFFFFFF; }); + stopwatch.Stop(); + if (it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)eastl::get<0>(*it)); + } + + template <typename Container> + void TestTupleSort(EA::StdC::Stopwatch& stopwatch, Container& c) + { + // Intentionally use eastl sort in order to measure just + // vector access speed and not be polluted by sort speed. + stopwatch.Restart(); + eastl::quick_sort(c.begin(), c.end(), [](auto a, auto b) { return eastl::get<0>(a) < eastl::get<0>(b); }); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(eastl::get<0>(c[0]) & 0xffffffff)); + } + + template <typename Container> + void TestTupleInsert(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + PaddedTuple tup(0xFFFFFFFF, DefaultPadding); + + stopwatch.Restart(); + for (j = 0, jEnd = 100, it = c.begin(); j < jEnd; ++j) + { + it = c.insert(it, tup); + + if (it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if (++it == c.end()) + it = c.begin(); + if (++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + + template <typename Container> + void TestTupleErase(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for (j = 0, jEnd = 100, it = c.begin(); j < jEnd; ++j) + { + it = c.erase(it); + + if (it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if (++it == c.end()) + it = c.begin(); + if (++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + +} // namespace + + + + + +void BenchmarkTupleVector() +{ + EASTLTest_Printf("TupleVector\n"); + + EA::UnitTest::RandGenT<uint32_t> rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector<uint32_t> intVector(100000); + eastl::generate(intVector.begin(), intVector.end(), rng); + + for(int i = 0; i < 2; i++) + { + StdVectorUint64 stdVectorUint64; + EaTupleVectorUint64 eaTupleVectorUint64; + + + /////////////////////////////// + // Test push_back + /////////////////////////////// + + TestPushBack(stopwatch1, stdVectorUint64, intVector); + TestPushBack(stopwatch2, eaTupleVectorUint64, intVector); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64>/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestBracket(stopwatch1, stdVectorUint64); + TestBracket(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration via find(). + /////////////////////////////// + + TestFind(stopwatch1, stdVectorUint64); + TestFind(stopwatch2, eaTupleVectorUint64); + TestFind(stopwatch1, stdVectorUint64); + TestFind(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test sort + /////////////////////////////// + + // Currently VC++ complains about our sort function decrementing std::iterator that is already at begin(). In the strictest sense, + // that's a valid complaint, but we aren't testing std STL here. We will want to revise our sort function eventually. + #if !defined(_MSC_VER) || !defined(_ITERATOR_DEBUG_LEVEL) || (_ITERATOR_DEBUG_LEVEL < 2) + TestSort(stopwatch1, stdVectorUint64); + TestSort(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64>/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + #endif + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestInsert(stopwatch1, stdVectorUint64); + TestInsert(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestErase(stopwatch1, stdVectorUint64); + TestErase(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of MovableType + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector<MovableType> stdVectorMovableType; + eastl::tuple_vector<MovableType> eaTupleVectorMovableType; + + TestMoveReallocate(stopwatch1, stdVectorMovableType); + TestMoveReallocate(stopwatch2, eaTupleVectorMovableType); + + if(i == 1) + Benchmark::AddResult("tuple_vector<MovableType>/reallocate", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + TestMoveErase(stopwatch1, stdVectorMovableType); + TestMoveErase(stopwatch2, eaTupleVectorMovableType); + + if(i == 1) + Benchmark::AddResult("tuple_vector<MovableType>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of AutoRefCount + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector<AutoRefCount<RefCounted> > stdVectorAutoRefCount; + eastl::tuple_vector<AutoRefCount<RefCounted> > eaTupleVectorAutoRefCount; + + for(size_t a = 0; a < 2048; a++) + { + stdVectorAutoRefCount.push_back(AutoRefCount<RefCounted>(new RefCounted)); + eaTupleVectorAutoRefCount.push_back(AutoRefCount<RefCounted>(new RefCounted)); + } + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch1, stdVectorAutoRefCount); + //EASTLTest_Printf("tuple_vector<AutoRefCount>/erase std counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch2, eaTupleVectorAutoRefCount); + //EASTLTest_Printf("tuple_vector<AutoRefCount>/erase EA counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + if(i == 1) + Benchmark::AddResult("tuple_vector<AutoRefCount>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + ////////////////////////////////////////////////////////////////////////// + // Test various operations with "padded" data, to demonstrate access/modification of sparse data + + StdVectorUint64Padded stdVectorUint64Padded; + EaTupleVectorUint64Padded eaTupleVectorUint64Padded; + + /////////////////////////////// + // Test push_back + /////////////////////////////// + + TestTuplePushBack(stopwatch1, stdVectorUint64Padded, intVector); + TestTuplePushBack(stopwatch2, eaTupleVectorUint64Padded, intVector); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64,Padding>/push_back", stopwatch1.GetUnits(), + stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestTupleBracket(stopwatch1, stdVectorUint64Padded); + TestTupleBracket(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64,Padding>/operator[]", stopwatch1.GetUnits(), + stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration via find(). + /////////////////////////////// + + TestTupleFind(stopwatch1, stdVectorUint64Padded); + TestTupleFind(stopwatch2, eaTupleVectorUint64Padded); + TestTupleFind(stopwatch1, stdVectorUint64Padded); + TestTupleFind(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64,Padding>/iteration", stopwatch1.GetUnits(), + stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test sort + /////////////////////////////// + + // Currently VC++ complains about our sort function decrementing std::iterator that is already at + // begin(). In the strictest sense, that's a valid complaint, but we aren't testing std STL here. We + // will want to revise our sort function eventually. + #if !defined(_MSC_VER) || !defined(_ITERATOR_DEBUG_LEVEL) || (_ITERATOR_DEBUG_LEVEL < 2) + TestTupleSort(stopwatch1, stdVectorUint64Padded); + TestTupleSort(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64,Padding>/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), + stopwatch2.GetElapsedTime()); + #endif + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestTupleInsert(stopwatch1, stdVectorUint64Padded); + TestTupleInsert(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64,Padding>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), + stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestTupleErase(stopwatch1, stdVectorUint64Padded); + TestTupleErase(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector<uint64,Padding>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), + stopwatch2.GetElapsedTime()); + } + } +} + + + + + + + + + + + + diff --git a/benchmark/source/BenchmarkVector.cpp b/benchmark/source/BenchmarkVector.cpp new file mode 100644 index 0000000..9331530 --- /dev/null +++ b/benchmark/source/BenchmarkVector.cpp @@ -0,0 +1,452 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/algorithm.h> +#include <EASTL/vector.h> +#include <EASTL/sort.h> + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) +#endif +#include <algorithm> +#include <vector> +#include <stdio.h> +#include <stdlib.h> +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; + + +typedef std::vector<uint64_t> StdVectorUint64; +typedef eastl::vector<uint64_t> EaVectorUint64; + + +namespace +{ + + + ////////////////////////////////////////////////////////////////////////////// + // MovableType + // + struct MovableType + { + int8_t* mpData; + enum { kDataSize = 128 }; + + MovableType() : mpData(new int8_t[kDataSize]) + { memset(mpData, 0, kDataSize); } + + MovableType(const MovableType& x) : mpData(new int8_t[kDataSize]) + { memcpy(mpData, x.mpData, kDataSize); } + + MovableType& operator=(const MovableType& x) + { + if(!mpData) + mpData = new int8_t[kDataSize]; + memcpy(mpData, x.mpData, kDataSize); + return *this; + } + + MovableType(MovableType&& x) EA_NOEXCEPT : mpData(x.mpData) + { x.mpData = NULL; } + + MovableType& operator=(MovableType&& x) + { + eastl::swap(mpData, x.mpData); // In practice it may not be right to do a swap, depending on the case. + return *this; + } + + ~MovableType() + { delete[] mpData; } + }; + + + ////////////////////////////////////////////////////////////////////////////// + // AutoRefCount + // + // Basic ref-counted object. + // + template <typename T> + class AutoRefCount + { + public: + T* mpObject; + + public: + AutoRefCount() EA_NOEXCEPT : mpObject(NULL) + {} + + AutoRefCount(T* pObject) EA_NOEXCEPT : mpObject(pObject) + { + if(mpObject) + mpObject->AddRef(); + } + + AutoRefCount(T* pObject, int) EA_NOEXCEPT : mpObject(pObject) + { + // Inherit the existing refcount. + } + + AutoRefCount(const AutoRefCount& x) EA_NOEXCEPT : mpObject(x.mpObject) + { + if(mpObject) + mpObject->AddRef(); + } + + AutoRefCount& operator=(const AutoRefCount& x) + { + return operator=(x.mpObject); + } + + AutoRefCount& operator=(T* pObject) + { + if(pObject != mpObject) + { + T* const pTemp = mpObject; // Create temporary to prevent possible problems with re-entrancy. + if(pObject) + pObject->AddRef(); + mpObject = pObject; + if(pTemp) + pTemp->Release(); + } + return *this; + } + + AutoRefCount(AutoRefCount&& x) EA_NOEXCEPT : mpObject(x.mpObject) + { + x.mpObject = NULL; + } + + AutoRefCount& operator=(AutoRefCount&& x) + { + if(mpObject) + mpObject->Release(); + mpObject = x.mpObject; + x.mpObject = NULL; + return *this; + } + + ~AutoRefCount() + { + if(mpObject) + mpObject->Release(); + } + + T& operator *() const EA_NOEXCEPT + { return *mpObject; } + + T* operator ->() const EA_NOEXCEPT + { return mpObject; } + + operator T*() const EA_NOEXCEPT + { return mpObject; } + + }; // class AutoRefCount + + + struct RefCounted + { + int mRefCount; + static int msAddRefCount; + static int msReleaseCount; + + RefCounted() : mRefCount(1) {} + + int AddRef() + { ++msAddRefCount; return ++mRefCount; } + + int Release() + { + ++msReleaseCount; + if(mRefCount > 1) + return --mRefCount; + delete this; + return 0; + } + }; + + int RefCounted::msAddRefCount = 0; + int RefCounted::msReleaseCount = 0; + +} // namespace + + +namespace +{ + template <typename Container> + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector<uint32_t>& intVector) + { + stopwatch.Restart(); + for(eastl_size_t j = 0, jEnd = intVector.size(); j < jEnd; j++) + c.push_back((uint64_t)intVector[j]); + stopwatch.Stop(); + } + + + template <typename Container> + void TestBracket(EA::StdC::Stopwatch& stopwatch, Container& c) + { + uint64_t temp = 0; + stopwatch.Restart(); + for(typename Container::size_type j = 0, jEnd = c.size(); j < jEnd; j++) + temp += c[j]; + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(temp & 0xffffffff)); + } + + + template <typename Container> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + typedef typename Container::iterator iterator_t; // This typedef is required to get this code to compile on RVCT + iterator_t it = eastl::find(c.begin(), c.end(), UINT64_C(0xffffffffffff)); + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)*it); + } + + + template <typename Container> + void TestSort(EA::StdC::Stopwatch& stopwatch, Container& c) + { + // Intentionally use eastl sort in order to measure just + // vector access speed and not be polluted by sort speed. + stopwatch.Restart(); + eastl::quick_sort(c.begin(), c.end()); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)(c[0] & 0xffffffff)); + } + + + template <typename Container> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = 100, it = c.begin(); j < jEnd; ++j) + { + it = c.insert(it, UINT64_C(0xffffffffffff)); + + if(it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestErase(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = 100, it = c.begin(); j < jEnd; ++j) + { + it = c.erase(it); + + if(it == c.end()) // Try to safely increment the iterator three times. + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + if(++it == c.end()) + it = c.begin(); + } + stopwatch.Stop(); + } + + + template <typename Container> + void TestMoveReallocate(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + while(c.size() < 8192) + c.resize(c.capacity() + 1); + stopwatch.Stop(); + } + + + template <typename Container> + void TestMoveErase(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + while(!c.empty()) + c.erase(c.begin()); + stopwatch.Stop(); + } + + +} // namespace + + + + + +void BenchmarkVector() +{ + EASTLTest_Printf("Vector\n"); + + EA::UnitTest::RandGenT<uint32_t> rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector<uint32_t> intVector(100000); + eastl::generate(intVector.begin(), intVector.end(), rng); + + for(int i = 0; i < 2; i++) + { + StdVectorUint64 stdVectorUint64; + EaVectorUint64 eaVectorUint64; + + + /////////////////////////////// + // Test push_back + /////////////////////////////// + + TestPushBack(stopwatch1, stdVectorUint64, intVector); + TestPushBack(stopwatch2, eaVectorUint64, intVector); + + if(i == 1) + Benchmark::AddResult("vector<uint64>/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestBracket(stopwatch1, stdVectorUint64); + TestBracket(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector<uint64>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration via find(). + /////////////////////////////// + + TestFind(stopwatch1, stdVectorUint64); + TestFind(stopwatch2, eaVectorUint64); + TestFind(stopwatch1, stdVectorUint64); + TestFind(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector<uint64>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test sort + /////////////////////////////// + + // Currently VC++ complains about our sort function decrementing std::iterator that is already at begin(). In the strictest sense, + // that's a valid complaint, but we aren't testing std STL here. We will want to revise our sort function eventually. + #if !defined(_MSC_VER) || !defined(_ITERATOR_DEBUG_LEVEL) || (_ITERATOR_DEBUG_LEVEL < 2) + TestSort(stopwatch1, stdVectorUint64); + TestSort(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector<uint64>/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + #endif + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestInsert(stopwatch1, stdVectorUint64); + TestInsert(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector<uint64>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestErase(stopwatch1, stdVectorUint64); + TestErase(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector<uint64>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of MovableType + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector<MovableType> stdVectorMovableType; + eastl::vector<MovableType> eaVectorMovableType; + + TestMoveReallocate(stopwatch1, stdVectorMovableType); + TestMoveReallocate(stopwatch2, eaVectorMovableType); + + if(i == 1) + Benchmark::AddResult("vector<MovableType>/reallocate", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + TestMoveErase(stopwatch1, stdVectorMovableType); + TestMoveErase(stopwatch2, eaVectorMovableType); + + if(i == 1) + Benchmark::AddResult("vector<MovableType>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of AutoRefCount + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector<AutoRefCount<RefCounted> > stdVectorAutoRefCount; + eastl::vector<AutoRefCount<RefCounted> > eaVectorAutoRefCount; + + for(size_t a = 0; a < 2048; a++) + { + stdVectorAutoRefCount.push_back(AutoRefCount<RefCounted>(new RefCounted)); + eaVectorAutoRefCount.push_back(AutoRefCount<RefCounted>(new RefCounted)); + } + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch1, stdVectorAutoRefCount); + EASTLTest_Printf("vector<AutoRefCount>/erase std counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch2, eaVectorAutoRefCount); + EASTLTest_Printf("vector<AutoRefCount>/erase EA counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + if(i == 1) + Benchmark::AddResult("vector<AutoRefCount>/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } +} + + + + + + + + + + + + diff --git a/benchmark/source/EASTLBenchmark.cpp b/benchmark/source/EASTLBenchmark.cpp new file mode 100644 index 0000000..8e4d3ae --- /dev/null +++ b/benchmark/source/EASTLBenchmark.cpp @@ -0,0 +1,291 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EASTL/string.h> +#include <EAMain/EAMain.h> + +#ifdef _MSC_VER + #pragma warning(push, 0) +#endif +#include <stdio.h> +#include <math.h> +#include <float.h> +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + + +namespace Benchmark +{ + static int64_t ConvertStopwatchUnits(EA::StdC::Stopwatch::Units unitsSource, int64_t valueSource, EA::StdC::Stopwatch::Units unitsDest) + { + using namespace EA::StdC; + + int64_t valueDest = valueSource; + + if(unitsSource != unitsDest) + { + double sourceMultiplier; + + switch (unitsSource) + { + case Stopwatch::kUnitsCPUCycles: + sourceMultiplier = Stopwatch::GetUnitsPerCPUCycle(unitsDest); // This will typically be a number less than 1. + valueDest = (int64_t)(valueSource * sourceMultiplier); + break; + + case Stopwatch::kUnitsCycles: + sourceMultiplier = Stopwatch::GetUnitsPerStopwatchCycle(unitsDest); // This will typically be a number less than 1. + valueDest = (int64_t)(valueSource * sourceMultiplier); + break; + + case Stopwatch::kUnitsNanoseconds: + case Stopwatch::kUnitsMicroseconds: + case Stopwatch::kUnitsMilliseconds: + case Stopwatch::kUnitsSeconds: + case Stopwatch::kUnitsMinutes: + case Stopwatch::kUnitsUserDefined: + // To do. Also, handle the case of unitsDest being Cycles or CPUCycles and unitsSource being a time. + break; + } + } + + return valueDest; + } + + void WriteTime(int64_t timeNS, eastl::string& sTime) + { + if(timeNS > 1000000000) + sTime.sprintf(" %6.2f s", (double)timeNS / 1000000000); + else if(timeNS > 1000000) + sTime.sprintf("%6.1f ms", (double)timeNS / 1000000); + else if(timeNS > 1000) + sTime.sprintf("%6.1f us", (double)timeNS / 1000); + else + sTime.sprintf("%6.1f ns", (double)timeNS / 1); + } + + + + Environment gEnvironment; + + Environment& GetEnvironment() + { + return gEnvironment; + } + + + + ResultSet gResultSet; + + ResultSet& GetResultSet() + { + return gResultSet; + } + + + + // Scratch sprintf buffer + char gScratchBuffer[1024]; + + + void DoNothing(...) + { + // Intentionally nothing. + } + + + void AddResult(const char* pName, int units, int64_t nTime1, int64_t nTime2, const char* pNotes) + { + Result result; + + result.msName = pName; + result.mUnits = units; + result.mTime1 = nTime1; + result.mTime1NS = ConvertStopwatchUnits((EA::StdC::Stopwatch::Units)units, nTime1, EA::StdC::Stopwatch::kUnitsNanoseconds); + result.mTime2 = nTime2; + result.mTime2NS = ConvertStopwatchUnits((EA::StdC::Stopwatch::Units)units, nTime2, EA::StdC::Stopwatch::kUnitsNanoseconds); + + if(pNotes) + result.msNotes = pNotes; + + gResultSet.insert(result); + } + + + void PrintResultLine(const Result& result) + { + const double fRatio = (double)result.mTime1 / (double)result.mTime2; + const double fRatioPrinted = (fRatio > 100) ? 100 : fRatio; + const double fPercentChange = fabs(((double)result.mTime1 - (double)result.mTime2) / (((double)result.mTime1 + (double)result.mTime2) / 2)); + const bool bDifference = (result.mTime1 > 10) && (result.mTime2 > 10) && (fPercentChange > 0.25); + const char* pDifference = (bDifference ? (result.mTime1 < result.mTime2 ? "-" : "+") : ""); + + eastl::string sClockTime1, sClockTime2; + + WriteTime(result.mTime1NS, sClockTime1); // This converts an integer in nanoseconds (e.g. 23400000) to a string (e.g. "23.4 ms") + WriteTime(result.mTime2NS, sClockTime2); + + EA::UnitTest::Report("%-43s | %13" PRIu64 " %s | %13" PRIu64 " %s | %10.2f%10s", result.msName.c_str(), result.mTime1, sClockTime1.c_str(), result.mTime2, sClockTime2.c_str(), fRatioPrinted, pDifference); + + if(result.msNotes.length()) // If there are any notes... + EA::UnitTest::Report(" %s", result.msNotes.c_str()); + EA::UnitTest::Report("\n"); + } + + + #if defined(EASTL_BENCHMARK_WRITE_FILE) && EASTL_BENCHMARK_WRITE_FILE + + #if !defined(EASTL_BENCHMARK_WRITE_FILE_PATH) + #define EASTL_BENCHMARK_WRITE_FILE_PATH "BenchmarkResults.txt" + #endif + + struct FileWriter + { + FILE* mpReportFile; + EA::EAMain::ReportFunction mpSavedReportFunction; + static FileWriter* gpFileWriter; + + static void StaticPrintfReportFunction(const char8_t* pText) + { + if(gpFileWriter) + gpFileWriter->PrintfReportFunction(pText); + } + + void PrintfReportFunction(const char8_t* pText) + { + fwrite(pText, strlen(pText), 1, mpReportFile); + EA::EAMain::ReportFunction gpReportFunction = EA::EAMain::GetDefaultReportFunction(); + gpReportFunction(pText); + } + + FileWriter() : mpReportFile(NULL), mpSavedReportFunction(NULL) + { + mpReportFile = fopen(EASTL_BENCHMARK_WRITE_FILE_PATH, "w+"); + + if(mpReportFile) + { + gpFileWriter = this; + mpSavedReportFunction = EA::EAMain::GetDefaultReportFunction(); + EA::EAMain::SetReportFunction(StaticPrintfReportFunction); + } + } + + ~FileWriter() + { + if(mpReportFile) + { + gpFileWriter = NULL; + EA::EAMain::SetReportFunction(mpSavedReportFunction); + fclose(mpReportFile); + } + } + }; + + FileWriter* FileWriter::gpFileWriter = NULL; + #endif + + + void PrintResults() + { + #if defined(EASTL_BENCHMARK_WRITE_FILE) && EASTL_BENCHMARK_WRITE_FILE + FileWriter fileWriter; // This will auto-execute. + #endif + + // Print the results + EA::UnitTest::Report("\n"); + EA::UnitTest::Report("****************************************************************************************\n"); + EA::UnitTest::Report("EASTL Benchmark test results\n"); + EA::UnitTest::Report("****************************************************************************************\n"); + EA::UnitTest::Report("\n"); + EA::UnitTest::Report("EASTL version: %s\n", EASTL_VERSION); + EA::UnitTest::Report("Platform: %s\n", gEnvironment.msPlatform.c_str()); + EA::UnitTest::Report("Compiler: %s\n", EA_COMPILER_STRING); + #if defined(EA_DEBUG) || defined(_DEBUG) + EA::UnitTest::Report("Allocator: PPMalloc::GeneralAllocatorDebug. Thread safety enabled.\n"); + EA::UnitTest::Report("Build: Debug. Inlining disabled. STL debug features disabled.\n"); + #else + EA::UnitTest::Report("Allocator: PPMalloc::GeneralAllocator. Thread safety enabled.\n"); + EA::UnitTest::Report("Build: Full optimization. Inlining enabled.\n"); + #endif + EA::UnitTest::Report("\n"); + EA::UnitTest::Report("Values are ticks and time to complete tests; smaller values are better.\n"); + EA::UnitTest::Report("\n"); + EA::UnitTest::Report("%-43s%26s%26s%13s%13s\n", "Test", gEnvironment.msSTLName1.c_str(), gEnvironment.msSTLName2.c_str(), "Ratio", "Difference?"); + EA::UnitTest::Report("---------------------------------------------------------------------------------------------------------------------\n"); + + eastl::string sTestTypeLast; + eastl::string sTestTypeTemp; + + for(ResultSet::iterator it = gResultSet.begin(); it != gResultSet.end(); ++it) + { + const Result& result = *it; + + eastl_size_t n = result.msName.find('/'); + if(n == eastl::string::npos) + n = result.msName.length(); + sTestTypeTemp.assign(result.msName, 0, n); + + if(sTestTypeTemp != sTestTypeLast) // If it looks like we are changing to a new test type... add an empty line to help readability. + { + if(it != gResultSet.begin()) + EA::UnitTest::Report("\n"); + sTestTypeLast = sTestTypeTemp; + } + + PrintResultLine(result); + } + + // We will print out a final line that has the sum of the rows printed above. + Result resultSum; + resultSum.msName = "sum"; + + for(ResultSet::iterator its = gResultSet.begin(); its != gResultSet.end(); ++its) + { + const Result& resultTemp = *its; + + EASTL_ASSERT(resultTemp.mUnits == EA::StdC::Stopwatch::kUnitsCPUCycles); // Our ConvertStopwatchUnits call below assumes that every measured time is CPUCycles. + resultSum.mTime1 += resultTemp.mTime1; + resultSum.mTime2 += resultTemp.mTime2; + } + + // We do this convert as a final step instead of the loop in order to avoid loss of precision. + resultSum.mTime1NS = ConvertStopwatchUnits(EA::StdC::Stopwatch::kUnitsCPUCycles, resultSum.mTime1, EA::StdC::Stopwatch::kUnitsNanoseconds); + resultSum.mTime2NS = ConvertStopwatchUnits(EA::StdC::Stopwatch::kUnitsCPUCycles, resultSum.mTime2, EA::StdC::Stopwatch::kUnitsNanoseconds); + EA::UnitTest::Report("\n"); + PrintResultLine(resultSum); + + EA::UnitTest::Report("\n"); + EA::UnitTest::Report("****************************************************************************************\n"); + EA::UnitTest::Report("\n"); + + // Clear the results + gResultSet.clear(); + gEnvironment.clear(); + } + +} // namespace Benchmark + + + + + + + + + + + + + + + + + + + diff --git a/benchmark/source/EASTLBenchmark.h b/benchmark/source/EASTLBenchmark.h new file mode 100644 index 0000000..a0833e6 --- /dev/null +++ b/benchmark/source/EASTLBenchmark.h @@ -0,0 +1,228 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#ifndef EASTLBENCHMARK_H +#define EASTLBENCHMARK_H + + +// Intrinsic control +// +// Our benchmark results are being skewed by inconsistent decisions by the +// VC++ compiler to use intrinsic functions. Additionally, many of our +// benchmarks work on large blocks of elements, whereas intrinsics often +// are an improvement only over small blocks of elements. As a result, +// enabling of intrinsics is often resulting in poor benchmark results for +// code that gets an intrinsic enabled for it, even though it will often +// happen in real code to be the opposite case. The disabling of intrinsics +// here often results in EASTL performance being lower than it would be in +// real-world situations. +// +#include <string.h> +#ifdef _MSC_VER + #pragma function(strlen, strcmp, strcpy, strcat, memcpy, memcmp, memset) +#endif + + +#include <EASTL/set.h> +#include <EASTL/string.h> +#include <EAStdC/EAStopwatch.h> +#include <stdlib.h> +#include <string.h> + + +void BenchmarkSort(); +void BenchmarkList(); +void BenchmarkString(); +void BenchmarkVector(); +void BenchmarkDeque(); +void BenchmarkSet(); +void BenchmarkMap(); +void BenchmarkHash(); +void BenchmarkAlgorithm(); +void BenchmarkHeap(); +void BenchmarkBitset(); +void BenchmarkTupleVector(); + + +namespace Benchmark +{ + + // Environment + // + // The environment for this benchmark test. + // + struct Environment + { + eastl::string8 msPlatform; // Name of test platform (e.g. "Windows") + eastl::string8 msSTLName1; // Name of competitor #1 (e.g. "EASTL"). + eastl::string8 msSTLName2; // Name of competitor #2 (e.g. "MS STL"). + + void clear() { msPlatform.set_capacity(0); msSTLName1.set_capacity(0); msSTLName2.set_capacity(0); } + }; + + Environment& GetEnvironment(); + + + // Result + // + // An individual benchmark result. + // + struct Result + { + eastl::string8 msName; // Test name (e.g. "vector/insert"). + int mUnits; // Timing units (e.g. EA::StdC::Stopwatch::kUnitsSeconds). + int64_t mTime1; // Time of competitor #1. + uint64_t mTime1NS; // Nanoseconds. + int64_t mTime2; // Time of competitor #2. + int64_t mTime2NS; // Nanoseconds. + eastl::string8 msNotes; // Any comments to attach to this result. + + Result() : msName(), mUnits(EA::StdC::Stopwatch::kUnitsCPUCycles), + mTime1(0), mTime1NS(0), mTime2(0), mTime2NS(0), msNotes() { } + }; + + inline bool operator<(const Result& r1, const Result& r2) + { return r1.msName < r2.msName; } + + typedef eastl::set<Result> ResultSet; + + ResultSet& GetResultSet(); + + + // Scratch sprintf buffer + extern char gScratchBuffer[1024]; + + + + // Utility functions + // + void DoNothing(...); + void AddResult(const char* pName, int units, int64_t nTime1, int64_t nTime2, const char* pNotes = NULL); + void PrintResults(); + void WriteTime(int64_t timeNS, eastl::string& sTime); + + +} // namespace Benchmark + + + + +/////////////////////////////////////////////////////////////////////////////// +/// LargePOD +/// +/// Implements a structure which is essentially a largish POD. Useful for testing +/// containers and algorithms for their ability to efficiently work with PODs. +/// This class isn't strictly a POD by the definition of the C++ standard, +/// but it suffices for our interests. +/// +struct LargeObject +{ + int32_t mData[2048]; +}; + +struct LargePOD +{ + LargeObject mLargeObject1; + LargeObject mLargeObject2; + const char* mpName1; + const char* mpName2; + + explicit LargePOD(int32_t x = 0) // A true POD doesn't have a non-trivial constructor. + { + memset(mLargeObject1.mData, 0, sizeof(mLargeObject1.mData)); + memset(mLargeObject2.mData, 0, sizeof(mLargeObject2.mData)); + mLargeObject1.mData[0] = x; + + mpName1 = "LargePOD1"; + mpName2 = "LargePOD2"; + } + + LargePOD(const LargePOD& largePOD) // A true POD doesn't have a non-trivial copy-constructor. + : mLargeObject1(largePOD.mLargeObject1), + mLargeObject2(largePOD.mLargeObject2), + mpName1(largePOD.mpName1), + mpName2(largePOD.mpName2) + { + } + + virtual ~LargePOD() { } + + LargePOD& operator=(const LargePOD& largePOD) // A true POD doesn't have a non-trivial assignment operator. + { + if(&largePOD != this) + { + mLargeObject1 = largePOD.mLargeObject1; + mLargeObject2 = largePOD.mLargeObject2; + mpName1 = largePOD.mpName1; + mpName2 = largePOD.mpName2; + } + return *this; + } + + virtual void DoSomething() // Note that by declaring this virtual, this class is not truly a POD. + { // But it acts like a POD for the purposes of EASTL algorithms. + mLargeObject1.mData[1]++; + } + + operator int() + { + return (int)mLargeObject1.mData[0]; + } +}; + +//EASTL_DECLARE_POD(LargePOD); +//EASTL_DECLARE_TRIVIAL_CONSTRUCTOR(LargePOD); +//EASTL_DECLARE_TRIVIAL_COPY(LargePOD); +//EASTL_DECLARE_TRIVIAL_ASSIGN(LargePOD); +//EASTL_DECLARE_TRIVIAL_DESTRUCTOR(LargePOD); +//EASTL_DECLARE_TRIVIAL_RELOCATE(LargePOD); + +// Operators +// We specifically define only == and <, in order to verify that +// our containers and algorithms are not mistakenly expecting other +// operators for the contained and manipulated classes. +inline bool operator==(const LargePOD& t1, const LargePOD& t2) +{ + return (memcmp(&t1.mLargeObject1, &t2.mLargeObject1, sizeof(t1.mLargeObject1)) == 0) && + (memcmp(&t1.mLargeObject2, &t2.mLargeObject2, sizeof(t1.mLargeObject2)) == 0) && + (strcmp(t1.mpName1, t2.mpName1) == 0) && + (strcmp(t1.mpName2, t2.mpName2) == 0); +} + +inline bool operator<(const LargePOD& t1, const LargePOD& t2) +{ + return (memcmp(&t1.mLargeObject1, &t2.mLargeObject1, sizeof(t1.mLargeObject1)) < 0) && + (memcmp(&t1.mLargeObject2, &t2.mLargeObject2, sizeof(t1.mLargeObject2)) < 0) && + (strcmp(t1.mpName1, t2.mpName1) < 0) && + (strcmp(t1.mpName2, t2.mpName2) < 0); +} + + + + + +#endif // Header sentry + + + + + + + + + + + + + + + + + + + + + + diff --git a/benchmark/source/main.cpp b/benchmark/source/main.cpp new file mode 100644 index 0000000..59ff5a9 --- /dev/null +++ b/benchmark/source/main.cpp @@ -0,0 +1,194 @@ +/////////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +/////////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#if !EASTL_OPENSOURCE + #include <PPMalloc/EAGeneralAllocatorDebug.h> +#endif +#include <EAStdC/EASprintf.h> +#include <EAStdC/EAStopwatch.h> +#include <EAStdC/EAString.h> +#include <EASTL/internal/config.h> +#include <string.h> +#include <stdio.h> +EA_DISABLE_VC_WARNING(4946) +#include "EAMain/EAEntryPointMain.inl" +#include "EASTLTestAllocator.h" + + +/////////////////////////////////////////////////////////////////////////////// +// gpEAGeneralAllocator / gpEAGeneralAllocatorDebug +// +#if !EASTL_OPENSOURCE +namespace EA +{ + namespace Allocator + { + #ifdef EA_DEBUG + extern GeneralAllocatorDebug gGeneralAllocator; + extern PPM_API GeneralAllocatorDebug* gpEAGeneralAllocatorDebug; + #else + extern GeneralAllocator gGeneralAllocator; + extern PPM_API GeneralAllocator* gpEAGeneralAllocator; + #endif + } +} +#endif + + +/////////////////////////////////////////////////////////////////////////////// +// Required by EASTL. +// +#if !defined(EASTL_EASTDC_VSNPRINTF) || !EASTL_EASTDC_VSNPRINTF + int Vsnprintf8(char8_t* pDestination, size_t n, const char8_t* pFormat, va_list arguments) + { + return EA::StdC::Vsnprintf(pDestination, n, pFormat, arguments); + } + + int Vsnprintf16(char16_t* pDestination, size_t n, const char16_t* pFormat, va_list arguments) + { + return EA::StdC::Vsnprintf(pDestination, n, pFormat, arguments); + } + + #if (EASTDC_VERSION_N >= 10600) + int Vsnprintf32(char32_t* pDestination, size_t n, const char32_t* pFormat, va_list arguments) + { + return EA::StdC::Vsnprintf(pDestination, n, pFormat, arguments); + } + #endif +#endif + + +/////////////////////////////////////////////////////////////////////////////// +// main +// +int EAMain(int argc, char* argv[]) +{ + bool bWaitAtEnd = false; + bool bPrintHelp = false; + int nOptionCount = 0; + int nErrorCount = 0; + + EA::EAMain::PlatformStartup(); + EA::EAMain::SetVerbosity(2); // Default value. + + // Set up debug parameters. + #ifdef EA_DEBUG + // Only enable this temporarily to help find any problems you might find. + // EA::Allocator::gpEAGeneralAllocatorDebug->SetAutoHeapValidation(EA::Allocator::GeneralAllocator::kHeapValidationLevelBasic, 16); + #endif + + // Parse command line arguments + for(int i = 1; i < argc; i++) + { + if(strstr(argv[i], "-w") == argv[i]) + { + bWaitAtEnd = true; + nOptionCount++; + } + else if(strstr(argv[i], "-v") == argv[i]) + { + uint32_t verbosity = EA::StdC::AtoU32(argv[i] + 3); + EA::EAMain::SetVerbosity(verbosity); + nOptionCount++; + } + else if(strstr(argv[i], "-l:") == argv[i]) + { + gEASTL_TestLevel = atoi(argv[i] + 3); + if(gEASTL_TestLevel < kEASTL_TestLevelLow) + gEASTL_TestLevel = kEASTL_TestLevelLow; + else if(gEASTL_TestLevel > kEASTL_TestLevelHigh) + gEASTL_TestLevel = kEASTL_TestLevelHigh; + nOptionCount++; + } + else if(strstr(argv[i], "-s:") == argv[i]) + { + uint32_t seed = (eastl_size_t)atoi(argv[i] + 3); + EA::UnitTest::SetRandSeed(seed); + nOptionCount++; + } + else if((strstr(argv[i], "-?") == argv[i]) || (strstr(argv[i], "-h") == argv[i])) + { + bPrintHelp = true; + nOptionCount++; + } + } + + // Print user help. + if(!bPrintHelp) + bPrintHelp = (nOptionCount == 0); + + if(bPrintHelp) + { + EASTLTest_Printf("Options\n"); + EASTLTest_Printf(" -w Wait at end.\n"); + EASTLTest_Printf(" -l:N Test level in range of [1, 10]. 10 means maximum testing.\n"); + EASTLTest_Printf(" -s:N Specify a randomization seed. 0 is default and means use clock.\n"); + EASTLTest_Printf(" -? Show help.\n"); + } + + + // Set up test information + Benchmark::Environment& environment = Benchmark::GetEnvironment(); + environment.msPlatform = EA_PLATFORM_DESCRIPTION; + environment.msSTLName1 = GetStdSTLName(); + environment.msSTLName2 = "EASTL"; + + + // Run tests + #ifndef EA_DEBUG + EA::UnitTest::SetHighThreadPriority(); + #endif + + EA::StdC::Stopwatch stopwatch(EA::StdC::Stopwatch::kUnitsSeconds, true); // Measure seconds, start the counting immediately. + + BenchmarkAlgorithm(); + BenchmarkList(); + BenchmarkString(); + BenchmarkVector(); + BenchmarkDeque(); + BenchmarkSet(); + BenchmarkMap(); + BenchmarkHash(); + BenchmarkHeap(); + BenchmarkBitset(); + BenchmarkSort(); + BenchmarkTupleVector(); + + stopwatch.Stop(); + + #ifndef EA_DEBUG + EA::UnitTest::SetNormalThreadPriority(); + #endif + + Benchmark::PrintResults(); + + eastl::string sClockTime; + Benchmark::WriteTime(stopwatch.GetElapsedTime(), sClockTime); + + EASTLTest_Printf("Time to complete all tests: %s.\n", sClockTime.c_str()); + + // Done + if(bWaitAtEnd) + { + EASTLTest_Printf("\nPress any key to exit.\n"); + getchar(); // Wait for the user and shutdown + } + + EA::EAMain::PlatformShutdown(nErrorCount); + + return 0; +} + + + + + + + + + + |