Exiv2

I have been using Exiv2 for a while, through the gexiv2 Python bindings. The images that I am most commonly processing contain about 300 Xmp tags, which I need to read most of. As the number of images I was processing began to scale up (1000+ images at a time), I began to notice significant performance issues. In profiling, I found that my program was spending upwards of 50ms per image just to read all of the XMP tags. Drilling down further, I found that Exiv2 stores all metadata in a std::vector of Exif, Xmp, or Iptc datums. The lookup time for a single tag is O(n) from the vector, since the entire vector needs to be scanned to find the tag. Since I was looking up all n tags, the total lookup runtime ended up being O(n^2), thus the poor performance for a large number of tags. Ideally, the metadata would be stored in a hash map, where it would have O(1) lookup times, or O(n) time for all tags.

Exiv2 does provide an iterator for the metadata, so this issue can be worked around by simply iterating through all tags once and either extracting the desired information, or by putting the metadata is secondary hash map data structure, which is used for all future lookups. Unfortunately, gexiv2 only provides the ability to get a list of all keys and then look up each value one at a time, not a way to directly iterate over all values. I submitted a patch to gexiv2¹ that adds the ability to get all key, value pairs in a single pass. This allowed me to build my own secondary hash map of metadata, which my application uses for all lookups.

Unfortunately, all of this is just a big workaround for the poor performance of lookups in Exiv2. It would be much preferred to simply improve the performance of Exiv2, both to avoid ugly workarounds, and to benefit all users of Exiv2.

Thus, I took it upon myself to convert the Exif, Iptc, and Xmp data storage from std::vector to std::multimap. The attached patches contain the conversion, and provide a massive performance increase for lookups with a large number of tags.

I spent quite a while trying to avoid changing the Exiv2 API, which is fairly tightly coupled to the use of std::vector. For example, most of the tag lookup methods return an iterator to values, which is simply the std::vector::iterator. On the other hand, std::multimap::iterator is a iterator to key, value pairs, and thus incompatible. The added "map_value_iterator" wraps the map iterator, providing the value on dereference, thus behaving like the std::vector::iterator.

The biggest publicly visible changes are to the sortByKey()/sortByTag() methods. std::multimap is kept sorted internally, so it does not make sense to provide sorting methods. Xmp tags are sorted by key, Exif by IfdId then tag number, and Iptc by record then tag number. XmpData::sortByKey(), ExifData::sortByTag(), and Iptc::sortByTag() are thus completely unnecessary, as the map is already sorted. Unfortunately, there is no practical way to resort the map, as would be necessary for ExifData::sortByKey() and IptcData::sortByKey(). These patches mark all of the sort*() methods as deprecated, and make them no-ops. A search on Debian Code Search² turns up only 3 uses of these methods. I sorted Exif and Iptc by their tag numbers, as it seems to be a more logical true sorting. If it were switched to sort by string key, then the sortByTag() functionality would be lost, which only has 1 use.[3]

The performance improvements moving from O(n) to O(1) lookups are quite impressive. The attached bench.cpp was used to benchmark total lookup times.

Looking at some of the typical images, we can see significant improvement, especially for XMP:

Before:

./bench /tmp/20140515-Yosemite-2233.jpg
Exif:    Tags: 52    Lookup time: 0.128897ms
Xmp:    Tags: 143    Lookup time: 7.52281ms
Iptc:    Tags: 12    Lookup time: 0.008165ms

After:

./bench /tmp/20140515-Yosemite-2233.jpg
Exif:    Tags: 52    Lookup time: 0.051482ms
Xmp:    Tags: 143    Lookup time: 0.414214ms
Iptc:    Tags: 12    Lookup time: 0.010078ms

This runtime reduction is really powerful in more extreme cases:

Before:

./bench /tmp/20140515-Yosemite-2233_quadxmp.jpg
Exif:    Tags: 52    Lookup time: 0.111087ms
Xmp:    Tags: 415    Lookup time: 35.7657ms
Iptc:    Tags: 12    Lookup time: 0.00966ms

After:

./bench /tmp/20140515-Yosemite-2233_quadxmp.jpg
Exif:    Tags: 52    Lookup time: 0.036755ms
Xmp:    Tags: 415    Lookup time: 0.844112ms
Iptc:    Tags: 12    Lookup time: 0.008161ms

Notice that the before lookup time has quadrupled, but the after lookup time only doubled. For a sufficiently small number of tags, the change is negligible.

I think this change would significantly improve Exiv2 across the board, and benefit all users.

¹ Related gexiv2 bug: https://bugzilla.gnome.org/show_bug.cgi?id=728072

² http://codesearch.debian.net/search?q=sortByKey%5C%28

³ http://codesearch.debian.net/search?q=sortByTag%5C%28