ghc/rts/RetainerSet.h

   1 /* -----------------------------------------------------------------------------
   2  * $Id: RetainerSet.h,v 1.1 2001/11/22 14:25:12 simonmar Exp $
   3  *
   4  * (c) The GHC Team, 2001
   5  * Author: Sungwoo Park
   6  *
   7  * Retainer set interface for retainer profiling.
   8  *
   9  * ---------------------------------------------------------------------------*/
  10
  11 #ifdef PROFILING
  12
  13 /*
  14   Note:
  15     There are two ways of maintaining all retainer sets. The first is simply by
  16     freeing all the retainer sets and re-initialize the hash table at each
  17     retainer profiling. The second is by setting the cost field of each
  18     retainer set. The second is preferred to the first if most retainer sets
  19     are likely to be observed again during the next retainer profiling. Note
  20     that in the first approach, we do not free the memory allocated for
  21     retainer sets; we just invalidate all retainer sets.
  22  */
  23 #ifdef DEBUG_RETAINER
  24 // In thise case, FIRST_APPROACH must be turned on because the memory pool
  25 // for retainer sets is freed each time.
  26 #define FIRST_APPROACH
  27 #else
  28 // #define FIRST_APPROACH
  29 #define SECOND_APPROACH
  30 #endif
  31
  32 // Creates the first pool and initializes a hash table. Frees all pools if any.
  33 void initializeAllRetainerSet(void);
  34
  35 // Refreshes all pools for reuse and initializes a hash table.
  36 void refreshAllRetainerSet(void);
  37
  38 // Frees all pools.
  39 void closeAllRetainerSet(void);
  40
  41 // Finds or creates if needed a singleton retainer set.
  42 RetainerSet *singleton(retainer r);
  43
  44 extern RetainerSet rs_MANY;
  45
  46 // Checks if a given retainer is a memeber of the retainer set.
  47 //
  48 // Note & (maybe) Todo:
  49 //   This function needs to be declared as an inline function, so it is declared
  50 //   as an inline static function here.
  51 //   This make the interface really bad, but isMember() returns a value, so
  52 //   it is not easy either to write it as a macro (due to my lack of C
  53 //   programming experience). Sungwoo
  54 //
  55 // rtsBool isMember(retainer, retainerSet *);
  56 /*
  57   Returns rtsTrue if r is a member of *rs.
  58   Invariants:
  59     rs is not NULL.
  60   Note:
  61     The efficiency of this function is subject to the typical size of
  62     retainer sets. If it is small, linear scan is better. If it
  63     is large in most cases, binary scan is better.
  64     The current implementation mixes the two search strategies.
  65  */
  66
  67 #define BINARY_SEARCH_THRESHOLD   8
  68 static inline rtsBool
  69 isMember(retainer r, RetainerSet *rs)
  70 {
  71   int i, left, right;       // must be int, not nat (because -1 can appear)
  72   retainer ri;
  73
  74   if (rs == &rs_MANY) { return rtsTrue; }
  75
  76   if (rs->num < BINARY_SEARCH_THRESHOLD) {
  77     for (i = 0; i < (int)rs->num; i++) {
  78       ri = rs->element[i];
  79       if (r == ri) return rtsTrue;
  80       else if (r < ri) return rtsFalse;
  81     }
  82   } else {
  83     left = 0;
  84     right = rs->num - 1;
  85     while (left <= right) {
  86       i = (left + right) / 2;
  87       ri = rs->element[i];
  88       if (r == ri) return rtsTrue;
  89       else if (r < ri) right = i - 1;
  90       else left = i + 1;
  91     }
  92   }
  93   return rtsFalse;
  94 }
  95
  96 // Finds or creates a retainer set augmented with a new retainer.
  97 RetainerSet *addElement(retainer, RetainerSet *);
  98
  99 // Call f() for each retainer set.
 100 void traverseAllRetainerSet(void (*f)(RetainerSet *));
 101
 102 #ifdef SECOND_APPROACH
 103 // Prints a single retainer set.
 104 void printRetainerSetShort(FILE *, RetainerSet *);
 105 #endif
 106
 107 // Print the statistics on all the retainer sets.
 108 // store the sum of all costs and the number of all retainer sets.
 109 void outputRetainerSet(FILE *, nat *, nat *);
 110
 111 #ifdef SECOND_APPROACH
 112 // Print all retainer sets at the exit of the program.
 113 void outputAllRetainerSet(FILE *);
 114 #endif
 115
 116 // Hashing functions
 117 /*
 118   Invariants:
 119     Once either initializeAllRetainerSet() or refreshAllRetainerSet()
 120     is called, there exists only one copy of any retainer set created
 121     through singleton() and addElement().  The pool (the storage for
 122     retainer sets) is consumed linearly.  All the retainer sets of the
 123     same hash function value are linked together from an element in
 124     hashTable[].  See the invariants of allocateInPool() for the
 125     maximum size of retainer sets.  The hashing function is defined by
 126     hashKeySingleton() and hashKeyAddElement(). The hash key for a set
 127     must be unique regardless of the order its elements are inserted,
 128     i.e., the hashing function must be additive(?).
 129 */
 130 #define hashKeySingleton(r)       ((StgWord)(r))
 131 #define hashKeyAddElement(r, s)   (hashKeySingleton((r)) + (s)->hashKey)
 132
 133 // Prints the full information on a given retainer.
 134 // Note: This function is not part of retainerSet interface, but this is
 135 //       the best place to define it.
 136 void printRetainer(FILE *, retainer);
 137
 138 #endif /* PROFILING */
 139