RetainerSet.h 5.76 KB
Newer Older
1 2 3 4 5 6 7 8 9
/* -----------------------------------------------------------------------------
 *
 * (c) The GHC Team, 2001
 * Author: Sungwoo Park
 *
 * Retainer set interface for retainer profiling.
 *
 * ---------------------------------------------------------------------------*/

10
#pragma once
11

12 13
#include <stdio.h>

Ben Gamari's avatar
Ben Gamari committed
14
#if defined(PROFILING)
15

16
#include "BeginPrivate.h"
17

18 19 20 21
/*
  Type 'retainer' defines the retainer identity.

  Invariant:
22
    1. The retainer identity of a given retainer cannot change during
23 24 25 26 27
    program execution, no matter where it is actually stored.
    For instance, the memory address of a retainer cannot be used as
    its retainer identity because its location may change during garbage
    collections.
    2. Type 'retainer' must come with comparison operations as well as
28
    an equality operation. That is, <, >, and == must be supported -
29 30 31 32 33 34 35 36
    this is necessary to store retainers in a sorted order in retainer sets.
    Therefore, you cannot use a huge structure type as 'retainer', for instance.
*/


typedef CostCentreStack *retainer;

/*
37
  Type 'retainerSet' defines an abstract datatype for sets of retainers.
38 39 40 41 42 43

  Invariants:
    A retainer set stores its elements in increasing order (in element[] array).
 */

typedef struct _RetainerSet {
44
  uint32_t num;                 // number of elements
45 46 47 48
  StgWord hashKey;              // hash key for this retainer set
  struct _RetainerSet *link;    // link to the next retainer set in the bucket
  int id;   // unique id of this retainer set (used when printing)
            // Its absolute value is interpreted as its true id; if id is
49
            // negative, it indicates that this retainer set has had a positive
50 51 52 53 54
            // cost after some retainer profiling.
  retainer element[0];          // elements of this retainer set
  // do not put anything below here!
} RetainerSet;

55
/*
56
  Note:
57 58
    There are two ways of maintaining all retainer sets. The first is simply by
    freeing all the retainer sets and re-initialize the hash table at each
59 60 61 62
    retainer profiling. The second is by setting the cost field of each
    retainer set. The second is preferred to the first if most retainer sets
    are likely to be observed again during the next retainer profiling. Note
    that in the first approach, we do not free the memory allocated for
63 64
    retainer sets; we just invalidate all retainer sets.
 */
Ben Gamari's avatar
Ben Gamari committed
65
#if defined(DEBUG_RETAINER)
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
// In thise case, FIRST_APPROACH must be turned on because the memory pool
// for retainer sets is freed each time.
#define FIRST_APPROACH
#else
// #define FIRST_APPROACH
#define SECOND_APPROACH
#endif

// Creates the first pool and initializes a hash table. Frees all pools if any.
void initializeAllRetainerSet(void);

// Refreshes all pools for reuse and initializes a hash table.
void refreshAllRetainerSet(void);

// Frees all pools.
void closeAllRetainerSet(void);

// Finds or creates if needed a singleton retainer set.
RetainerSet *singleton(retainer r);

extern RetainerSet rs_MANY;

Gabor Greif's avatar
Gabor Greif committed
88
// Checks if a given retainer is a member of the retainer set.
89
//
90 91 92 93
// Note & (maybe) Todo:
//   This function needs to be declared as an inline function, so it is declared
//   as an inline static function here.
//   This make the interface really bad, but isMember() returns a value, so
94
//   it is not easy either to write it as a macro (due to my lack of C
95 96
//   programming experience). Sungwoo
//
Ben Gamari's avatar
Ben Gamari committed
97
// bool isMember(retainer, retainerSet *);
98
/*
Ben Gamari's avatar
Ben Gamari committed
99
  Returns true if r is a member of *rs.
100 101 102 103 104
  Invariants:
    rs is not NULL.
  Note:
    The efficiency of this function is subject to the typical size of
    retainer sets. If it is small, linear scan is better. If it
105
    is large in most cases, binary scan is better.
106 107 108 109
    The current implementation mixes the two search strategies.
 */

#define BINARY_SEARCH_THRESHOLD   8
Ben Gamari's avatar
Ben Gamari committed
110
INLINE_HEADER bool
111 112
isMember(retainer r, RetainerSet *rs)
{
113
  int i, left, right;       // must be int, not uint32_t (because -1 can appear)
114 115
  retainer ri;

Ben Gamari's avatar
Ben Gamari committed
116
  if (rs == &rs_MANY) { return true; }
117 118 119 120

  if (rs->num < BINARY_SEARCH_THRESHOLD) {
    for (i = 0; i < (int)rs->num; i++) {
      ri = rs->element[i];
Ben Gamari's avatar
Ben Gamari committed
121 122
      if (r == ri) return true;
      else if (r < ri) return false;
123 124 125 126 127 128 129
    }
  } else {
    left = 0;
    right = rs->num - 1;
    while (left <= right) {
      i = (left + right) / 2;
      ri = rs->element[i];
Ben Gamari's avatar
Ben Gamari committed
130
      if (r == ri) return true;
131 132 133 134
      else if (r < ri) right = i - 1;
      else left = i + 1;
    }
  }
Ben Gamari's avatar
Ben Gamari committed
135
  return false;
136 137 138 139 140
}

// Finds or creates a retainer set augmented with a new retainer.
RetainerSet *addElement(retainer, RetainerSet *);

Ben Gamari's avatar
Ben Gamari committed
141
#if defined(SECOND_APPROACH)
142
// Prints a single retainer set.
143
void printRetainerSetShort(FILE *, RetainerSet *, W_, uint32_t);
144 145 146
#endif

// Print the statistics on all the retainer sets.
147
// store the sum of all costs and the number of all retainer sets.
148
void outputRetainerSet(FILE *, uint32_t *, uint32_t *);
149

Ben Gamari's avatar
Ben Gamari committed
150
#if defined(SECOND_APPROACH)
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
// Print all retainer sets at the exit of the program.
void outputAllRetainerSet(FILE *);
#endif

// Hashing functions
/*
  Invariants:
    Once either initializeAllRetainerSet() or refreshAllRetainerSet()
    is called, there exists only one copy of any retainer set created
    through singleton() and addElement().  The pool (the storage for
    retainer sets) is consumed linearly.  All the retainer sets of the
    same hash function value are linked together from an element in
    hashTable[].  See the invariants of allocateInPool() for the
    maximum size of retainer sets.  The hashing function is defined by
    hashKeySingleton() and hashKeyAddElement(). The hash key for a set
    must be unique regardless of the order its elements are inserted,
    i.e., the hashing function must be additive(?).
*/
#define hashKeySingleton(r)       ((StgWord)(r))
#define hashKeyAddElement(r, s)   (hashKeySingleton((r)) + (s)->hashKey)

172
#include "EndPrivate.h"
173

174
#endif /* PROFILING */