https://bugs.kde.org/show_bug.cgi?id=524383
Bug ID: 524383
Summary: Fingerprint maintenance stuck at 0% for hours on large
collections — calculateAffectedAlbums() is O(N²) due
to QList::contains() per item
Classification: Applications
Product: digikam
Version First 9.1.0
Reported In:
Platform: Other
OS: Microsoft Windows
Status: REPORTED
Severity: normal
Priority: NOR
Component: Maintenance-Similarities
Assignee: [email protected]
Reporter: [email protected]
Target Milestone: ---
SUMMARY
On a large collection (anything over 1.5-2 million and getting exponentially
worse as it grows), starting the fingerprints maintenance tool over the whole
collection leaves the progress bar at 0% for hours with no fingerprints written
to similarity.db, no debug-log output, and near-idle CPU except one busy
thread. The job looks frozen and users (me included) kill the application
believing it crashed.
The tool is not frozen. Before any fingerprinting begins,
FingerPrintsGenerator::calculateAffectedAlbums() builds its work list with a
quadratic algorithm:
core/utilities/maintenance/tools/fingerprints/fingerprintsgenerator.cpp (line
references from master @ db9a2209e90b, 2026-08-10; same code path as 9.1.0):
* Line 58 declares the accumulator as a plain list:
```
QList<qlonglong> allItemIds;
```
* calculateAffectedAlbums() (from line 144) then does, for every item id of
every album (and again for tag albums):
```
if (!d->allItemIds.contains(id))
{
d->allItemIds << id;
}
```
(lines 162 and 174)
QList::contains() is a linear scan, so inserting N ids costs ~N²/4 comparisons.
For N = 1.5 million that is on the order of 562.5 billion comparisons on a
single thread (the function runs via QtConcurrent::run from slotStart()). For
N = 4 million it jumps to 4 trillion comparisons and only gets worse from
there. Depending on processor, storage, and the size of the database this can
turn into hours of silent work before the first fingerprint is computed.
Two aggravating factors make this read as a freeze rather than as slowness:
1. slotStart() sets a placeholder total before the enumeration:
```
setTotalItems(1);
```
so the progress UI shows a pinned, meaningless 0% for the entire quadratic
phase.
2. calculateAffectedAlbums() produces no log output, so even with "Enable
internal debug logging" active there is no sign of life in DebugView.
STEPS TO REPRODUCE
Use a collection with several million items (mine: ~4M items, ~70k albums,
SQLite backend, WAL enabled, DB on NVMe SSD — so this is not an I/O problem).
Tools -> Maintenance -> check "Rebuild Finger-prints" (scan for changed or new
items), whole collection (all albums).
Start, and monitor: progress UI, similarity.db growth, debug log.
OBSERVED RESULT
Progress remains at 0% indefinitely (>1 hour in my runs before I killed the
app). No rows are added to ImageHaarMatrix in similarity.db during this time
(verified by monitoring the row count externally). No debug output is produced.
One CPU thread is busy. Users interpret this as a hang/crash.
Restricting the same maintenance run to individual albums (small N) starts
fingerprinting within seconds, confirming the enumeration phase is the
bottleneck.
EXPECTED RESULT
Whole-collection enumeration of item ids should take seconds. Deduplicating ~4M
ids is trivial with a hash set, which is why my collection is so big -- I want
to fingerprint and then deduplicate.
SUGGESTED FIX
Use a QSet<qlonglong> for the membership test (or collect everything, then sort
+ std::unique once at the end), e.g.:
```
QSet<qlonglong> seen;
...
if (!seen.contains(id))
{
seen.insert(id);
d->allItemIds << id;
}
```
This is O(N) and reduces hours to seconds.
Important note -- Only the fingerprints tool appears to have this pattern — a
grep for "allItemIds.contains" over core/utilities/maintenance/tools/ matches
fingerprintsgenerator.cpp only, which is consistent with the thumbnails and
faces maintenance tools not exhibiting the stall on the same collection.
Additionally, it would help perceived behavior to show real progress during the
enumeration (e.g. per-album progress, since the loop already iterates albums
and checks canceled()) instead of the setTotalItems(1) placeholder.
SOFTWARE/OS VERSIONS
digiKam: 9.1.0 (official Qt6 Win64 installer, also reproduced with the -debug
installer) Windows: Windows 11 (build 26100) Qt: 6.11.0 (bundled) Database:
SQLite (WAL), on NVMe SSD
ADDITIONAL INFORMATION
Since no debug information is outputted during this period there is no debug
trail to provide.
--
You are receiving this mail because:
You are watching all bug changes.
