File indexing completed on 2024-04-28 15:27:46
0001 /* 0002 SPDX-FileCopyrightText: 2010 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.net> 0003 SPDX-FileContributor: Stephen Kelly <stephen@kdab.com> 0004 0005 SPDX-License-Identifier: LGPL-2.0-or-later 0006 */ 0007 0008 #include <QObject> 0009 #include <QRandomGenerator> 0010 #include <QTest> 0011 0012 #define KBIHASH 1 0013 // #define BOOST_BIMAP 1 0014 0015 #define LEFT int 0016 #define RIGHT int 0017 // #define LEFT QString 0018 // #define RIGHT QString 0019 0020 #ifdef KBIHASH 0021 #include "kbihash_p.h" 0022 #endif 0023 0024 #ifdef BOOST_BIMAP 0025 #include <boost/bimap.hpp> 0026 #endif 0027 0028 typedef QHash<LEFT, RIGHT> Hash; 0029 0030 #ifdef KBIHASH 0031 typedef KBiHash<LEFT, RIGHT> Mapping; 0032 #endif 0033 0034 #ifdef BOOST_BIMAP 0035 typedef boost::bimap<LEFT, RIGHT> Mapping; 0036 0037 static Mapping hashToBiMap(const Hash &hash) 0038 { 0039 Mapping biMap; 0040 Hash::const_iterator it = hash.constBegin(); 0041 const Hash::const_iterator end = hash.constEnd(); 0042 for (; it != end; ++it) { 0043 biMap.insert(Mapping::value_type(it.key(), it.value())); 0044 } 0045 return biMap; 0046 } 0047 #endif 0048 0049 // #define QBENCHMARK_ONCE 0050 0051 #define MAX_SIZE 25000 0052 #define MAX_DIGITS 5 0053 0054 #define NEW_ROW(num) QTest::newRow(QString("%1").arg(num).toLatin1()) << num; 0055 0056 template<typename T> 0057 T containedValue(int value); 0058 0059 template<> 0060 int containedValue(int value) 0061 { 0062 return value; 0063 } 0064 0065 template<> 0066 QString containedValue(int value) 0067 { 0068 return QString("%1").arg(value, MAX_DIGITS); 0069 } 0070 0071 template<typename T> 0072 T updatedValue(int value); 0073 0074 template<> 0075 int updatedValue(int value) 0076 { 0077 return value + MAX_SIZE; 0078 } 0079 0080 template<> 0081 QString updatedValue(int value) 0082 { 0083 return QString("%1").arg(value + MAX_SIZE, MAX_DIGITS); 0084 } 0085 0086 class BiHashBenchmarks : public QObject 0087 { 0088 Q_OBJECT 0089 public: 0090 BiHashBenchmarks(QObject *parent = nullptr) 0091 : QObject(parent) 0092 { 0093 } 0094 0095 private: 0096 Hash createHash(int numElements) 0097 { 0098 Hash hash; 0099 hash.reserve(numElements); 0100 for (int i = 0; i < numElements; ++i) { 0101 hash.insert(containedValue<Hash::key_type>(i), containedValue<Hash::mapped_type>(i)); 0102 } 0103 return hash; 0104 } 0105 void getTestData(); 0106 0107 QRandomGenerator m_randomGenerator; 0108 0109 private Q_SLOTS: 0110 0111 void testInsert(); 0112 void testLookup(); 0113 void testReverseLookup(); 0114 void testRemoveKey(); 0115 void testRemoveValue(); 0116 void testUpdateKey(); 0117 void testUpdateValue(); 0118 0119 void testInsert_data(); 0120 void testLookup_data(); 0121 void testReverseLookup_data(); 0122 void testRemoveKey_data(); 0123 void testRemoveValue_data(); 0124 void testUpdateKey_data(); 0125 void testUpdateValue_data(); 0126 }; 0127 0128 void BiHashBenchmarks::testInsert() 0129 { 0130 QFETCH(int, numElements); 0131 0132 #ifdef KBIHASH 0133 Mapping biHash; 0134 QBENCHMARK_ONCE { 0135 for (int i = 0; i < numElements; ++i) { 0136 biHash.insert(containedValue<Hash::key_type>(i), containedValue<Hash::mapped_type>(i)); 0137 } 0138 biHash.clear(); 0139 } 0140 #else 0141 #ifdef BOOST_BIMAP 0142 Mapping biMap; 0143 QBENCHMARK_ONCE { 0144 for (int i = 0; i < numElements; ++i) { 0145 biMap.insert(Mapping::value_type(containedValue<Hash::key_type>(i), containedValue<Hash::mapped_type>(i))); 0146 } 0147 biMap.clear(); 0148 } 0149 #else 0150 Hash hash; 0151 QBENCHMARK_ONCE { 0152 for (int i = 0; i < numElements; ++i) { 0153 hash.insert(containedValue<Hash::key_type>(i), containedValue<Hash::mapped_type>(i)); 0154 } 0155 hash.clear(); 0156 } 0157 #endif 0158 #endif 0159 } 0160 0161 void BiHashBenchmarks::getTestData() 0162 { 0163 QTest::addColumn<int>("numElements"); 0164 0165 NEW_ROW(1); 0166 NEW_ROW(2); 0167 NEW_ROW(3); 0168 NEW_ROW(5); 0169 NEW_ROW(8); 0170 NEW_ROW(13); 0171 NEW_ROW(21); 0172 NEW_ROW(34); 0173 0174 NEW_ROW(50); 0175 NEW_ROW(100); 0176 NEW_ROW(150); 0177 NEW_ROW(200); 0178 NEW_ROW(250); 0179 0180 NEW_ROW(500); 0181 NEW_ROW(1000); 0182 NEW_ROW(1500); 0183 NEW_ROW(2000); 0184 NEW_ROW(2500); 0185 0186 NEW_ROW(5000); 0187 NEW_ROW(10000); 0188 NEW_ROW(15000); 0189 NEW_ROW(20000); 0190 NEW_ROW(MAX_SIZE); 0191 } 0192 0193 void BiHashBenchmarks::testInsert_data() 0194 { 0195 getTestData(); 0196 } 0197 0198 void BiHashBenchmarks::testLookup() 0199 { 0200 QFETCH(int, numElements); 0201 Hash hash = createHash(numElements); 0202 0203 Hash::mapped_type result; 0204 const Hash::key_type key = containedValue<Hash::key_type>(m_randomGenerator.bounded(numElements)); 0205 0206 #ifdef KBIHASH 0207 Mapping biHash = Mapping::fromHash(hash); 0208 QBENCHMARK_ONCE { 0209 result = biHash.leftToRight(key); 0210 } 0211 #else 0212 #if BOOST_BIMAP 0213 Mapping biMap = hashToBiMap(hash); 0214 QBENCHMARK_ONCE { 0215 result = biMap.left[key]; 0216 } 0217 #else 0218 QBENCHMARK_ONCE { 0219 result = hash.value(key); 0220 } 0221 #endif 0222 #endif 0223 } 0224 0225 void BiHashBenchmarks::testLookup_data() 0226 { 0227 getTestData(); 0228 } 0229 0230 void BiHashBenchmarks::testReverseLookup() 0231 { 0232 QFETCH(int, numElements); 0233 Hash hash = createHash(numElements); 0234 0235 Hash::key_type result; 0236 const Hash::mapped_type value = containedValue<Hash::mapped_type>(m_randomGenerator.bounded(numElements)); 0237 0238 #ifdef KBIHASH 0239 Mapping biHash = Mapping::fromHash(hash); 0240 QBENCHMARK_ONCE { 0241 result = biHash.rightToLeft(value); 0242 } 0243 #else 0244 #if BOOST_BIMAP 0245 Mapping biMap = hashToBiMap(hash); 0246 QBENCHMARK_ONCE { 0247 result = biMap.right[value]; 0248 } 0249 #else 0250 QBENCHMARK_ONCE { 0251 result = hash.key(value); 0252 } 0253 #endif 0254 #endif 0255 } 0256 0257 void BiHashBenchmarks::testReverseLookup_data() 0258 { 0259 getTestData(); 0260 } 0261 0262 void BiHashBenchmarks::testRemoveKey() 0263 { 0264 QFETCH(int, numElements); 0265 Hash hash = createHash(numElements); 0266 0267 const Hash::key_type key = containedValue<Hash::key_type>(m_randomGenerator.bounded(numElements)); 0268 Hash::mapped_type value; 0269 0270 #ifdef KBIHASH 0271 Mapping biHash = Mapping::fromHash(hash); 0272 QBENCHMARK_ONCE { 0273 value = biHash.takeLeft(key); 0274 } 0275 #else 0276 #if BOOST_BIMAP 0277 Mapping biMap = hashToBiMap(hash); 0278 Mapping::size_type t; 0279 QBENCHMARK_ONCE { 0280 t = biMap.erase(key); 0281 } 0282 #else 0283 QBENCHMARK_ONCE { 0284 value = hash.take(key); 0285 } 0286 #endif 0287 #endif 0288 } 0289 0290 void BiHashBenchmarks::testRemoveKey_data() 0291 { 0292 getTestData(); 0293 } 0294 0295 void BiHashBenchmarks::testRemoveValue() 0296 { 0297 QFETCH(int, numElements); 0298 Hash hash = createHash(numElements); 0299 0300 Hash::key_type result; 0301 const Hash::mapped_type value = containedValue<Hash::mapped_type>(m_randomGenerator.bounded(numElements)); 0302 0303 #ifdef KBIHASH 0304 Mapping biHash = Mapping::fromHash(hash); 0305 QBENCHMARK_ONCE { 0306 result = biHash.takeRight(value); 0307 } 0308 #else 0309 #ifdef BOOST_BIMAP 0310 Mapping biMap = hashToBiMap(hash); 0311 Mapping::size_type t; 0312 QBENCHMARK_ONCE { 0313 t = biMap.right.erase(value); 0314 } 0315 #else 0316 QBENCHMARK_ONCE { 0317 result = hash.key(value); 0318 hash.remove(result); 0319 } 0320 #endif 0321 #endif 0322 } 0323 0324 void BiHashBenchmarks::testRemoveValue_data() 0325 { 0326 getTestData(); 0327 } 0328 0329 void BiHashBenchmarks::testUpdateKey() 0330 { 0331 QFETCH(int, numElements); 0332 Hash hash = createHash(numElements); 0333 0334 const int num = m_randomGenerator.bounded(numElements); 0335 const Hash::key_type oldKey = containedValue<Hash::key_type>(num); 0336 const Hash::key_type newKey = updatedValue<Hash::key_type>(num); 0337 0338 #ifdef KBIHASH 0339 Mapping biHash = Mapping::fromHash(hash); 0340 QBENCHMARK_ONCE { 0341 Mapping::right_iterator it = biHash.findRight(biHash.leftToRight(oldKey)); 0342 biHash.updateLeft(it, newKey); 0343 } 0344 #else 0345 #ifdef BOOST_BIMAP 0346 Mapping biMap = hashToBiMap(hash); 0347 QBENCHMARK_ONCE { 0348 Mapping::right_iterator it = biMap.left.find(oldKey); 0349 it->first = newKey; 0350 } 0351 #else 0352 QBENCHMARK_ONCE { 0353 const Hash::mapped_type value = hash.take(oldKey); 0354 hash.insert(newKey, value); 0355 } 0356 #endif 0357 #endif 0358 } 0359 0360 void BiHashBenchmarks::testUpdateKey_data() 0361 { 0362 getTestData(); 0363 } 0364 0365 void BiHashBenchmarks::testUpdateValue() 0366 { 0367 QFETCH(int, numElements); 0368 Hash hash = createHash(numElements); 0369 0370 const int num = m_randomGenerator.bounded(numElements); 0371 const Hash::key_type key = containedValue<Hash::key_type>(num); 0372 0373 #ifdef KBIHASH 0374 Mapping biHash = Mapping::fromHash(hash); 0375 const Hash::mapped_type newValue = updatedValue<Hash::mapped_type>(num); 0376 QBENCHMARK_ONCE { 0377 Mapping::left_iterator it = biHash.findLeft(key); 0378 biHash.updateRight(it, newValue); 0379 } 0380 #else 0381 #if BOOST_BIMAP 0382 Mapping biMap = hashToBiMap(hash); 0383 const Hash::mapped_type newValue = updatedValue<Hash::mapped_type>(num); 0384 QBENCHMARK_ONCE { 0385 Mapping::left_iterator it = biMap.left.find(key); 0386 it->second = newValue; 0387 } 0388 #else 0389 const Hash::mapped_type newValue = updatedValue<Hash::mapped_type>(num); 0390 QBENCHMARK_ONCE { 0391 hash[key] = newValue; 0392 } 0393 #endif 0394 #endif 0395 } 0396 0397 void BiHashBenchmarks::testUpdateValue_data() 0398 { 0399 getTestData(); 0400 } 0401 0402 QTEST_MAIN(BiHashBenchmarks) 0403 #include "benchmarks.moc"