dupe: Eliminate O(n^2) code in dupe_files_add_queue_cb()
authorFrej Drejhammar <frej.drejhammar@gmail.com>
Fri, 12 Mar 2021 20:02:16 +0000 (21:02 +0100)
committerFrej Drejhammar <frej.drejhammar@gmail.com>
Sat, 27 Mar 2021 12:52:38 +0000 (13:52 +0100)
commit75794b0d65929caac0e4d0969ba05bdb00b456e9
tree2fbb1a8fd67c0ab272589f49ea6c180d34501fac
parent513bc7148be74632d9c410ffbfaf8c3e21a82aef
dupe: Eliminate O(n^2) code in dupe_files_add_queue_cb()

Geeqie is, compared to its ancestor Gqview, embarrassingly slow while
loading a set of files to look for duplicates (most noticeable when
looking for duplicate names). Profiling shows that a lot of time is
spent in dupe_files_add_queue_cb(). The culprit turns out to be two
loops, which for each newly loaded file, traverses the list of already
loaded images. As this gives a time complexity of O(n^2) where n is
the number of images, loading times become very large when the number
of files increases.

This patch adds a GHashTable-based cache which is created when a
loading operation starts and destroyed when it completes. The cache is
initialized with the loaded images on creation (an O(n)
operation). Using the cache, checking for duplicates in the lists can
be done in constant time, thus making the loading time linear in the
number of images loaded. With this change Geeqie now matches the
performance of Gqview.

As a side effect, this patch also fixes a memory leak when an attempt
is made to re-add an already added file, as the unmodified version
never freed the DupeItem allocated for the twice added file.
src/dupe.c
src/dupe.h