Microsoft MVP성태의 닷넷 이야기
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일

lock-free 방식이 과연 성능에 얼마나 도움이 될까요?

lock-free는 명시적인 lock을 사용하지 않고 그와 동일한 효력을 내는 동기화 방식입니다. 그렇긴 해도, 프로세스 간에 동기화를 해주는 Kernel 동기화 객체를 대체할 수는 없고 같은 프로세스에서 CriticalSection의 사용을 대체하는 정도입니다.

Win32 API같은 경우에는 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

닷넷에서 lock-free를 구현하려면 Interlocked.CompareExchange를 사용해야 합니다. 아래의 글에서 자세히 설명되어 있습니다. ^^

Lock-free data structures: the stack 
; http://www.boyet.com/Articles/LockfreeStack.html

CAS(Compare and Swap)라고 일컬어지는 방식인데, 위의 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 문을 무한 반복해서 실행합니다. 이 대목에서 눈치채시겠지만, 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);
}

이렇게 하는 것이 좀 더 빠르긴 합니다.




그런데, 과연 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

다른 활용 사례에서는 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는 이제 구형이 되어 버렸으니 당분간 기다려야겠군요.




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]


donaricano-btn



[최초 등록일: ]
[최종 수정일: 7/10/2021

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 쓴 사람
 



2014-08-26 12시14분
위에서 제가 제시한 방법은 엄밀히 lock-free라고 볼 수 없고, 그냥 CAS를 이용한 lock을 한 것에 불과합니다. lock-free에 대한 자세한 사항은 다음의 글을 참조하세요. ^^

Chapter 17. Boost.Lockfree
; http://www.boost.org/doc/libs/1_53_0/doc/html/lockfree.html

Ndc2014 시즌 2 : 멀티스레드 프로그래밍이 왜 이리 힘드나요? (Lock-free에서 Transactional Memory까지)
; http://www.slideshare.net/zzapuno/ndc2014-2
정성태

[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
12739정성태7/28/202114오류 유형: 746. Azure Active Directory - IDW10106: The 'ClientId' option must be provided.
12738정성태7/28/202114오류 유형: 745. Azure Active Directory - Client credential flows must have a scope value with /.default suffixed to the resource identifier (application ID URI).
12737정성태7/28/202118오류 유형: 744. Azure Active Directory - The resource principal named api://...[client_id]... was not found in the tenant
12736정성태7/28/202117오류 유형: 743. Active Azure Directory에서 "API permissions"의 권한 설정이 "Not granted for ..."로 나오는 문제
12735정성태7/27/202159.NET Framework: 1081. C# - Azure AD 인증을 지원하는 데스크톱 애플리케이션 예제(Windows Forms)파일 다운로드1
12734정성태7/26/202173스크립트: 20. 특정 단어로 시작하거나/끝나는 문자열을 포함/제외하는 정규 표현식 - Look-around
12733정성태7/23/202178.NET Framework: 1081. Self-Contained/SingleFile 유형의 .NET Core/5+ 실행 파일을 임베딩한다면?파일 다운로드2
12732정성태7/23/202128오류 유형: 742. SharePoint - The super user account utilized by the cache is not configured.
12731정성태7/23/202137개발 환경 구성: 584. Add Internal URLs 화면에서 "Save" 버튼이 비활성화 된 경우
12730정성태7/23/202145개발 환경 구성: 583. Visual Studio Code - Go 코드에서 입력을 받는 경우
12729정성태7/22/202158.NET Framework: 1080. xUnit 단위 테스트에 메서드/클래스 수준의 문맥 제공 - Fixture
12728정성태7/22/202162.NET Framework: 1079. MSTestv2 단위 테스트에 메서드/클래스/어셈블리 수준의 문맥 제공
12727정성태7/21/2021121.NET Framework: 1078. C# 단위 테스트 - MSTestv2/NUnit의 Assert.Inconclusive 사용법(?)
12726정성태7/21/202185VS.NET IDE: 169. 비주얼 스튜디오 - 단위 테스트 선택 시 MSTestv2 외의 xUnit, NUnit 사용법
12725정성태7/21/202135오류 유형: 741. Failed to find the "go" binary in either GOROOT() or PATH
12724정성태7/21/2021105개발 환경 구성: 582. 윈도우 환경에서 Visual Studio Code + Go (Zip) 개발 환경 [1]
12723정성태7/21/202145오류 유형: 740. SharePoint - Alternate access mappings have not been configured 경고
12722정성태7/20/202196오류 유형: 739. MSVCR110.dll이 없어 exe 실행이 안 되는 경우
12721정성태7/20/202151오류 유형: 738. The trust relationship between this workstation and the primary domain failed. - 세 번째 이야기
12720정성태7/19/202187Linux: 43. .NET Core/5+ 응용 프로그램의 Ubuntu (Debian) 패키지 준비
12719정성태7/19/202187오류 유형: 737. SharePoint 설치 시 "0x800710D8 The object identifier does not represent a valid object." 오류 발생
12718정성태7/19/2021119개발 환경 구성: 581. Windows에서 WSL로 파일 복사 시 root 소유권으로 적용되는 문제파일 다운로드1
12717정성태7/18/202196Windows: 195. robocopy에서 파일의 ADS(Alternate Data Stream) 정보 복사를 제외하는 방법
12716정성태7/17/202186개발 환경 구성: 580. msbuild의 Exec Task에 robocopy를 사용하는 방법파일 다운로드1
12715정성태7/17/202180오류 유형: 736. Windows - MySQL zip 파일 버전의 "mysqld --skip-grant-tables" 실행 시 비정상 종료
[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...