1 # This file is part of NIT ( http://www.nitlanguage.org ).
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
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.
15 # This module helps to detect, and track bad behavior on hash-collections,
16 # especially collisions.
20 # 1. compile your program with `-m hash_debug`
21 # 2. execute your program.
25 # import this module and use the functions `Sys::show_hash_stats` and
26 # `Sys::clear_hash_stats` at strategic points.
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`.
32 intrude import standard
::collection
::hash_collection
36 # Number of calls of `HashCollection::node_at_idx`
38 # Number of calls of `HashCollection::node_at_idx` that collided
40 # Total length of collisions on calls of `HashCollection::node_at_idx` that collided
42 # Total length of hash collections receiver of `HashCollection::node_at_idx`
44 # Total capacity of hash collections receiver `HashCollection::node_at_idx`
47 # Number of calls of `HashCollection::store`
49 # Number of calls of `HashCollection::store` that collided
51 # Total length of collisions on calls of `HashCollection::store` that collided
53 # Total length of hash collections receiver of `HashCollection::store`
55 # Total capacity of hash collections receiver `HashCollection::store`
58 private fun div
(n
,d
: Int): String
60 if d
== 0 then return "NA"
61 return (n
.to_f
/ d
.to_f
).to_precision
(2)
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`.
68 var auto_hash_display
= true is writable
70 # Force the display of the current hash statistics
73 if gt_count
== 0 and st_count
== 0 then
74 print
"~~~No hash statistics~~~"
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)}}}%)
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)}}}%)
96 # Reset the hash statistics to 0
114 if auto_hash_display
then show_hash_stats
120 if sys
.auto_hash_display
then sys
.show_hash_stats
124 redef class HashCollection[K
]
125 redef fun node_at_idx
(i
,k
)
128 sys
.gt_tot_length
+= _the_length
129 sys
.gt_tot_cap
+= _capacity
131 if c
!= null and c
._next_in_bucklet
!= null then gt_collide
(i
,k
)
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 private fun gt_collide
(i
: Int, k
: K
)
145 c
= c
._next_in_bucklet
149 redef fun store
(i
, n
)
152 if _array
[i
] != null then st_collide
(i
,n
)
153 sys
.st_tot_length
+= _the_length
154 sys
.st_tot_cap
+= _capacity
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 private fun st_collide
(i
: Int, n
: N
)
169 c
= c
._next_in_bucklet