Op 20/07/2016 om 10:41 schreef Olivier Goffart:
On Mittwoch, 20. Juli 2016 10:01:26 CEST André Somers wrote:
Op 19/07/2016 om 18:06 schreef Olivier Goffart:
It is true that we could consider trying to clean the connection list
after
each signal emission if it is dirty.
We don't want to do it after each disconnect because this can turn a O(n)
algorithm into a O(n^2) (cleaning the list is O(n), if we have to do it
for every disconnect, that n*O(n))
Did anyone ever measure in practice what the distribution in values for
n is here? My *guess* is that it won't be all that large. I expect a
distribution with a spike at n=1 or 2, and then a dropoff with a very
long tail, perhaps spiking at a bit larger number when using QML for all
the propertybindings going on. Big-O notation doesn't make a lot of
sense if the n is small, it only starts to have an impact if n grows.
The distribution does not matter. If it can be big, quadradic complexity can
be a blocker.
Nonsense. There is no need to pessimize the frequent cases to cater for
avoiding a performance issue in an exceptional case. The test case
presented is clearly not a normal usage pattern. Of course, if you can
optimize the algorithmic complexity for the exceptional cases without
affecting the performance for the cases where n is small, then by all
means do just that. I also don't think it is up to Qt to try to mitigate
wrong usage patterns like disconnecting many slots from a single signal
in a loop.
I would be suprised if the impact of the list being a single-linked list
and thus having to skip through memory to get from node to node was not
bigger than any "big-O" benefits you gained from doing it this way in
the first place.
Maybe changing to a vector could be indeed beneficial. Note that it's not that
simple as the nodes are in two different linked list at the same time. And
this is used for efficient disconnect when a reciever is destroyed.
You know much more about this than I do of course, and perhaps a linked
list _is_ the best data structure for this case.
On the other hand, you'd have to consider the likelyhood of another
connect hapening after a disconnect. If that is nearly 1, then sure,
that may be a good time to clean up. But if it is closer to 0 in reality...
It would still not be a leak since the used memory is bounded to O (maximum
amount of connection on that object at the same time)
No, it would not be a leak. I did not claim it was. It would still be
wasted memory though that is kept for (way) longer than needed.
André
_______________________________________________
Development mailing list
Development@qt-project.org
http://lists.qt-project.org/mailman/listinfo/development