diff options
Diffstat (limited to 'benchmark/source/BenchmarkMap.cpp')
| -rw-r--r-- | benchmark/source/BenchmarkMap.cpp | 382 |
1 files changed, 382 insertions, 0 deletions
diff --git a/benchmark/source/BenchmarkMap.cpp b/benchmark/source/BenchmarkMap.cpp new file mode 100644 index 0000000..d2fc35e --- /dev/null +++ b/benchmark/source/BenchmarkMap.cpp @@ -0,0 +1,382 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#include "EASTLBenchmark.h" +#include "EASTLTest.h" +#include <EAStdC/EAStopwatch.h> +#include <EASTL/map.h> +#include <EASTL/vector.h> +#include <EASTL/algorithm.h> + +EA_DISABLE_ALL_VC_WARNINGS() +#include <map> +#include <algorithm> +EA_RESTORE_ALL_VC_WARNINGS() + + +using namespace EA; + + +typedef std::map<TestObject, uint32_t> StdMapTOUint32; +typedef eastl::map<TestObject, uint32_t> EaMapTOUint32; + + +namespace +{ + template <typename Container, typename Value> + void TestInsert(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd, const Value& highValue) + { + stopwatch.Restart(); + c.insert(pArrayBegin, pArrayEnd); + stopwatch.Stop(); + c.insert(highValue); + } + + + template <typename Container, typename Value> + void TestIteration(EA::StdC::Stopwatch& stopwatch, const Container& c, const Value& findValue) + { + stopwatch.Restart(); + typename Container::const_iterator it = eastl::find(c.begin(), c.end(), findValue); // It shouldn't matter what find implementation we use here, as it merely iterates values. + stopwatch.Stop(); + if(it != c.end()) + sprintf(Benchmark::gScratchBuffer, "%p", &*it); + } + + + template <typename Container, typename Value> + void TestBracket(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c[pArrayBegin->first]); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestFind(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.find(pArrayBegin->first)->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestCount(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + typename Container::size_type temp = 0; + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + temp += c.count(pArrayBegin->first); + ++pArrayBegin; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)temp); + } + + + template <typename Container, typename Value> + void TestLowerBound(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.lower_bound(pArrayBegin->first)->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestUpperBound(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.upper_bound(pArrayBegin->first)->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestEqualRange(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + Benchmark::DoNothing(c.equal_range(pArrayBegin->first).second->second); + ++pArrayBegin; + } + stopwatch.Stop(); + } + + + template <typename Container, typename Value> + void TestEraseValue(EA::StdC::Stopwatch& stopwatch, Container& c, const Value* pArrayBegin, const Value* pArrayEnd) + { + stopwatch.Restart(); + while(pArrayBegin != pArrayEnd) + { + c.erase(pArrayBegin->first); + ++pArrayBegin; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + + template <typename Container> + void TestErasePosition(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it; + + stopwatch.Restart(); + for(j = 0, jEnd = c.size() / 3, it = c.begin(); j < jEnd; ++j) + { + // The erase fucntion is supposed to return an iterator, but the C++ standard was + // not initially clear about it and some STL implementations don't do it correctly. + #if (((defined(_MSC_VER) || defined(_CPPLIB_VER)) && !defined(_HAS_STRICT_CONFORMANCE))) // _CPPLIB_VER is something defined by Dinkumware STL. + it = c.erase(it); // Standard behavior. + #else + // This pathway may execute at a slightly different speed than the + // standard behaviour, but that's fine for the benchmark because the + // benchmark is measuring the speed of erasing while iterating, and + // however it needs to get done by the given STL is how it is measured. + const typename Container::iterator itErase(it++); + c.erase(itErase); + #endif + + ++it; + ++it; + } + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p %p", &c, &it); + } + + + template <typename Container> + void TestEraseRange(EA::StdC::Stopwatch& stopwatch, Container& c) + { + typename Container::size_type j, jEnd; + typename Container::iterator it1 = c.begin(); + typename Container::iterator it2 = c.begin(); + + for(j = 0, jEnd = c.size() / 3; j < jEnd; ++j) + ++it2; + + stopwatch.Restart(); + c.erase(it1, it2); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%p %p %p", &c, &it1, &it2); + } + + + template <typename Container> + void TestClear(EA::StdC::Stopwatch& stopwatch, Container& c) + { + stopwatch.Restart(); + c.clear(); + stopwatch.Stop(); + sprintf(Benchmark::gScratchBuffer, "%u", (unsigned)c.size()); + } + + +} // namespace + + + +void BenchmarkMap() +{ + EASTLTest_Printf("Map\n"); + + EA::UnitTest::Rand rng(EA::UnitTest::GetRandSeed()); + EA::StdC::Stopwatch stopwatch1(EA::StdC::Stopwatch::kUnitsCPUCycles); + EA::StdC::Stopwatch stopwatch2(EA::StdC::Stopwatch::kUnitsCPUCycles); + + { + eastl::vector< std::pair<TestObject, uint32_t> > stdVector(10000); + eastl::vector< eastl::pair<TestObject, uint32_t> > eaVector(10000); + + for(eastl_size_t i = 0, iEnd = stdVector.size(); i < iEnd; i++) + { + const uint32_t n1 = rng.RandLimit(((uint32_t)iEnd / 2)); + const uint32_t n2 = rng.RandValue(); + + stdVector[i] = std::pair<TestObject, uint32_t>(TestObject(n1), n2); + eaVector[i] = eastl::pair<TestObject, uint32_t>(TestObject(n1), n2); + } + + for(int i = 0; i < 2; i++) + { + StdMapTOUint32 stdMapTOUint32; + EaMapTOUint32 eaMapTOUint32; + + + /////////////////////////////// + // Test insert(const value_type&) + /////////////////////////////// + const std::pair<TestObject, uint32_t> stdHighValue(TestObject(0x7fffffff), 0x7fffffff); + const eastl::pair<TestObject, uint32_t> eaHighValue(TestObject(0x7fffffff), 0x7fffffff); + + TestInsert(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size(), stdHighValue); + TestInsert(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size(), eaHighValue); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/insert", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test iteration + /////////////////////////////// + + TestIteration(stopwatch1, stdMapTOUint32, StdMapTOUint32::value_type(TestObject(9999999), 9999999)); + TestIteration(stopwatch2, eaMapTOUint32, EaMapTOUint32::value_type(TestObject(9999999), 9999999)); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/iteration", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test operator[] + /////////////////////////////// + + TestBracket(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestBracket(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/operator[]", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test find + /////////////////////////////// + + TestFind(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestFind(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/find", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test count + /////////////////////////////// + + TestCount(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestCount(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/count", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test lower_bound + /////////////////////////////// + + TestLowerBound(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestLowerBound(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/lower_bound", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test upper_bound + /////////////////////////////// + + TestUpperBound(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestUpperBound(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/upper_bound", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test equal_range + /////////////////////////////// + + TestEqualRange(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + stdVector.size()); + TestEqualRange(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + eaVector.size()); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/equal_range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(const key_type& key) + /////////////////////////////// + + TestEraseValue(stopwatch1, stdMapTOUint32, stdVector.data(), stdVector.data() + (stdVector.size() / 2)); + TestEraseValue(stopwatch2, eaMapTOUint32, eaVector.data(), eaVector.data() + (eaVector.size() / 2)); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/erase/key", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test erase(iterator position) + /////////////////////////////// + + TestErasePosition(stopwatch1, stdMapTOUint32); + TestErasePosition(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/erase/pos", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime(), + GetStdSTLType() == kSTLMS ? "MS uses a code bloating implementation of erase." : NULL); + + + /////////////////////////////// + // Test erase(iterator first, iterator last) + /////////////////////////////// + + TestEraseRange(stopwatch1, stdMapTOUint32); + TestEraseRange(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/erase/range", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + + /////////////////////////////// + // Test clear() + /////////////////////////////// + + TestClear(stopwatch1, stdMapTOUint32); + TestClear(stopwatch2, eaMapTOUint32); + + if(i == 1) + Benchmark::AddResult("map<TestObject, uint32_t>/clear", stopwatch1.GetUnits(), stopwatch1.GetElapsedTime(), stopwatch2.GetElapsedTime()); + + } + } +} + + + + + + + + + + + + + + + |