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 core::collection::hash_collection
  33 import core
  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         # Number of calls of `HashCollection::enlarge`
  59         var en_count = 0
  60         # Total length of hash collections receiver of `HashCollection::enlarge`
  61         var en_tot_length = 0
  62         # Total capacity of hash collections receiver `HashCollection::enlarge`
  63         var en_tot_cap = 0
  64
  65         private fun div(n,d: Int): String
  66         do
  67                 if d == 0 then return "NA"
  68                 return (n.to_f / d.to_f).to_precision(2)
  69         end
  70
  71         # Activate the automatic call of `show_hash_stats` at the end of programs
  72         # If false, you can still manually invoke `show_hash_stats`.
  73         #
  74         # Default: true
  75         var auto_hash_display = true is writable
  76
  77         # Force the display of the current hash statistics
  78         fun show_hash_stats
  79         do
  80                 if gt_count == 0 and st_count == 0 then
  81                         print "~~~No hash statistics~~~"
  82                         return
  83                 end
  84
  85                 print """
  86 ~~~Hash statistics~~~
  87 GET:
  88 number of get and has_key: {{{gt_count}}}
  89 number of collisions: {{{gt_coll}}} ({{{div(gt_coll*100,gt_count)}}}%)
  90 average length of collisions: {{{div(gt_tot_coll,gt_coll)}}}
  91 average length of considered collections: {{{div(gt_tot_length,sys.gt_count)}}}
  92 average capacity of considered collections: {{{div(gt_tot_cap,sys.gt_count)}}} ({{{div(gt_tot_cap*100,gt_tot_length)}}}%)
  93
  94 STORE:
  95 number of stores: {{{st_count}}}
  96 number of collisions: {{{st_coll}}} ({{{div(st_coll*100,st_count)}}}%)
  97 average length of collisions: {{{div(st_tot_coll,st_coll)}}}
  98 average length of considered collections: {{{div(st_tot_length,sys.st_count)}}}
  99 average capacity or considered collections: {{{div(st_tot_cap,sys.st_count)}}} ({{{div(st_tot_cap*100,st_tot_length)}}}%)
 100
 101 ENLARGE:
 102 number of enlarge: {{{en_count}}}
 103 average length of considered collections: {{{div(en_tot_length,sys.en_count)}}}
 104 average capacity or considered collections: {{{div(en_tot_cap,sys.en_count)}}} ({{{div(en_tot_cap*100,en_tot_length)}}}%)
 105 ~~~~~~"""
 106         end
 107
 108         # Reset the hash statistics to 0
 109         fun clear_hash_stats
 110         do
 111                 gt_count = 0
 112                 gt_coll = 0
 113                 gt_tot_coll = 0
 114                 gt_tot_length = 0
 115                 gt_tot_cap = 0
 116
 117                 st_count = 0
 118                 st_coll = 0
 119                 st_tot_coll = 0
 120                 st_tot_length = 0
 121                 st_tot_cap = 0
 122         end
 123
 124         redef fun run do
 125                 super
 126                 if auto_hash_display then show_hash_stats
 127         end
 128 end
 129
 130 redef fun exit(i)
 131 do
 132         if sys.auto_hash_display then sys.show_hash_stats
 133         super
 134 end
 135
 136 redef class HashCollection[K]
 137         redef fun node_at_idx(i,k)
 138         do
 139                 sys.gt_count += 1
 140                 sys.gt_tot_length += _the_length
 141                 sys.gt_tot_cap += _capacity
 142                 var c = _array[i]
 143                 if c != null and c._next_in_bucklet != null then gt_collide(i,k)
 144
 145                 return super
 146         end
 147
 148         redef fun enlarge(c)
 149         do
 150                 super
 151                 sys.en_count += 1
 152                 sys.en_tot_length += _the_length
 153                 sys.en_tot_cap += _capacity
 154         end
 155
 156         # Count and update length of collisions for `node_at_idx`
 157         # Note for dynamic call-graph analysis: callers of this functions are
 158         # responsible of collisions.
 159         fun gt_collide(i: Int, k: K)
 160         do
 161                 var c = _array[i]
 162                 sys.gt_coll += 1
 163                 while c != null do
 164                         sys.gt_tot_coll += 1
 165                         c = c._next_in_bucklet
 166                 end
 167         end
 168
 169         redef fun store(i, n)
 170         do
 171                 sys.st_count += 1
 172                 if _array[i] != null then st_collide(i,n)
 173                 sys.st_tot_length += _the_length
 174                 sys.st_tot_cap += _capacity
 175
 176                 super
 177         end
 178
 179         # Count and update length of collisions for `store`
 180         # Note for dynamic call-graph analysis: callers of this functions are
 181         # responsible of collisions.
 182         fun st_collide(i: Int, n: N)
 183         do
 184                 var c = _array[i]
 185                 sys.st_coll += 1
 186                 sys.st_tot_coll += 1
 187                 while c != null do
 188                         sys.st_tot_coll += 1
 189                         c = c._next_in_bucklet
 190                 end
 191         end
 192 end