Last active
August 29, 2015 14:09
-
-
Save sehe/c14c3411288d73f63f5e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define NDEBUG | |
#define FLAT_TAILORED | |
#define FLYWEIGHT | |
// MIC stuff | |
#include <boost/multi_index_container.hpp> | |
#include <boost/multi_index/member.hpp> | |
#include <boost/multi_index/random_access_index.hpp> | |
#include <boost/multi_index/ordered_index.hpp> | |
#include <boost/multi_index/hashed_index.hpp> | |
#include <boost/multi_index/composite_key.hpp> | |
#include <boost/multi_index/mem_fun.hpp> | |
// flyweight implementation stuff | |
#include <boost/flyweight.hpp> | |
#include <boost/flyweight/key_value.hpp> | |
#include <boost/flyweight/no_locking.hpp> | |
#include <boost/flyweight/no_tracking.hpp> | |
#include <boost/range/iterator_range.hpp> | |
#include <string> | |
#include <unordered_map> | |
#include <vector> | |
#include <chrono> | |
#include <iostream> | |
#include <nonius/nonius.h++> | |
#include <nonius/main.h++> | |
namespace bmi = boost::multi_index; | |
constexpr auto ITERATIONS = 1000000; | |
//constexpr auto ITERATIONS = 10000000; | |
std::string getRandomString(size_t length) { return "http://www.contoso.com/some/path/someasp.aspx?test=8"; } | |
std::wstring getRandomWString(size_t length) { return L"http://www.contoso.com/some/path/someasp.aspx?test=8"; } | |
struct VersionsData { | |
VersionsData(int subdeliveryGroupId = -1, int retargetingId = -1, std::wstring flightName = std::wstring{}) | |
: m_subdeliveryGroupId(subdeliveryGroupId), | |
m_retargetingId(retargetingId), | |
m_flightName(std::move(flightName)) {} | |
VersionsData(VersionsData &&rhs) = default; | |
VersionsData(VersionsData const&rhs) = default; | |
VersionsData &operator=(VersionsData &&rhs) = default; | |
bool operator==(const VersionsData &rhs) const { | |
return m_subdeliveryGroupId == rhs.m_subdeliveryGroupId && | |
m_retargetingId == rhs.m_retargetingId && | |
m_flightName == rhs.m_flightName; | |
} | |
int m_subdeliveryGroupId; | |
int m_retargetingId; | |
std::wstring m_flightName; | |
}; | |
namespace boost { | |
template <> struct hash<VersionsData> { | |
size_t operator()(const VersionsData &ecv) const { | |
size_t seed = hash_value(ecv.m_flightName); | |
hash_combine(seed, ecv.m_retargetingId); | |
hash_combine(seed, ecv.m_subdeliveryGroupId); | |
return seed; | |
}; | |
}; | |
} | |
template <typename BackendImplementation> | |
struct BenchmarkScenarios { | |
BackendImplementation backend_; | |
int maxi, maxj, maxk; | |
wchar_t const* label; | |
BenchmarkScenarios(int maxi, int maxj, int maxk, wchar_t const* label) | |
: maxi(maxi), maxj(maxj), maxk(maxk), label(label) | |
{ | |
backend_.populate(maxi, maxj, maxk, label); | |
} | |
void isValidVersion() { | |
volatile int count = 0; | |
for (auto i = 0; i < ITERATIONS; ++i) | |
if (backend_.isValidVersion(456789 + i)) | |
count++; | |
std::cout << count << " valid versions." << std::endl; | |
} | |
void hasDefaultImage() { | |
volatile int count = 0; | |
for (auto i = 0; i < ITERATIONS; ++i) | |
if (backend_.hasDefaultImage(456789 + i)) | |
count++; | |
std::cout << count << " versions with default images." << std::endl; | |
} | |
void hasPreferredVersion() { | |
volatile int count = 0; | |
for (auto i = 0; i < ITERATIONS; ++i) | |
if (backend_.hasPreferredVersion()) | |
count++; | |
std::cout << count << " preferred versions." << std::endl; | |
} | |
void getVersionData() { | |
volatile int count = 0; | |
for (auto i = 0; i < maxi; ++i) { | |
for (auto j = 0; j < maxj; ++j) { | |
for (auto k = 0; k < maxk; ++k) { | |
count += backend_.getVersionData(234567 + i, 123456 + j, label); | |
} | |
} | |
} | |
std::cout << count << " sum of all version IDs." << std::endl; | |
} | |
}; | |
#ifdef FLAT_TAILORED | |
struct FlatTailoredBackendImpl { | |
void populate(int maxi, int maxj, int maxk, wchar_t const* label) { | |
m_data.clear(); | |
m_versions.clear(); | |
m_versions.reserve(maxi*maxj*maxk); | |
int counter = 0; | |
for (auto i = 0; i < maxi; ++i) { | |
for (auto j = 0; j < maxj; ++j) { | |
for (auto k = 0; k < maxk; ++k, ++counter) { | |
VersionsData data; | |
data.m_flightName = label; | |
data.m_retargetingId = 123456 + j; | |
data.m_subdeliveryGroupId = 234567 + i; | |
VersionData version; | |
version.m_hasDefaultImage = ((i + j + k) % 2 == 1); | |
version.m_isPreferred = ((i + j + k) % 3 == 1); | |
version.m_jumpUrl = getRandomString(100); | |
version.m_productId = 345678 + i + j + k; | |
version.m_versionId = 456789 + counter; | |
version.m_versionSuffix = getRandomWString(3); | |
version.m_weight = (i + j + k) % 100; | |
m_data[std::move(data)].push_back(version.m_versionId); | |
m_versions.push_back(std::move(version)); | |
} | |
} | |
} | |
// rearrange | |
std::sort(m_versions.begin(), m_versions.end()); | |
auto newEnd = std::unique(m_versions.begin(), m_versions.end()); | |
m_versions.resize(std::distance(m_versions.begin(), newEnd)); | |
for (auto& data : m_data) { | |
for (size_t i = 0; i < data.second.size(); ++i) { | |
auto findRef = lower_bound(m_versions.cbegin(), m_versions.cend(), | |
data.second.at(i)); | |
if (findRef != m_versions.end() && | |
findRef->m_versionId == data.second[i]) { | |
VersionRefStorage::reference ref = data.second.at(i); | |
data.second[i] = std::distance(m_versions.cbegin(), findRef); | |
} | |
} | |
} | |
std::cout << "Index size: " << m_data.size() << std::endl; | |
std::cout << "Data size: " << m_versions.size() << std::endl; | |
} | |
bool isValidVersion(int versionId) const { | |
auto findRef = lower_bound(m_versions.begin(), m_versions.end(), versionId); | |
return (findRef != m_versions.end() && findRef->m_versionId == versionId); | |
} | |
bool hasDefaultImage(int versionId) const { | |
auto findRef = lower_bound(m_versions.begin(), m_versions.end(), versionId); | |
if (findRef != m_versions.end() && findRef->m_versionId == versionId && | |
findRef->m_hasDefaultImage) { | |
return true; | |
} else { | |
return false; | |
} | |
} | |
bool hasPreferredVersion() const { | |
auto iter = find_if(m_versions.begin(), m_versions.end(), | |
[&](const VersionData& data) { return data.m_isPreferred; }); | |
return iter != m_versions.end(); | |
} | |
int getVersionData(int subdeliveryGroupId, int retargetingId, std::wstring flightName) const { | |
VersionsData data; | |
data.m_flightName = flightName; | |
data.m_retargetingId = retargetingId; | |
data.m_subdeliveryGroupId = subdeliveryGroupId; | |
auto findIt = m_data.find(data); | |
return (findIt != m_data.end())? 1 : 0; | |
} | |
private: | |
struct VersionData { | |
bool operator==(VersionData const& rhs) const { return (m_versionId == rhs.m_versionId); } | |
bool operator< (VersionData const& rhs) const { return (m_versionId < rhs.m_versionId); } | |
bool operator> (VersionData const& rhs) const { return (m_versionId > rhs.m_versionId); } | |
bool operator==(int version) const { return (m_versionId == version); } | |
bool operator< (int version) const { return (m_versionId < version); } | |
bool operator> (int version) const { return (m_versionId > version); } | |
std::wstring m_versionSuffix; | |
std::string m_jumpUrl; | |
int m_versionId = -1; | |
int m_weight = -1; | |
int m_productId = -1; | |
bool m_hasDefaultImage = false; | |
bool m_isPreferred = false; | |
}; | |
struct VersionDataHashByKey { | |
std::size_t operator()(const VersionsData& rhs) const { | |
#if 0 | |
return (std::hash<int>()(rhs.m_subdeliveryGroupId) ^ | |
std::hash<int>()(rhs.m_retargetingId) ^ | |
std::hash<std::wstring>()(rhs.m_flightName)); | |
#else | |
return boost::hash<VersionsData>()(rhs); | |
#endif | |
} | |
std::size_t operator()(const VersionData& rhs) const { | |
return (std::hash<int>()(rhs.m_versionId)); | |
} | |
}; | |
typedef std::vector<VersionData> VersionDataContainer; | |
typedef std::vector<VersionDataContainer::difference_type> VersionRefStorage; | |
typedef std::unordered_map<VersionsData, VersionRefStorage, VersionDataHashByKey> MassVersionsDataContainer; | |
MassVersionsDataContainer m_data; | |
VersionDataContainer m_versions; | |
}; | |
#endif | |
#ifdef FLYWEIGHT | |
struct FlyweightMicBackendImpl { | |
void populate(int maxi, int maxj, int maxk, wchar_t const* label) { | |
m_data.clear(); | |
int counter = 0; | |
for (auto i = 0; i < maxi; ++i) { | |
for (auto j = 0; j < maxj; ++j) { | |
for (auto k = 0; k < maxk; ++k, ++counter) { | |
FlyweightMicBackendImpl::VersionData data(234567 + i, 123456 + j, label); | |
data.m_hasDefaultImage = ((i + j + k) % 2 == 1); | |
data.m_isPreferred = ((i + j + k) % 3 == 1); | |
data.m_jumpUrl = getRandomString(100); | |
data.m_productId = 345678 + i + j + k; | |
data.m_versionId = 456789 + counter; | |
data.m_versionSuffix = getRandomWString(3); | |
data.m_weight = (i + j + k) % 100; | |
m_data.insert(data); | |
} | |
} | |
} | |
std::cout << "Index size: " << m_data.size() << std::endl; | |
} | |
bool isValidVersion(int versionId) const { | |
auto range = m_data.get<VersionId>().equal_range(versionId); | |
return (range.first != range.second); | |
} | |
bool hasDefaultImage(int versionId) const { | |
auto range = | |
m_data.get<VerDef>().equal_range(boost::make_tuple(versionId, true)); | |
return (range.first != range.second); | |
} | |
bool hasPreferredVersion() const { | |
auto range = m_data.get<Preferred>().equal_range(true); | |
return (range.first != range.second); | |
} | |
int getVersionData(int subdeliveryGroupId, int retargetingId, std::wstring flightName) const { | |
int retVal = 0; | |
auto range = m_data.get<mvKey>().equal_range( | |
boost::make_tuple(subdeliveryGroupId, retargetingId, flightName)); | |
if (range.first != range.second) | |
retVal = 1; | |
return retVal; | |
} | |
private: | |
typedef boost::flyweight<VersionsData, | |
boost::flyweights::no_locking, | |
boost::flyweights::no_tracking> VersionKey; | |
struct VersionData { | |
VersionData(int subdeliveryGroupId, int retargetingId, std::wstring flightName) | |
: m_key(subdeliveryGroupId, retargetingId, flightName) | |
{ | |
} | |
int getSDGId() const { return m_key.get().m_subdeliveryGroupId; } | |
int getRetargetingId() const { return m_key.get().m_retargetingId; } | |
std::wstring getFlightName() const { return m_key.get().m_flightName; } | |
VersionKey m_key; | |
std::wstring m_versionSuffix; | |
std::string m_jumpUrl; | |
int m_versionId = -1; | |
int m_weight = -1; | |
int m_productId = -1; | |
bool m_hasDefaultImage = false; | |
bool m_isPreferred = false; | |
}; | |
typedef boost::multi_index_container< | |
VersionData, | |
bmi::indexed_by< | |
bmi::ordered_non_unique< | |
bmi::tag<struct mvKey>, | |
bmi::composite_key<VersionData, | |
bmi::const_mem_fun<VersionData, int, &VersionData::getSDGId>, | |
bmi::const_mem_fun<VersionData, int, &VersionData::getRetargetingId>, | |
bmi::const_mem_fun<VersionData, std::wstring, &VersionData::getFlightName> | |
> >, | |
bmi::ordered_non_unique<bmi::tag<struct VersionId>, bmi::member<VersionData, int, &VersionData::m_versionId> >, | |
bmi::ordered_non_unique<bmi::tag<struct Preferred>, bmi::member<VersionData, bool, &VersionData::m_isPreferred> > | |
, bmi::ordered_non_unique< | |
bmi::tag<struct VerDef>, | |
bmi::composite_key<VersionData, | |
bmi::member<VersionData, int, &VersionData::m_versionId>, | |
bmi::member<VersionData, bool, &VersionData::m_hasDefaultImage> > > | |
> > MassVersionsDataContainer; | |
MassVersionsDataContainer m_data; | |
}; | |
#endif | |
#ifdef FLAT_TAILORED | |
BenchmarkScenarios<FlatTailoredBackendImpl> flat_deep(3,3,111111,L"DeepTest"); | |
BenchmarkScenarios<FlatTailoredBackendImpl> flat_wide(200,200,25,L"WideTest"); | |
NONIUS_BENCHMARK("Flat-deep-isValidVersion", [] { flat_deep.isValidVersion(); }) | |
NONIUS_BENCHMARK("Flat-deep-hasDefaultImage", [] { flat_deep.hasDefaultImage(); }) | |
NONIUS_BENCHMARK("Flat-deep-hasPreferredVersion", [] { flat_deep.hasPreferredVersion(); }) | |
NONIUS_BENCHMARK("Flat-deep-getVersionData", [] { flat_deep.getVersionData(); }) | |
NONIUS_BENCHMARK("Flat-wide-isValidVersion", [] { flat_wide.isValidVersion(); }) | |
NONIUS_BENCHMARK("Flat-wide-hasDefaultImage", [] { flat_wide.hasDefaultImage(); }) | |
NONIUS_BENCHMARK("Flat-wide-hasPreferredVersion", [] { flat_wide.hasPreferredVersion(); }) | |
NONIUS_BENCHMARK("Flat-wide-getVersionData", [] { flat_wide.getVersionData(); }) | |
#endif | |
#ifdef FLYWEIGHT | |
BenchmarkScenarios<FlyweightMicBackendImpl> fwmic_deep(3,3,111111,L"DeepTest"); | |
BenchmarkScenarios<FlyweightMicBackendImpl> fwmic_wide(200,200,25,L"WideTest"); | |
NONIUS_BENCHMARK("fwmic-deep-isValidVersion", [] { fwmic_deep.isValidVersion(); }) | |
NONIUS_BENCHMARK("fwmic-deep-hasDefaultImage", [] { fwmic_deep.hasDefaultImage(); }) | |
NONIUS_BENCHMARK("fwmic-deep-hasPreferredVersion", [] { fwmic_deep.hasPreferredVersion(); }) | |
NONIUS_BENCHMARK("fwmic-deep-getVersionData", [] { fwmic_deep.getVersionData(); }) | |
NONIUS_BENCHMARK("fwmic-wide-isValidVersion", [] { fwmic_wide.isValidVersion(); }) | |
NONIUS_BENCHMARK("fwmic-wide-hasDefaultImage", [] { fwmic_wide.hasDefaultImage(); }) | |
NONIUS_BENCHMARK("fwmic-wide-hasPreferredVersion", [] { fwmic_wide.hasPreferredVersion(); }) | |
NONIUS_BENCHMARK("fwmic-wide-getVersionData", [] { fwmic_wide.getVersionData(); }) | |
#endif | |
#ifdef BOOST_MULTI_INDEX_ENABLE_SAFE_MODE | |
#error whoops | |
#endif | |
#ifdef BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING | |
#error whoops | |
#endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment