1.
CPU가 멀티코어로 진화하면서 Concurrency는 소프트웨어기술의 중심 화두중 하나였습니다. Herb Sutter라는 소프트웨어 엔지니어가 있습니다. Exceptional C++의 저자이고 C++ Coding Standards를 같이 썼고 C++ 및 Concurrency와 관련한 글을 계속 발표하는 분입니다. 이 분이 유명한 Dr.Dobb’s Journal에 ‘Effective Concurrency’라는 주제로 기고한 칼럼만 보다라도 2007년부터 시작합니다. Mr.Herb가 2005년에 발표한 논문인 ‘Software and the Concurrency Revolution’을 보면 멀티코어 환경이 소프트웨어 발전에서 중요한 변곡점이었습니다. Herb Sutter가 발표한 글을 보시려면 아래에서 찾을 수 있습니다.
비슷한 이야기를 concurrency와 parallelism에서도 했습니다. 이 글에서 소개하였던 The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software도 Herb Sutter가 저자입니다.
Herb Sutter가 쓴 글을 보면 어느 때부터 Lock에 대한 글쓰기가 늘어납니다.
Use Critical Sections (Preferably Locks) to Eliminate Races(October 2007)2007)
Use Lock Hierarchies to Avoid Deadlock(January 2007)
Choose Concurrency-Friendly Data Structures(July 2008)
The Many Faces of Deadlock(August 2008)
Lock-Free Code: A False Sense of Security(September 2008)
Writing Lock-Free Code: A Corrected Queue(October 2008)
Writing a Generalized Concurrent Queue(November 2008)
Lock이란 단어는 Shared Memory로 개발할 때부터 들었지만 Lock Free란 단어에 익숙해진 때는 2009년쯤입니다. 이후 Inter Thread Communication이나 Parallel Computing과 관련한 자료를 찾다보면 Lock Free와 관련한 자료는 현재까지 쏫아지고 있습니다. Lock Free는 증권IT에서도 중요합니다. Low Latency와 HPC를 필요로 하는 업무영역들이 많기때문입니다. 2008년 Morgan Stanley에서 근무하는 Petru Marginean가 쓴 논문도 이런 필요를 보여주는 듯 합니다.
2.
최근 Lock Free와 관련하여 소개하였던 라이브러리(혹은 Pattern)이 몇 있습니다. 가장 대표적인 것이 LMAX의 Disruptor입니다. Disruptor는 지금도 많은 관심을 받고 있고 다양한 언어로 포팅되고 있습니다.
Lock free Algorithms for Ultimate Performance
또다른 것은 Linux Journal에서 소개하였던 NatSys의 작업입니다.
Lock-Free Multi-Producer Multi-Consumer Queue on Ring Buffer
이보다 더 오래되었고 C++를 사용하는 분들이 애용하는 Boost는 QuantLib, Boost C++ Library 및 ZeroMQ에서 소개하였습니다. Boost:lockfree와 관련하여 좀더 자세한 정보는 아래입니다.
이외에도 더 많은 것들이 있지만 오래전부터 혹은 최근에 주목받고 있는 것들입니다. 이와 관련하여 글을 보면 항상 따르는 질문이 있습니다.
“Diruptor와 비교하면 성능이 어떻게 되나요? Boost와 비교하면 어떻게 되나요? 무엇이 더 빠른가요?”
이에 대한 절대적인 답변은 있을 수 없습니다. 개발자의 능력이 다르고 도입하고자 하는 시스템의 구조와 업무가 다르기때문에 개발자들이 직접 시험을 해보고 결정하여야 합니다. 그렇지만 어떤 사람들은 무언가의 증명을 위해 결과를 만들어 내려고 합니다. 오늘 소개하는 내용이 그렇습니다. 앞서 소개하였던 NatSys의 Alexander Krizhanovsky입니다.
NatSys Lock-free Queue vs LMAX Disruptor vs boost::lockfree::queue
Java로 개발한 Dirupotr와 직접적인 비교를 하지 않고 C로 Diruptor Pattern을 구현한 Varon-t을 분석하였습니다. 정량적인 분석이 아니라 방법론에 대한 비평, 정성적 분석(^^)입니다.
The implementation is bit inaccurate: there are a lot of branches without branch prediction information available at compile time, to avoid cache line bouncing it wastes two cache lines instead of simple align an item on cache line (I mean vrt_padded_int). I didn’t pay too much attention to memory barriers usage, but giving that X86-64 provides relatively strict memory ordering, probably some of them also could be eliminated. Disruptor uses very cleaver ideas, but I believe its performance can be improved after good code review.
One more point is that while our queue implementation is C++, it’s still self sufficient and can be easily ported to C for using in kernel space. It’s doubtful (in my humble opinion) that generic container depends on non-standard libcork and moreover logging library (clogger).
One more thing to note about our queue and Disruptor. Dirsuptor’s uses naive yielding logic. The problems with the logic is that if a thread has not job for long time it fails to sleep for increasing from yield to yield call time, this if the queue has no job for long time, but at once has a big spike, then it typically will waking up for some time before it starts to work. We solved the issue with lock-free condition wait.
Boost:Lockfree:Queue와의 비교는 정량적입니다. BMT를 위한 소스코드를 소개하였고 이를 이용한 시험결과를 공개하였습니다. 직접 시험해보면 좋을 듯 합니다.
|
1 2 3 4 5 6 7 8 9 10 11 |
$ g++ -Wall -std=c++0x -O2 -D DCACHE1_LINESIZE=`getconf LEVEL1_DCACHE_LINESIZE` -I/opt/boost_1_55_0/include/ lockfree_rb_q.cc -lpthread $ ./a.out 13969ms check X data... Passed 69357ms check X data... Passed 20240ms check X data... Passed |
혹 여러분은 Lock Free Algorithm을 사용하시나요? 저는 Multi Thread가 아닌 Multi Process으로 동작하여야 하는 구조라 고민이 많습니다.(^^) 아마 현실적인 모습은 대신증권이 BMT를 했던 구조가 아닐까 합니다.
