Replace hashing function for string keys implementation with xxhash
[ghc.git] / rts / RetainerSet.h
1 /* -----------------------------------------------------------------------------
2 *
3 * (c) The GHC Team, 2001
4 * Author: Sungwoo Park
5 *
6 * Retainer set interface for retainer profiling.
7 *
8 * ---------------------------------------------------------------------------*/
9
10 #pragma once
11
12 #include <stdio.h>
13
14 #if defined(PROFILING)
15
16 #include "BeginPrivate.h"
17
18 /*
19 Type 'retainer' defines the retainer identity.
20
21 Invariant:
22 1. The retainer identity of a given retainer cannot change during
23 program execution, no matter where it is actually stored.
24 For instance, the memory address of a retainer cannot be used as
25 its retainer identity because its location may change during garbage
26 collections.
27 2. Type 'retainer' must come with comparison operations as well as
28 an equality operation. That it, <, >, and == must be supported -
29 this is necessary to store retainers in a sorted order in retainer sets.
30 Therefore, you cannot use a huge structure type as 'retainer', for instance.
31
32 We illustrate three possibilities of defining 'retainer identity'.
33 Choose one of the following three compiler directives:
34
35 Retainer scheme 1 (RETAINER_SCHEME_INFO) : retainer = info table
36 Retainer scheme 2 (RETAINER_SCHEME_CCS) : retainer = cost centre stack
37 Retainer scheme 3 (RETAINER_SCHEME_CC) : retainer = cost centre
38 */
39
40 // #define RETAINER_SCHEME_INFO
41 #define RETAINER_SCHEME_CCS
42 // #define RETAINER_SCHEME_CC
43
44 #if defined(RETAINER_SCHEME_INFO)
45 struct _StgInfoTable;
46 typedef struct _StgInfoTable *retainer;
47 #endif
48
49 #if defined(RETAINER_SCHEME_CCS)
50 typedef CostCentreStack *retainer;
51 #endif
52
53 #if defined(RETAINER_SCHEME_CC)
54 typedef CostCentre *retainer;
55 #endif
56
57 /*
58 Type 'retainerSet' defines an abstract datatype for sets of retainers.
59
60 Invariants:
61 A retainer set stores its elements in increasing order (in element[] array).
62 */
63
64 typedef struct _RetainerSet {
65 uint32_t num; // number of elements
66 StgWord hashKey; // hash key for this retainer set
67 struct _RetainerSet *link; // link to the next retainer set in the bucket
68 int id; // unique id of this retainer set (used when printing)
69 // Its absolute value is interpreted as its true id; if id is
70 // negative, it indicates that this retainer set has had a positive
71 // cost after some retainer profiling.
72 retainer element[0]; // elements of this retainer set
73 // do not put anything below here!
74 } RetainerSet;
75
76 /*
77 Note:
78 There are two ways of maintaining all retainer sets. The first is simply by
79 freeing all the retainer sets and re-initialize the hash table at each
80 retainer profiling. The second is by setting the cost field of each
81 retainer set. The second is preferred to the first if most retainer sets
82 are likely to be observed again during the next retainer profiling. Note
83 that in the first approach, we do not free the memory allocated for
84 retainer sets; we just invalidate all retainer sets.
85 */
86 #if defined(DEBUG_RETAINER)
87 // In thise case, FIRST_APPROACH must be turned on because the memory pool
88 // for retainer sets is freed each time.
89 #define FIRST_APPROACH
90 #else
91 // #define FIRST_APPROACH
92 #define SECOND_APPROACH
93 #endif
94
95 // Creates the first pool and initializes a hash table. Frees all pools if any.
96 void initializeAllRetainerSet(void);
97
98 // Refreshes all pools for reuse and initializes a hash table.
99 void refreshAllRetainerSet(void);
100
101 // Frees all pools.
102 void closeAllRetainerSet(void);
103
104 // Finds or creates if needed a singleton retainer set.
105 RetainerSet *singleton(retainer r);
106
107 extern RetainerSet rs_MANY;
108
109 // Checks if a given retainer is a member of the retainer set.
110 //
111 // Note & (maybe) Todo:
112 // This function needs to be declared as an inline function, so it is declared
113 // as an inline static function here.
114 // This make the interface really bad, but isMember() returns a value, so
115 // it is not easy either to write it as a macro (due to my lack of C
116 // programming experience). Sungwoo
117 //
118 // bool isMember(retainer, retainerSet *);
119 /*
120 Returns true if r is a member of *rs.
121 Invariants:
122 rs is not NULL.
123 Note:
124 The efficiency of this function is subject to the typical size of
125 retainer sets. If it is small, linear scan is better. If it
126 is large in most cases, binary scan is better.
127 The current implementation mixes the two search strategies.
128 */
129
130 #define BINARY_SEARCH_THRESHOLD 8
131 INLINE_HEADER bool
132 isMember(retainer r, RetainerSet *rs)
133 {
134 int i, left, right; // must be int, not uint32_t (because -1 can appear)
135 retainer ri;
136
137 if (rs == &rs_MANY) { return true; }
138
139 if (rs->num < BINARY_SEARCH_THRESHOLD) {
140 for (i = 0; i < (int)rs->num; i++) {
141 ri = rs->element[i];
142 if (r == ri) return true;
143 else if (r < ri) return false;
144 }
145 } else {
146 left = 0;
147 right = rs->num - 1;
148 while (left <= right) {
149 i = (left + right) / 2;
150 ri = rs->element[i];
151 if (r == ri) return true;
152 else if (r < ri) right = i - 1;
153 else left = i + 1;
154 }
155 }
156 return false;
157 }
158
159 // Finds or creates a retainer set augmented with a new retainer.
160 RetainerSet *addElement(retainer, RetainerSet *);
161
162 #if defined(SECOND_APPROACH)
163 // Prints a single retainer set.
164 void printRetainerSetShort(FILE *, RetainerSet *, uint32_t);
165 #endif
166
167 // Print the statistics on all the retainer sets.
168 // store the sum of all costs and the number of all retainer sets.
169 void outputRetainerSet(FILE *, uint32_t *, uint32_t *);
170
171 #if defined(SECOND_APPROACH)
172 // Print all retainer sets at the exit of the program.
173 void outputAllRetainerSet(FILE *);
174 #endif
175
176 // Hashing functions
177 /*
178 Invariants:
179 Once either initializeAllRetainerSet() or refreshAllRetainerSet()
180 is called, there exists only one copy of any retainer set created
181 through singleton() and addElement(). The pool (the storage for
182 retainer sets) is consumed linearly. All the retainer sets of the
183 same hash function value are linked together from an element in
184 hashTable[]. See the invariants of allocateInPool() for the
185 maximum size of retainer sets. The hashing function is defined by
186 hashKeySingleton() and hashKeyAddElement(). The hash key for a set
187 must be unique regardless of the order its elements are inserted,
188 i.e., the hashing function must be additive(?).
189 */
190 #define hashKeySingleton(r) ((StgWord)(r))
191 #define hashKeyAddElement(r, s) (hashKeySingleton((r)) + (s)->hashKey)
192
193 #include "EndPrivate.h"
194
195 #endif /* PROFILING */