File indexing completed on 2024-04-07 03:51:19

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 #if defined(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 #elif defined(BOOST_BIMAP)
0141     Mapping biMap;
0142     QBENCHMARK_ONCE {
0143         for (int i = 0; i < numElements; ++i) {
0144             biMap.insert(Mapping::value_type(containedValue<Hash::key_type>(i), containedValue<Hash::mapped_type>(i)));
0145         }
0146         biMap.clear();
0147     }
0148 #else
0149     Hash hash;
0150     QBENCHMARK_ONCE {
0151         for (int i = 0; i < numElements; ++i) {
0152             hash.insert(containedValue<Hash::key_type>(i), containedValue<Hash::mapped_type>(i));
0153         }
0154         hash.clear();
0155     }
0156 #endif
0157 }
0158 
0159 void BiHashBenchmarks::getTestData()
0160 {
0161     QTest::addColumn<int>("numElements");
0162 
0163     NEW_ROW(1);
0164     NEW_ROW(2);
0165     NEW_ROW(3);
0166     NEW_ROW(5);
0167     NEW_ROW(8);
0168     NEW_ROW(13);
0169     NEW_ROW(21);
0170     NEW_ROW(34);
0171 
0172     NEW_ROW(50);
0173     NEW_ROW(100);
0174     NEW_ROW(150);
0175     NEW_ROW(200);
0176     NEW_ROW(250);
0177 
0178     NEW_ROW(500);
0179     NEW_ROW(1000);
0180     NEW_ROW(1500);
0181     NEW_ROW(2000);
0182     NEW_ROW(2500);
0183 
0184     NEW_ROW(5000);
0185     NEW_ROW(10000);
0186     NEW_ROW(15000);
0187     NEW_ROW(20000);
0188     NEW_ROW(MAX_SIZE);
0189 }
0190 
0191 void BiHashBenchmarks::testInsert_data()
0192 {
0193     getTestData();
0194 }
0195 
0196 void BiHashBenchmarks::testLookup()
0197 {
0198     QFETCH(int, numElements);
0199     Hash hash = createHash(numElements);
0200 
0201     Hash::mapped_type result;
0202     const Hash::key_type key = containedValue<Hash::key_type>(m_randomGenerator.bounded(numElements));
0203 
0204 #if defined(KBIHASH)
0205     Mapping biHash = Mapping::fromHash(hash);
0206     QBENCHMARK_ONCE {
0207         result = biHash.leftToRight(key);
0208     }
0209 #elif defined(BOOST_BIMAP)
0210     Mapping biMap = hashToBiMap(hash);
0211     QBENCHMARK_ONCE {
0212         result = biMap.left[key];
0213     }
0214 #else
0215     QBENCHMARK_ONCE {
0216         result = hash.value(key);
0217     }
0218 #endif
0219     Q_UNUSED(result);
0220 }
0221 
0222 void BiHashBenchmarks::testLookup_data()
0223 {
0224     getTestData();
0225 }
0226 
0227 void BiHashBenchmarks::testReverseLookup()
0228 {
0229     QFETCH(int, numElements);
0230     Hash hash = createHash(numElements);
0231 
0232     Hash::key_type result;
0233     const Hash::mapped_type value = containedValue<Hash::mapped_type>(m_randomGenerator.bounded(numElements));
0234 
0235 #if defined(KBIHASH)
0236     Mapping biHash = Mapping::fromHash(hash);
0237     QBENCHMARK_ONCE {
0238         result = biHash.rightToLeft(value);
0239     }
0240 #elif defined(BOOST_BIMAP)
0241     Mapping biMap = hashToBiMap(hash);
0242     QBENCHMARK_ONCE {
0243         result = biMap.right[value];
0244     }
0245 #else
0246     QBENCHMARK_ONCE {
0247         result = hash.key(value);
0248     }
0249 #endif
0250     Q_UNUSED(result);
0251 }
0252 
0253 void BiHashBenchmarks::testReverseLookup_data()
0254 {
0255     getTestData();
0256 }
0257 
0258 void BiHashBenchmarks::testRemoveKey()
0259 {
0260     QFETCH(int, numElements);
0261     Hash hash = createHash(numElements);
0262 
0263     const Hash::key_type key = containedValue<Hash::key_type>(m_randomGenerator.bounded(numElements));
0264     Hash::mapped_type value;
0265 
0266 #if defined(KBIHASH)
0267     Mapping biHash = Mapping::fromHash(hash);
0268     QBENCHMARK_ONCE {
0269         value = biHash.takeLeft(key);
0270     }
0271 #elif defined(BOOST_BIMAP)
0272     Mapping biMap = hashToBiMap(hash);
0273     Mapping::size_type t;
0274     QBENCHMARK_ONCE {
0275         t = biMap.erase(key);
0276     }
0277 #else
0278     QBENCHMARK_ONCE {
0279         value = hash.take(key);
0280     }
0281 #endif
0282     Q_UNUSED(value);
0283 }
0284 
0285 void BiHashBenchmarks::testRemoveKey_data()
0286 {
0287     getTestData();
0288 }
0289 
0290 void BiHashBenchmarks::testRemoveValue()
0291 {
0292     QFETCH(int, numElements);
0293     Hash hash = createHash(numElements);
0294 
0295     Hash::key_type result;
0296     const Hash::mapped_type value = containedValue<Hash::mapped_type>(m_randomGenerator.bounded(numElements));
0297 
0298 #if defined(KBIHASH)
0299     Mapping biHash = Mapping::fromHash(hash);
0300     QBENCHMARK_ONCE {
0301         result = biHash.takeRight(value);
0302     }
0303 #elif defined(BOOST_BIMAP)
0304     Mapping biMap = hashToBiMap(hash);
0305     Mapping::size_type t;
0306     QBENCHMARK_ONCE {
0307         t = biMap.right.erase(value);
0308     }
0309 #else
0310     QBENCHMARK_ONCE {
0311         result = hash.key(value);
0312         hash.remove(result);
0313     }
0314 #endif
0315     Q_UNUSED(result);
0316 }
0317 
0318 void BiHashBenchmarks::testRemoveValue_data()
0319 {
0320     getTestData();
0321 }
0322 
0323 void BiHashBenchmarks::testUpdateKey()
0324 {
0325     QFETCH(int, numElements);
0326     Hash hash = createHash(numElements);
0327 
0328     const int num = m_randomGenerator.bounded(numElements);
0329     const Hash::key_type oldKey = containedValue<Hash::key_type>(num);
0330     const Hash::key_type newKey = updatedValue<Hash::key_type>(num);
0331 
0332 #if defined(KBIHASH)
0333     Mapping biHash = Mapping::fromHash(hash);
0334     QBENCHMARK_ONCE {
0335         Mapping::right_iterator it = biHash.findRight(biHash.leftToRight(oldKey));
0336         biHash.updateLeft(it, newKey);
0337     }
0338 #elif defined(BOOST_BIMAP)
0339     Mapping biMap = hashToBiMap(hash);
0340     QBENCHMARK_ONCE {
0341         Mapping::right_iterator it = biMap.left.find(oldKey);
0342         it->first = newKey;
0343     }
0344 #else
0345     QBENCHMARK_ONCE {
0346         const Hash::mapped_type value = hash.take(oldKey);
0347         hash.insert(newKey, value);
0348     }
0349 #endif
0350 }
0351 
0352 void BiHashBenchmarks::testUpdateKey_data()
0353 {
0354     getTestData();
0355 }
0356 
0357 void BiHashBenchmarks::testUpdateValue()
0358 {
0359     QFETCH(int, numElements);
0360     Hash hash = createHash(numElements);
0361 
0362     const int num = m_randomGenerator.bounded(numElements);
0363     const Hash::key_type key = containedValue<Hash::key_type>(num);
0364 
0365 #if defined(KBIHASH)
0366     Mapping biHash = Mapping::fromHash(hash);
0367     const Hash::mapped_type newValue = updatedValue<Hash::mapped_type>(num);
0368     QBENCHMARK_ONCE {
0369         Mapping::left_iterator it = biHash.findLeft(key);
0370         biHash.updateRight(it, newValue);
0371     }
0372 #elif defined(BOOST_BIMAP)
0373     Mapping biMap = hashToBiMap(hash);
0374     const Hash::mapped_type newValue = updatedValue<Hash::mapped_type>(num);
0375     QBENCHMARK_ONCE {
0376         Mapping::left_iterator it = biMap.left.find(key);
0377         it->second = newValue;
0378     }
0379 #else
0380     const Hash::mapped_type newValue = updatedValue<Hash::mapped_type>(num);
0381     QBENCHMARK_ONCE {
0382         hash[key] = newValue;
0383     }
0384 #endif
0385 }
0386 
0387 void BiHashBenchmarks::testUpdateValue_data()
0388 {
0389     getTestData();
0390 }
0391 
0392 QTEST_MAIN(BiHashBenchmarks)
0393 #include "benchmarks.moc"