russell@unturf.com
191f018d78
tiled-0001: mapdocument.cpp sortObjects/sortLayers/moveLayersUp/Down/duplicate QList.contains() inside iteration over all map layers/objects = O(N*S) Fix: QSet O(1) lookup. MEDIUM severity. 24x speedup at N=2000,S=1000. tiled-0002: mapobjectmodel.cpp classChanged QList.contains(tile) inside nested loop over all map objects = O(O*T) Fix: QSet O(1) lookup. MEDIUM severity. 14x speedup at O=2000,T=500. tiled-0003: editpolygontool.cpp updateHandles QList.contains() inside QHash iteration = O(H*S) Fix: QSet O(1) lookup. MEDIUM severity. 13x speedup at H=1000,S=500. 3/3 PASS. MOAD-0002/0003/0004/0005 CLEAN.
79 lines
2.7 KiB
C++
79 lines
2.7 KiB
C++
// tiled-0002-test.cpp
|
|
// CWE-407 unit test: mapobjectmodel.cpp classChanged
|
|
// QList<Object*>.contains(tile) inside nested loop over all map objects = O(MapObjects * ChangedTiles)
|
|
// Fix: QSet lookup O(1) per item
|
|
|
|
#include <QList>
|
|
#include <QSet>
|
|
#include <QElapsedTimer>
|
|
#include <cstdio>
|
|
#include <cassert>
|
|
|
|
// Simulate: for each map object, check if its tile is in the changed-objects list
|
|
static int classChanged_defective(const QList<void*> &allMapObjects,
|
|
const QList<void*> &objectTiles,
|
|
const QList<void*> &changedObjects) {
|
|
int count = 0;
|
|
for (int i = 0; i < allMapObjects.size(); ++i) {
|
|
if (changedObjects.contains(objectTiles[i])) // O(N) per call
|
|
count++;
|
|
}
|
|
return count;
|
|
}
|
|
|
|
static int classChanged_fixed(const QList<void*> &allMapObjects,
|
|
const QList<void*> &objectTiles,
|
|
const QList<void*> &changedObjects) {
|
|
const QSet<void*> objectSet(changedObjects.begin(), changedObjects.end());
|
|
int count = 0;
|
|
for (int i = 0; i < allMapObjects.size(); ++i) {
|
|
if (objectSet.contains(objectTiles[i])) // O(1) per call
|
|
count++;
|
|
}
|
|
return count;
|
|
}
|
|
|
|
int main() {
|
|
const int MAP_OBJECTS = 2000;
|
|
const int CHANGED_TILES = 500;
|
|
|
|
QList<void*> tiles;
|
|
for (int i = 0; i < CHANGED_TILES; ++i)
|
|
tiles.append(reinterpret_cast<void*>(static_cast<uintptr_t>(i + 1)));
|
|
|
|
QList<void*> allMapObjects;
|
|
QList<void*> objectTiles;
|
|
for (int i = 0; i < MAP_OBJECTS; ++i) {
|
|
allMapObjects.append(reinterpret_cast<void*>(static_cast<uintptr_t>(i + 10000)));
|
|
// Half the objects reference changed tiles
|
|
objectTiles.append(tiles[i % CHANGED_TILES]);
|
|
}
|
|
|
|
const int ITERS = 500;
|
|
|
|
QElapsedTimer timer;
|
|
timer.start();
|
|
for (int i = 0; i < ITERS; ++i) {
|
|
int r = classChanged_defective(allMapObjects, objectTiles, tiles);
|
|
assert(r == MAP_OBJECTS);
|
|
}
|
|
qint64 defective_us = timer.nsecsElapsed() / 1000;
|
|
|
|
timer.restart();
|
|
for (int i = 0; i < ITERS; ++i) {
|
|
int r = classChanged_fixed(allMapObjects, objectTiles, tiles);
|
|
assert(r == MAP_OBJECTS);
|
|
}
|
|
qint64 fixed_us = timer.nsecsElapsed() / 1000;
|
|
|
|
double ratio = (double)defective_us / (double)fixed_us;
|
|
|
|
printf("tiled-0002 CWE-407 classChanged QList.contains in nested loop\n");
|
|
printf(" MAP_OBJECTS=%d, CHANGED_TILES=%d, %d iterations\n", MAP_OBJECTS, CHANGED_TILES, ITERS);
|
|
printf(" defective: %lld us\n", defective_us);
|
|
printf(" fixed: %lld us\n", fixed_us);
|
|
printf(" ratio: %.1fx\n", ratio);
|
|
printf(" %s\n", ratio >= 2.0 ? "PASS" : "FAIL");
|
|
|
|
return ratio >= 2.0 ? 0 : 1;
|
|
}
|