CAS Lock lock-free 방식이 과연 성능에 얼마나 도움이 될까요?
CAS Lock lock-free는 명시적인 lock을 사용하지 않고 그와 동일한 효력을 내는 동기화 방식입니다. 그렇긴 해도, 프로세스 간에 동기화를 해주는 Kernel 동기화 객체를 대체할 수는 없고 같은 프로세스에서 CriticalSection의 사용을 대체하는 정도입니다.
Win32 API같은 경우에는 CAS Lock lock-free의 일환으로 spin 카운트를 도입하는데요. 예를 들어, A 스레드가 진입해서 lock을 소유하고 있는 상태에서 B 스레드가 해당 구역에 진입하면 곧바로 lock 대기 상태로 진입하지 않고 일정 시간 동안 루프를 돌면서 lock이 풀렸는지를 계속 체크하는 방식입니다.
그럼, 닷넷에 한번 비교해 볼까요? 닷넷은 Win32의 CriticalSection에 해당하는 것으로 참조개체의 SyncBlock을 이용한 Monitor.Enter/Exit 코드를 사용합니다. C#으로는 lock 키워드로 단축 표기가 되는데요. 이에 대해서는 전에 다음의 글에서 상세하게 다룬 적이 있습니다.
.NET 참조 개체 인스턴스의 SyncBlock을 확인하는 방법
; https://www.sysnet.pe.kr/2/0/1175
닷넷에서 CAS Lock
lock-free를 구현하려면 Interlocked.CompareExchange를 사용해야 합니다. 아래의 글에서 자세히 설명되어 있습니다. ^^
Lock-free data structures: the stack
; http://www.boyet.com/Articles/LockfreeStack.html
CAS(Compare and Swap)라고 일컬어지는 방식인데, 위의 CAS Lock
lock-free 방식을 다소 비효율적이지만 약간 더 이해하기 쉽게 바꿔보면 다음과 같습니다.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
namespace ConsoleApplication1
{
class Program
{
int _count;
int _lockVariable;
private void IncrementLockFree()
{
while (Interlocked.CompareExchange(ref _lockVariable, 1, 0) != 0)
{
}
_count++;
_lockVariable = 0;
}
private static void TestWithLockFree(int threadCount, int incCount)
{
Program pg = new Program();
List<Thread> list = new List<Thread>();
for (int i = 0; i < threadCount; i++)
{
Thread t = new Thread(
(obj) =>
{
for (int j = 0; j < incCount; j++)
{
pg.IncrementLockFree();
}
});
t.Start(pg);
list.Add(t);
}
list.ForEach((elem) => { elem.Join(); });
}
}
}
Interlocked.CompareExchange 메서드는 첫 번째 인자의 값이 세 번째 인자의 값과 같다면 두 번째 인자의 값으로 바꾸는 역할을 합니다. 그리고 그 반환값은 첫 번째 값이 원래 가지고 있던 예전 값이 반환됩니다. 물론, 바뀌지 않았다면 아무런 일도 발생하지 않고 반환값 역시 자신의 값 그대로 나옵니다.
따라서 "while (Interlocked.CompareExchange(ref _lockVariable, 1, 0) != 0)" 문을 최초 진입한 스레드는 _lockVariable 값을 1로 바꾸게 되고 이후의 코드로 진입할 수 있지만, 그 상태에서 두 번째로 진입한 스레드가 있다면 _lockVariable 값이 0이 아니기 때문에 먼저 진입한 스레드가 0으로 다시 돌려 놓지 않는 한 while 문을 무한 반복해서 실행합니다. 이 대목에서 눈치채시겠지만, CAS Lock
lock-free는 대기 상태로 진입하지 않는 대신 CPU 자원을 일부러 소모해가면서 동기화를 구현하는 방식입니다. (Win32의 spin count도 이런 방식입니다.)
위의 내용이 이해되셨다면 이제 해당 코드를 "
Lock-free data structures: the stack"글에서 구현한 방식으로 바꿔보면 다음과 같습니다.
private void IncrementLockFree()
{
int count;
do
{
count = _count;
} while (Interlocked.CompareExchange(ref _count, count + 1, count) != count);
}
이렇게 하는 것이 좀 더 빠르긴 합니다.
그런데, 과연 CAS Lock
lock-free 방식이 얼마나 빠를까요? 물론 다양한 상황에서 테스트 해보는 것이 중요하겠지만 여기서는 단순하게 변수의 값을 증가하는 것으로만 국한해서 테스트 해보겠습니다.
테스트는 C#의 lock을 사용한 것과 IncrementLockFree 메소드에 사용한 방식을 비교해 성능을 측정했고 최종 코드는 다음과 같습니다.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Tuple[] counts = new Tuple[]
{
new Tuple(1, 1), // JIT 컴파일 시간을 배제하기 위해 미리 한 번씩 실행
new Tuple(100, 10000),
new Tuple(10000, 1000),
new Tuple(10, 1000000),
new Tuple(2, 10000000),
};
foreach (var item in counts)
{
GC.Collect();
TestWithMonitor(item.Item1, item.Item2);
GC.Collect();
TestWithLockFree(item.Item1, item.Item2);
Console.WriteLine();
}
}
private static void TestWithMonitor(int threadCount, int incCount)
{
Stopwatch st = new Stopwatch();
Program pg = new Program();
List<Thread> list = new List<Thread>();
st.Start();
for (int i = 0; i < threadCount; i++)
{
Thread t = new Thread(
(obj) =>
{
for (int j = 0; j < incCount; j++)
{
pg.Increment();
}
});
t.Start(pg);
list.Add(t);
}
list.ForEach((elem) => { elem.Join(); });
st.Stop();
Console.WriteLine(st.ElapsedMilliseconds + "ms: " + pg.Count);
}
int _count;
object _lockInstance = new object();
public int Count { get { return _count; } }
private void Increment()
{
lock (_lockInstance)
{
_count++;
}
}
private void IncrementLockFree()
{
int count;
do
{
count = _count;
} while (Interlocked.CompareExchange(ref _count, count + 1, count) != count);
}
private static void TestWithLockFree(int threadCount, int incCount)
{
Stopwatch st = new Stopwatch();
Program pg = new Program();
List<Thread> list = new List<Thread>();
st.Start();
for (int i = 0; i < threadCount; i++)
{
Thread t = new Thread(
(obj) =>
{
for (int j = 0; j < incCount; j++)
{
pg.IncrementLockFree();
}
});
t.Start(pg);
list.Add(t);
}
list.ForEach((elem) => { elem.Join(); });
st.Stop();
Console.WriteLine(st.ElapsedMilliseconds + "ms: " + pg.Count);
}
}
}
아래는 그 결과인데, 물론 스레드 스케쥴링에 따른 오차가 포함될 수 있지만 대체적인 결과를 보면 단순한 lock 코드가 더 빠르다는 것을 알 수 있습니다.
C# lock - 47ms: 1000000
lock-free - 101ms: 1000000
C# lock - 716ms: 10000000
lock-free - 803ms: 10000000
C# lock - 387ms: 10000000
lock-free - 1314ms: 10000000
C# lock - 558ms: 20000000
lock-free - 1183ms: 20000000
다른 활용 사례에서는 CAS Lock
lock-free가 빠를 수도 있다는 것을 감안해도 코드의 가독성 측면까지 고려해 본다면 C#의 lock 코드가 더욱 추천됩니다.
(
첨부한 파일은 위의 코드를 포함합니다.)
최근에 공개된 인텔 Haswell 아키텍쳐의 CPU에서 TSX(transactional syncronisation extensions)와 메모리 트랜잭션을 제공해 준다는 기사를 보았습니다.
Benchmarks : Haswell's TSX and Memory Transaction Throughput (HLE and RTM)
; http://www.sisoftware.co.uk/?d=qa&f=ben_mem_hle
(윈도우 블루라고 알려진) 윈도우 8.1 빌드가 Haswell을 지원한다고도 하고... 닷넷 프레임워크의 경우 8.1에 포함된 것은 4.5.1 버전일 거라는 소식도 있고... 어찌되었건 닷넷이 Win32를 바탕으로 실행되니 아마도 윈도우 블루에서 실행되는 닷넷 프로그램은 자연스럽게 TSX의 혜택을 입지 않을까 예상해 봅니다.
... 하지만 ^^ 제 노트북의 CPU는 이제 구형이 되어 버렸으니 당분간 기다려야겠군요.
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]