pooled_map.h 8.75 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you 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.
gejun's avatar
gejun committed
17

gejun's avatar
gejun committed
18 19
// Date: Sat Dec  3 13:11:32 CST 2016

20 21
#ifndef BUTIL_POOLED_MAP_H
#define BUTIL_POOLED_MAP_H
gejun's avatar
gejun committed
22

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

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

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

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

// [ value = 8 bytes ]
66 67 68 69 70 71
// 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
72
// [ value = 32 bytes ]
73 74 75 76 77 78
// 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
79
// [ value = 128 bytes ]
80 81 82 83 84 85
// 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
86 87 88 89

template <typename K, typename V, size_t BLOCK_SIZE = 512,
          typename C = std::less<K> >
class PooledMap
90
    : public std::map<K, V, C, details::PooledAllocator<std::pair<const K, V>, BLOCK_SIZE> > {
gejun's avatar
gejun committed
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
    
};

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.
zjbztianya's avatar
zjbztianya committed
133 134
    pointer address(reference r) const { return &r; }
    const_pointer address(const_reference r) const { return &r; }
gejun's avatar
gejun committed
135 136 137 138 139 140 141 142

    // 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));
        }
zjbztianya's avatar
zjbztianya committed
143
    }
gejun's avatar
gejun committed
144 145 146 147 148 149 150 151

    // 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);
        }
zjbztianya's avatar
zjbztianya committed
152
    }
gejun's avatar
gejun committed
153 154

    // Return the largest possible storage available through a call to allocate.
zjbztianya's avatar
zjbztianya committed
155
    size_type max_size() const { return 0xFFFFFFFF / sizeof(T1); }
gejun's avatar
gejun committed
156

zjbztianya's avatar
zjbztianya committed
157 158
    void construct(pointer ptr) { ::new (ptr) T1; }
    void construct(pointer ptr, const T1& val) { ::new (ptr) T1(val); }
gejun's avatar
gejun committed
159 160 161
    template <class U1> void construct(pointer ptr, const U1& val)
    { ::new (ptr) T1(val); }

zjbztianya's avatar
zjbztianya committed
162
    void destroy(pointer p) { p->T1::~T1(); }
gejun's avatar
gejun committed
163 164

private:
165
    butil::SingleThreadedPool<sizeof(T1), BLOCK_SIZE, 1> _pool;
gejun's avatar
gejun committed
166 167 168 169 170 171
};

// 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>&)
zjbztianya's avatar
zjbztianya committed
172
{ return false; }
gejun's avatar
gejun committed
173 174
template <typename T1, size_t S1, typename T2, size_t S2>
bool operator!=(const PooledAllocator<T1, S1>& a, const PooledAllocator<T2, S2>& b)
zjbztianya's avatar
zjbztianya committed
175
{ return !(a == b); }
gejun's avatar
gejun committed
176 177

} // namespace details
178
} // namespace butil
gejun's avatar
gejun committed
179 180 181

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

196
#endif  // BUTIL_POOLED_MAP_H