Bug 26387 - Adding listeners to an event has unexpected high complexity
Summary: Adding listeners to an event has unexpected high complexity
Status: RESOLVED DUPLICATE of bug 26550
Alias: None
Product: Runtime
Classification: Mono
Component: JIT ()
Version: 3.8.0
Hardware: PC All
: --- normal
Target Milestone: ---
Assignee: Ludovic Henry
URL:
Depends on:
Blocks:
 
Reported: 2015-01-24 19:49 UTC by Lukas Grundmann
Modified: 2015-05-05 05:59 UTC (History)
5 users (show)

Tags:
Is this bug a regression?: ---
Last known good build:

Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.


Please create a new report on GitHub or Developer Community with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:
Status:
RESOLVED DUPLICATE of bug 26550

Description Lukas Grundmann 2015-01-24 19:49:09 UTC
Adding a listener to an event seems to have a higher complexity than O(n). n are the listeners already attached to the event. Microsoft's implementation of adding listeners to an event has a better complexity.

Following simple code should reproduce the problem:

class MainClass
{
	static event EventHandler<int> eventHandler;

	public static void Main (string[] args)
	{
		
		var time = DateTime.Now.Ticks;
		for (int i = 0; i < 100000; i++) {
			eventHandler += (s, x) => Console.WriteLine (x);

			if (i % 5000 == 0) {
				Console.WriteLine ("After " + i + " added event listeners "
					+ ((DateTime.Now.Ticks - time) / 10000.0) + " ms passed ");
			}
		}
	}
}
Comment 1 Christian Hüning 2015-01-25 05:29:45 UTC
I can second this! It's also present on OSX using latest Mono stable build.
Comment 2 Marek Safar 2015-01-28 06:21:09 UTC
It's due to linked list implementation of our MulticaseDelegate..net uses an array (or single object) for this which behaves much better because we copy everything on every add.

Moving this to runtime as the corlib change is easy but we need to fix the trampolines to deal with it as well.
Comment 3 Lukas Grundmann 2015-01-29 12:16:12 UTC
I quicked fixed the bug in the corlib without the need of a trampolin change.

In the remainder I'll present my solution. It is based on an assumption which might be wrong!

The assumption is that "delagate c = a combined with b" is following the functional programming paradigm. So that "a" and "b" are never changed once created.

Following this it is enough for combining a single delegate with a real multicast delegate to clone the single delegate's linked list head and link the cloned head to the linked list of the real multicast delegate. (in CombineImpl)

This solution works with the code snippet above and more complicated application code, which also removes listeners and actually signals. But the problem is that changing one of the combined delegates would also change the resulting delegate, which then might lead to problems somewhere in Mono, applications ...
Comment 4 Ludovic Henry 2015-05-05 05:59:50 UTC
Both these bugs are due to the implementation of the delegates, so as soon as the implementation is fixed, both these bugs should be too.

*** This bug has been marked as a duplicate of bug 26550 ***