pooled_map.h 8.58 KB
Newer Older
gejun's avatar
gejun committed
1
// Copyright (c) 2016 Baidu, Inc.
gejun's avatar
gejun committed
2 3 4 5 6 7
// 
// 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
gejun's avatar
gejun committed
8
// 
gejun's avatar
gejun committed
9 10 11 12 13 14 15
// 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)
gejun's avatar
gejun committed
16 17
// Date: Sat Dec  3 13:11:32 CST 2016

18 19
#ifndef BUTIL_POOLED_MAP_H
#define BUTIL_POOLED_MAP_H
gejun's avatar
gejun committed
20

21
#include "butil/single_threaded_pool.h"
gejun's avatar
gejun committed
22 23 24
#include <new>
#include <map>

25
namespace butil {
gejun's avatar
gejun committed
26 27 28 29
namespace details {
template <class T1, size_t BLOCK_SIZE> class PooledAllocator;
}

gejun's avatar
gejun committed
30 31
// A drop-in replacement for std::map to improve insert/erase performance slightly
//
gejun's avatar
gejun committed
32 33 34 35 36 37
// 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
38
//   100 elements, you should use butil::FlatMap instead.
gejun's avatar
gejun committed
39 40 41

// insert/erase comparisons between several maps:
// [ value = 8 bytes ]
42 43 44 45 46 47
// 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
gejun's avatar
gejun committed
48
// [ value = 32 bytes ]
49 50 51 52 53 54
// 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
gejun's avatar
gejun committed
55
// [ value = 128 bytes ]
56 57 58 59 60 61
// 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
gejun's avatar
gejun committed
62 63

// [ value = 8 bytes ]
64 65 66 67 68 69
// 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
gejun's avatar
gejun committed
70
// [ value = 32 bytes ]
71 72 73 74 75 76
// 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
gejun's avatar
gejun committed
77
// [ value = 128 bytes ]
78 79 80 81 82 83
// 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
gejun's avatar
gejun committed
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

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:
163
    butil::SingleThreadedPool<sizeof(T1), BLOCK_SIZE, 1> _pool;
gejun's avatar
gejun committed
164 165 166 167 168 169 170 171 172 173 174 175
};

// 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
176
} // namespace butil
gejun's avatar
gejun committed
177 178 179

// Since this allocator can't be exchanged(check impl. of operator==) nor
// copied, specializing swap() is a must to make map.swap() work.
180
#if !defined(BUTIL_CXX11_ENABLED)
gejun's avatar
gejun committed
181 182 183 184 185 186 187
#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>
188 189
inline void swap(::butil::details::PooledAllocator<T1, BLOCK_SIZE> &lhs,
                 ::butil::details::PooledAllocator<T1, BLOCK_SIZE> &rhs){
gejun's avatar
gejun committed
190 191 192 193
    lhs.swap(rhs);
}
}  // namespace std

194
#endif  // BUTIL_POOLED_MAP_H