1 /* -----------------------------------------------------------------------------
2 * $Id: RetainerSet.h,v 1.2 2001/11/26 16:54:21 simonmar Exp $
4 * (c) The GHC Team, 2001
7 * Retainer set interface for retainer profiling.
9 * ---------------------------------------------------------------------------*/
17 Type 'retainer' defines the retainer identity.
20 1. The retainer identity of a given retainer cannot change during
21 program execution, no matter where it is actually stored.
22 For instance, the memory address of a retainer cannot be used as
23 its retainer identity because its location may change during garbage
25 2. Type 'retainer' must come with comparison operations as well as
26 an equality operation. That it, <, >, and == must be supported -
27 this is necessary to store retainers in a sorted order in retainer sets.
28 Therefore, you cannot use a huge structure type as 'retainer', for instance.
30 We illustrate three possibilities of defining 'retainer identity'.
31 Choose one of the following three compiler directives:
33 Retainer scheme 1 (RETAINER_SCHEME_INFO) : retainer = info table
34 Retainer scheme 2 (RETAINER_SCHEME_CCS) : retainer = cost centre stack
35 Retainer scheme 3 (RETAINER_SCHEME_CC) : retainer = cost centre
38 // #define RETAINER_SCHEME_INFO
39 #define RETAINER_SCHEME_CCS
40 // #define RETAINER_SCHEME_CC
42 #ifdef RETAINER_SCHEME_INFO
44 typedef struct _StgInfoTable *retainer;
47 #ifdef RETAINER_SCHEME_CCS
48 typedef CostCentreStack *retainer;
51 #ifdef RETAINER_SCHEME_CC
52 typedef CostCentre *retainer;
56 Type 'retainerSet' defines an abstract datatype for sets of retainers.
59 A retainer set stores its elements in increasing order (in element[] array).
62 typedef struct _RetainerSet {
63 nat num; // number of elements
64 StgWord hashKey; // hash key for this retainer set
65 struct _RetainerSet *link; // link to the next retainer set in the bucket
66 int id; // unique id of this retainer set (used when printing)
67 // Its absolute value is interpreted as its true id; if id is
68 // negative, it indicates that this retainer set has had a postive
69 // cost after some retainer profiling.
70 retainer element[0]; // elements of this retainer set
71 // do not put anything below here!
76 There are two ways of maintaining all retainer sets. The first is simply by
77 freeing all the retainer sets and re-initialize the hash table at each
78 retainer profiling. The second is by setting the cost field of each
79 retainer set. The second is preferred to the first if most retainer sets
80 are likely to be observed again during the next retainer profiling. Note
81 that in the first approach, we do not free the memory allocated for
82 retainer sets; we just invalidate all retainer sets.
85 // In thise case, FIRST_APPROACH must be turned on because the memory pool
86 // for retainer sets is freed each time.
87 #define FIRST_APPROACH
89 // #define FIRST_APPROACH
90 #define SECOND_APPROACH
93 // Creates the first pool and initializes a hash table. Frees all pools if any.
94 void initializeAllRetainerSet(void);
96 // Refreshes all pools for reuse and initializes a hash table.
97 void refreshAllRetainerSet(void);
100 void closeAllRetainerSet(void);
102 // Finds or creates if needed a singleton retainer set.
103 RetainerSet *singleton(retainer r);
105 extern RetainerSet rs_MANY;
107 // Checks if a given retainer is a memeber of the retainer set.
109 // Note & (maybe) Todo:
110 // This function needs to be declared as an inline function, so it is declared
111 // as an inline static function here.
112 // This make the interface really bad, but isMember() returns a value, so
113 // it is not easy either to write it as a macro (due to my lack of C
114 // programming experience). Sungwoo
116 // rtsBool isMember(retainer, retainerSet *);
118 Returns rtsTrue if r is a member of *rs.
122 The efficiency of this function is subject to the typical size of
123 retainer sets. If it is small, linear scan is better. If it
124 is large in most cases, binary scan is better.
125 The current implementation mixes the two search strategies.
128 #define BINARY_SEARCH_THRESHOLD 8
129 static inline rtsBool
130 isMember(retainer r, RetainerSet *rs)
132 int i, left, right; // must be int, not nat (because -1 can appear)
135 if (rs == &rs_MANY) { return rtsTrue; }
137 if (rs->num < BINARY_SEARCH_THRESHOLD) {
138 for (i = 0; i < (int)rs->num; i++) {
140 if (r == ri) return rtsTrue;
141 else if (r < ri) return rtsFalse;
146 while (left <= right) {
147 i = (left + right) / 2;
149 if (r == ri) return rtsTrue;
150 else if (r < ri) right = i - 1;
157 // Finds or creates a retainer set augmented with a new retainer.
158 RetainerSet *addElement(retainer, RetainerSet *);
160 // Call f() for each retainer set.
161 void traverseAllRetainerSet(void (*f)(RetainerSet *));
163 #ifdef SECOND_APPROACH
164 // Prints a single retainer set.
165 void printRetainerSetShort(FILE *, RetainerSet *);
168 // Print the statistics on all the retainer sets.
169 // store the sum of all costs and the number of all retainer sets.
170 void outputRetainerSet(FILE *, nat *, nat *);
172 #ifdef SECOND_APPROACH
173 // Print all retainer sets at the exit of the program.
174 void outputAllRetainerSet(FILE *);
180 Once either initializeAllRetainerSet() or refreshAllRetainerSet()
181 is called, there exists only one copy of any retainer set created
182 through singleton() and addElement(). The pool (the storage for
183 retainer sets) is consumed linearly. All the retainer sets of the
184 same hash function value are linked together from an element in
185 hashTable[]. See the invariants of allocateInPool() for the
186 maximum size of retainer sets. The hashing function is defined by
187 hashKeySingleton() and hashKeyAddElement(). The hash key for a set
188 must be unique regardless of the order its elements are inserted,
189 i.e., the hashing function must be additive(?).
191 #define hashKeySingleton(r) ((StgWord)(r))
192 #define hashKeyAddElement(r, s) (hashKeySingleton((r)) + (s)->hashKey)
194 // Prints the full information on a given retainer.
195 // Note: This function is not part of retainerSet interface, but this is
196 // the best place to define it.
197 void printRetainer(FILE *, retainer);
200 #endif // RETAINERSET_H