无锁(lock-free)容器库libcds的使用指引及调查
写在最前：(1).libcds依赖boost。Boost的下载、编译可参考博文：http://blog.csdn.net/great3779/article/details/7310392(2).本文中用到了我自己封装的线程安全容器CWnQueue，可参考http://blog.csdn.net/great3779/article/details/7180383获取。(3).本文中用到
写在最前：
(1).libcds依赖boost。Boost的下载、编译可参考博文：http://blog.csdn.net/great3779/article/details/7310392
(2).本文中用到了我自己封装的线程安全容器CWnQueue，可参考http://blog.csdn.net/great3779/article/details/7180383获取。
(3).本文中用到的测时套件TimerKit，可参考http://blog.csdn.net/great3779/article/details/7353028获取。
下面开始对libcds的讨论：
1. 获取：http://libcds.sourceforge.net/其中有源码、文档及论坛等。
2. 开源协议：BSD License
3. 主要功能：提供了lockfree（无锁的）浸入式和非浸入式容器。
非浸入式容器：类似于STL容器，入容器时采用值传递方式；
浸入式容器：入容器时采用引用传递方式。
浸入式容器是非浸入式容器的基类（即浸入式容器是基础，非浸入式容器实现于浸入式容器之上）
从上图可以看出，libcds主要提供了四类容器：Stacks（栈容器）、Queues（队列容器）、Maps（映射表容器）、Lists（链表容器），分别对应STL相对应的容器。
4. 编译：参考http://libcds.sourceforge.net/doc/cds-api/index.html
摘抄如下：
由于我在windows下试用libcds，因此总结一下windows下编译libcds的方法：
(1).编译并配置好boost。（关于boost的编译及配置，可以参考我相关文章：http://blog.csdn.net/great3779/article/details/7310392等）
(2).至cds目录下的\projects\Win子目录，选择相应的解决方案（.sln）。（例如，使用VS2008的朋友，可以打开vc9下的cds.sln）
(3).打开后，会发现其中包含了三个工程，编译cds工程即可。（其他两个工程是cds的单元测试以及hdr测试工程，可以不编译）。
(4).编译完成后，会在cds根目录下生成bin目录，内含cds的dll和lib文件。
(5).在你的demo工程中，引入dll和lib，就可以使用libcds了。
5. 使用示例（以Queues为例，其余容器类似）：
(1).使用前准备
libcds文档原文摘抄如下：
First, in your code you should initialize cds library and a garbage collectorin main function:
#include <cds/init.h> // for cds::Initialize and cds::Terminate #include <cds/gc/hp.h> // for cds::HP (Hazard Pointer) garbage collector int main(int argc, char** argv) { // Initialize libcds cds::Initialize() ; { // Initialize Hazard Pointer singleton cds::gc::HP hpGC() ; // Do what you need ... } // Terminate libcds cds::Terminate() ; }
Second, any of your thread should be attached to cds infrastructure.
#include <cds/gc/hp.h> int myThreadEntryPoint(void *) { // Attach the thread to Hazard Pointer singleton cds::gc::HP::thread_gc myThreadGC() ; // Do some work ... // The destructor of myThreadGC object detaches the thread from HP singleton }
After that, you can use cds lock-freecontainers safely without any synchronization.
从文档中可以看出，要使用libcds，主线程需进行三个步骤：
(a). 初始化libcds
(b). 初始化Hazard指针单例
cds::gc::HP hpGC();
(c). 结束libcds
此外，每个子线程的开头需要关联线程至Hazard指针单例
cds::gc::HP::thread_gcmyThreadGC();
(2). Demo程序（小技巧：libcds源码注释中提供了比较详细的类使用方式，例如michael_map.h中就提供了非常详细的使用MichaelHashMap的方法）
#include <cds/init.h> // for cds::Initialize andcds::Terminate
#include <cds/gc/hp.h> // for cds::HP (Hazard Pointer) garbagecollector
#include <cds/container/msqueue.h> // msqueue
typedef cds::container::MSQueue<cds::gc::HP,int> INT_MSQueue;
int main(int argc, char** argv)
{
//Initialize libcds
cds::Initialize();
//Initialize Hazard Pointer singleton
cds::gc::HPhpGC;
//Attach the thread to Hazard Pointer singleton
cds::gc::HP::thread_gcmyThreadGC;
//define queues
INT_MSQueue cds_queue;
//push element to queue
cds_queue.push(33);
//Terminate libcds
cds::Terminate();
}(1).libcds容器的接口不丰富（或不完善）。这导致了实用性下降。
例如：有些容器不提供迭代器，例如MSQueue。或者就算提供了，也不太好用（相对标准STL），例如MichaelKVList的iterator。
上图左侧为STL queue接口，右侧为libcds MSQueue接口。MSQueue没有提供front方法，且size()方法无效（实践中发现其值总为0，也可参考其注释）。此外，enqueue/dequeue方法与push/pop方法有重复之嫌（为接口兼容？）。
(2).最重要的，与我自己封装的线程安全队列CWnQueue相比，性能上不占优势（甚至还更慢，这很难理解！）。
对比如下：
(a).单线程测试（push/pop操作）
int main(int argc, char** argv)
{
//Initialize libcds
cds::Initialize();
//Initialize Hazard Pointer singleton
cds::gc::HPhpGC;
cds::gc::HP::thread_gcmyThreadGC;
{
TKittk;
//Do what you need
intnSize = 10*1000*1000;
//test cds MSQueue
INT_MSQueuearr;
{
TUnittu("cds_queue_push");
RegisterUnit(tu);
for(inti = 0 ; i < nSize; ++i)
arr.push(i);
}
{
TUnittu("cds_queue_pop");
RegisterUnit(tu);
inti;
while(arr.pop(i));
}
//test stl queue
queue<int>arr2;
{
TUnittu("stl_queue_push");
RegisterUnit(tu);
for(inti = 0; i < nSize; ++i)
arr2.push(i);
}
{
TUnittu("stl_queue_pop");
RegisterUnit(tu);
while(!arr2.empty())
arr2.pop();
}
//test CWnQueue
CWnQueue<int>arr3;
{
TUnittu("wn_queue_push");
RegisterUnit(tu);
for(inti = 0; i < nSize; ++i)
arr3.push(i);
}
{
TUnittu("wn_queue_pop");
RegisterUnit(tu);
inti;
while(arr3.pop(i));
}
}
//Terminate libcds
cds::Terminate();
}测时结果：
从上图测时结果可以看出，cds的单线程push/pop表现均最差，甚至比CWnQueue也慢了不少！
(b).多线程测试（libcds意义所在）
#define TEST_CDS_QUEUE
#ifdef TEST_CDS_QUEUE
INT_MSQueue arr;
#else
CWnQueue<int> arr;
#endif
const int TEST_SIZE = 1000*1000*10;
void Push()
{
TUnittu("push");
RegisterUnit(tu);
#ifdef TEST_CDS_QUEUE
cds::gc::HP::thread_gcmyThreadGC;
#endif
for(inti = 0; i < TEST_SIZE; ++i)
{
arr.push(i);
}
}
void Pop()
{
{
TUnittu("pop");
RegisterUnit(tu);
#ifdef TEST_CDS_QUEUE
cds::gc::HP::thread_gcmyThreadGC;
#endif
inti;
while(1)
{
while(arr.pop(i))
{
if(i== TEST_SIZE-1)
{
cout<< "Finish" << endl;
gotoEND;
}
}
Sleep(100);
}
}
END:
EndTC();
}
int main(int argc, char** argv)
{
//Initialize libcds
cds::Initialize();
//Initialize Hazard Pointer singleton
cds::gc::HPhpGC;
cds::gc::HP::thread_gcmyThreadGC;
{
TKittk;
boost::threadt_push(Push);
for(inti = 0; i < 10; ++i)
boost::threadt_pop(Pop);
Sleep(10*1000);
}
//Terminate libcds
cds::Terminate();
}
MSQueue测时结果：
CWnQueue测试结果：
由于STL queue非线程安全，因此没有参与测试。从测试结果看，MSQueue在多线程表现下依旧没有任何优势，甚至表现还不如CWnQueue。而这原本应该是MSQueue的强项所在！
(c).带MSQueue的测试程序，在程序结束后总会报一个错误（Debug/Release下均有，经跟踪，是由于libcds内部获取某线程信息失败导致）。原因不明。不知是否与我的测试环境有关。
附上测试环境
软件环境：
WindowsServer 2003 Enterprise x64 Edition sp2 + VS2008sp1 +Boost1.49.0
硬件环境：
Pentium(R)Dual-Core E5200 + 4.00G + 160G(7200)
结论在最后：
Libcds容器既没有提供完善优雅的接口，在单/多线程下表现也不行（还不如我自己封装的线程安全容器）。似乎不是一个好的解决方案。（这实在是很难令人置信！！！）
（当然，由于测试还比较浅显、粗糙，有很大可能是我对libcds使用方法理解不够充分，从而误解了它。另外，对于浸入式容器，我也没测试，表现应该会比非浸入式容器好。但由于STL容器都是非浸入式容器，并且浸入式容器使用中陷阱很多，因此意义仿佛不是太大。）
最后非常希望有志之士能与我一起讨论libcds或纠正我对其使用/认识上的一些误区。邮件：great3779@sina.com。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
1
0- 0
已为社区贡献3条内容
所有评论(0)