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/source/BenchmarkDeque.cpp | 342 ++++++++++++++++++++++++++++++++++++ 1 file changed, 342 insertions(+) create mode 100644 benchmark/source/BenchmarkDeque.cpp (limited to 'benchmark/source/BenchmarkDeque.cpp') 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()); + } + } +} + + + + + + + + + + + + -- cgit v1.2.3