Last active
December 16, 2020 09:27
-
-
Save jkotas/aff2ca3774414807be7312fa00d3d521 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Threading.Tasks; | |
using System.Diagnostics; | |
using System.Runtime.InteropServices; | |
using System.Threading; | |
// Taking this lock on the same thread repeatedly is very fast because of it has no interlocked operations. | |
// Switching the thread where the lock is taken is expensive because of allocation and FlushProcessWriteBuffers. | |
class AsymmetricLock | |
{ | |
public class LockCookie | |
{ | |
internal LockCookie(int threadId) | |
{ | |
ThreadId = threadId; | |
Taken = false; | |
} | |
public void Exit() | |
{ | |
Debug.Assert(ThreadId == Environment.CurrentManagedThreadId); | |
Taken = false; | |
} | |
internal readonly int ThreadId; | |
internal bool Taken; | |
} | |
LockCookie _current = new LockCookie(-1); | |
// Returning LockCookie to call Exit on is the fastest implementation because of it works naturally with the RCU pattern. | |
// The traditional Enter/Exit lock interface would require thread local storage or some other scheme to reclaim the cookie. | |
public LockCookie Enter() | |
{ | |
int currentThreadId = Environment.CurrentManagedThreadId; | |
LockCookie entry = _current; | |
if (entry.ThreadId == currentThreadId) | |
{ | |
entry.Taken = true; | |
// | |
// If other thread started stealing the ownership, we need to take slow path. | |
// | |
// Volatile works here, but it is too big of a hammer because of it will result into memory barrier on ARM that | |
// we do not need here. We really just need to make sure that the compiler won't reorder the read with the above write. | |
// RyuJIT won't reorder them today, but more advanced optimizers might. We may need Interlocked.CompilerBarrier() API | |
// to mark places where we just want to prevent compiler reordering without actual memory barrier. | |
// | |
if (Volatile.Read(ref _current) == entry) | |
{ | |
return entry; | |
} | |
entry.Taken = false; | |
} | |
return EnterSlow(); | |
} | |
private LockCookie EnterSlow() | |
{ | |
// Attempt to steal the ownership. Take a regular lock to make sure that only thread is trying to steal it at a time. | |
lock (this) | |
{ | |
// We are the new fast thread now! | |
var oldEntry = _current; | |
_current = new LockCookie(Environment.CurrentManagedThreadId); | |
// After FlushProcessWriteBuffers, we can be sure that the Volatile.Read done by the fast thread will see that it is not a fast | |
// thread anymore, and thus it will not attempt to enter the lock. | |
FlushProcessWriteBuffers(); | |
// Keep looping as long as the lock is taken by other thread | |
SpinWait sw = new SpinWait(); | |
while (oldEntry.Taken) | |
sw.SpinOnce(); | |
_current.Taken = true; | |
return _current; | |
} | |
} | |
[DllImport("kernel32.dll")] | |
extern static void FlushProcessWriteBuffers(); | |
} | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
int myCounter = 0; | |
AsymmetricLock myLock = new AsymmetricLock(); | |
Task[] tasks = new Task[10]; | |
for (int i = 0; i < tasks.Length; i++) | |
{ | |
tasks[i] = Task.Run(() => | |
{ | |
for (int j = 0; j < 100000000; j++) | |
{ | |
var lockCookie = myLock.Enter(); | |
myCounter++; | |
lockCookie.Exit(); | |
} | |
} | |
); | |
} | |
Task.WaitAll(tasks); | |
Console.WriteLine(myCounter); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment