Skip to content

Commit b3ddc5e

Browse files
kazcwkazcw
committed
LockedPool: avoid quadratic-time allocation
Use separate maps for used/free chunks to avoid linear scan through alloced chunks for each alloc.
1 parent 0b59f80 commit b3ddc5e

File tree

3 files changed

+60
-90
lines changed

3 files changed

+60
-90
lines changed

‎src/support/lockedpool.cpp‎

Lines changed: 56 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,8 @@
2626
#include <unistd.h> // for sysconf
2727
#endif
2828

29+
#include <algorithm>
30+
2931
LockedPoolManager* LockedPoolManager::_instance = NULL;
3032
std::once_flag LockedPoolManager::init_flag;
3133

@@ -45,7 +47,7 @@ Arena::Arena(void *base_in, size_t size_in, size_t alignment_in):
4547
base(static_cast<char*>(base_in)), end(static_cast<char*>(base_in) + size_in), alignment(alignment_in)
4648
{
4749
// Start with one free chunk that covers the entire arena
48-
chunks.emplace(base, Chunk(size_in, false));
50+
chunks_free.emplace(base, size_in);
4951
}
5052

5153
Arena::~Arena()
@@ -57,24 +59,30 @@ void* Arena::alloc(size_t size)
5759
// Round to next multiple of alignment
5860
size = align_up(size, alignment);
5961

60-
// Don't handle zero-sized chunks, or those bigger than MAX_SIZE
61-
if (size == 0 || size >= Chunk::MAX_SIZE) {
62+
// Don't handle zero-sized chunks
63+
if (size == 0)
6264
return nullptr;
63-
}
6465

65-
for (auto& chunk: chunks) {
66-
if (!chunk.second.isInUse() && size <= chunk.second.getSize()) {
67-
char* _base = chunk.first;
68-
size_t leftover = chunk.second.getSize() - size;
69-
if (leftover > 0) { // Split chunk
70-
chunks.emplace(_base + size, Chunk(leftover, false));
71-
chunk.second.setSize(size);
72-
}
73-
chunk.second.setInUse(true);
74-
return reinterpret_cast<void*>(_base);
75-
}
66+
// Pick a large enough free-chunk
67+
auto it = std::find_if(chunks_free.begin(), chunks_free.end(),
68+
[=](const std::map<char*, size_t>::value_type& chunk){ return chunk.second >= size; });
69+
if (it == chunks_free.end())
70+
return nullptr;
71+
72+
// Create the used-chunk, taking its space from the end of the free-chunk
73+
auto alloced = chunks_used.emplace(it->first + it->second - size, size).first;
74+
if (!(it->second -= size))
75+
chunks_free.erase(it);
76+
return reinterpret_cast<void*>(alloced->first);
77+
}
78+
79+
/* extend the Iterator if other begins at its end */
80+
template <class Iterator, class Pair> bool extend(Iterator it, const Pair& other) {
81+
if (it->first + it->second == other.first) {
82+
it->second += other.second;
83+
return true;
7684
}
77-
return nullptr;
85+
return false;
7886
}
7987

8088
void Arena::free(void *ptr)
@@ -83,65 +91,49 @@ void Arena::free(void *ptr)
8391
if (ptr == nullptr) {
8492
return;
8593
}
86-
auto i = chunks.find(static_cast<char*>(ptr));
87-
if (i == chunks.end() || !i->second.isInUse()) {
88-
throw std::runtime_error("Arena: invalid or double free");
89-
}
9094

91-
i->second.setInUse(false);
92-
93-
if (i != chunks.begin()) { // Absorb into previous chunk if exists and free
94-
auto prev = i;
95-
--prev;
96-
if (!prev->second.isInUse()) {
97-
// Absorb current chunk size into previous chunk.
98-
prev->second.setSize(prev->second.getSize() + i->second.getSize());
99-
// Erase current chunk. Erasing does not invalidate current
100-
// iterators for a map, except for that pointing to the object
101-
// itself, which will be overwritten in the next statement.
102-
chunks.erase(i);
103-
// From here on, the previous chunk is our current chunk.
104-
i = prev;
105-
}
106-
}
107-
auto next = i;
108-
++next;
109-
if (next != chunks.end()) { // Absorb next chunk if exists and free
110-
if (!next->second.isInUse()) {
111-
// Absurb next chunk size into current chunk
112-
i->second.setSize(i->second.getSize() + next->second.getSize());
113-
// Erase next chunk.
114-
chunks.erase(next);
115-
}
95+
// Remove chunk from used map
96+
auto i = chunks_used.find(static_cast<char*>(ptr));
97+
if (i == chunks_used.end()) {
98+
throw std::runtime_error("Arena: invalid or double free");
11699
}
100+
auto freed = *i;
101+
chunks_used.erase(i);
102+
103+
// Add space to free map, coalescing contiguous chunks
104+
auto next = chunks_free.upper_bound(freed.first);
105+
auto prev = (next == chunks_free.begin()) ? chunks_free.end() : std::prev(next);
106+
if (prev == chunks_free.end() || !extend(prev, freed))
107+
prev = chunks_free.emplace_hint(next, freed);
108+
if (next != chunks_free.end() && extend(prev, *next))
109+
chunks_free.erase(next);
117110
}
118111

119112
Arena::Stats Arena::stats() const
120113
{
121-
Arena::Stats r;
122-
r.used = r.free = r.total = r.chunks_used = r.chunks_free = 0;
123-
for (const auto& chunk: chunks) {
124-
if (chunk.second.isInUse()) {
125-
r.used += chunk.second.getSize();
126-
r.chunks_used += 1;
127-
} else {
128-
r.free += chunk.second.getSize();
129-
r.chunks_free += 1;
130-
}
131-
r.total += chunk.second.getSize();
132-
}
114+
Arena::Stats r{ 0, 0, 0, chunks_used.size(), chunks_free.size() };
115+
for (const auto& chunk: chunks_used)
116+
r.used += chunk.second;
117+
for (const auto& chunk: chunks_free)
118+
r.free += chunk.second;
119+
r.total = r.used + r.free;
133120
return r;
134121
}
135122

136123
#ifdef ARENA_DEBUG
124+
void printchunk(char* base, size_t sz, bool used) {
125+
std::cout <<
126+
"0x" << std::hex << std::setw(16) << std::setfill('0') << base <<
127+
" 0x" << std::hex << std::setw(16) << std::setfill('0') << sz <<
128+
" 0x" << used << std::endl;
129+
}
137130
void Arena::walk() const
138131
{
139-
for (const auto& chunk: chunks) {
140-
std::cout <<
141-
"0x" << std::hex << std::setw(16) << std::setfill('0') << chunk.first <<
142-
" 0x" << std::hex << std::setw(16) << std::setfill('0') << chunk.second.getSize() <<
143-
" 0x" << chunk.second.isInUse() << std::endl;
144-
}
132+
for (const auto& chunk: chunks_used)
133+
printchunk(chunk.first, chunk.second, true);
134+
std::cout << std::endl;
135+
for (const auto& chunk: chunks_free)
136+
printchunk(chunk.first, chunk.second, false);
145137
std::cout << std::endl;
146138
}
147139
#endif
@@ -312,9 +304,7 @@ void LockedPool::free(void *ptr)
312304
LockedPool::Stats LockedPool::stats() const
313305
{
314306
std::lock_guard<std::mutex> lock(mutex);
315-
LockedPool::Stats r;
316-
r.used = r.free = r.total = r.chunks_used = r.chunks_free = 0;
317-
r.locked = cumulative_bytes_locked;
307+
LockedPool::Stats r{0, 0, 0, cumulative_bytes_locked, 0, 0};
318308
for (const auto &arena: arenas) {
319309
Arena::Stats i = arena.stats();
320310
r.used += i.used;

‎src/support/lockedpool.h‎

Lines changed: 2 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -50,27 +50,6 @@ class Arena
5050
Arena(void *base, size_t size, size_t alignment);
5151
virtual ~Arena();
5252

53-
/** A chunk of memory.
54-
*/
55-
struct Chunk
56-
{
57-
/** Most significant bit of size_t. This is used to mark
58-
* in-usedness of chunk.
59-
*/
60-
const static size_t SIZE_MSB = 1LLU << ((sizeof(size_t)*8)-1);
61-
/** Maximum size of a chunk */
62-
const static size_t MAX_SIZE = SIZE_MSB - 1;
63-
64-
Chunk(size_t size_in, bool used_in):
65-
size(size_in | (used_in ? SIZE_MSB : 0)) {}
66-
67-
bool isInUse() const { return size & SIZE_MSB; }
68-
void setInUse(bool used_in) { size = (size & ~SIZE_MSB) | (used_in ? SIZE_MSB : 0); }
69-
size_t getSize() const { return size & ~SIZE_MSB; }
70-
void setSize(size_t size_in) { size = (size & SIZE_MSB) | size_in; }
71-
private:
72-
size_t size;
73-
};
7453
/** Memory statistics. */
7554
struct Stats
7655
{
@@ -112,7 +91,8 @@ class Arena
11291
/** Map of chunk address to chunk information. This class makes use of the
11392
* sorted order to merge previous and next chunks during deallocation.
11493
*/
115-
std::map<char*, Chunk> chunks;
94+
std::map<char*, size_t> chunks_free;
95+
std::map<char*, size_t> chunks_used;
11696
/** Base address of arena */
11797
char* base;
11898
/** End address of arena */

‎src/test/allocator_tests.cpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,6 @@ BOOST_AUTO_TEST_CASE(arena_tests)
3939
}
4040

4141
void *a0 = b.alloc(128);
42-
BOOST_CHECK(a0 == synth_base); // first allocation must start at beginning
4342
void *a1 = b.alloc(256);
4443
void *a2 = b.alloc(512);
4544
BOOST_CHECK(b.stats().used == 896);
@@ -63,8 +62,10 @@ BOOST_AUTO_TEST_CASE(arena_tests)
6362
BOOST_CHECK(b.stats().used == 128);
6463
b.free(a3);
6564
BOOST_CHECK(b.stats().used == 0);
65+
BOOST_CHECK_EQUAL(b.stats().chunks_used, 0);
6666
BOOST_CHECK(b.stats().total == synth_size);
6767
BOOST_CHECK(b.stats().free == synth_size);
68+
BOOST_CHECK_EQUAL(b.stats().chunks_free, 1);
6869

6970
std::vector<void*> addr;
7071
BOOST_CHECK(b.alloc(0) == nullptr); // allocating 0 always returns nullptr
@@ -74,7 +75,6 @@ BOOST_AUTO_TEST_CASE(arena_tests)
7475
// Sweeping allocate all memory
7576
for (int x=0; x<1024; ++x)
7677
addr.push_back(b.alloc(1024));
77-
BOOST_CHECK(addr[0] == synth_base); // first allocation must start at beginning
7878
BOOST_CHECK(b.stats().free == 0);
7979
BOOST_CHECK(b.alloc(1024) == nullptr); // memory is full, this must return nullptr
8080
BOOST_CHECK(b.alloc(0) == nullptr);

0 commit comments

Comments
 (0)