From e59cf7b09e7388d369e8d2bf73501cde79c28708 Mon Sep 17 00:00:00 2001 From: Toni Uhlig Date: Thu, 8 Apr 2021 16:43:58 +0200 Subject: Squashed 'EASTL/' content from commit fad5471 git-subtree-dir: EASTL git-subtree-split: fad54717f8e4ebb13b20095da7efd07a53af0f10 --- benchmark/CMakeLists.txt | 93 ++ benchmark/source/BenchmarkAlgorithm.cpp | 1241 +++++++++++++++++++++++++ benchmark/source/BenchmarkBitset.cpp | 366 ++++++++ benchmark/source/BenchmarkDeque.cpp | 342 +++++++ benchmark/source/BenchmarkHash.cpp | 469 ++++++++++ benchmark/source/BenchmarkHeap.cpp | 238 +++++ benchmark/source/BenchmarkList.cpp | 382 ++++++++ benchmark/source/BenchmarkMap.cpp | 382 ++++++++ benchmark/source/BenchmarkSet.cpp | 353 ++++++++ benchmark/source/BenchmarkSort.cpp | 1399 +++++++++++++++++++++++++++++ benchmark/source/BenchmarkString.cpp | 531 +++++++++++ benchmark/source/BenchmarkTupleVector.cpp | 667 ++++++++++++++ benchmark/source/BenchmarkVector.cpp | 452 ++++++++++ benchmark/source/EASTLBenchmark.cpp | 291 ++++++ benchmark/source/EASTLBenchmark.h | 228 +++++ benchmark/source/main.cpp | 194 ++++ 16 files changed, 7628 insertions(+) create mode 100644 benchmark/CMakeLists.txt create mode 100644 benchmark/source/BenchmarkAlgorithm.cpp create mode 100644 benchmark/source/BenchmarkBitset.cpp create mode 100644 benchmark/source/BenchmarkDeque.cpp create mode 100644 benchmark/source/BenchmarkHash.cpp create mode 100644 benchmark/source/BenchmarkHeap.cpp create mode 100644 benchmark/source/BenchmarkList.cpp create mode 100644 benchmark/source/BenchmarkMap.cpp create mode 100644 benchmark/source/BenchmarkSet.cpp create mode 100644 benchmark/source/BenchmarkSort.cpp create mode 100644 benchmark/source/BenchmarkString.cpp create mode 100644 benchmark/source/BenchmarkTupleVector.cpp create mode 100644 benchmark/source/BenchmarkVector.cpp create mode 100644 benchmark/source/EASTLBenchmark.cpp create mode 100644 benchmark/source/EASTLBenchmark.h create mode 100644 benchmark/source/main.cpp (limited to 'benchmark') diff --git a/benchmark/CMakeLists.txt b/benchmark/CMakeLists.txt new file mode 100644 index 0000000..94bc971 --- /dev/null +++ b/benchmark/CMakeLists.txt @@ -0,0 +1,93 @@ +#------------------------------------------------------------------------------------------- +# Copyright (C) Electronic Arts Inc. All rights reserved. +#------------------------------------------------------------------------------------------- + +#------------------------------------------------------------------------------------------- +# CMake info +#------------------------------------------------------------------------------------------- +cmake_minimum_required(VERSION 3.1) +project(EASTLBenchmarks CXX) +include(CTest) + +#------------------------------------------------------------------------------------------- +# Defines +#------------------------------------------------------------------------------------------- +add_definitions(-D_CHAR16T) + +#------------------------------------------------------------------------------------------- +# Include directories +#------------------------------------------------------------------------------------------- +include_directories(source) +include_directories(../test/source) + +#------------------------------------------------------------------------------------------- +# Compiler Flags +#------------------------------------------------------------------------------------------- +set (CMAKE_MODULE_PATH "${CMAKE_MODULE_PATH};${CMAKE_CURRENT_SOURCE_DIR}/../scripts/CMake") +include(CommonCppFlags) + +# Libstdc++ calls new internally, since DLLs have no weak symbols, runtime symbol resolution fails and EASTL's new is not called. +# Linking against static libstdc++ fixes this. +# See https://github.com/electronicarts/EASTL/issues/40 for more info. +if (CMAKE_CXX_COMPILER_ID MATCHES "Clang" OR CMAKE_CXX_COMPILER_ID MATCHES "GNU" AND MINGW) + set(CMAKE_EXE_LINKER_FLAGS_RELEASE "${CMAKE_EXE_LINKER_FLAGS_RELEASE} -static-libstdc++") + set(CMAKE_EXE_LINKER_FLAGS_RELWITHDEBINFO "${CMAKE_EXE_LINKER_FLAGS_RELWITHDEBINFO} -static-libstdc++") + set(CMAKE_EXE_LINKER_FLAGS_MINSIZEREL "${CMAKE_EXE_LINKER_FLAGS_MINSIZEREL} -static-libstdc++") +endif() + +if (CMAKE_CXX_COMPILER_ID MATCHES "Clang" AND CMAKE_BUILD_TYPE MATCHES "MinSizeRel" AND MINGW) + message(FATAL_ERROR "FIXME: MinSizeRel on MingW-w64's Clang fails to link.") +endif() + +# The benchmark suite fails to compile if char8_t is enabled, so disable it. +if (EASTL_NO_CHAR8T_FLAG) + add_compile_options(${EASTL_NO_CHAR8T_FLAG}) +endif() + +#------------------------------------------------------------------------------------------- +# Source files +#------------------------------------------------------------------------------------------- +file(GLOB EASTLBENCHMARK_SOURCES "source/*.cpp" "../test/source/EASTLTestAllocator.cpp" "../test/source/EASTLTest.cpp") +set(SOURCES ${EASTLBENCHMARK_SOURCES}) + +#------------------------------------------------------------------------------------------- +# Defines +#------------------------------------------------------------------------------------------- +add_definitions(-D_CRT_SECURE_NO_WARNINGS) +add_definitions(-D_SCL_SECURE_NO_WARNINGS) +add_definitions(-DEASTL_THREAD_SUPPORT_AVAILABLE=0) +add_definitions(-DEASTL_OPENSOURCE=1) +add_definitions(-D_SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS) # silence std::hash_map deprecation warnings + +if(NOT EASTL_BUILD_TESTS) + add_subdirectory(../test/packages/EAStdC ../test/EAStdC) + add_subdirectory(../test/packages/EAAssert ../test/EAAssert) + add_subdirectory(../test/packages/EAThread ../test/EAThread) + add_subdirectory(../test/packages/EATest ../test/EATest) + add_subdirectory(../test/packages/EAMain ../test/EAMain) +endif() + +#------------------------------------------------------------------------------------------- +# Executable definition +#------------------------------------------------------------------------------------------- +add_executable(EASTLBenchmarks ${EASTLBENCHMARK_SOURCES}) + +set(THREADS_PREFER_PTHREAD_FLAG ON) +find_package(Threads REQUIRED) + +set(EASTLBenchmark_Libraries + EABase + EAAssert + EAMain + EAThread + EAStdC + EASTL + EATest) +target_link_libraries(EASTLBenchmarks ${EASTLBenchmark_Libraries} Threads::Threads) + +#------------------------------------------------------------------------------------------- +# Run Unit tests and verify the results. +#------------------------------------------------------------------------------------------- +add_test(EASTLBenchmarkRuns EASTLBenchmarks) +set_tests_properties (EASTLBenchmarkRuns PROPERTIES PASS_REGULAR_EXPRESSION "RETURNCODE=0") + 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 +#include +#include +#include +#include +#include +#include +#include +#include + +EA_DISABLE_ALL_VC_WARNINGS() +#include +#include +#include +#include +#include +#include +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 StdVectorUChar; +typedef eastl::vector EaVectorUChar; + +typedef std::vector StdVectorSChar; +typedef eastl::vector EaVectorSChar; + +typedef std::vector StdVectorUint32; +typedef eastl::vector EaVectorUint32; + +typedef std::vector StdVectorUint64; +typedef eastl::vector EaVectorUint64; + +typedef std::vector StdVectorTO; +typedef eastl::vector 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 + inline InputIterator + next(InputIterator it, typename std::iterator_traits::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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 itPair = std::equal_range(c.begin(), c.end(), *pBegin++); + + Benchmark::DoNothing(&itPair); + } + stopwatch.Stop(); + } + + template + 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 itPair = eastl::equal_range(c.begin(), c.end(), *pBegin++); + Benchmark::DoNothing(&itPair); + } + stopwatch.Stop(); + } + + + + template + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + void TestReverseStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + std::reverse(first, last); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + template + void TestReverseEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + eastl::reverse(first, last); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p", &*first); + } + + + + template + 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 + 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 + 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 + 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", 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", 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", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestUniqueStd(stopwatch1, stdVectorUint64); + TestUniqueEa (stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("algorithm/unique/vector", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestUniqueStd(stopwatch1, stdVectorTO); + TestUniqueEa (stopwatch2, eaVectorTO); + + if(i == 1) + Benchmark::AddResult("algorithm/unique/vector", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test min_element + /////////////////////////////// + + TestMinElementStd(stopwatch1, stdVectorTO); + TestMinElementEa (stopwatch2, eaVectorTO); + + if(i == 1) + Benchmark::AddResult("algorithm/min_element/vector", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test count + /////////////////////////////// + + TestCountStd(stopwatch1, stdVectorUint64); + TestCountEa (stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("algorithm/count/vector", 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", 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", 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", 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", 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", 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", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } + +} + + +void BenchmarkAlgorithm4(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + std::vector stdVectorUint321(10000); + std::vector stdVectorUint322(10000); + eastl::vector eaVectorUint321(10000); + eastl::vector eaVectorUint322(10000); + + std::vector stdVectorUint64(100000); + eastl::vector 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", 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", 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", 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", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } +} + + +void BenchmarkAlgorithm5(EASTLTest_Rand& /*rng*/, EA::StdC::Stopwatch& stopwatch1, EA::StdC::Stopwatch& stopwatch2) +{ + { + std::vector stdVectorVoid(100000); + eastl::vector eaVectorVoid(100000); + + std::vector stdVectorChar(100000); + eastl::vector eaVectorChar(100000); + + std::vector stdVectorBool(100000); + eastl::vector 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", 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/'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/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* pstdVectorLP1 = new std::vector(100); + std::vector* pstdVectorLP2 = new std::vector(100); + eastl::vector* peaVectorLP1 = new eastl::vector(100); + eastl::vector* peaVectorLP2 = new eastl::vector(100); + + // Aliases. + std::vector& stdVectorLP1 = *pstdVectorLP1; + std::vector& stdVectorLP2 = *pstdVectorLP2; + eastl::vector& eaVectorLP1 = *peaVectorLP1; + eastl::vector& 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", 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", 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 stdListTO(10000); + eastl::list eaListTO(10000); + + std::vector stdVectorTO(10000); + eastl::vector 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", 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", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + } + } + + { + // Create some containers and seed them with incremental values (i.e. 0, 1, 2, 3...). + eastl::slist eaSlistIntLarge(10000); + eastl::generate(eaSlistIntLarge.begin(), eaSlistIntLarge.end(), GenerateIncrementalIntegers()); + + + 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 stdListIntLarge(10000); + eastl::generate(stdListIntLarge.begin(), stdListIntLarge.end(), GenerateIncrementalIntegers()); + + eastl::list eaListIntLarge(10000); + eastl::generate(eaListIntLarge.begin(), eaListIntLarge.end(), GenerateIncrementalIntegers()); + + + std::vector stdVectorIntLarge(10000); + eastl::generate(stdVectorIntLarge.begin(), stdVectorIntLarge.end(), GenerateIncrementalIntegers()); + + eastl::vector eaVectorIntLarge(10000); + eastl::generate(eaVectorIntLarge.begin(), eaVectorIntLarge.end(), GenerateIncrementalIntegers()); + + + std::list stdListIntSmall(10); + eastl::generate(stdListIntLarge.begin(), stdListIntLarge.end(), GenerateIncrementalIntegers()); + + eastl::list eaListIntSmall(10); + eastl::generate(eaListIntLarge.begin(), eaListIntLarge.end(), GenerateIncrementalIntegers()); + + + std::vector stdVectorIntSmall(10); + eastl::generate(stdVectorIntLarge.begin(), stdVectorIntLarge.end(), GenerateIncrementalIntegers()); + + eastl::vector eaVectorIntSmall(10); + eastl::generate(eaVectorIntLarge.begin(), eaVectorIntLarge.end(), GenerateIncrementalIntegers()); + + + + std::list stdListTOLarge(10000); + eastl::generate(stdListTOLarge.begin(), stdListTOLarge.end(), GenerateIncrementalIntegers()); + + eastl::list eaListTOLarge(10000); + eastl::generate(eaListTOLarge.begin(), eaListTOLarge.end(), GenerateIncrementalIntegers()); + + + std::vector stdVectorTOLarge(10000); + eastl::generate(stdVectorTOLarge.begin(), stdVectorTOLarge.end(), GenerateIncrementalIntegers()); + + eastl::vector eaVectorTOLarge(10000); + eastl::generate(eaVectorTOLarge.begin(), eaVectorTOLarge.end(), GenerateIncrementalIntegers()); + + + std::list stdListTOSmall(10); + eastl::generate(stdListTOSmall.begin(), stdListTOSmall.end(), GenerateIncrementalIntegers()); + + eastl::list eaListTOSmall(10); + eastl::generate(eaListTOSmall.begin(), eaListTOSmall.end(), GenerateIncrementalIntegers()); + + + std::vector stdVectorTOSmall(10); + eastl::generate(stdVectorTOSmall.begin(), stdVectorTOSmall.end(), GenerateIncrementalIntegers()); + + eastl::vector eaVectorTOSmall(10); + eastl::generate(eaVectorTOSmall.begin(), eaVectorTOSmall.end(), GenerateIncrementalIntegers()); + + + 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 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> 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 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", 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 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", 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", 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", 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", 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", 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 srcVecA(ElementCount); + eastl::vector srcVecB(ElementCount); + + std::vector stdVecAInt(ElementCount); + std::vector stdVecBInt(ElementCount); + std::vector stdVecOutInt(2 * ElementCount); + std::vector stdVecATestObject(ElementCount); + std::vector stdVecBTestObject(ElementCount); + std::vector stdVecOutTestObject(2 * ElementCount); + + eastl::vector eaVecAInt(ElementCount); + eastl::vector eaVecBInt(ElementCount); + eastl::vector eaVecOutInt(2 * ElementCount); + eastl::vector eaVecATestObject(ElementCount); + eastl::vector eaVecBTestObject(ElementCount); + eastl::vector 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 (unpred)", + "algorithm/merge/vector (pred)", + }, + { + "algorithm/merge/vector (unpred)", + "algorithm/merge/vector (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 +#include + + +EA_DISABLE_ALL_VC_WARNINGS() +#include +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +namespace +{ + template + 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 + 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 + 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 + 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 + 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 + 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 + 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 +#include +#include +#include +#include + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) // behavior change: X called instead of Y +#endif +#include +#include +#include +#include +#include +#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 StdDeque; +typedef eastl::deque 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 + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector& 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 + void TestPushFront(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector& 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 + 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 + 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 + 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 + 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 + 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 + 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 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 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/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/push_front", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[] + /////////////////////////////// + + TestBracket(stopwatch1, stdDeque); + TestBracket(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration + /////////////////////////////// + + TestIteration(stopwatch1, stdDeque); + TestIteration(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find() + /////////////////////////////// + + TestFind(stopwatch1, stdDeque); + TestFind(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque/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/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + #endif + + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestInsert(stopwatch1, stdDeque); + TestInsert(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestErase(stopwatch1, stdDeque); + TestErase(stopwatch2, eaDeque); + + if(i == 1) + Benchmark::AddResult("deque/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 +#include +#include +#include +#include + + + +EA_DISABLE_ALL_VC_WARNINGS() +#include +#include +#include +#include +EA_RESTORE_ALL_VC_WARNINGS() + + + +using namespace EA; + + +// HashString8 +// +// We define a string +// +template +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; +using StdMapStrUint32 = std::unordered_map>; + +using EaMapUint32TO = eastl::hash_map; +using EaMapStrUint32 = eastl::hash_map>; + + +namespace +{ + template + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + c.insert(pArrayBegin, pArrayEnd); + stopwatch.Stop(); + } + + + template + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 > stdVectorUT(10000); + eastl::vector< eastl::pair > eaVectorUT(10000); + + eastl::vector< std::pair< std::string, uint32_t> > stdVectorSU(10000); + eastl::vector< eastl::pair > 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(n1, TestObject(n2)); + eaVectorUT[i] = eastl::pair(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(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/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/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/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/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/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/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/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/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/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/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/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/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/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/erase pos", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestErasePosition(stopwatch1, stdMapStrUint32); + TestErasePosition(stopwatch2, eaMapStrUint32); + + if(i == 1) + Benchmark::AddResult("hash_map/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/erase range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestEraseRange(stopwatch1, stdMapStrUint32); + TestEraseRange(stopwatch2, eaMapStrUint32); + + if(i == 1) + Benchmark::AddResult("hash_map/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/clear", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestClear(stopwatch1, stdMapStrUint32); + TestClear(stopwatch2, eaMapStrUint32); + + if(i == 1) + Benchmark::AddResult("hash_map/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 +#include +#include +#include + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) // behavior change: X called instead of Y +#endif +#include +#include +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; + + +namespace +{ + template + void TestMakeHeapStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + std::make_heap(first, last); + stopwatch.Stop(); + } + + template + void TestMakeHeapEa(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + eastl::make_heap(first, last); + stopwatch.Stop(); + } + + + + template + 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 + 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 + 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 + 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 + void TestSortHeapStd(EA::StdC::Stopwatch& stopwatch, Iterator first, Iterator last) + { + stopwatch.Restart(); + std::sort_heap(first, last); + stopwatch.Stop(); + } + + template + 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 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 + std::vector stdVectorTO(kArraySize * 2); + std::vector stdVectorTO2(kArraySize); + eastl::vector eaVectorTO(kArraySize * 2); + eastl::vector 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)/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)/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)/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)/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 +#include +#include +#include +#include + +#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 +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; +using namespace eastl; + + + +typedef std::list StdListTO; +typedef eastl::list EaListTO; + + + +namespace +{ + void DoNothing(void*) + { + // Empty + } + + + template + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 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/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/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/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/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/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/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/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/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test reverse() + /////////////////////////////// + + TestReverse(stopwatch1, stdListTO); + TestReverse(stopwatch2, eaListTO); + + if(i == 1) + Benchmark::AddResult("list/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/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/splice", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + + /////////////////////////////// + // Test erase() + /////////////////////////////// + + TestErase(stopwatch1, stdListTO); + TestErase(stopwatch2, eaListTO); + + if(i == 1) + Benchmark::AddResult("list/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 +#include +#include +#include + +EA_DISABLE_ALL_VC_WARNINGS() +#include +#include +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +typedef std::map StdMapTOUint32; +typedef eastl::map EaMapTOUint32; + + +namespace +{ + template + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 > stdVector(10000); + eastl::vector< eastl::pair > 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(n1), n2); + eaVector[i] = eastl::pair(TestObject(n1), n2); + } + + for(int i = 0; i < 2; i++) + { + StdMapTOUint32 stdMapTOUint32; + EaMapTOUint32 eaMapTOUint32; + + + /////////////////////////////// + // Test insert(const value_type&) + /////////////////////////////// + const std::pair stdHighValue(TestObject(0x7fffffff), 0x7fffffff); + const eastl::pair 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/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/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/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/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/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/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/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/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/erase/key", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(iterator position) + /////////////////////////////// + + TestErasePosition(stopwatch1, stdMapTOUint32); + TestErasePosition(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map/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/erase/range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test clear() + /////////////////////////////// + + TestClear(stopwatch1, stdMapTOUint32); + TestClear(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map/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 +#include +#include +#include + +EA_DISABLE_ALL_VC_WARNINGS() +#include +#include +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +typedef std::set StdSetUint32; +typedef eastl::set EaSetUint32; + + +namespace +{ + template + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 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/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration + /////////////////////////////// + + TestIteration(stopwatch1, stdSetUint32); + TestIteration(stopwatch2, eaSetUint32); + + if(i == 1) + Benchmark::AddResult("set/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/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/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/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/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/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/erase/val", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(iterator position) + /////////////////////////////// + + TestErasePosition(stopwatch1, stdSetUint32); + TestErasePosition(stopwatch2, eaSetUint32); + + if(i == 1) + Benchmark::AddResult("set/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/erase range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test clear() + /////////////////////////////// + + TestClear(stopwatch1, stdSetUint32); + TestClear(stopwatch2, eaSetUint32); + + if(i == 1) + Benchmark::AddResult("set/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 +#include +#include +#include +#include "EASTLBenchmark.h" +#include "EASTLTest.h" + +EA_DISABLE_ALL_VC_WARNINGS() +#include +#include +#include +#include +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 StdVectorVP; +typedef eastl::vector EaVectorVP; + +typedef std::vector StdVectorInt; +typedef eastl::vector EaVectorInt; + +typedef std::vector StdVectorTO; +typedef eastl::vector 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 + void Randomize(eastl::vector& v, EA::UnitTest::RandGenT& 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 + 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::nAssignCount = 0; + + template + bool operator <(const SlowAssign& a, const SlowAssign& b) + { return a.x < b.x; } + + + // SlowCompare + // Implements a compare which is N time slower than a simple integer compare. + template + 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::nCompareCount = 0; + + + // qsort callback functions + // qsort compare function returns negative if b > a and positive if a > b. + template + 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::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 + 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 + 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 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 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 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 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>(v.begin(), v.end(), pBuffer); + stopwatch.Stop(); + break; + + case sf_qsort: + stopwatch.Restart(); + qsort(&v[0], (size_t)v.size(), sizeof(ElementType), CompareInteger); + stopwatch.Stop(); + break; + + case sf_std_sort: + stopwatch.Restart(); + std::sort(v.data(), v.data() + v.size(), std::less()); + stopwatch.Stop(); + break; + + case sf_std_stable_sort: + stopwatch.Restart(); + std::stable_sort(v.data(), v.data() + v.size(), std::less()); + 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 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 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 ElementType; + typedef eastl::less 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 v(size); + + Randomize(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>(v.begin(), v.end(), pBuffer); + stopwatch.Stop(); + break; + + case sf_std_sort: + stopwatch.Restart(); + std::sort(v.begin(), v.end(), std::less()); + stopwatch.Stop(); + break; + + case sf_std_stable_sort: + stopwatch.Restart(); + std::stable_sort(v.begin(), v.end(), std::less()); + 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 OutputResultCallback; +typedef eastl::function PostExecuteCallback; +typedef eastl::function PreExecuteCallback; + + +template +static int CompareSmallInputSortPerformanceHelper(eastl::vector &arraySizes, eastl::vector &sortFunctions, const PreExecuteCallback &preExecuteCallback, const PostExecuteCallback &postExecuteCallback, const OutputResultCallback &outputResultCallback) +{ + int nErrorCount = 0; + + EA::UnitTest::RandGenT 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 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 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 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>( + 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>( + arraySizes, sortFunctions, PreExecuteCallback([]() { SlowCompare::Reset(); }), + PostExecuteCallback( + [](BenchmarkResult& result) { result.mCompareCount = (uint64_t)SlowCompare::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, eastl::less>>( + arraySizes, sortFunctions, PreExecuteCallback([]() { SlowAssign::Reset(); }), + PostExecuteCallback([](BenchmarkResult& result) { + result.mCompareCount = (uint64_t)SlowCompare::nCompareCount; + result.mAssignCount = (uint64_t)SlowAssign::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 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 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", 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/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", 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/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", 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/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 +#include +#include +#include + +EA_DISABLE_ALL_VC_WARNINGS() +#include +#include +#include +#include +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +namespace +{ + template + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 + 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 ss8(16, 0); // We initialize to size of 16 because different implementations may make + eastl::basic_string 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 ss16(16, 0); // We try to nullify this tradeoff for the tests below by starting all at + eastl::basic_string es16(16, 0); // the same baseline allocation. + + + /////////////////////////////// + // Test push_back + /////////////////////////////// + + TestPushBack(stopwatch1, ss8); + TestPushBack(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestPushBack(stopwatch1, ss16); + TestPushBack(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string/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/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/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/erase/pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestErase1(stopwatch1, ss16); + TestErase1(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string/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/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/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/reserve", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestReserve(stopwatch1, ss16); + TestReserve(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string/reserve", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test size() + /////////////////////////////// + + TestSize(stopwatch1, ss8); + TestSize(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string/size", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSize(stopwatch1, ss16); + TestSize(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string/size", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestBracket(stopwatch1, ss8); + TestBracket(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestBracket(stopwatch1, ss16); + TestBracket(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration via find(). + /////////////////////////////// + + TestFind(stopwatch1, ss8); + TestFind(stopwatch2, es8); + + if(i == 1) + Benchmark::AddResult("string/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestFind(stopwatch1, ss16); + TestFind(stopwatch2, es16); + + if(i == 1) + Benchmark::AddResult("string/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/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/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/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/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/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/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/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/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/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/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/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/find_last_of/p,pos,n", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + #endif + + /////////////////////////////// + // Test compare() + /////////////////////////////// + + std::basic_string ss8X(ss8); + eastl::basic_string es8X(es8); + std::basic_string ss16X(ss16); + eastl::basic_string es16X(es16); + + TestCompare(stopwatch1, ss8, ss8X); + TestCompare(stopwatch2, es8, es8X); + + if(i == 1) + Benchmark::AddResult("string/compare", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestCompare(stopwatch1, ss16, ss16X); + TestCompare(stopwatch2, es16, es16X); + + if(i == 1) + Benchmark::AddResult("string/compare", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + + /////////////////////////////// + // Test swap() + /////////////////////////////// + + TestSwap(stopwatch1, ss8, ss8X); + TestSwap(stopwatch2, es8, es8X); + + if(i == 1) + Benchmark::AddResult("string/swap", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + TestSwap(stopwatch1, ss16, ss16X); + TestSwap(stopwatch2, es16, es16X); + + if(i == 1) + Benchmark::AddResult("string/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 +#include +#include +#include + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) +#endif +#include +#include +#include +#include +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; + + +typedef std::vector StdVectorUint64; +typedef eastl::tuple_vector EaTupleVectorUint64; + + struct PaddingStruct +{ + char padding[56] = { 0 }; +}; +static const PaddingStruct DefaultPadding; +typedef eastl::tuple PaddedTuple; +typedef std::vector StdVectorUint64Padded; +typedef eastl::tuple_vector 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 + 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 + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector& 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 + 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 + 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 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 + 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 + 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 + 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 + void TestMoveReallocate(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + while(c.size() < 8192) + c.resize(c.capacity() + 1); + stopwatch.Stop(); + } + + + template + 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 + void TestTuplePushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector& 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 + 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 + 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 + 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 + 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 + 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 rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector 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/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestBracket(stopwatch1, stdVectorUint64); + TestBracket(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector/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/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/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + #endif + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestInsert(stopwatch1, stdVectorUint64); + TestInsert(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestErase(stopwatch1, stdVectorUint64); + TestErase(stopwatch2, eaTupleVectorUint64); + + if(i == 1) + Benchmark::AddResult("tuple_vector/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of MovableType + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector stdVectorMovableType; + eastl::tuple_vector eaTupleVectorMovableType; + + TestMoveReallocate(stopwatch1, stdVectorMovableType); + TestMoveReallocate(stopwatch2, eaTupleVectorMovableType); + + if(i == 1) + Benchmark::AddResult("tuple_vector/reallocate", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + TestMoveErase(stopwatch1, stdVectorMovableType); + TestMoveErase(stopwatch2, eaTupleVectorMovableType); + + if(i == 1) + Benchmark::AddResult("tuple_vector/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of AutoRefCount + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector > stdVectorAutoRefCount; + eastl::tuple_vector > eaTupleVectorAutoRefCount; + + for(size_t a = 0; a < 2048; a++) + { + stdVectorAutoRefCount.push_back(AutoRefCount(new RefCounted)); + eaTupleVectorAutoRefCount.push_back(AutoRefCount(new RefCounted)); + } + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch1, stdVectorAutoRefCount); + //EASTLTest_Printf("tuple_vector/erase std counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch2, eaTupleVectorAutoRefCount); + //EASTLTest_Printf("tuple_vector/erase EA counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + if(i == 1) + Benchmark::AddResult("tuple_vector/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/push_back", stopwatch1.GetUnits(), + stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestTupleBracket(stopwatch1, stdVectorUint64Padded); + TestTupleBracket(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector/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/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/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), + stopwatch2.GetElapsedTime()); + #endif + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestTupleInsert(stopwatch1, stdVectorUint64Padded); + TestTupleInsert(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), + stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestTupleErase(stopwatch1, stdVectorUint64Padded); + TestTupleErase(stopwatch2, eaTupleVectorUint64Padded); + + if(i == 1) + Benchmark::AddResult("tuple_vector/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 +#include +#include +#include + +#ifdef _MSC_VER + #pragma warning(push, 0) + #pragma warning(disable: 4350) +#endif +#include +#include +#include +#include +#ifdef _MSC_VER + #pragma warning(pop) +#endif + + +using namespace EA; + + +typedef std::vector StdVectorUint64; +typedef eastl::vector 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 + 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 + void TestPushBack(EA::StdC::Stopwatch& stopwatch, Container& c, eastl::vector& 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 + 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 + 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 + 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 + 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 + 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 + void TestMoveReallocate(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + while(c.size() < 8192) + c.resize(c.capacity() + 1); + stopwatch.Stop(); + } + + + template + 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 rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector 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/push_back", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[]. + /////////////////////////////// + + TestBracket(stopwatch1, stdVectorUint64); + TestBracket(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector/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/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/sort", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + #endif + + /////////////////////////////// + // Test insert + /////////////////////////////// + + TestInsert(stopwatch1, stdVectorUint64); + TestInsert(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase + /////////////////////////////// + + TestErase(stopwatch1, stdVectorUint64); + TestErase(stopwatch2, eaVectorUint64); + + if(i == 1) + Benchmark::AddResult("vector/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of MovableType + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector stdVectorMovableType; + eastl::vector eaVectorMovableType; + + TestMoveReallocate(stopwatch1, stdVectorMovableType); + TestMoveReallocate(stopwatch2, eaVectorMovableType); + + if(i == 1) + Benchmark::AddResult("vector/reallocate", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + TestMoveErase(stopwatch1, stdVectorMovableType); + TestMoveErase(stopwatch2, eaVectorMovableType); + + if(i == 1) + Benchmark::AddResult("vector/erase", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////////////////// + // Test move of AutoRefCount + // Should be much faster with C++11 move. + /////////////////////////////////////////// + + std::vector > stdVectorAutoRefCount; + eastl::vector > eaVectorAutoRefCount; + + for(size_t a = 0; a < 2048; a++) + { + stdVectorAutoRefCount.push_back(AutoRefCount(new RefCounted)); + eaVectorAutoRefCount.push_back(AutoRefCount(new RefCounted)); + } + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch1, stdVectorAutoRefCount); + EASTLTest_Printf("vector/erase std counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + RefCounted::msAddRefCount = 0; + RefCounted::msReleaseCount = 0; + TestMoveErase(stopwatch2, eaVectorAutoRefCount); + EASTLTest_Printf("vector/erase EA counts: %d %d\n", RefCounted::msAddRefCount, RefCounted::msReleaseCount); + + if(i == 1) + Benchmark::AddResult("vector/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 +#include + +#ifdef _MSC_VER + #pragma warning(push, 0) +#endif +#include +#include +#include +#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 +#ifdef _MSC_VER + #pragma function(strlen, strcmp, strcpy, strcat, memcpy, memcmp, memset) +#endif + + +#include +#include +#include +#include +#include + + +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 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 +#endif +#include +#include +#include +#include +#include +#include +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; +} + + + + + + + + + + -- cgit v1.2.3