Interconnect - Slots are not called according to their record order

[sq-gilles]

Hi,

Using the signal/slot library of Corrade, it appears that when one attaches many slots to same signal, the slots are not called in any particular order. In particular, there are not called in the record order.

We can easily see that by tweaking the Corrade/Interconnect/Test/LibraryTest.cpp

void LibraryTest::test() {
    EmitterLibrary e;

    int orderedFired = 1;
    int expected = orderedFired;
    for (int i : {1, 2, 3, 4, 5}) {
        connect(e, &EmitterLibrary::fireInline,
                [&orderedFired, i]() { orderedFired = (orderedFired + i) * (i + 1); });
        // non commutative operation
        expected = (expected + i) * (i + 1);
    }

    e.fireInline();
    CORRADE_COMPARE(orderedFired, expected); // will certainly fail
}

Controlling the slot invocation order is mandatory when we want to manage events layer by layer (e.g. when managing io events in a scene graph). For example Qt (that seems to have inspired this api) ensures this behavior https://doc.qt.io/qt-6/signalsandslots.html#signals

If several slots are connected to one signal, the slots will be executed one after the other, in the order they have been connected, when the signal is emitted.

This is due to the usage of std::unordered_multimap in src/Corrade/Interconnect/Emitter.h:510. In fact, there is no guarantee on the order for "key-value pairs whose keys compare equivalent".

A very simple fix would be to replace the unordered_multimap by a multimap. Indeed, multimap ensures the order of equivalent keys is the same as their insertion order (https://en.cppreference.com/w/cpp/container/multimap)

diff --git a/src/Corrade/Interconnect/Connection.h b/src/Corrade/Interconnect/Connection.h
index 86b0b4d8..4e660d8b 100644
--- a/src/Corrade/Interconnect/Connection.h
+++ b/src/Corrade/Interconnect/Connection.h
@@ -90,6 +90,12 @@ namespace Implementation {
                 return !operator==(other);
             }

+            bool operator<(const SignalData& other) const {
+                for(std::size_t i = 0; i != FunctionPointerSize; ++i)
+                    if(data[i] < other.data[i]) return true;
+                return false;
+            }
+
         private:
             /* https://bugzilla.gnome.org/show_bug.cgi?id=776986 */
             #ifndef DOXYGEN_GENERATING_OUTPUT
diff --git a/src/Corrade/Interconnect/Emitter.h b/src/Corrade/Interconnect/Emitter.h
index ed151032..a02955cb 100644
--- a/src/Corrade/Interconnect/Emitter.h
+++ b/src/Corrade/Interconnect/Emitter.h
@@ -34,6 +34,7 @@
 #include <cstdint>
 #include <type_traits>
 #include <unordered_map>
+#include <map>
 #include <utility>

 #include "Corrade/Interconnect/Connection.h"
@@ -506,7 +507,7 @@ class CORRADE_INTERCONNECT_EXPORT Emitter {

         void disconnectInternal(const Implementation::SignalData& signal);

-        std::unordered_multimap<Implementation::SignalData, Implementation::ConnectionData, Implementation::SignalDataHash> _connections;
+        std::multimap<Implementation::SignalData, Implementation::ConnectionData> _connections;
         std::uint32_t _lastHandledSignal;
         bool _connectionsChanged;
 };

[mosra]

Hi,

First of all thanks a lot for a very clever repro case, for linking to the matching Qt docs, and for proposing a patch as well :+1:

This is something I was aware of, and silently hoped nobody would need them to be processed in order :sweat_smile: The only concern I have is lookup performance -- asymptotically at least, and considering a good-enough hash function, the hashmap would have a O(1) lookup complexity, while the tree-based map O(log n). But the constant factors in the hashmap case are quite high so it's possible the tree-based map still wins in most cases.

There's a benchmark among the test files, built as InterconnectBenchmark. Could you run it before and after to compare the perf? If the difference is acceptable, I'm happy to merge this as-is, if not then the solution would need to be something like a std::unordered_map<SignalData, std::vector<ConnectionData>> instead. That could guarantee order as well and even be a bit faster than the original, as each connection wouldn't be a separate loose allocation. The only downside would be potentially slower connection removal.

Thanks!