2 using System.Collections;
3 using System.Collections.Generic;
4 using System.Threading;
8 public List<object> Links = new List<object> ();
9 public static int fin_count;
16 public class NonBridge
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;
28 * Pathological case for the original old algorithm. Goes
29 * away when merging is replaced by appending with flag
32 static void SetupLinks () {
33 var list = new List<Bridge> ();
34 for (int i = 0; i < OBJ_COUNT; ++i) {
35 var bridge = new Bridge ();
39 var r = new Random (100);
40 for (int i = 0; i < OBJ_COUNT; ++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)
46 if (r.NextDouble () <= survival_rate)
49 Console.WriteLine ("-setup done-");
52 const int LIST_LENGTH = 20000;
53 const int FAN_OUT = 20000;
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
61 static void SetupLinkedFan ()
63 var head = new Bridge ();
64 var tail = new NonBridge ();
65 head.Links.Add (tail);
66 for (int i = 0; i < LIST_LENGTH; ++i)
68 var obj = new NonBridge ();
72 var list = new List<Bridge> ();
74 for (int i = 0; i < FAN_OUT; ++i)
75 list.Add (new Bridge ());
76 Console.WriteLine ("-linked fan done-");
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.
84 static void SetupInverseFan ()
86 var tail = new Bridge ();
88 for (int i = 0; i < LIST_LENGTH; ++i)
90 var obj = new NonBridge ();
94 var heads = new Bridge [FAN_OUT];
95 for (int i = 0; i < FAN_OUT; ++i)
97 var obj = new Bridge ();
101 Console.WriteLine ("-inverse fan done-");
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.
109 static void SetupDoubleFan ()
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)
117 heads [i].Links.Add (multiplexer);
118 multiplexer [i] = new Bridge ();
120 Console.WriteLine ("-double fan done-");
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.
134 static void SetupDeadList ()
136 var head = new Bridge ();
137 var tail = new NonBridge ();
138 head.Links.Add (tail);
139 for (int i = 0; i < LIST_LENGTH; ++i)
141 var obj = new NonBridge ();
148 * Triggered a bug in the forwarding mechanic.
150 static void SetupSelfLinks ()
152 var head = new Bridge ();
153 var tail = new NonBridge ();
154 head.Links.Add (tail);
158 const int L0_COUNT = 100000;
159 const int L1_COUNT = 100000;
160 const int EXTRA_LEVELS = 4;
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.
167 static void Spider () {
168 Bridge a = new Bridge ();
169 Bridge b = new Bridge ();
171 var l1 = new List<object> ();
172 for (int i = 0; i < L0_COUNT; ++i) {
173 var l0 = new List<object> ();
179 for (int l = 0; l < EXTRA_LEVELS; ++l) {
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]);
190 Bridge c = new Bridge ();
191 c.Links.Add (last_level);
194 static void RunTest (ThreadStart setup)
196 var t = new Thread (setup);
200 for (int i = 0; i < 5; ++i) {
201 Console.WriteLine("-GC {0}/5-", i);
203 GC.WaitForPendingFinalizers ();
206 Console.WriteLine ("-GCs done- {0}", Bridge.fin_count);
211 RunTest (SetupLinks);
212 RunTest (SetupLinkedFan);
213 RunTest (SetupInverseFan);
214 RunTest (SetupDoubleFan);
215 RunTest (SetupDeadList);
216 RunTest (SetupSelfLinks);
219 for (int i = 0; i < 0; ++i) {
221 GC.WaitForPendingFinalizers ();
222 Console.WriteLine ("-Cleanup GC- {0}", Bridge.fin_count);