One of the items that came up at the last Online Developer Meeting was basing more of Octave internals on C++ libraries, rather than our own hand-rolled code. This should get us 1) more cross-platform compatibility, 2) less code of our own to maintain with a limited number of volunteers, and 3) better performance as library code has typically been optimized.
In that regard, I suggested a useful activity might be to replace instances of
std::unordered_map in order to move from O(log2(N)) performance to O(1) performance.
I’m happy to report that I made this change while rewriting
gsvd.cc and it was just as simple as I had hoped. All that was required was to replace
and then instances of
I then re-built Octave and that was it—the compiler and linker took care of everything and we should get better performance.
I would recommend the same strategy to anyone occasionally looking through the C++ code. If they find an instance of std::map in which we aren’t doing much iterating over the keys, then this is a good chance to replace it with std::unordered_map. In particular, I’m guessing that our caching mechanisms, such as load_path, might benefit. In caches, the frequent operations are to add keys, search keys, and delete keys, but not to list all the keys and loop over them.