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         static void RunTest (ThreadStart setup)
 148         {
 149                 var t = new Thread (setup);
 150                 t.Start ();
 151                 t.Join ();
 152
 153                 for (int i = 0; i < 5; ++i) {
 154                         GC.Collect ();
 155                         GC.WaitForPendingFinalizers ();
 156                 }
 157
 158                 Console.WriteLine ("-GCs done- {0}", Bridge.fin_count);
 159         }
 160
 161         static int Main ()
 162         {
 163                 RunTest (SetupLinks);
 164                 RunTest (SetupLinkedFan);
 165                 RunTest (SetupInverseFan);
 166                 RunTest (SetupDoubleFan);
 167                 RunTest (SetupDeadList);
 168
 169                 for (int i = 0; i < 0; ++i) {
 170                         GC.Collect ();
 171                         GC.WaitForPendingFinalizers ();
 172                         Console.WriteLine ("-Cleanup GC- {0}", Bridge.fin_count);
 173                 }
 174                 return 0;
 175         }
 176 }