diff --git a/contrib/teamcity/build-configurations.sh b/contrib/teamcity/build-configurations.sh
--- a/contrib/teamcity/build-configurations.sh
+++ b/contrib/teamcity/build-configurations.sh
@@ -61,6 +61,7 @@
   build-asan)
     # Build with the address sanitizer, then run unit tests and functional tests.
     CMAKE_FLAGS=(
+      "-DCMAKE_CXX_FLAGS=-DARENA_DEBUG"
       "-DCMAKE_BUILD_TYPE=Debug"
       # ASAN does not support assembly code: https://github.com/google/sanitizers/issues/192
       # This will trigger a segfault if the SSE4 implementation is selected for SHA256.
diff --git a/src/bench/lockedpool.cpp b/src/bench/lockedpool.cpp
--- a/src/bench/lockedpool.cpp
+++ b/src/bench/lockedpool.cpp
@@ -41,4 +41,4 @@
     addr.clear();
 }
 
-BENCHMARK(BenchLockedPool, 530);
+BENCHMARK(BenchLockedPool, 1300);
diff --git a/src/support/lockedpool.h b/src/support/lockedpool.h
--- a/src/support/lockedpool.h
+++ b/src/support/lockedpool.h
@@ -10,6 +10,7 @@
 #include <map>
 #include <memory>
 #include <mutex>
+#include <unordered_map>
 
 /**
  * OS-dependent allocation and deallocation of locked/pinned memory pages.
@@ -92,12 +93,20 @@
     bool addressInArena(void *ptr) const { return ptr >= base && ptr < end; }
 
 private:
-    /**
-     * Map of chunk address to chunk information. This class makes use of the
-     * sorted order to merge previous and next chunks during deallocation.
-     */
-    std::map<char *, size_t> chunks_free;
-    std::map<char *, size_t> chunks_used;
+    typedef std::multimap<size_t, char *> SizeToChunkSortedMap;
+    /** Map to enable O(log(n)) best-fit allocation, as it's sorted by size */
+    SizeToChunkSortedMap size_to_free_chunk;
+
+    typedef std::unordered_map<char *, SizeToChunkSortedMap::const_iterator>
+        ChunkToSizeMap;
+    /** Map from begin of free chunk to its node in size_to_free_chunk */
+    ChunkToSizeMap chunks_free;
+    /** Map from end of free chunk to its node in size_to_free_chunk */
+    ChunkToSizeMap chunks_free_end;
+
+    /** Map from begin of used chunk to its size */
+    std::unordered_map<char *, size_t> chunks_used;
+
     /** Base address of arena */
     char *base;
     /** End address of arena */
diff --git a/src/support/lockedpool.cpp b/src/support/lockedpool.cpp
--- a/src/support/lockedpool.cpp
+++ b/src/support/lockedpool.cpp
@@ -28,6 +28,10 @@
 
 #include <algorithm>
 #include <memory>
+#ifdef ARENA_DEBUG
+#include <iomanip>
+#include <iostream>
+#endif
 
 LockedPoolManager *LockedPoolManager::_instance = nullptr;
 std::once_flag LockedPoolManager::init_flag;
@@ -47,7 +51,9 @@
     : base(static_cast<char *>(base_in)),
       end(static_cast<char *>(base_in) + size_in), alignment(alignment_in) {
     // Start with one free chunk that covers the entire arena
-    chunks_free.emplace(base, size_in);
+    auto it = size_to_free_chunk.emplace(size_in, base);
+    chunks_free.emplace(base, it);
+    chunks_free_end.emplace(base + size_in, it);
 }
 
 Arena::~Arena() {}
@@ -61,33 +67,36 @@
         return nullptr;
     }
 
-    // Pick a large enough free-chunk
-    auto it =
-        std::find_if(chunks_free.begin(), chunks_free.end(),
-                     [=](const std::map<char *, size_t>::value_type &chunk) {
-                         return chunk.second >= size;
-                     });
-    if (it == chunks_free.end()) {
+    // Pick a large enough free-chunk. Returns an iterator pointing to the first
+    // element that is not less than key. This allocation strategy is best-fit.
+    // According to "Dynamic Storage Allocation: A Survey and Critical Review",
+    // Wilson et. al. 1995,
+    // http://www.scs.stanford.edu/14wi-cs140/sched/readings/wilson.pdf,
+    // best-fit and first-fit policies seem to work well in practice.
+    auto size_ptr_it = size_to_free_chunk.lower_bound(size);
+    if (size_ptr_it == size_to_free_chunk.end()) {
         return nullptr;
     }
 
     // Create the used-chunk, taking its space from the end of the free-chunk
+    const size_t size_remaining = size_ptr_it->first - size;
     auto alloced =
-        chunks_used.emplace(it->first + it->second - size, size).first;
-    if (!(it->second -= size)) {
-        chunks_free.erase(it);
+        chunks_used.emplace(size_ptr_it->second + size_remaining, size).first;
+    chunks_free_end.erase(size_ptr_it->second + size_ptr_it->first);
+    if (size_ptr_it->first == size) {
+        // whole chunk is used up
+        chunks_free.erase(size_ptr_it->second);
+    } else {
+        // still some memory left in the chunk
+        auto it_remaining =
+            size_to_free_chunk.emplace(size_remaining, size_ptr_it->second);
+        chunks_free[size_ptr_it->second] = it_remaining;
+        chunks_free_end.emplace(size_ptr_it->second + size_remaining,
+                                it_remaining);
     }
-    return reinterpret_cast<void *>(alloced->first);
-}
+    size_to_free_chunk.erase(size_ptr_it);
 
-/* extend the Iterator if other begins at its end */
-template <class Iterator, class Pair>
-bool extend(Iterator it, const Pair &other) {
-    if (it->first + it->second == other.first) {
-        it->second += other.second;
-        return true;
-    }
-    return false;
+    return reinterpret_cast<void *>(alloced->first);
 }
 
 void Arena::free(void *ptr) {
@@ -101,19 +110,30 @@
     if (i == chunks_used.end()) {
         throw std::runtime_error("Arena: invalid or double free");
     }
-    auto freed = *i;
+    std::pair<char *, size_t> freed = *i;
     chunks_used.erase(i);
 
-    // Add space to free map, coalescing contiguous chunks
-    auto next = chunks_free.upper_bound(freed.first);
-    auto prev =
-        (next == chunks_free.begin()) ? chunks_free.end() : std::prev(next);
-    if (prev == chunks_free.end() || !extend(prev, freed)) {
-        prev = chunks_free.emplace_hint(next, freed);
+    // coalesce freed with previous chunk
+    auto prev = chunks_free_end.find(freed.first);
+    if (prev != chunks_free_end.end()) {
+        freed.first -= prev->second->first;
+        freed.second += prev->second->first;
+        size_to_free_chunk.erase(prev->second);
+        chunks_free_end.erase(prev);
     }
-    if (next != chunks_free.end() && extend(prev, *next)) {
+
+    // coalesce freed with chunk after freed
+    auto next = chunks_free.find(freed.first + freed.second);
+    if (next != chunks_free.end()) {
+        freed.second += next->second->first;
+        size_to_free_chunk.erase(next->second);
         chunks_free.erase(next);
     }
+
+    // Add/set space with coalesced free chunk
+    auto it = size_to_free_chunk.emplace(freed.second, freed.first);
+    chunks_free[freed.first] = it;
+    chunks_free_end[freed.first + freed.second] = it;
 }
 
 Arena::Stats Arena::stats() const {
@@ -122,14 +142,14 @@
         r.used += chunk.second;
     }
     for (const auto &chunk : chunks_free) {
-        r.free += chunk.second;
+        r.free += chunk.second->first;
     }
     r.total = r.used + r.free;
     return r;
 }
 
 #ifdef ARENA_DEBUG
-static void printchunk(char *base, size_t sz, bool used) {
+static void printchunk(void *base, size_t sz, bool used) {
     std::cout << "0x" << std::hex << std::setw(16) << std::setfill('0') << base
               << " 0x" << std::hex << std::setw(16) << std::setfill('0') << sz
               << " 0x" << used << std::endl;
@@ -140,7 +160,7 @@
     }
     std::cout << std::endl;
     for (const auto &chunk : chunks_free) {
-        printchunk(chunk.first, chunk.second, false);
+        printchunk(chunk.first, chunk.second->first, false);
     }
     std::cout << std::endl;
 }