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 core
::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 # Number of calls of `HashCollection::enlarge`
60 # Total length of hash collections receiver of `HashCollection::enlarge`
62 # Total capacity of hash collections receiver `HashCollection::enlarge`
65 private fun div
(n
,d
: Int): String
67 if d
== 0 then return "NA"
68 return (n
.to_f
/ d
.to_f
).to_precision
(2)
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`.
75 var auto_hash_display
= true is writable
77 # Force the display of the current hash statistics
80 if gt_count
== 0 and st_count
== 0 then
81 print
"~~~No hash statistics~~~"
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)}}}%)
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)}}}%)
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)}}}%)
108 # Reset the hash statistics to 0
126 if auto_hash_display
then show_hash_stats
132 if sys
.auto_hash_display
then sys
.show_hash_stats
136 redef class HashCollection[K
]
137 redef fun node_at_idx
(i
,k
)
140 sys
.gt_tot_length
+= _the_length
141 sys
.gt_tot_cap
+= _capacity
143 if c
!= null and c
._next_in_bucklet
!= null then gt_collide
(i
,k
)
152 sys
.en_tot_length
+= _the_length
153 sys
.en_tot_cap
+= _capacity
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
)
165 c
= c
._next_in_bucklet
169 redef fun store
(i
, n
)
172 if _array
[i
] != null then st_collide
(i
,n
)
173 sys
.st_tot_length
+= _the_length
174 sys
.st_tot_cap
+= _capacity
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
)
189 c
= c
._next_in_bucklet