russell@unturf.com
ad90dddbcc
libreoffice-0001: SavePivotTableXml member-to-cache O(M*C) std::find sc/source/filter/excel/xepivotxml.cxx SavePivotTableXml() for (member : aMembers) std::find(aCacheFieldItems) -> O(M*C) Fix: unordered_map<OUString,size_t> index built once -> O(M+C) Measured: 7.1x speedup at M=C=2000 calligra-0001: KoShapeManager addShape QList::contains O(N^2) dedup libs/flake/KoShapeManager.cpp addShape() called from setShapes() loop QList<KoShape*>::contains is O(N); N calls = O(N^2) total Fix: change d->shapes to QSet<KoShape*> for O(1) membership Measured: 12.6x speedup at N=5000 MOADs 0002-0005: CLEAN for both targets (see README.md per defect) Both unit tests: PASS
1.6 KiB
libreoffice-0001: SavePivotTableXml member-to-cache linear scan O(M*C)
Target: LibreOffice (sc/source/filter/excel/xepivotxml.cxx) MOAD: 0001 (CWE-407) Severity: MEDIUM-HIGH Complexity: O(M*C) -> O(M+C) Measured speedup: 7.1x at M=C=2000
Location
sc/source/filter/excel/xepivotxml.cxx
XclExpXmlPivotTables::SavePivotTableXml(), loop around line 1409
Defect
When exporting a pivot table to XLSX format, the code builds a member sequence by matching each pivot member name against a flat vector of cache field items:
for (const auto & rMember : aMembers)
{
auto it = std::find(aCacheFieldItems.begin(), aCacheFieldItems.end(), rMember.maName);
// ...
}
std::find scans the entire aCacheFieldItems vector for each member, giving
O(M * C) total work where M = aMembers.size() and C = aCacheFieldItems.size().
A pivot table with 5000 distinct values in a text dimension produces M=C=5000,
making the save operation 5000x slower than necessary.
Fix
Build a std::unordered_map<OUString, size_t> index from aCacheFieldItems
once before the loop, then look up each member in O(1).
MOAD-0002 through 0005 (scan notes)
- MOAD-0002 (Intertangle): ScDocument is our known god object. Not a new finding.
- MOAD-0003 (Leaked Context):
thread_local ScDocumentThreadSpecificholds formula evaluation state (pContext, xRecursionHelper), not request-scoped identity. CLEAN. - MOAD-0004 (CWE-312):
tabprotection.cxxpassword logging is behind#if DEBUG_TAB_PROTECTIONwhereDEBUG_TAB_PROTECTION 0. Compiled out. CLEAN. - MOAD-0005 (Thundering Herd): No unguarded cache get+null+compute+put found. CLEAN.