1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <functional>
18 #include <iostream>
19 #include <limits>
20 #include <memory>
21 #include <string>
22 #include <unordered_map>
23 #include <utility>
24
25 #include <folly/container/F14Map.h>
26
27 using namespace std;
28 using namespace folly;
29
30 template <typename T>
31 struct LoggingAlloc {
32 using value_type = T;
33
LoggingAllocLoggingAlloc34 LoggingAlloc() {}
35
36 template <typename A>
LoggingAllocLoggingAlloc37 explicit LoggingAlloc(A&&) {}
38
allocateLoggingAlloc39 T* allocate(std::size_t n) {
40 cout << "allocate " << n << " values, " << n * sizeof(T) << " bytes\n";
41 return std::allocator<T>{}.allocate(n);
42 }
43
deallocateLoggingAlloc44 void deallocate(T* ptr, std::size_t n) {
45 cout << "deallocate " << n << " values, " << n * sizeof(T) << " bytes\n";
46 std::allocator<T>{}.deallocate(ptr, n);
47 }
48
operator ==LoggingAlloc49 bool operator==(LoggingAlloc<T> const&) const { return true; }
operator !=LoggingAlloc50 bool operator!=(LoggingAlloc<T> const&) const { return false; }
51
52 // Everything below here is optional when properly using
53 // allocator_traits, but dense_hash_map doesn't use allocator_traits yet
54
55 using pointer = T*;
56 using const_pointer = T const*;
57 using reference = T&;
58 using const_reference = T const&;
59 using size_type = std::size_t;
60 using difference_type = std::ptrdiff_t;
61
62 template <typename U>
63 struct rebind {
64 using other = LoggingAlloc<U>;
65 };
66
addressLoggingAlloc67 T* address(T& v) const { return &v; }
addressLoggingAlloc68 T const* address(T const& v) const { return &v; }
max_sizeLoggingAlloc69 std::size_t max_size() const {
70 return std::numeric_limits<std::size_t>::max();
71 }
72 };
73
74 template <typename K, typename V, template <typename> class A>
75 using StdUnorderedMapTable = std::unordered_map<
76 K,
77 V,
78 std::hash<K>,
79 std::equal_to<K>,
80 A<std::pair<K const, V>>>;
81
82 template <typename K, typename V, template <typename> class A>
83 using F14ValueMapTable =
84 F14ValueMap<K, V, std::hash<K>, std::equal_to<K>, A<std::pair<K const, V>>>;
85
86 template <typename K, typename V, template <typename> class A>
87 using F14NodeMapTable =
88 F14NodeMap<K, V, std::hash<K>, std::equal_to<K>, A<std::pair<K const, V>>>;
89
90 template <typename K, typename V, template <typename> class A>
91 using F14VectorMapTable = F14VectorMap<
92 K,
93 V,
94 std::hash<K>,
95 std::equal_to<K>,
96 A<std::pair<K const, V>>>;
97
98 template <typename M>
runSingleInsert(std::string const & name)99 void runSingleInsert(std::string const& name) {
100 cout << "----------------------\n";
101 cout << name << "\n";
102 cout << "SIZE = " << sizeof(M) << "\n";
103 cout << "CONSTRUCTING\n";
104 {
105 M map;
106 cout << "INSERTING 1 VALUE\n";
107 typename M::key_type k{};
108 map[k];
109 cout << "DESTROYING\n";
110 }
111 cout << "\n";
112 }
113
114 template <template <typename, typename, template <typename> class> class T>
runSingleInserts(std::string const & name)115 void runSingleInserts(std::string const& name) {
116 runSingleInsert<T<uint64_t, array<char, 8>, LoggingAlloc>>(
117 name + " uint64_t 8");
118 runSingleInsert<T<string, array<char, 8>, LoggingAlloc>>(name + " string 8");
119 runSingleInsert<T<uint64_t, array<char, 128>, LoggingAlloc>>(
120 name + " uint64_t 128");
121 runSingleInsert<T<string, array<char, 128>, LoggingAlloc>>(
122 name + " string 128");
123 }
124
codeSize_find_Std(std::unordered_map<int16_t,float> & m,int16_t k)125 FOLLY_NOINLINE int codeSize_find_Std(
126 std::unordered_map<int16_t, float>& m, int16_t k) {
127 auto i = m.find(k);
128 return i != m.end() ? 1 : 0;
129 }
130
codeSize_find_F14Value(F14ValueMap<int16_t,float> & m,int16_t k)131 FOLLY_NOINLINE int codeSize_find_F14Value(
132 F14ValueMap<int16_t, float>& m, int16_t k) {
133 auto i = m.find(k);
134 return i != m.end() ? 1 : 0;
135 }
136
codeSize_find_F14Node(F14NodeMap<int16_t,float> & m,int16_t k)137 FOLLY_NOINLINE int codeSize_find_F14Node(
138 F14NodeMap<int16_t, float>& m, int16_t k) {
139 auto i = m.find(k);
140 return i != m.end() ? 1 : 0;
141 }
142
codeSize_find_F14Vector(F14VectorMap<int16_t,float> & m,int16_t k)143 FOLLY_NOINLINE int codeSize_find_F14Vector(
144 F14VectorMap<int16_t, float>& m, int16_t k) {
145 auto i = m.find(k);
146 return i != m.end() ? 1 : 0;
147 }
148
codeSize_bracket_Std(std::unordered_map<int16_t,uint32_t> & m,int16_t k,uint32_t v)149 FOLLY_NOINLINE void codeSize_bracket_Std(
150 std::unordered_map<int16_t, uint32_t>& m, int16_t k, uint32_t v) {
151 m[k] = v;
152 }
153
codeSize_bracket_F14Value(F14ValueMap<int16_t,uint32_t> & m,int16_t k,uint32_t v)154 FOLLY_NOINLINE void codeSize_bracket_F14Value(
155 F14ValueMap<int16_t, uint32_t>& m, int16_t k, uint32_t v) {
156 m[k] = v;
157 }
158
codeSize_bracket_F14Node(F14NodeMap<int16_t,uint32_t> & m,int16_t k,uint32_t v)159 FOLLY_NOINLINE void codeSize_bracket_F14Node(
160 F14NodeMap<int16_t, uint32_t>& m, int16_t k, uint32_t v) {
161 m[k] = v;
162 }
163
codeSize_bracket_F14Vector(F14VectorMap<int16_t,uint32_t> & m,int16_t k,uint32_t v)164 FOLLY_NOINLINE void codeSize_bracket_F14Vector(
165 F14VectorMap<int16_t, uint32_t>& m, int16_t k, uint32_t v) {
166 m[k] = v;
167 }
168
codeSize_erase_Std(std::unordered_map<int16_t,uint32_t> & m,std::unordered_map<int16_t,uint32_t>::iterator iter)169 FOLLY_NOINLINE void codeSize_erase_Std(
170 std::unordered_map<int16_t, uint32_t>& m,
171 std::unordered_map<int16_t, uint32_t>::iterator iter) {
172 m.erase(iter);
173 }
174
codeSize_erase_F14Value(F14ValueMap<int16_t,uint32_t> & m,F14ValueMap<int16_t,uint32_t>::iterator iter)175 FOLLY_NOINLINE void codeSize_erase_F14Value(
176 F14ValueMap<int16_t, uint32_t>& m,
177 F14ValueMap<int16_t, uint32_t>::iterator iter) {
178 m.erase(iter);
179 }
180
codeSize_erase_F14Node(F14NodeMap<int16_t,uint32_t> & m,F14NodeMap<int16_t,uint32_t>::iterator iter)181 FOLLY_NOINLINE void codeSize_erase_F14Node(
182 F14NodeMap<int16_t, uint32_t>& m,
183 F14NodeMap<int16_t, uint32_t>::iterator iter) {
184 m.erase(iter);
185 }
186
codeSize_erase_F14Vector(F14VectorMap<int16_t,uint32_t> & m,F14VectorMap<int16_t,uint32_t>::iterator iter)187 FOLLY_NOINLINE void codeSize_erase_F14Vector(
188 F14VectorMap<int16_t, uint32_t>& m,
189 F14VectorMap<int16_t, uint32_t>::iterator iter) {
190 m.erase(iter);
191 }
192
main(int,char **)193 int main(int, char**) {
194 (void)codeSize_find_Std;
195 (void)codeSize_find_F14Value;
196 (void)codeSize_find_F14Node;
197 (void)codeSize_find_F14Vector;
198
199 (void)codeSize_bracket_Std;
200 (void)codeSize_bracket_F14Value;
201 (void)codeSize_bracket_F14Node;
202 (void)codeSize_bracket_F14Vector;
203
204 (void)codeSize_erase_Std;
205 (void)codeSize_erase_F14Value;
206 (void)codeSize_erase_F14Node;
207 (void)codeSize_erase_F14Vector;
208
209 runSingleInserts<StdUnorderedMapTable>("std");
210 runSingleInserts<F14ValueMapTable>("f14value");
211 runSingleInserts<F14NodeMapTable>("f14node");
212 runSingleInserts<F14VectorMapTable>("f14vector");
213
214 return 0;
215 }
216