1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
// Copyright (c) 2016 Baidu, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Author: Ge,Jun (gejun@baidu.com)
// Date: Sat Dec 3 13:11:32 CST 2016
#ifndef BUTIL_POOLED_MAP_H
#define BUTIL_POOLED_MAP_H
#include "butil/single_threaded_pool.h"
#include <new>
#include <map>
namespace butil {
namespace details {
template <class T1, size_t BLOCK_SIZE> class PooledAllocator;
}
// A drop-in replacement for std::map to improve insert/erase performance slightly
//
// When do use PooledMap?
// A std::map with 10~100 elements. insert/erase performance will be slightly
// improved. Performance of find() is unaffected.
// When do NOT use PooledMap?
// When the std::map has less that 10 elements, PooledMap is probably slower
// because it allocates BLOCK_SIZE memory at least. When the std::map has more than
// 100 elements, you should use butil::FlatMap instead.
// insert/erase comparisons between several maps:
// [ value = 8 bytes ]
// Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 15/114/54/60
// Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/123/56/37
// Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 9/92/56/54
// Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 3/68/51/35
// Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/99/63/54
// Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/73/54/35
// [ value = 32 bytes ]
// Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 14/107/57/57
// Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/75/53/37
// Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/94/55/53
// Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/67/50/37
// Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/102/63/54
// Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/69/53/36
// [ value = 128 bytes ]
// Sequentially inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 35/160/96/98
// Sequentially erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/96/53/42
// Sequentially inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 30/159/98/98
// Sequentially erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/82/49/43
// Sequentially inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 29/155/114/116
// Sequentially erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/81/53/43
// [ value = 8 bytes ]
// Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/168/103/59
// Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/159/125/37
// Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/157/115/54
// Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/175/138/36
// Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 11/219/177/56
// Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/229/207/47
// [ value = 32 bytes ]
// Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 17/178/112/57
// Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/149/117/38
// Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 15/169/135/54
// Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/157/129/39
// Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 19/242/203/55
// Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/233/218/54
// [ value = 128 bytes ]
// Randomly inserting 100 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 36/214/145/96
// Randomly erasing 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/166/122/53
// Randomly inserting 1000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 36/230/174/100
// Randomly erasing 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/193/153/65
// Randomly inserting 10000 into FlatMap/std::map/butil::PooledMap/butil::hash_map takes 45/304/270/115
// Randomly erasing 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/299/246/88
template <typename K, typename V, size_t BLOCK_SIZE = 512,
typename C = std::less<K> >
class PooledMap
: public std::map<K, V, C, details::PooledAllocator<int, BLOCK_SIZE> > {
};
namespace details {
// Specialize for void
template <size_t BLOCK_SIZE>
class PooledAllocator<void, BLOCK_SIZE> {
public:
typedef void * pointer;
typedef const void* const_pointer;
typedef void value_type;
template <class U1> struct rebind {
typedef PooledAllocator<U1, BLOCK_SIZE> other;
};
};
template <class T1, size_t BLOCK_SIZE>
class PooledAllocator {
public:
typedef T1 value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T1* pointer;
typedef const T1* const_pointer;
typedef T1& reference;
typedef const T1& const_reference;
template <class U1> struct rebind {
typedef PooledAllocator<U1, BLOCK_SIZE> other;
};
public:
PooledAllocator() {}
PooledAllocator(const PooledAllocator&) {}
template <typename U1, size_t BS2>
PooledAllocator(const PooledAllocator<U1, BS2>&) {}
void operator=(const PooledAllocator&) {}
template <typename U1, size_t BS2>
void operator=(const PooledAllocator<U1, BS2>&) {}
void swap(PooledAllocator& other) { _pool.swap(other._pool); }
// Convert references to pointers.
pointer address(reference r) const { return &r; };
const_pointer address(const_reference r) const { return &r; };
// Allocate storage for n values of T1.
pointer allocate(size_type n, PooledAllocator<void, 0>::const_pointer = 0) {
if (n == 1) {
return (pointer)_pool.get();
} else {
return (pointer)malloc(n * sizeof(T1));
}
};
// Deallocate storage obtained by a call to allocate.
void deallocate(pointer p, size_type n) {
if (n == 1) {
return _pool.back(p);
} else {
free(p);
}
};
// Return the largest possible storage available through a call to allocate.
size_type max_size() const { return 0xFFFFFFFF / sizeof(T1); };
void construct(pointer ptr) { ::new (ptr) T1; };
void construct(pointer ptr, const T1& val) { ::new (ptr) T1(val); };
template <class U1> void construct(pointer ptr, const U1& val)
{ ::new (ptr) T1(val); }
void destroy(pointer p) { p->T1::~T1(); };
private:
butil::SingleThreadedPool<sizeof(T1), BLOCK_SIZE, 1> _pool;
};
// Return true if b could be used to deallocate storage obtained through a
// and vice versa. It's clear that our allocator can't be exchanged.
template <typename T1, size_t S1, typename T2, size_t S2>
bool operator==(const PooledAllocator<T1, S1>&, const PooledAllocator<T2, S2>&)
{ return false; };
template <typename T1, size_t S1, typename T2, size_t S2>
bool operator!=(const PooledAllocator<T1, S1>& a, const PooledAllocator<T2, S2>& b)
{ return !(a == b); };
} // namespace details
} // namespace butil
// Since this allocator can't be exchanged(check impl. of operator==) nor
// copied, specializing swap() is a must to make map.swap() work.
#if !defined(BUTIL_CXX11_ENABLED)
#include <algorithm> // std::swap until C++11
#else
#include <utility> // std::swap since C++11
#endif
namespace std {
template <class T1, size_t BLOCK_SIZE>
inline void swap(::butil::details::PooledAllocator<T1, BLOCK_SIZE> &lhs,
::butil::details::PooledAllocator<T1, BLOCK_SIZE> &rhs){
lhs.swap(rhs);
}
} // namespace std
#endif // BUTIL_POOLED_MAP_H