Boost.Intrusive에서 제공되는 Container의 종류는 아래과 같음.
- Singly Linked List
- Circularly Linked List (like std::list)
- set/multiset/rbtree
- avl_set/avl_multiset/avltree
- splay_set/splay_multiset/splaytree
- sg_set/sg_multiset/sgtree
- unordered_set/unordered_multiset
먼저 Intrusive Container와 Non-intrusive Container의 차이점에 대해서 알아야 한다.
쉽게 설명하면.. 기존에 우리가 쓰는 Container들은 보통 Non-intrusive Container라고 생각하면 된다.
Linked List를 한번이라도 구현해보거나 구조에 대해서 생각해 본 사람이라면 알겠지만.
대략 Linked List는 아래와 같이 생겼다.
1 class SomeValue
2 {
3 //.. some members ..///
4 int asdf;
5 };
6
7 template <typename T>
8 class List<T>
9 {
10 class list_node
11 {
12 list_node *next;
13 list_node *previous;
14 T value;
15 };
16
17 //....
18 };
19
20 List<SomeValue> list;
여기서 14번째 줄처럼 Non-Intrusive Container는 Value값을 복사해서 가지게 되어 있다.
하지만 Intrusive Container의 Linked List는 아래와 같이 구현한다.
1 class SomeValue
2 {
3 // intrusive members.
4 SomeValue *previous;
5 SomeValue *next;
6
7 //.. some members ..///
8 int asdf;
9 };
10
11 template <typename T>
12 class List<T>
13 {
14 //....
15 };
16
17 List<SomeValue> list;
4번째, 5번째 줄처럼 기존에 Value 구조체에 Linked List에 필요한 구조체를 포함 시키는 게 핵심이다.
따라서, 메모리 관리는 Container 외부에서 담당하게 되는 것이고
Container 관리를 위한 메모리를 따로 할당 하지 않기 때문에 Performance 향상을 볼 수 있다.
아래는 비교표.
|
Issue |
Intrusive |
Non-intrusive |
|---|---|---|
|
Memory management |
External |
Internal through allocator |
|
Insertion/Erasure time |
Faster |
Slower |
|
Memory locality |
Better |
Worse |
|
Can hold non-copyable and non-movable objects by value |
Yes |
No |
|
Exception guarantees |
Better |
Worse |
|
Computation of iterator from value |
Constant |
Non-constant |
|
Insertion/erasure predictability |
High |
Low |
|
Memory use |
Minimal |
More than minimal |
|
Insert objects by value retaining polymorphic behavior |
Yes |
No (slicing) |
|
User must modify the definition of the values to insert |
Yes |
No |
|
Containers are copyable |
No |
Yes |
|
Inserted object's lifetime managed by |
User (more complex) |
Container (less complex) |
|
Container invariants can be broken without using the container |
Easier |
Harder (only with containers of pointers) |
|
Thread-safety analysis |
Harder |
Easier |
내가 제일 마음에 드는 부분은..
메모리 관리를 외부에서 할 수 있다는 점과 Memory Locality가 향상 된다는 점이 아닐까 싶다.
이를 잘 활용하면 불필요하게 Heap을 사용하는 것을 줄일 수 있다.
개발의 편의성 보다는 성능(!!)에 초점이 맞추어진 프로젝트가 있다면 써보길 추천..
아.. 실제 Boost.Intrusive를 쓰는 코드는 아래와 같이 생겼다.
1
2 struct SomeStruct
3 {
4 int i;
5 char someBuffer[1024];
6
7 SomeStruct()
8 {
9 }
10 };
11
12 struct SomeStructI
13 : public boost::intrusive::slist_base_hook<>
14 , public SomeStruct
15 {
16 };
17
18 slist<SomeStructI, cache_last<true> > ptrContainer;
19
20 BOOST_FOREACH(SomeStructI& someStruct, ptrContainer)
21 {
22 // ...
23 }
그다지 못 생긴 것도 아니다.
'정보 공유터' 카테고리의 다른 글
| [VS] Visual Studio 2008 SP1, Hotfix and Powertoys (0) | 2009/05/07 |
|---|---|
| C++ Concurrent Container - Intel TBB. (0) | 2009/05/06 |
| 영어에서 시간과 시각 구분하기 (2) | 2009/04/28 |
| Boost.Intrusive - STL Container보다 빠른 Container (1) | 2009/04/28 |
| Windows Tip - 메시지 박스 내용 복사하기. (10) | 2008/07/19 |
| C++에서 const char** (2) | 2008/06/30 |
| [TIP] 티스토리에서 MP3 쉽게 다운 받기 (3) | 2008/06/05 |
