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

   1 // -*- C++ -*-
   2 //
   3 // Copyright (C) 2009-2017 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 */