mono/tests/sgen-bridge-pathologies.cs

   1 using System;
   2 using System.Collections;
   3 using System.Collections.Generic;
   4 using System.Threading;
   5
   6 public class Bridge {
   7         public int __test;
   8         public List<object> Links = new List<object> ();
   9         public static int fin_count;
  10         ~Bridge () {
  11                 ++fin_count;
  12                 Links = null;
  13         }
  14 }
  15
  16 public class NonBridge
  17 {
  18         public object Link;
  19 }
  20
  21 class Driver {
  22         const int OBJ_COUNT = 200 * 1000;
  23         const int LINK_COUNT = 2;
  24         const int EXTRAS_COUNT = 0;
  25         const double survival_rate = 0.6;
  26
  27         /*
  28          * Pathological case for the original old algorithm.  Goes
  29          * away when merging is replaced by appending with flag
  30          * checking.
  31          */
  32         static void SetupLinks () {
  33                 var list = new List<Bridge> ();
  34                 for (int i = 0; i < OBJ_COUNT; ++i) {
  35                         var bridge = new Bridge ();
  36                         list.Add (bridge);
  37                 }
  38
  39                 var r = new Random (100);
  40                 for (int i = 0; i < OBJ_COUNT; ++i) {
  41                         var n = list [i];
  42                         for (int j = 0; j < LINK_COUNT; ++j)
  43                                 n.Links.Add (list [r.Next (OBJ_COUNT)]);
  44                         for (int j = 0; j < EXTRAS_COUNT; ++j)
  45                                 n.Links.Add (j);
  46                         if (r.NextDouble () <= survival_rate)
  47                                 n.__test = 1;
  48                 }
  49                 Console.WriteLine ("-setup done-");
  50         }
  51
  52         const int LIST_LENGTH = 20000;
  53         const int FAN_OUT = 20000;
  54
  55         /*
  56          * Pathological case for the new algorithm.  Goes away with
  57          * the single-node elimination optimization, but will still
  58          * persist if modified by using a ladder instead of the single
  59          * list.
  60          */
  61         static void SetupLinkedFan ()
  62         {
  63                 var head = new Bridge ();
  64                 var tail = new NonBridge ();
  65                 head.Links.Add (tail);
  66                 for (int i = 0; i < LIST_LENGTH; ++i)
  67                 {
  68                         var obj = new NonBridge ();
  69                         tail.Link = obj;
  70                         tail = obj;
  71                 }
  72                 var list = new List<Bridge> ();
  73                 tail.Link = list;
  74                 for (int i = 0; i < FAN_OUT; ++i)
  75                         list.Add (new Bridge ());
  76                 Console.WriteLine ("-linked fan done-");
  77         }
  78
  79         /*
  80          * Pathological case for the improved old algorithm.  Goes
  81          * away with copy-on-write DynArrays, but will still persist
  82          * if modified by using a ladder instead of the single list.
  83          */
  84         static void SetupInverseFan ()
  85         {
  86                 var tail = new Bridge ();
  87                 object list = tail;
  88                 for (int i = 0; i < LIST_LENGTH; ++i)
  89                 {
  90                         var obj = new NonBridge ();
  91                         obj.Link = list;
  92                         list = obj;
  93                 }
  94                 var heads = new Bridge [FAN_OUT];
  95                 for (int i = 0; i < FAN_OUT; ++i)
  96                 {
  97                         var obj = new Bridge ();
  98                         obj.Links.Add (list);
  99                         heads [i] = obj;
 100                 }
 101                 Console.WriteLine ("-inverse fan done-");
 102         }
 103
 104         /*
 105          * Pathological case for the bridge in general.  We generate
 106          * 2*FAN_OUT bridge objects here, but the output of the bridge
 107          * is a graph with FAN_OUT^2 edges.
 108          */
 109         static void SetupDoubleFan ()
 110         {
 111                 var heads = new Bridge [FAN_OUT];
 112                 for (int i = 0; i < FAN_OUT; ++i)
 113                         heads [i] = new Bridge ();
 114                 var multiplexer = new Bridge [FAN_OUT];
 115                 for (int i = 0; i < FAN_OUT; ++i)
 116                 {
 117                         heads [i].Links.Add (multiplexer);
 118                         multiplexer [i] = new Bridge ();
 119                 }
 120                 Console.WriteLine ("-double fan done-");
 121         }
 122
 123         /*
 124          * Not necessarily a pathology, but a special case of where we
 125          * generate lots of "dead" SCCs.  A non-bridge object that
 126          * can't reach a bridge object can safely be removed from the
 127          * graph.  In this special case it's a linked list hanging off
 128          * a bridge object.  We can handle this by "forwarding" edges
 129          * going to non-bridge nodes that have only a single outgoing
 130          * edge.  That collapses the whole list into a single node.
 131          * We could remove that node, too, by removing non-bridge
 132          * nodes with no outgoing edges.
 133          */
 134         static void SetupDeadList ()
 135         {
 136                 var head = new Bridge ();
 137                 var tail = new NonBridge ();
 138                 head.Links.Add (tail);
 139                 for (int i = 0; i < LIST_LENGTH; ++i)
 140                 {
 141                         var obj = new NonBridge ();
 142                         tail.Link = obj;
 143                         tail = obj;
 144                 }
 145         }
 146
 147         /*
 148          * Triggered a bug in the forwarding mechanic.
 149          */
 150         static void SetupSelfLinks ()
 151         {
 152                 var head = new Bridge ();
 153                 var tail = new NonBridge ();
 154                 head.Links.Add (tail);
 155                 tail.Link = tail;
 156         }
 157
 158         const int L0_COUNT = 100000;
 159         const int L1_COUNT = 100000;
 160         const int EXTRA_LEVELS = 4;
 161
 162         /*
 163         Set a complex graph from one bridge to a couple.
 164         The graph is designed to expose naive coloring on
 165         tarjan and SCC explosion on classic.
 166         */
 167         static void Spider () {
 168                 Bridge a = new Bridge ();
 169                 Bridge b = new Bridge ();
 170
 171                 var l1 = new List<object> ();
 172                 for (int i = 0; i < L0_COUNT; ++i) {
 173                         var l0 = new List<object> ();
 174                         l0.Add (a);
 175                         l0.Add (b);
 176                         l1.Add (l0);
 177                 }
 178                 var last_level = l1;
 179                 for (int l = 0; l < EXTRA_LEVELS; ++l) {
 180                         int j = 0;
 181                         var l2 = new List<object> ();
 182                         for (int i = 0; i < L1_COUNT; ++i) {
 183                                 var tmp = new List<object> ();
 184                                 tmp.Add (last_level [j++ % last_level.Count]);
 185                                 tmp.Add (last_level [j++ % last_level.Count]);
 186                                 l2.Add (tmp);
 187                         }
 188                         last_level = l2;
 189                 }
 190                 Bridge c = new Bridge ();
 191                 c.Links.Add (last_level);
 192         }
 193
 194         static void RunTest (ThreadStart setup)
 195         {
 196                 var t = new Thread (setup);
 197                 t.Start ();
 198                 t.Join ();
 199
 200                 for (int i = 0; i < 5; ++i) {
 201                         GC.Collect ();
 202                         GC.WaitForPendingFinalizers ();
 203                 }
 204
 205                 Console.WriteLine ("-GCs done- {0}", Bridge.fin_count);
 206         }
 207
 208         static int Main ()
 209         {
 210                 RunTest (SetupLinks);
 211                 RunTest (SetupLinkedFan);
 212                 RunTest (SetupInverseFan);
 213                 RunTest (SetupDoubleFan);
 214                 RunTest (SetupDeadList);
 215                 RunTest (SetupSelfLinks);
 216                 RunTest (Spider);
 217
 218                 for (int i = 0; i < 0; ++i) {
 219                         GC.Collect ();
 220                         GC.WaitForPendingFinalizers ();
 221                         Console.WriteLine ("-Cleanup GC- {0}", Bridge.fin_count);
 222                 }
 223                 return 0;
 224         }
 225 }