From d497b64f3d712eeaa5956436fef1a3ca16ef59e9 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=A9mie=20Laval?= Date: Wed, 24 Mar 2010 19:26:00 +0000 Subject: [PATCH] =?utf8?q?2010-03-24=20=20J=C3=A9r=C3=A9mie=20Laval=20=20?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit In class/corlib/System.Collections.Concurrent/: * ConcurrentDictionary.cs: Enable tracking on SpinLock * ConcurrentSkipList.cs: Use Spinlock instead of Monitor and refactor to use a saner lock acquiring scheme. In class/corlib/Test/System.Collections.Concurrent/: * ConcurrentDictionaryTests.cs: Renaming in Assert svn path=/trunk/mcs/; revision=154165 --- .../System.Collections.Concurrent/ChangeLog | 6 + .../ConcurrentDictionary.cs | 2 +- .../ConcurrentSkipList.cs | 174 ++++++++++-------- .../System.Collections.Concurrent/ChangeLog | 4 + .../ConcurrentDictionaryTests.cs | 12 +- 5 files changed, 110 insertions(+), 88 deletions(-) diff --git a/mcs/class/corlib/System.Collections.Concurrent/ChangeLog b/mcs/class/corlib/System.Collections.Concurrent/ChangeLog index bec065be180..b6fd28405ae 100644 --- a/mcs/class/corlib/System.Collections.Concurrent/ChangeLog +++ b/mcs/class/corlib/System.Collections.Concurrent/ChangeLog @@ -1,3 +1,9 @@ +2010-03-24 Jérémie Laval + + * ConcurrentDictionary.cs: Enable tracking on SpinLock + * ConcurrentSkipList.cs: Use Spinlock instead of Monitor and + refactor to use a saner lock acquiring scheme. + 2010-03-24 Jérémie Laval * ConcurrentDictionary.cs: Fix lock releasing diff --git a/mcs/class/corlib/System.Collections.Concurrent/ConcurrentDictionary.cs b/mcs/class/corlib/System.Collections.Concurrent/ConcurrentDictionary.cs index ede3b3b0d02..eff27c01fc9 100644 --- a/mcs/class/corlib/System.Collections.Concurrent/ConcurrentDictionary.cs +++ b/mcs/class/corlib/System.Collections.Concurrent/ConcurrentDictionary.cs @@ -60,7 +60,7 @@ namespace System.Collections.Concurrent class Basket: List { - public SpinLock Lock = new SpinLock (); + public SpinLock Lock = new SpinLock (true); } // Assumption: a List is never empty diff --git a/mcs/class/corlib/System.Collections.Concurrent/ConcurrentSkipList.cs b/mcs/class/corlib/System.Collections.Concurrent/ConcurrentSkipList.cs index 57e267c2ab5..247b5059756 100644 --- a/mcs/class/corlib/System.Collections.Concurrent/ConcurrentSkipList.cs +++ b/mcs/class/corlib/System.Collections.Concurrent/ConcurrentSkipList.cs @@ -30,22 +30,24 @@ using System.Collections.Generic; namespace System.Collections.Concurrent { - + internal class ConcurrentSkipList : IProducerConsumerCollection { // Used for randomSeed [ThreadStatic] static Random r; // Used in FindNodes and thus most others methods - // avoid heavy local array creation at each method call and use + // avoid heavy local array creation at each method call and use // for thread locallity ThreadStatic attribute - [ThreadStaticAttribute] - static Node[] preds; - [ThreadStaticAttribute] - static Node[] succs; + [ThreadStatic] + static Node[] precedents; + [ThreadStatic] + static Node[] succedings; + [ThreadStatic] + static bool[] takenLocks; int count = 0; - + class Node { public readonly int Key; @@ -54,7 +56,7 @@ namespace System.Collections.Concurrent public readonly Node[] Nexts; public volatile bool Marked; public volatile bool FullyLinked; - public readonly object Lock; + public SpinLock Lock; public Node (int key, T value, int heightValue) { @@ -62,7 +64,7 @@ namespace System.Collections.Concurrent Value = value; TopLayer = heightValue; Nexts = new Node [heightValue + 1]; - Lock = new object (); + Lock = new SpinLock (true); Marked = FullyLinked = false; } } @@ -83,7 +85,7 @@ namespace System.Collections.Concurrent : this ((value) => comparer.GetHashCode (value)) { } - + public ConcurrentSkipList(Func hasher) { GetKey = hasher; @@ -92,11 +94,6 @@ namespace System.Collections.Concurrent void Init () { - if (succs == null) - succs = new Node [MaxHeight]; - if (preds == null) - preds = new Node [MaxHeight]; - leftSentinel = new Node (int.MinValue, default (T), MaxHeight); rightSentinel = new Node (int.MaxValue, default (T), MaxHeight); @@ -106,46 +103,46 @@ namespace System.Collections.Concurrent // The or ensures that randomSeed != 0 randomSeed = ((uint)Math.Abs (Next())) | 0x0100; } - + public bool TryAdd (T value) { if (value == null) throw new ArgumentNullException ("value"); - + CleanArrays (); int topLayer = GetRandomLevel (); int v = GetKey (value); while (true) { - int found = FindNode (v, preds, succs); + int found = FindNode (v, precedents, succedings); if (found != -1) { // A node with the same key already exists - Node nodeFound = succs [found]; + Node nodeFound = succedings [found]; if (!nodeFound.Marked) { SpinWait sw = new SpinWait (); - while (!nodeFound.FullyLinked) { + while (!nodeFound.FullyLinked) sw.SpinOnce (); - } + return false; } continue; } int highestLocked = -1; try { - bool valid = LockNodes (topLayer, ref highestLocked, + bool valid = LockNodes (topLayer, ref highestLocked, precedents, succedings, (layer, pred, succ) => !pred.Marked && !succ.Marked && pred.Nexts [layer] == succ); if (!valid) continue; - + Node newNode = new Node (v, value, topLayer); for (int layer = 0; layer <= topLayer; layer++) { - newNode.Nexts [layer] = succs [layer]; - preds [layer].Nexts [layer] = newNode; + newNode.Nexts [layer] = succedings [layer]; + precedents [layer].Nexts [layer] = newNode; } newNode.FullyLinked = true; } finally { - Unlock (preds, highestLocked); + Unlock (precedents, takenLocks, highestLocked); } Interlocked.Increment (ref count); return true; @@ -161,7 +158,7 @@ namespace System.Collections.Concurrent { int countSnapshot = count; T[] temp = new T [countSnapshot]; - + CopyTo(temp, 0); return temp; @@ -203,7 +200,7 @@ namespace System.Collections.Concurrent { if (value == null) throw new ArgumentNullException ("value"); - + CleanArrays(); Node toDelete = null; bool isMarked = false; @@ -211,36 +208,39 @@ namespace System.Collections.Concurrent int v = GetKey (value); while (true) { - int found = FindNode (v, preds, succs); - - if (isMarked || (found != -1 && OkToDelete (succs [found], found))) { + int found = FindNode (v, precedents, succedings); + bool taken = false; + int highestLocked = -1; + + if (isMarked || (found != -1 && OkToDelete (succedings [found], found))) { // If not marked then logically delete the node - if (!isMarked) { - toDelete = succs [found]; - topLayer = toDelete.TopLayer; - Monitor.Enter (toDelete.Lock); - // Now that we have the lock, check if the node hasn't already been marked - if (toDelete.Marked) { - Monitor.Exit (toDelete.Lock); - return false; - } - toDelete.Marked = true; - isMarked = true; - } - int highestLocked = -1; try { - bool valid = LockNodes (topLayer, ref highestLocked, + if (!isMarked) { + toDelete = succedings [found]; + topLayer = toDelete.TopLayer; + + toDelete.Lock.Enter (ref taken); + // Now that we have the lock, check if the node hasn't already been marked + if (toDelete.Marked) + return false; + + toDelete.Marked = true; + isMarked = true; + } + + bool valid = LockNodes (topLayer, ref highestLocked, precedents, succedings, (layer, pred, succ) => !pred.Marked && pred.Nexts [layer] == succ); if (!valid) continue; - for (int layer = topLayer; layer >= 0; layer--) { - preds [layer].Nexts [layer] = toDelete.Nexts [layer]; - } - Monitor.Exit (toDelete.Lock); + for (int layer = topLayer; layer >= 0; layer--) + precedents [layer].Nexts [layer] = toDelete.Nexts [layer]; } finally { - Unlock (preds, highestLocked); + if (taken) + toDelete.Lock.Exit (); + Unlock (precedents, takenLocks, highestLocked); } + Interlocked.Decrement (ref count); return true; } else { @@ -253,38 +253,42 @@ namespace System.Collections.Concurrent { if (value == null) throw new ArgumentNullException ("value"); - + return ContainsFromHash (GetKey (value)); } - + internal bool ContainsFromHash (int hash) { CleanArrays (); - int found = FindNode (hash, preds, succs); - return found != -1 && succs [found].FullyLinked && !succs [found].Marked; + int found = FindNode (hash, precedents, succedings); + return found != -1 && succedings [found].FullyLinked && !succedings [found].Marked; } - + internal bool GetFromHash (int hash, out T value) { value = default (T); CleanArrays (); // We are blindly supposing that the hash is correct // i.e. I trust myself :-) - int found = FindNode (hash, preds, succs); + int found = FindNode (hash, precedents, succedings); if (found == -1) return false; - + + bool taken = false; + Node node = succedings [found]; + try { - Monitor.Enter (succs [found].Lock); - Node node = succs [found]; + node.Lock.Enter (ref taken); + if (node.FullyLinked && !node.Marked) { value = node.Value; return true; } } finally { - Monitor.Exit (succs [found].Lock); + if (taken) + node.Lock.Exit (); } - + return false; } @@ -303,7 +307,7 @@ namespace System.Collections.Concurrent { return GetInternalEnumerator (); } - + IEnumerator GetInternalEnumerator () { Node curr = leftSentinel; @@ -311,34 +315,37 @@ namespace System.Collections.Concurrent // If there is an Add operation ongoing we wait a little // Possible optimization : use a helping scheme SpinWait sw = new SpinWait (); - while (!curr.FullyLinked) { + while (!curr.FullyLinked) sw.SpinOnce (); - } + yield return curr.Value; } } - void Unlock(Node[] preds, int highestLocked) + void Unlock (Node[] preds, bool[] takenLocks, int highestLocked) { - for (int i = 0; i <= highestLocked; i++) { - Monitor.Exit (preds [i].Lock); - } + for (int layer = 0; layer <= highestLocked; layer++) + if (takenLocks [layer]) + preds [layer].Lock.Exit (); } - bool LockNodes (int topLayer, ref int highestLocked, Func validityTest) + bool LockNodes (int topLayer, ref int highestLocked, Node[] preds, Node[] succs, Func validityTest) { Node pred, succ, prevPred = null; bool valid = true; - + for (int layer = 0; valid && (layer <= topLayer); layer++) { pred = preds [layer]; succ = succs [layer]; + takenLocks[layer] = false; + if (pred != prevPred) { // Possible optimization : limit topLayer to the first refused lock - Monitor.Enter (pred.Lock); + pred.Lock.Enter (ref takenLocks[layer]); highestLocked = layer; prevPred = pred; } + valid = validityTest (layer, pred, succ); } @@ -349,7 +356,7 @@ namespace System.Collections.Concurrent { // With preds and succs we record the path we use for searching v if (preds.Length != MaxHeight || succs.Length != MaxHeight) - throw new Exception ("precs or succs don't have the good length"); + throw new Exception ("preds or succs don't have the good length"); int found = -1; Node pred = leftSentinel; @@ -368,7 +375,7 @@ namespace System.Collections.Concurrent preds [layer] = pred; succs [layer] = curr; } - + return found; } @@ -391,18 +398,23 @@ namespace System.Collections.Concurrent while (((x >>= 1) & 1) != 0) ++level; return level; } - + void CleanArrays () { - if (succs == null) - succs = new Node [MaxHeight]; - if (preds == null) - preds = new Node [MaxHeight]; - + // If one is null, the others too + if (succedings == null) { + succedings = new Node [MaxHeight]; + precedents = new Node [MaxHeight]; + takenLocks = new bool [MaxHeight]; + + return; + } + // Hopefully these are more optimized than a bare for loop // (I suppose it uses memset internally) - Array.Clear (preds, 0, preds.Length); - Array.Clear (succs, 0, succs.Length); + Array.Clear (precedents, 0, precedents.Length); + Array.Clear (succedings, 0, succedings.Length); + Array.Clear (takenLocks, 0, takenLocks.Length); } int Next () diff --git a/mcs/class/corlib/Test/System.Collections.Concurrent/ChangeLog b/mcs/class/corlib/Test/System.Collections.Concurrent/ChangeLog index 99e0c37fc42..c81fae3d0aa 100644 --- a/mcs/class/corlib/Test/System.Collections.Concurrent/ChangeLog +++ b/mcs/class/corlib/Test/System.Collections.Concurrent/ChangeLog @@ -1,3 +1,7 @@ +2010-03-24 Jérémie Laval + + * ConcurrentDictionaryTests.cs: Renaming in Assert + 2010-03-24 Jérémie Laval * ConcurrentDictionaryTests.cs: Update behavior of TryAddDuplicateTest diff --git a/mcs/class/corlib/Test/System.Collections.Concurrent/ConcurrentDictionaryTests.cs b/mcs/class/corlib/Test/System.Collections.Concurrent/ConcurrentDictionaryTests.cs index 620bd8c66cd..4f1ad64ce2f 100644 --- a/mcs/class/corlib/Test/System.Collections.Concurrent/ConcurrentDictionaryTests.cs +++ b/mcs/class/corlib/Test/System.Collections.Concurrent/ConcurrentDictionaryTests.cs @@ -47,7 +47,7 @@ namespace MonoTests.System.Collections.Concurrent void AddStuff () { - map.TryAdd ("foo", 1); + map.TryAdd ("foo", 1); map.TryAdd ("bar", 2); map.TryAdd ("foobar", 3); } @@ -82,16 +82,16 @@ namespace MonoTests.System.Collections.Concurrent int value; Assert.IsTrue (map.TryGetValue ("monkey1", out value), "#1"); - Assert.AreEqual (3, value, "#1"); + Assert.AreEqual (3, value, "#1b"); Assert.IsTrue (map.TryGetValue ("monkey2", out value), "#2"); - Assert.AreEqual (3, value, "#2"); + Assert.AreEqual (3, value, "#2b"); Assert.IsTrue (map.TryGetValue ("monkey3", out value), "#3"); - Assert.AreEqual (3, value, "#3"); + Assert.AreEqual (3, value, "#3b"); Assert.IsTrue (map.TryGetValue ("monkey4", out value), "#4"); - Assert.AreEqual (3, value, "#4"); + Assert.AreEqual (3, value, "#4b"); }); } @@ -141,7 +141,7 @@ namespace MonoTests.System.Collections.Concurrent [Test] public void GetValueTest() { - Assert.AreEqual(1, map["foo"], "#1"); + Assert.AreEqual(1, map["foo"], "#1"); Assert.AreEqual(2, map["bar"], "#2"); Assert.AreEqual(3, map.Count, "#3"); } -- 2.25.1