1 // -*- C++ -*- 2 // 3 // Copyright (C) 2009-2018 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 // 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License along 21 // with this library; see the file COPYING3. If not see 22 // <http://www.gnu.org/licenses/>. 23 24 /** @file profile/impl/profiler_map_to_unordered_map.h 25 * @brief Diagnostics for map to unordered_map. 26 */ 27 28 // Written by Silvius Rus. 29 30 #ifndef _GLIBCXX_PROFILE_PROFILER_MAP_TO_UNORDERED_MAP_H 31 #define _GLIBCXX_PROFILE_PROFILER_MAP_TO_UNORDERED_MAP_H 1 32 33 #include "profile/impl/profiler.h" 34 #include "profile/impl/profiler_node.h" 35 #include "profile/impl/profiler_trace.h" 36 37 namespace __gnu_profile 38 { 39 inline int 40 __log2(std::size_t __size) 41 { 42 for (int __bit_count = sizeof(std::size_t) - 1; __bit_count >= 0; 43 -- __bit_count) 44 if ((2 << __bit_count) & __size) 45 return __bit_count; 46 return 0; 47 } 48 49 inline float 50 __map_insert_cost(std::size_t __size) 51 { return (_GLIBCXX_PROFILE_DATA(__map_insert_cost_factor).__value 52 * static_cast<float>(__log2(__size))); } 53 54 inline float 55 __map_erase_cost(std::size_t __size) 56 { return (_GLIBCXX_PROFILE_DATA(__map_erase_cost_factor).__value 57 * static_cast<float>(__log2(__size))); } 58 59 inline float 60 __map_find_cost(std::size_t __size) 61 { return (_GLIBCXX_PROFILE_DATA(__map_find_cost_factor).__value 62 * static_cast<float>(__log2(__size))); } 63 64 /** @brief A map-to-unordered_map instrumentation line in the 65 object table. */ 66 class __map2umap_info 67 : public __object_info_base 68 { 69 public: 70 __map2umap_info(__stack_t __stack) 71 : __object_info_base(__stack), _M_insert(0), _M_erase(0), _M_find(0), 72 _M_iterate(0), _M_umap_cost(0.0), _M_map_cost(0.0) 73 { } 74 75 void 76 __merge(const __map2umap_info& __o) 77 { 78 __object_info_base::__merge(__o); 79 _M_insert += __o._M_insert; 80 _M_erase += __o._M_erase; 81 _M_find += __o._M_find; 82 _M_iterate += __o._M_iterate; 83 _M_umap_cost += __o._M_umap_cost; 84 _M_map_cost += __o._M_map_cost; 85 } 86 87 void 88 __write(FILE* __f) const 89 { 90 std::fprintf(__f, "%Zu %Zu %Zu %Zu %.0f %.0f\n", 91 _M_insert, _M_erase, _M_find, _M_iterate, _M_map_cost, 92 _M_umap_cost); 93 } 94 95 float 96 __magnitude() const 97 { return _M_map_cost - _M_umap_cost; } 98 99 std::string 100 __advice() const 101 { return "prefer an unordered container"; } 102 103 void 104 __record_insert(std::size_t __size, std::size_t __count) 105 { 106 ++_M_insert; 107 if (__count) 108 { 109 _M_map_cost += __count * __map_insert_cost(__size); 110 _M_umap_cost 111 += (__count 112 * _GLIBCXX_PROFILE_DATA(__umap_insert_cost_factor).__value); 113 } 114 } 115 116 void 117 __record_erase(std::size_t __size, std::size_t __count) 118 { 119 ++_M_erase; 120 if (__count) 121 { 122 _M_map_cost += __count * __map_erase_cost(__size); 123 _M_umap_cost 124 += (__count 125 * _GLIBCXX_PROFILE_DATA(__umap_erase_cost_factor).__value); 126 } 127 } 128 129 void 130 __record_find(std::size_t __size) 131 { 132 ++_M_find; 133 _M_map_cost += __map_find_cost(__size); 134 _M_umap_cost += _GLIBCXX_PROFILE_DATA(__umap_find_cost_factor).__value; 135 } 136 137 void 138 __record_iterate(int __count) 139 { __gnu_cxx::__atomic_add(&_M_iterate, __count); } 140 141 void 142 __set_iterate_costs() 143 { 144 _M_umap_cost 145 += (_M_iterate 146 * _GLIBCXX_PROFILE_DATA(__umap_iterate_cost_factor).__value); 147 _M_map_cost 148 += (_M_iterate 149 * _GLIBCXX_PROFILE_DATA(__map_iterate_cost_factor).__value); 150 } 151 152 private: 153 std::size_t _M_insert; 154 std::size_t _M_erase; 155 std::size_t _M_find; 156 mutable _Atomic_word _M_iterate; 157 float _M_umap_cost; 158 float _M_map_cost; 159 }; 160 161 162 /** @brief A map-to-unordered_map instrumentation line in the 163 stack table. */ 164 class __map2umap_stack_info 165 : public __map2umap_info 166 { 167 public: 168 __map2umap_stack_info(const __map2umap_info& __o) 169 : __map2umap_info(__o) { } 170 }; 171 172 /** @brief Map-to-unordered_map instrumentation producer. */ 173 class __trace_map2umap 174 : public __trace_base<__map2umap_info, __map2umap_stack_info> 175 { 176 public: 177 __trace_map2umap() 178 : __trace_base<__map2umap_info, __map2umap_stack_info>() 179 { __id = "ordered-to-unordered"; } 180 181 // Call at destruction/clean to set container final size. 182 void 183 __destruct(__map2umap_info* __obj_info) 184 { 185 __obj_info->__set_iterate_costs(); 186 __retire_object(__obj_info); 187 } 188 }; 189 190 inline void 191 __trace_map_to_unordered_map_init() 192 { _GLIBCXX_PROFILE_DATA(_S_map2umap) = new __trace_map2umap(); } 193 194 inline void 195 __trace_map_to_unordered_map_free() 196 { delete _GLIBCXX_PROFILE_DATA(_S_map2umap); } 197 198 inline void 199 __trace_map_to_unordered_map_report(FILE* __f, 200 __warning_vector_t& __warnings) 201 { __trace_report(_GLIBCXX_PROFILE_DATA(_S_map2umap), __f, __warnings); } 202 203 inline __map2umap_info* 204 __trace_map_to_unordered_map_construct() 205 { 206 if (!__profcxx_init()) 207 return 0; 208 209 if (!__reentrance_guard::__get_in()) 210 return 0; 211 212 __reentrance_guard __get_out; 213 return _GLIBCXX_PROFILE_DATA(_S_map2umap)->__add_object(__get_stack()); 214 } 215 216 inline void 217 __trace_map_to_unordered_map_insert(__map2umap_info* __info, 218 std::size_t __size, std::size_t __count) 219 { 220 if (!__info) 221 return; 222 223 __info->__record_insert(__size, __count); 224 } 225 226 inline void 227 __trace_map_to_unordered_map_erase(__map2umap_info* __info, 228 std::size_t __size, std::size_t __count) 229 { 230 if (!__info) 231 return; 232 233 __info->__record_erase(__size, __count); 234 } 235 236 inline void 237 __trace_map_to_unordered_map_find(__map2umap_info* __info, 238 std::size_t __size) 239 { 240 if (!__info) 241 return; 242 243 __info->__record_find(__size); 244 } 245 246 inline void 247 __trace_map_to_unordered_map_iterate(__map2umap_info* __info, 248 int) 249 { 250 if (!__info) 251 return; 252 253 // We only collect if an iteration took place no matter in what side. 254 __info->__record_iterate(1); 255 } 256 257 inline void 258 __trace_map_to_unordered_map_invalidate(__map2umap_info* __info) 259 { 260 if (!__info) 261 return; 262 263 __info->__set_invalid(); 264 } 265 266 inline void 267 __trace_map_to_unordered_map_destruct(__map2umap_info* __info) 268 { 269 if (!__info) 270 return; 271 272 _GLIBCXX_PROFILE_DATA(_S_map2umap)->__destruct(__info); 273 } 274 } // namespace __gnu_profile 275 #endif /* _GLIBCXX_PROFILE_PROFILER_MAP_TO_UNORDERED_MAP_H */ 276