File indexing completed on 2024-04-28 08:27:25
0001 /* 0002 Copyright 2009 Milian Wolff <mail@milianw.de> 0003 0004 This library is free software; you can redistribute it and/or 0005 modify it under the terms of the GNU Library General Public 0006 License version 2 as published by the Free Software Foundation. 0007 0008 This library is distributed in the hope that it will be useful, 0009 but WITHOUT ANY WARRANTY; without even the implied warranty of 0010 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0011 Library General Public License for more details. 0012 0013 You should have received a copy of the GNU Library General Public License 0014 along with this library; see the file COPYING.LIB. If not, write to 0015 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0016 Boston, MA 02110-1301, USA. 0017 */ 0018 0019 #include "benchmarks.h" 0020 0021 #include <cstdlib> 0022 #include <cmath> 0023 #include <ctime> 0024 #include <algorithm> 0025 0026 #include <QtAlgorithms> 0027 0028 #include "../include/kdev-pg-location-table.h" 0029 0030 #include <QTest> 0031 #include <QDebug> 0032 0033 using namespace std; 0034 0035 namespace KDevPG 0036 { 0037 0038 class BenchmarkLocationTable : public LocationTable 0039 { 0040 public: 0041 BenchmarkLocationTable() 0042 : LocationTable(), m_lastLine(0) 0043 { 0044 0045 /// number of lines in each table 0046 const int lines = 12500; 0047 /// every i-th line has i chars, which gets reset each \p charResetLine line. 0048 const int charResetLine = 160; 0049 0050 tableMaxOffset = 0; 0051 for ( int i = 0; i < lines; ++i ) { 0052 tableMaxOffset += tableMaxOffset % charResetLine + 1; 0053 newline(tableMaxOffset); 0054 } 0055 } 0056 /** 0057 * Implements a bisection algorithm / binary search 0058 * for the offset. 0059 * 0060 * Should perform pretty good for any kind of usage, but potentially not 0061 * as good as positionAtWithMemory for linear access. 0062 */ 0063 void positionAtQtBisection(qint64 offset, qint64 *line, qint64 *column) const 0064 { 0065 if ( offset < 0 ) { 0066 *line = -1; 0067 *column = -1; 0068 return; 0069 } else if ( offset > lines[currentLine - 1] ) { 0070 *line = currentLine - 1; 0071 *column = offset - lines[currentLine - 1]; 0072 return; 0073 } 0074 0075 qint64 i = -1; 0076 // search relative to last line (next line and the one after that) 0077 if ( m_lastLine + 1 < currentLine && lines[m_lastLine] <= offset ) { 0078 if ( lines[m_lastLine + 1] > offset ) { 0079 // last matched line matches again 0080 i = m_lastLine; 0081 } else if ( m_lastLine + 2 < currentLine && lines[m_lastLine + 2] > offset ) { 0082 // next line relative to last matched matches 0083 i = m_lastLine + 1; 0084 } 0085 } 0086 if ( i == -1 ) { 0087 // fallback to binary search 0088 qint64 *it = std::lower_bound(lines, lines + currentLine, offset); 0089 Q_ASSERT(it != lines + currentLine); 0090 0091 if (*it != offset) { 0092 --it; 0093 } 0094 *line = it - lines; 0095 *column = offset - *it; 0096 } else { 0097 *line = i; 0098 *column = offset - lines[i]; 0099 } 0100 0101 m_lastLine = *line; 0102 } 0103 /** 0104 * Uses old algorithm as written by Roberto Raggi in r687144 (kdevelop-pg/include/kdev-pg-location-table.h) 0105 */ 0106 void positionAtSTLBisection(qint64 offset, qint64 *line, qint64 *column) const 0107 { 0108 if ( offset < 0 ) { 0109 *line = -1; 0110 *column = -1; 0111 return; 0112 } else if ( offset > lines[currentLine - 1] ) { 0113 *line = currentLine - 1; 0114 *column = offset - lines[currentLine - 1]; 0115 return; 0116 } 0117 0118 qint64 i = -1; 0119 // search relative to last line (next line and the one after that) 0120 if ( m_lastLine + 1 < currentLine && lines[m_lastLine] <= offset ) { 0121 if ( lines[m_lastLine + 1] > offset ) { 0122 // last matched line matches again 0123 i = m_lastLine; 0124 } else if ( m_lastLine + 2 < currentLine && lines[m_lastLine + 2] > offset ) { 0125 // next line relative to last matched matches 0126 i = m_lastLine + 1; 0127 } 0128 } 0129 if ( i == -1 ) { 0130 // fallback to binary search 0131 qint64 *it = std::lower_bound(lines, lines + currentLine, offset); 0132 Q_ASSERT(it != lines + currentLine); 0133 0134 if (*it != offset) { 0135 --it; 0136 } 0137 *line = it - lines; 0138 *column = offset - *it; 0139 } else { 0140 *line = i; 0141 *column = offset - lines[i]; 0142 } 0143 0144 m_lastLine = *line; 0145 } 0146 qint64 tableMaxOffset; 0147 0148 private: 0149 mutable qint64 m_lastLine; 0150 }; 0151 0152 void Benchmarks::initTestCase() 0153 { 0154 srand ( time(nullptr) ); 0155 } 0156 0157 void Benchmarks::positionAt() 0158 { 0159 QFETCH(int, algorithm); 0160 QFETCH(int, access); 0161 0162 BenchmarkLocationTable table; 0163 qint64 line; 0164 qint64 column; 0165 0166 switch ( algorithm) { 0167 case CurrentPositionAt: { 0168 switch ( access ) { 0169 case LinearAccess: { 0170 QBENCHMARK { 0171 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0172 table.positionAt(i, &line, &column); 0173 } 0174 } 0175 break; 0176 } 0177 case RandomAccess: { 0178 QBENCHMARK { 0179 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0180 table.positionAt(rand() % table.tableMaxOffset, &line, &column); 0181 } 0182 } 0183 break; 0184 } 0185 default: 0186 qFatal("unexpected access type"); 0187 break; 0188 } 0189 break; 0190 } 0191 case QtBinaryPositionAt: { 0192 switch ( access ) { 0193 case LinearAccess: { 0194 QBENCHMARK { 0195 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0196 table.positionAtQtBisection(i, &line, &column); 0197 } 0198 } 0199 break; 0200 } 0201 case RandomAccess: { 0202 QBENCHMARK { 0203 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0204 table.positionAtQtBisection(rand() % table.tableMaxOffset, &line, &column); 0205 } 0206 } 0207 break; 0208 } 0209 default: 0210 qFatal("unexpected access type"); 0211 break; 0212 } 0213 break; 0214 } 0215 case STLBinaryPositionAt: { 0216 switch ( access ) { 0217 case LinearAccess: { 0218 QBENCHMARK { 0219 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0220 table.positionAtSTLBisection(i, &line, &column); 0221 } 0222 } 0223 break; 0224 } 0225 case RandomAccess: { 0226 QBENCHMARK { 0227 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0228 table.positionAtSTLBisection(rand() % table.tableMaxOffset, &line, &column); 0229 } 0230 } 0231 break; 0232 } 0233 default: 0234 qFatal("unexpected access type"); 0235 break; 0236 } 0237 break; 0238 } 0239 } 0240 } 0241 0242 void Benchmarks::positionAt_data() 0243 { 0244 QTest::addColumn<int>("algorithm"); 0245 QTest::addColumn<int>("access"); 0246 0247 QTest::newRow("current, linear") << (int) CurrentPositionAt << (int) LinearAccess; 0248 QTest::newRow("current, random") << (int) CurrentPositionAt << (int) RandomAccess; 0249 QTest::newRow("qt binary, linear") << (int) QtBinaryPositionAt << (int) LinearAccess; 0250 QTest::newRow("qt binary, random") << (int) QtBinaryPositionAt << (int) RandomAccess; 0251 QTest::newRow("stl binary, linear") << (int) STLBinaryPositionAt << (int) LinearAccess; 0252 QTest::newRow("stl binary, random") << (int) STLBinaryPositionAt << (int) RandomAccess; 0253 } 0254 0255 void Benchmarks::verifyPositionAt() 0256 { 0257 QFETCH(int, algorithm); 0258 QFETCH(int, access); 0259 0260 BenchmarkLocationTable table; 0261 qint64 oldLine; 0262 qint64 oldColumn; 0263 qint64 newLine; 0264 qint64 newColumn; 0265 switch ( algorithm) { 0266 case QtBinaryPositionAt: { 0267 switch ( access ) { 0268 case LinearAccess: { 0269 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0270 table.positionAt(i, &oldLine, &oldColumn); 0271 table.positionAtQtBisection(i, &newLine, &newColumn); 0272 QCOMPARE(newLine, oldLine); 0273 QCOMPARE(newColumn, oldColumn); 0274 } 0275 // special cases 0276 // underflow 0277 table.positionAt(-5, &oldLine, &oldColumn); 0278 table.positionAtQtBisection(-5, &newLine, &newColumn); 0279 QCOMPARE(newLine, oldLine); 0280 QCOMPARE(newColumn, oldColumn); 0281 // overflow 0282 table.positionAt(table.tableMaxOffset + 10, &oldLine, &oldColumn); 0283 table.positionAtQtBisection(table.tableMaxOffset + 10, &newLine, &newColumn); 0284 QCOMPARE(newLine, oldLine); 0285 QCOMPARE(newColumn, oldColumn); 0286 break; 0287 } 0288 case RandomAccess: { 0289 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0290 qint64 offset = rand() % table.tableMaxOffset; 0291 table.positionAt(offset, &oldLine, &oldColumn); 0292 table.positionAtQtBisection(offset, &newLine, &newColumn); 0293 QCOMPARE(newLine, oldLine); 0294 QCOMPARE(newColumn, oldColumn); 0295 } 0296 break; 0297 } 0298 default: 0299 qFatal("unexpected access type"); 0300 break; 0301 } 0302 break; 0303 } 0304 case STLBinaryPositionAt: { 0305 switch ( access ) { 0306 case LinearAccess: { 0307 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0308 table.positionAt(i, &oldLine, &oldColumn); 0309 table.positionAtSTLBisection(i, &newLine, &newColumn); 0310 QCOMPARE(newLine, oldLine); 0311 QCOMPARE(newColumn, oldColumn); 0312 } 0313 // special cases 0314 // underflow 0315 table.positionAt(-5, &oldLine, &oldColumn); 0316 table.positionAtSTLBisection(-5, &newLine, &newColumn); 0317 QCOMPARE(newLine, oldLine); 0318 QCOMPARE(newColumn, oldColumn); 0319 // overflow 0320 table.positionAt(table.tableMaxOffset + 10, &oldLine, &oldColumn); 0321 table.positionAtSTLBisection(table.tableMaxOffset + 10, &newLine, &newColumn); 0322 QCOMPARE(newLine, oldLine); 0323 QCOMPARE(newColumn, oldColumn); 0324 break; 0325 } 0326 case RandomAccess: { 0327 for ( qint64 i = 0; i < table.tableMaxOffset; i += 10 ) { 0328 qint64 offset = rand() % table.tableMaxOffset; 0329 table.positionAt(offset, &oldLine, &oldColumn); 0330 table.positionAtSTLBisection(offset, &newLine, &newColumn); 0331 QCOMPARE(newLine, oldLine); 0332 QCOMPARE(newColumn, oldColumn); 0333 } 0334 break; 0335 } 0336 default: 0337 qFatal("unexpected access type"); 0338 break; 0339 } 0340 break; 0341 } 0342 default: 0343 qFatal("unexpected algorithm"); 0344 break; 0345 } 0346 } 0347 0348 void Benchmarks::verifyPositionAt_data() 0349 { 0350 QTest::addColumn<int>("algorithm"); 0351 QTest::addColumn<int>("access"); 0352 QTest::newRow("qt binary, linear") << (int) QtBinaryPositionAt << (int) LinearAccess; 0353 QTest::newRow("qt binary, random") << (int) QtBinaryPositionAt << (int) RandomAccess; 0354 QTest::newRow("stl binary, linear") << (int) STLBinaryPositionAt << (int) LinearAccess; 0355 QTest::newRow("stl binary, random") << (int) STLBinaryPositionAt << (int) RandomAccess; 0356 } 0357 0358 } 0359 0360 QTEST_MAIN(KDevPG::Benchmarks) 0361 0362 #include "moc_benchmarks.cpp"