libstdc++-v3/include/profile/impl/profiler_map_to_unordered_map.h

   1 // -*- C++ -*-
   2 //
   3 // Copyright (C) 2009 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 terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file profile/impl/profiler_map_to_unordered_map.h
  32  *  @brief Diagnostics for map to unordered_map.
  33  */
  34
  35 // Written by Silvius Rus.
  36
  37 #ifndef PROFCXX_PROFILER_MAP_TO_UNORDERED_MAP_H__
  38 #define PROFCXX_PROFILER_MAP_TO_UNORDERED_MAP_H__ 1
  39
  40 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  41 #include <cstdlib>
  42 #include <cstdio>
  43 #include <cstring>
  44 #else
  45 #include <stdlib.h>
  46 #include <stdio.h>
  47 #include <string.h>
  48 #endif
  49 #include "profile/impl/profiler.h"
  50 #include "profile/impl/profiler_node.h"
  51 #include "profile/impl/profiler_trace.h"
  52
  53 namespace __cxxprof_impl
  54 {
  55
  56 // Cost model. XXX: this must be taken from the machine model instead.
  57 //  Map operations:
  58 //   - insert: 1.5 * log(size)
  59 //   - erase: 1.5 * log(size)
  60 //   - find: log(size)
  61 //   - iterate: 2.3
  62 //  Unordered map operations:
  63 //   - insert: 12
  64 //   - erase: 12
  65 //   - find: 10
  66 //   - iterate: 1.7
  67
  68 const float __map_insert_cost_factor = 1.5;
  69 const float __map_erase_cost_factor = 1.5;
  70 const float __map_find_cost_factor = 1;
  71 const float __map_iterate_cost = 2.3;
  72
  73 const float __umap_insert_cost = 12.0;
  74 const float __umap_erase_cost = 12.0;
  75 const float __umap_find_cost = 10.0;
  76 const float __umap_iterate_cost = 1.7;
  77
  78 inline int __log2(size_t __size)
  79 {
  80   for (int __bit_count = sizeof(size_t) - 1; __bit_count >= 0; --__bit_count) {
  81     if ((2 << __bit_count) & __size) {
  82       return __bit_count;
  83     }
  84   }
  85   return 0;
  86 }
  87
  88 inline float __map_insert_cost(size_t __size)
  89 {
  90   return __map_insert_cost_factor * static_cast<float>(__log2(__size));
  91 }
  92
  93 inline float __map_erase_cost(size_t __size)
  94 {
  95   return __map_erase_cost_factor * static_cast<float>(__log2(__size));
  96 }
  97
  98 inline float __map_find_cost(size_t __size)
  99 {
 100   return __map_find_cost_factor * static_cast<float>(__log2(__size));
 101 }
 102
 103 /** @brief A map-to-unordered_map instrumentation line in the object table.  */
 104 class __map2umap_info: public __object_info_base
 105 {
 106  public:
 107   __map2umap_info()
 108       : _M_insert(0), _M_erase(0), _M_find(0), _M_iterate(0),
 109         _M_map_cost(0.0), _M_umap_cost(0.0), _M_valid(true) {}
 110   __map2umap_info(__stack_t __stack)
 111       : __object_info_base(__stack), _M_insert(0), _M_erase(0), _M_find(0),
 112         _M_iterate(0), _M_map_cost(0.0), _M_umap_cost(0.0), _M_valid(true) {}
 113   virtual ~__map2umap_info() {}
 114   __map2umap_info(const __map2umap_info& o);
 115   void __merge(const __map2umap_info& o);
 116   void __write(FILE* __f) const;
 117   float __magnitude() const { return _M_map_cost - _M_umap_cost; }
 118   const char* __advice() const;
 119
 120   void __record_insert(size_t __size, size_t __count);
 121   void __record_erase(size_t __size, size_t __count);
 122   void __record_find(size_t __size);
 123   void __record_iterate(size_t __count);
 124   void __record_invalidate();
 125
 126  private:
 127   size_t _M_insert;
 128   size_t _M_erase;
 129   size_t _M_find;
 130   size_t _M_iterate;
 131   float _M_umap_cost;
 132   float _M_map_cost;
 133   bool  _M_valid;
 134 };
 135
 136 inline const char* __map2umap_info::__advice() const
 137 {
 138   return "change std::map to std::unordered_map";
 139 }
 140
 141 inline __map2umap_info::__map2umap_info(const __map2umap_info& __o)
 142     : __object_info_base(__o),
 143       _M_insert(__o._M_insert),
 144       _M_erase(__o._M_erase),
 145       _M_find(__o._M_find),
 146       _M_iterate(__o._M_iterate),
 147       _M_map_cost(__o._M_map_cost),
 148       _M_umap_cost(__o._M_umap_cost),
 149       _M_valid(__o._M_valid)
 150 {}
 151
 152 inline void __map2umap_info::__merge(const __map2umap_info& __o)
 153 {
 154   _M_insert    += __o._M_insert;
 155   _M_erase     += __o._M_erase;
 156   _M_find      += __o._M_find;
 157   _M_map_cost  += __o._M_map_cost;
 158   _M_umap_cost += __o._M_umap_cost;
 159   _M_valid     &= __o._M_valid;
 160 }
 161
 162 inline void __map2umap_info:: __record_insert(size_t __size, size_t __count)
 163 {
 164   _M_insert += __count;
 165   _M_map_cost += __count * __map_insert_cost(__size);
 166   _M_umap_cost += __count * __umap_insert_cost;
 167 }
 168
 169 inline void __map2umap_info:: __record_erase(size_t __size, size_t __count)
 170 {
 171   _M_erase += __count;
 172   _M_map_cost += __count * __map_erase_cost(__size);
 173   _M_umap_cost += __count * __umap_erase_cost;
 174 }
 175
 176 inline void __map2umap_info:: __record_find(size_t __size)
 177 {
 178   _M_find += 1;
 179   _M_map_cost += __map_find_cost(__size);
 180   _M_umap_cost += __umap_find_cost;
 181 }
 182
 183 inline void __map2umap_info:: __record_iterate(size_t __count)
 184 {
 185   _M_iterate += __count;
 186   _M_map_cost += __count * __map_iterate_cost;
 187   _M_umap_cost += __count * __umap_iterate_cost;
 188 }
 189
 190 inline void __map2umap_info:: __record_invalidate()
 191 {
 192   _M_valid = false;
 193 }
 194
 195 inline void __map2umap_info::__write(FILE* __f) const
 196 {
 197   fprintf(__f, "%Zu %Zu %Zu %Zu %.0f %.0f %s\n",
 198           _M_insert, _M_erase, _M_find, _M_iterate, _M_map_cost, _M_umap_cost,
 199           _M_valid ? "valid" : "invalid");
 200 }
 201
 202 /** @brief A map-to-unordered_map instrumentation line in the stack table.  */
 203 class __map2umap_stack_info: public __map2umap_info
 204 {
 205  public:
 206   __map2umap_stack_info(const __map2umap_info& o) : __map2umap_info(o) {}
 207 };
 208
 209 /** @brief Map-to-unordered_map instrumentation producer.  */
 210 class __trace_map2umap
 211     : public __trace_base<__map2umap_info, __map2umap_stack_info>
 212 {
 213  public:
 214   __trace_map2umap();
 215 };
 216
 217 inline __trace_map2umap::__trace_map2umap()
 218     : __trace_base<__map2umap_info, __map2umap_stack_info>()
 219 {
 220   __id = "map-to-unordered-map";
 221 }
 222
 223 inline void __trace_map_to_unordered_map_init()
 224 {
 225   __tables<0>::_S_map2umap = new __trace_map2umap();
 226 }
 227
 228 inline void __trace_map_to_unordered_map_report(
 229     FILE* __f, __warning_vector_t& __warnings)
 230 {
 231   if (__tables<0>::_S_map2umap) {
 232     __tables<0>::_S_map2umap->__collect_warnings(__warnings);
 233     __tables<0>::_S_map2umap->__write(__f);
 234   }
 235 }
 236
 237 //////////////////////////////////////////////////////////////////////////////
 238 // Implementations of instrumentation hooks.
 239 //////////////////////////////////////////////////////////////////////////////
 240
 241 inline void __trace_map_to_unordered_map_construct(const void* __obj)
 242 {
 243   if (!__profcxx_init()) return;
 244
 245   __tables<0>::_S_map2umap->__add_object(__obj,
 246                                          __map2umap_info(__get_stack()));
 247 }
 248
 249 inline void __trace_map_to_unordered_map_destruct(const void* __obj)
 250 {
 251   if (!__profcxx_init()) return;
 252
 253   __tables<0>::_S_map2umap->__retire_object(__obj);
 254 }
 255
 256 inline void __trace_map_to_unordered_map_insert(const void* __obj,
 257                                                 size_t __size, size_t __count)
 258 {
 259   if (!__profcxx_init()) return;
 260
 261   __map2umap_info* __info = __tables<0>::_S_map2umap->__get_object_info(__obj);
 262
 263   if (__info) __info->__record_insert(__size, __count);
 264 }
 265
 266 inline void __trace_map_to_unordered_map_erase(const void* __obj,
 267                                                size_t __size, size_t __count)
 268 {
 269   if (!__profcxx_init()) return;
 270
 271   __map2umap_info* __info = __tables<0>::_S_map2umap->__get_object_info(__obj);
 272
 273   if (__info) __info->__record_erase(__size, __count);
 274 }
 275
 276 inline void __trace_map_to_unordered_map_find(const void* __obj, size_t __size)
 277 {
 278   if (!__profcxx_init()) return;
 279
 280   __map2umap_info* __info = __tables<0>::_S_map2umap->__get_object_info(__obj);
 281
 282   if (__info) __info->__record_find(__size);
 283 }
 284
 285 inline void __trace_map_to_unordered_map_iterate(const void* __obj,
 286                                                  size_t __count)
 287 {
 288   if (!__profcxx_init()) return;
 289
 290   __map2umap_info* __info = __tables<0>::_S_map2umap->__get_object_info(__obj);
 291
 292   if (__info) __info->__record_iterate(__count);
 293 }
 294
 295 inline void __trace_map_to_unordered_map_invalidate(const void* __obj)
 296 {
 297   if (!__profcxx_init()) return;
 298
 299   __map2umap_info* __info = __tables<0>::_S_map2umap->__get_object_info(__obj);
 300
 301   if (__info) __info->__record_invalidate();
 302 }
 303
 304 } // namespace __cxxprof_impl
 305 #endif /* PROFCXX_PROFILER_MAP_TO_UNORDERED_MAP_H__ */