Merge pull request #3422 from xmcclure/tarjan-doublefan
authormonojenkins <jo.shields+jenkins@xamarin.com>
Mon, 29 Aug 2016 20:30:06 +0000 (22:30 +0200)
committerGitHub <noreply@github.com>
Mon, 29 Aug 2016 20:30:06 +0000 (22:30 +0200)
Make GC bridge perform well in the "double fan" scenario

The GC bridge currently performs VERY poorly when the object graph has a "double fan" shape. If M Java objects point to 1 C# object which points to N Java objects, the graph exported to Monodroid will currently drop the C# object node and replace it with (M\*N) edges. It is easy to write code where (M\*N) grows ludicrously big.

In testing on device, this patch solves that problem while leaving other cases unaffected. In testing on device, I found:
* All performance tests except double fan: No discernible performance difference after patch
* Double fan test with M=N=1000: Before the patch this took between three and seven seconds. After the patch this took between 0.2 and 0.3 seconds.
* Double fan test with M=N=4000: Before the patch this took anywhere from one to two minutes. After the patch, this took about 1.2 seconds.
* Double fan test with M=N=6000: Before the patch, this took so long I was not able to get it to ever complete. After the patch, this took about 1.3 seconds.
* Double fan test with M=N=20000: I did not attempt this test pre-patch. After the patch, it took about 5.6 seconds.

The commit messages describe the changes in some detail but the short version is:
* Add a mechanism for exporting non-bridged SCCs to the bridge client
* Turn that mechanism on whenever the product fanin*fanout grows too large
* Make the merge cache more aggressive

To function, this patch requires a corresponding change to monodroid. See https://github.com/xamarin/xamarin-android/pull/154


Trivial merge