using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Threading;
using System.Linq;
using glue;
using glue.Debugging;
using glue.Extensions.Enumerable;
using System.Threading.Tasks;
using glue.Tasks;
#pragma warning disable 0649
namespace agree
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
sealed public class ConcurrentTray : Tray, IFreezableTray
{
public ConcurrentTray(int tix, TypeMgr tm, int last_mark, int next_id)
: base(tix, tm, last_mark, next_id)
{
for (int i = 0; i < Pools.Length; i++)
Pools[i] = new Pool(this, i, 223, 525713);
}
public void Freeze()
{
//foreach (Pool p in Pools)
//{
// p.Resize(-1);
//}
}
public void Shrink()
{
//int b4 = Pools.Sum(cp => ((Pool)cp).m_buckets.Length);
foreach (Pool p in Pools)
p.Shrink();
//Console.WriteLine("{0} -> {1}", b4, Pools.Sum(cp => ((Pool)cp).m_buckets.Length));
}
public int c_resizes = 0;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void Report()
{
Console.WriteLine();
Console.WriteLine("fix feature PMs edges m-min m-max in-stdev density types nzm buckets");
int o_min = int.MaxValue;
int o_max = int.MinValue;
int c_pm = 0;
HashSet<int> in_use = new HashSet<int>();
foreach (Pool p in Pools)
{
int n = 0;
double mx = 0, mean = 0;
int min = int.MaxValue;
int max = int.MinValue;
HashSet<Edge> d_edges = new HashSet<Edge>();
HashSet<Type> d_types = new HashSet<Type>();
int c_nonzero = 0;
foreach (var pe in p.PoolEdges)
{
int m = pe.Key;
n++;
double delta = m - mean;
mean += delta / n;
mx += delta * (m - mean);
if (m < min)
min = m;
if (m > max)
max = m;
in_use.Add(m);
d_edges.Add(pe.Value);
d_types.Add(tm.GetEdgeType(pe.Value.FlagsId));
if (pe.Value.Mark != 0)
c_nonzero++;
}
c_pm += n;
if (min < o_min)
o_min = min;
if (max > o_max)
o_max = max;
String extra = "";
//if (d_edges.Count <= 8)
// extra = d_edges.Select(e => e.ToString()).StringJoin(" ");
double variance = n <= 1 ? Double.NaN : mx / (n - 1);
Console.WriteLine("{0,3} {1,16} {2,6} {3,6} {4,6} {5,7} {6,9:0.0} {7,10:0.000} {8,5} {9,5} {10,7} {11}",
p.i_feat,
p.Feature.ToUpper(),
n,
d_edges.Count,
min,
max,
Math.Sqrt(variance),
(n * 100.0) / (max - min),
d_types.Count,
c_nonzero > 0 ? c_nonzero.ToString() : "",
#if DEBUG
p.m_buckets.Length,
#else
"n/a",
#endif
extra);
}
Console.WriteLine();
Console.WriteLine("overall mark usage:");
Console.WriteLine("PMs: {0} distinct: {1} m-min: {2} m-max: {3} range-unused: {4} density: {5:0.000}",
c_pm,
in_use.Count,
o_min,
o_max,
(o_max - o_min + 1) - in_use.Count,
(in_use.Count * 100.0) / (o_max - o_min));
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
sealed public class Pool : ConstraintPool
{
sealed internal class Node
{
internal Edge m_edge;
readonly internal int m_mark;
internal Node m_next;
internal Node(Edge e, int m, Node next)
{
m_edge = e;
m_mark = m;
m_next = next;
}
};
private const int DEFAULT_CAPACITY = 31;
private const int DEFAULT_CONCURRENCY_MULTIPLIER = 4;
FalseSharing.Padding56 fsp1;
//#if DEBUG
internal
//#endif
volatile Node[] m_buckets;
FalseSharing.Padding56 fsp2;
int[] m_countPerLock;
FalseSharing.Padding56 fsp3;
readonly Object[] m_locks;
FalseSharing.Padding56 fsp4;
public Pool(Tray tr, int i_feat)
: this(tr, i_feat, DEFAULT_CONCURRENCY_MULTIPLIER * Environment.ProcessorCount, DEFAULT_CAPACITY, null)
{
}
public Pool(Tray tr, int i_feat, IEnumerable<KeyValuePair<int, Edge>> collection)
: this(tr, i_feat, DEFAULT_CONCURRENCY_MULTIPLIER * Environment.ProcessorCount, DEFAULT_CAPACITY, collection)
{
}
public Pool(Tray tr, int i_feat, int concurrencyLevel, IEnumerable<KeyValuePair<int, Edge>> collection)
: this(tr, i_feat, concurrencyLevel, DEFAULT_CAPACITY, collection)
{
}
public Pool(Tray tr, int i_feat, int concurrencyLevel, int capacity)
: this(tr, i_feat, concurrencyLevel, capacity, null)
{
}
public Pool(Tray tr, int i_feat, int concurrencyLevel, int capacity, IEnumerable<KeyValuePair<int, Edge>> collection)
: base(tr, i_feat)
{
Nop.X(fsp1, fsp2, fsp3, fsp4);
if (concurrencyLevel < 1)
throw new ArgumentOutOfRangeException("concurrencyLevel");
if (capacity < 0)
throw new ArgumentOutOfRangeException("capacity");
// The capacity should be at least as large as the concurrency level. Otherwise, we would have locks that don't guard
// any buckets.
if (capacity < concurrencyLevel)
capacity = concurrencyLevel;
m_locks = new Object[concurrencyLevel];
for (int i = 0; i < m_locks.Length; i++)
m_locks[i] = new Object();
m_countPerLock = new int[m_locks.Length];
m_buckets = new Node[capacity];
if (collection != null)
{
foreach (var pair in collection)
{
int bucketNo = pair.Key % m_buckets.Length;
int lockNo = bucketNo % m_locks.Length;
Node first;
for (Node cur = first = m_buckets[bucketNo]; cur != null; cur = cur.m_next)
if (cur.m_mark == pair.Key)
throw new ArgumentException();
// The key was not found in the bucket. Insert the key-value pair.
m_buckets[bucketNo] = new Node(pair.Value, pair.Key, first);
m_countPerLock[lockNo]++;
// If this lock has element / bucket ratio greater than 1, resize the entire table.
// Note: the formula is chosen to avoid overflow, but has a small inaccuracy due to
// rounding.
if (m_countPerLock[lockNo] > m_buckets.Length / m_locks.Length)
Resize();
}
}
}
public override bool ContainsInMark(int m)
{
Debug.Assert(m != 0);
Node[] buckets = m_buckets;
Node n = buckets[m % buckets.Length];
while (n != null)
{
if (n.m_mark == m)
return true;
n = n.m_next;
}
return false;
}
public override Edge GetEdge(Int32 m)
{
Debug.Assert(m != 0);
Node[] buckets = m_buckets;
Node n = buckets[m % buckets.Length];
for (; n != null; n = n.m_next)
if (n.m_mark == m)
return n.m_edge;
return default(Edge);
}
public override bool TryGetEdge(int m, out Edge e)
{
Debug.Assert(m != 0);
Node[] buckets = m_buckets;
Node n = buckets[m % buckets.Length];
for (; n != null; n = n.m_next)
if (n.m_mark == m)
{
e = n.m_edge;
return true;
}
e = default(Edge);
return false;
}
public unsafe override void SetEdge(int m, Edge e)
{
Debug.Assert(m != 0 && m >= tr._protect_mark && e.FlagsId != 0);
int i_bucket, i_lock, c;
Object o;
Node[] buckets;
while (true)
{
buckets = m_buckets;
o = m_locks[i_lock = (i_bucket = m % (c = buckets.Length)) % m_locks.Length];
Monitor.Enter(o);
if (buckets == m_buckets)
break;
Monitor.Exit(o);
}
Node first;
for (Node cur = first = buckets[i_bucket]; cur != null; cur = cur.m_next)
{
if (cur.m_mark == m)
{
fixed (Edge* pe = &cur.m_edge)
*(long*)pe = *(long*)&e;
Monitor.Exit(o);
return;
}
}
buckets[i_bucket] = new Node(e, m, first);
m_countPerLock[i_lock]++;
bool resizeDesired = m_countPerLock[i_lock] > c / m_locks.Length;
Monitor.Exit(o);
if (resizeDesired)
Resize();
return;
}
public override void RemoveEdge(int m)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
int i_bucket, i_lock;
Object o;
Node[] buckets;
while (true)
{
buckets = m_buckets;
o = m_locks[i_lock = (i_bucket = m % buckets.Length) % m_locks.Length];
Monitor.Enter(o);
if (buckets == m_buckets)
break;
Monitor.Exit(o);
}
for (Node prev = null, cur = buckets[i_bucket]; cur != null; prev = cur, cur = cur.m_next)
{
if (cur.m_mark == m)
{
if (prev == null)
buckets[i_bucket] = cur.m_next;
else
prev.m_next = cur.m_next;
m_countPerLock[i_lock]--;
break;
}
}
Monitor.Exit(o);
}
public override bool TryRemoveEdge(int m, out Edge e)
{
Debug.Assert(m != 0 && m >= tr._protect_mark);
int i_bucket, i_lock;
Object o;
Node[] buckets;
while (true)
{
buckets = m_buckets;
o = m_locks[i_lock = (i_bucket = m % buckets.Length) % m_locks.Length];
Monitor.Enter(o);
if (buckets == m_buckets)
break;
Monitor.Exit(o);
}
for (Node prev = null, cur = buckets[i_bucket]; cur != null; prev = cur, cur = cur.m_next)
{
if (cur.m_mark == m)
{
if (prev == null)
buckets[i_bucket] = cur.m_next;
else
prev.m_next = cur.m_next;
e = cur.m_edge;
m_countPerLock[i_lock]--;
Monitor.Exit(o);
return true;
}
}
Monitor.Exit(o);
e = default(Edge);
return false;
}
public override int Count
{
get
{
int count = 0;
try
{
// Acquire all locks
EnterAllLocks();
// Compute the count, we allow overflow
for (int i = 0; i < m_countPerLock.Length; i++)
count += m_countPerLock[i];
}
finally
{
// Release locks that have been acquired earlier
ExitAllLocks();
}
return count;
}
}
public override IEnumerable<int> Marks
{
get
{
tr.mre_truncate_ok.WaitOne();
#if LOCKED_ENUMS
int acquiredLocks = 0;
try
{
AcquireLocks(0, m_locks.Length, ref acquiredLocks);
Debug.Assert(acquiredLocks == m_locks.Length);
List<int> keys = new List<int>();
for (int i = 0; i < m_buckets.Length; i++)
{
for (Node current = m_buckets[i]; current != null; current = current.m_next)
keys.Add(current.m_mark);
}
return new ReadOnlyCollection<int>(keys);
}
finally
{
ReleaseLocks(0, acquiredLocks);
}
#else
foreach (Node n in m_buckets)
for (Node cur = n; cur != null; cur = cur.m_next)
yield return cur.m_mark;
#endif
}
}
public override IEnumerable<Edge> Edges
{
get
{
tr.mre_truncate_ok.WaitOne();
#if LOCKED_ENUMS
int acquiredLocks = 0;
try
{
AcquireLocks(0, m_locks.Length, ref acquiredLocks);
Debug.Assert(acquiredLocks == m_locks.Length);
List<Edge> values = new List<Edge>();
for (int i = 0; i < m_buckets.Length; i++)
{
for (Node current = m_buckets[i]; current != null; current = current.m_next)
values.Add(current.m_edge);
}
return new ReadOnlyCollection<Edge>(values);
}
finally
{
ReleaseLocks(0, acquiredLocks);
}
#else
foreach (Node n in m_buckets)
for (Node cur = n; cur != null; cur = cur.m_next)
yield return cur.m_edge;
#endif
}
}
public override IEnumerable<KeyValuePair<int, Edge>> PoolEdges
{
get
{
tr.mre_truncate_ok.WaitOne();
#if LOCKED_ENUMS
Node[] buckets = m_buckets;
for (int i = 0; i < buckets.Length; i++)
{
Node current = buckets[i];
// The memory barrier ensures that the load of the fields of 'current' doesn’t move before the load from buckets[i].
Thread.MemoryBarrier();
while (current != null)
{
yield return new KeyValuePair<int, Edge>(current.m_mark, current.m_edge);
current = current.m_next;
}
}
#else
foreach (Node n in m_buckets)
for (Node cur = n; cur != null; cur = cur.m_next)
yield return new KeyValuePair<int, Edge>(cur.m_mark, cur.m_edge);
#endif
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// extra
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void Clear()
{
try
{
EnterAllLocks();
Thread.MemoryBarrier();
m_buckets = new Node[DEFAULT_CAPACITY];
Array.Clear(m_countPerLock, 0, m_countPerLock.Length);
}
finally
{
ExitAllLocks();
}
}
public bool IsEmpty
{
get
{
try
{
EnterAllLocks();
for (int i = 0; i < m_countPerLock.Length; i++)
{
if (m_countPerLock[i] != 0)
return false;
}
}
finally
{
ExitAllLocks();
}
return true;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// internal
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void EnterAllLocks()
{
for (int i = 0; i < m_locks.Length; i++)
Monitor.Enter(m_locks[i]);
}
void ExitAllLocks()
{
for (int i = 0; i < m_locks.Length; i++)
Monitor.Exit(m_locks[i]);
}
public void Resize()
{
//if (tr.c_truncators > 0)
//{
// //foreach (Thread th in tr.truncators)
// // th.Priority = ThreadPriority.AboveNormal;
// return;
//}
Node[] buckets = m_buckets;
Monitor.Enter(m_locks[0]);
if (buckets != m_buckets)
{
Monitor.Exit(m_locks[0]);
return;
}
using (var q = new ThreadPriorityRegion(ThreadPriority.Highest))
{
int c = (int)(buckets.Length * 2) - 5;
while (c % 3 == 0 || c % 5 == 0 || c % 7 == 0 || c % 11 == 0)
c -= 2;
Node[] newBuckets = new Node[c];
int[] newCountPerLock = new int[m_locks.Length];
for (int i = 1; i < m_locks.Length; i++)
Monitor.Enter(m_locks[i]);
// Copy all data into a new table, creating new nodes for all elements
for (int i = 0; i < buckets.Length; i++)
{
for (Node current = buckets[i]; current != null; current = current.m_next)
{
int newBucketNo = current.m_mark % newBuckets.Length;
int newLockNo = newBucketNo % m_locks.Length;
newBuckets[newBucketNo] = new Node(current.m_edge, current.m_mark, newBuckets[newBucketNo]);
newCountPerLock[newLockNo]++;
}
}
Interlocked.Increment(ref ((ConcurrentTray)tr).c_resizes);
Thread.MemoryBarrier();
m_buckets = newBuckets;
m_countPerLock = newCountPerLock;
for (int i = 0; i < m_locks.Length; i++)
Monitor.Exit(m_locks[i]);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// internal
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void Shrink()
{
//tr.mre_truncate_ok.Wait();
Node[] buckets = m_buckets;
int c = m_countPerLock.Sum();
if (c == buckets.Length)
return;
Node[] newBuckets = new Node[c];
int[] newCountPerLock = new int[m_locks.Length];
// Copy all data into a new table, creating new nodes for all elements
for (int i = 0; i < buckets.Length; i++)
{
Node next;
for (Node current = buckets[i]; current != null; current = next)
{
next = current.m_next;
int newBucketNo = current.m_mark % newBuckets.Length;
int newLockNo = newBucketNo % m_locks.Length;
current.m_next = newBuckets[newBucketNo];
newBuckets[newBucketNo] = current;
newCountPerLock[newLockNo]++;
}
}
// And finally adjust m_buckets and m_countPerLock to point to data for the new table
Thread.MemoryBarrier();
m_buckets = newBuckets;
m_countPerLock = newCountPerLock;
}
};
};
}