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
 115                 // We make five identical multiplexers to verify Tarjan-bridge can merge them together correctly.
 116                 var MULTIPLEXER_COUNT = 5;
 117                 Bridge[] multiplexer0 = null;
 118                 for(int m = 0; m < MULTIPLEXER_COUNT; m++) {
 119                         var multiplexer = new Bridge [FAN_OUT];
 120                         if (m == 0) {
 121                                 multiplexer0 = multiplexer;
 122                                 for (int i = 0; i < FAN_OUT; ++i)
 123                                 {
 124                                         heads [i].Links.Add (multiplexer);
 125                                         multiplexer [i] = new Bridge ();
 126                                 }
 127                         } else {
 128                                 for (int i = 0; i < FAN_OUT; ++i)
 129                                 {
 130                                         heads [i].Links.Add (multiplexer);
 131                                         multiplexer [i] = multiplexer0 [i];
 132                                 }
 133                         }
 134                 }
 135
 136                 Console.WriteLine ("-double fan x5 done-");
 137         }
 138
 139         /*
 140          * Not necessarily a pathology, but a special case of where we
 141          * generate lots of "dead" SCCs.  A non-bridge object that
 142          * can't reach a bridge object can safely be removed from the
 143          * graph.  In this special case it's a linked list hanging off
 144          * a bridge object.  We can handle this by "forwarding" edges
 145          * going to non-bridge nodes that have only a single outgoing
 146          * edge.  That collapses the whole list into a single node.
 147          * We could remove that node, too, by removing non-bridge
 148          * nodes with no outgoing edges.
 149          */
 150         static void SetupDeadList ()
 151         {
 152                 var head = new Bridge ();
 153                 var tail = new NonBridge ();
 154                 head.Links.Add (tail);
 155                 for (int i = 0; i < LIST_LENGTH; ++i)
 156                 {
 157                         var obj = new NonBridge ();
 158                         tail.Link = obj;
 159                         tail = obj;
 160                 }
 161         }
 162
 163         /*
 164          * Triggered a bug in the forwarding mechanic.
 165          */
 166         static void SetupSelfLinks ()
 167         {
 168                 var head = new Bridge ();
 169                 var tail = new NonBridge ();
 170                 head.Links.Add (tail);
 171                 tail.Link = tail;
 172         }
 173
 174         const int L0_COUNT = 100000;
 175         const int L1_COUNT = 100000;
 176         const int EXTRA_LEVELS = 4;
 177
 178         /*
 179         Set a complex graph from one bridge to a couple.
 180         The graph is designed to expose naive coloring on
 181         tarjan and SCC explosion on classic.
 182         */
 183         static void Spider () {
 184                 Bridge a = new Bridge ();
 185                 Bridge b = new Bridge ();
 186
 187                 var l1 = new List<object> ();
 188                 for (int i = 0; i < L0_COUNT; ++i) {
 189                         var l0 = new List<object> ();
 190                         l0.Add (a);
 191                         l0.Add (b);
 192                         l1.Add (l0);
 193                 }
 194                 var last_level = l1;
 195                 for (int l = 0; l < EXTRA_LEVELS; ++l) {
 196                         int j = 0;
 197                         var l2 = new List<object> ();
 198                         for (int i = 0; i < L1_COUNT; ++i) {
 199                                 var tmp = new List<object> ();
 200                                 tmp.Add (last_level [j++ % last_level.Count]);
 201                                 tmp.Add (last_level [j++ % last_level.Count]);
 202                                 l2.Add (tmp);
 203                         }
 204                         last_level = l2;
 205                 }
 206                 Bridge c = new Bridge ();
 207                 c.Links.Add (last_level);
 208         }
 209
 210         static void RunTest (ThreadStart setup)
 211         {
 212                 var t = new Thread (setup);
 213                 t.Start ();
 214                 t.Join ();
 215
 216                 for (int i = 0; i < 5; ++i) {
 217                         Console.WriteLine("-GC {0}/5-", i);
 218                         GC.Collect ();
 219                         GC.WaitForPendingFinalizers ();
 220                 }
 221
 222                 Console.WriteLine ("-GCs done- {0}", Bridge.fin_count);
 223         }
 224
 225         static int Main ()
 226         {
 227                 RunTest (SetupLinks);
 228                 RunTest (SetupLinkedFan);
 229                 RunTest (SetupInverseFan);
 230                 RunTest (SetupDoubleFan);
 231                 RunTest (SetupDeadList);
 232                 RunTest (SetupSelfLinks);
 233                 RunTest (Spider);
 234
 235                 for (int i = 0; i < 0; ++i) {
 236                         GC.Collect ();
 237                         GC.WaitForPendingFinalizers ();
 238                         Console.WriteLine ("-Cleanup GC- {0}", Bridge.fin_count);
 239                 }
 240                 return 0;
 241         }
 242 }