lib/hash_debug.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # This file is free software, which comes along with NIT.  This software is
   4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   5 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   6 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   7 # is kept unaltered, and a notification of the changes is added.
   8 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
   9 # another product.
  10
  11 # Inject behavior analysis to hash-collections (HashMap, HashSet, etc.)
  12 # Accesses to hash collections are instrumented, and statistics are
  13 # automatically displayed at the end of the program.
  14 #
  15 # This module helps to detect, and track bad behavior on hash-collections,
  16 # especially collisions.
  17 #
  18 # Simple usage:
  19 #
  20 # 1. compile your program with `-m hash_debug`
  21 # 2. execute your program.
  22 #
  23 # Advanced usage:
  24 #
  25 # import this module and use the functions `Sys::show_hash_stats` and
  26 # `Sys::clear_hash_stats` at strategic points.
  27 #
  28 # You can also use some dynamic call-graph tools (like valgrind) and look
  29 # at callers of `HashCollection::gt_collide` and `HashCollection::st_collide`.
  30 module hash_debug
  31
  32 intrude import standard::collection::hash_collection
  33 import standard
  34
  35 redef class Sys
  36         # Number of calls of `HashCollection::node_at_idx`
  37         var gt_count = 0
  38         # Number of calls of `HashCollection::node_at_idx` that collided
  39         var gt_coll = 0
  40         # Total length of collisions on calls of `HashCollection::node_at_idx` that collided
  41         var gt_tot_coll = 0
  42         # Total length of hash collections receiver of `HashCollection::node_at_idx`
  43         var gt_tot_length = 0
  44         # Total capacity of hash collections receiver `HashCollection::node_at_idx`
  45         var gt_tot_cap = 0
  46
  47         # Number of calls of `HashCollection::store`
  48         var st_count = 0
  49         # Number of calls of `HashCollection::store` that collided
  50         var st_coll = 0
  51         # Total length of collisions on calls of `HashCollection::store` that collided
  52         var st_tot_coll = 0
  53         # Total length of hash collections receiver of `HashCollection::store`
  54         var st_tot_length = 0
  55         # Total capacity of hash collections receiver `HashCollection::store`
  56         var st_tot_cap = 0
  57
  58         private fun div(n,d: Int): String
  59         do
  60                 if d == 0 then return "NA"
  61                 return (n.to_f / d.to_f).to_precision(2)
  62         end
  63
  64         # Activate the automatic call of `show_hash_stats` at the end of programs
  65         # If false, you can still manually invoke `show_hash_stats`.
  66         #
  67         # Default: true
  68         var auto_hash_display = true is writable
  69
  70         # Force the display of the current hash statistics
  71         fun show_hash_stats
  72         do
  73                 if gt_count == 0 and st_count == 0 then
  74                         print "~~~No hash statistics~~~"
  75                         return
  76                 end
  77
  78                 print """
  79 ~~~Hash statistics~~~
  80 GET:
  81 number of get and has_key: {{{gt_count}}}
  82 number of collisions: {{{gt_coll}}} ({{{div(gt_coll*100,gt_count)}}}%)
  83 average length of collisions: {{{div(gt_tot_coll,gt_coll)}}}
  84 average length of considered collections: {{{div(gt_tot_length,sys.gt_count)}}}
  85 average capacity of considered collections: {{{div(gt_tot_cap,sys.gt_count)}}} ({{{div(gt_tot_cap*100,gt_tot_length)}}}%)
  86
  87 STORE:
  88 number of stores: {{{st_count}}}
  89 number of collisions: {{{st_coll}}} ({{{div(st_coll*100,st_count)}}}%)
  90 average length of collisions: {{{div(st_tot_coll,st_coll)}}}
  91 average length of considered collections: {{{div(st_tot_length,sys.st_count)}}}
  92 average capacity or considered collections: {{{div(st_tot_cap,sys.st_count)}}} ({{{div(st_tot_cap*100,st_tot_length)}}}%)
  93 ~~~~~~"""
  94         end
  95
  96         # Reset the hash statistics to 0
  97         fun clear_hash_stats
  98         do
  99                 gt_count = 0
 100                 gt_coll = 0
 101                 gt_tot_coll = 0
 102                 gt_tot_length = 0
 103                 gt_tot_cap = 0
 104
 105                 st_count = 0
 106                 st_coll = 0
 107                 st_tot_coll = 0
 108                 st_tot_length = 0
 109                 st_tot_cap = 0
 110         end
 111
 112         redef fun run do
 113                 super
 114                 if auto_hash_display then show_hash_stats
 115         end
 116 end
 117
 118 redef fun exit(i)
 119 do
 120         if sys.auto_hash_display then sys.show_hash_stats
 121         super
 122 end
 123
 124 redef class HashCollection[K]
 125         redef fun node_at_idx(i,k)
 126         do
 127                 sys.gt_count += 1
 128                 sys.gt_tot_length += _the_length
 129                 sys.gt_tot_cap += _capacity
 130                 var c = _array[i]
 131                 if c != null and c._next_in_bucklet != null then gt_collide(i,k)
 132
 133                 return super
 134         end
 135
 136         # Count and update length of collisions for `node_at_idx`
 137         # Note for dynamic call-graph analysis: callers of this functions are
 138         # responsible of collisions.
 139         fun gt_collide(i: Int, k: K)
 140         do
 141                 var c = _array[i]
 142                 sys.gt_coll += 1
 143                 while c != null do
 144                         sys.gt_tot_coll += 1
 145                         c = c._next_in_bucklet
 146                 end
 147         end
 148
 149         redef fun store(i, n)
 150         do
 151                 sys.st_count += 1
 152                 if _array[i] != null then st_collide(i,n)
 153                 sys.st_tot_length += _the_length
 154                 sys.st_tot_cap += _capacity
 155
 156                 super
 157         end
 158
 159         # Count and update length of collisions for `store`
 160         # Note for dynamic call-graph analysis: callers of this functions are
 161         # responsible of collisions.
 162         fun st_collide(i: Int, n: N)
 163         do
 164                 var c = _array[i]
 165                 sys.st_coll += 1
 166                 sys.st_tot_coll += 1
 167                 while c != null do
 168                         sys.st_tot_coll += 1
 169                         c = c._next_in_bucklet
 170                 end
 171         end
 172 end