hphp/util/hfsort.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_UTIL_HFSORT_H
  18 #define incl_HPHP_UTIL_HFSORT_H
  19
  20 #include <string>
  21 #include <unordered_set>
  22 #include <vector>
  23
  24 #include "hphp/util/hash.h"
  25
  26 namespace HPHP { namespace hfsort {
  27
  28 using TargetId = int32_t;
  29 constexpr TargetId InvalidId = -1;
  30
  31 struct Arc {
  32   Arc(TargetId s, TargetId d, double w = 0)
  33       : src(s)
  34       , dst(d)
  35       , weight(w)
  36   {}
  37   Arc(const Arc&) = delete;
  38
  39   friend bool operator==(const Arc& lhs, const Arc& rhs) {
  40     return lhs.src == rhs.src && lhs.dst == rhs.dst;
  41   }
  42
  43   const TargetId src;
  44   const TargetId dst;
  45   mutable double weight;
  46   mutable double normalizedWeight{0};
  47   mutable double avgCallOffset{0};
  48 };
  49
  50 struct ArcHash {
  51   int64_t operator()(const Arc& arc) const {
  52     return hash_int64_pair(int64_t(arc.src), int64_t(arc.dst));
  53   }
  54 };
  55
  56 struct Target {
  57   explicit Target(uint32_t size, uint32_t samples = 0)
  58     : size(size)
  59     , samples(samples)
  60   {}
  61
  62   uint32_t size;
  63   uint32_t samples;
  64
  65   // preds and succs contain no duplicate elements and self arcs are not allowed
  66   std::vector<TargetId> preds;
  67   std::vector<TargetId> succs;
  68 };
  69
  70 struct TargetGraph {
  71   TargetId addTarget(uint32_t size, uint32_t samples = 0);
  72   void setSamples(TargetId id, uint32_t samples);
  73   uint32_t getSamples(TargetId id);
  74   const Arc& incArcWeight(TargetId src, TargetId dst, double w = 1.0);
  75   void normalizeArcWeights();
  76
  77   template<class L>
  78   void printDot(char* fileName, L getLabel) const;
  79
  80   std::vector<Target> targets;
  81   std::unordered_set<Arc, ArcHash> arcs;
  82 };
  83
  84 struct Cluster {
  85   Cluster(TargetId id, const Target& f);
  86
  87   std::string toString() const;
  88   double density() const;
  89
  90   std::vector<TargetId> targets;
  91   uint32_t samples;
  92   uint32_t size;
  93   bool frozen; // not a candidate for merging
  94 };
  95
  96 /////////////////////////////////////////////////////////////////////////
  97
  98 bool compareClustersDensity(const Cluster& c1, const Cluster& c2);
  99 std::vector<Cluster> clusterize(const TargetGraph& cg);
 100
 101 /*
 102  * HFSortPlus - layout of hot functions with iTLB cache optimization
 103  */
 104 std::vector<Cluster> hfsortPlus(const TargetGraph& cg);
 105
 106 /*
 107  * Pettis-Hansen code layout algorithm
 108  * reference: K. Pettis and R. C. Hansen, "Profile Guided Code Positioning",
 109  *            PLDI '90
 110  */
 111 std::vector<Cluster> pettisAndHansen(const TargetGraph& cg);
 112
 113 /////////////////////////////////////////////////////////////////////////
 114
 115 template<class L>
 116 void TargetGraph::printDot(char* fileName, L getLabel) const {
 117   FILE* file = fopen(fileName, "wt");
 118   if (!file) return;
 119
 120   fprintf(file, "digraph g {\n");
 121   for (size_t f = 0; f < targets.size(); f++) {
 122     if (targets[f].samples == 0) continue;
 123     fprintf(
 124       file,
 125       "f%lu [label=\"%s\\nsamples=%u\\nsize=%u\"];\n",
 126       f,
 127       getLabel(f),
 128       targets[f].samples,
 129       targets[f].size);
 130   }
 131   for (size_t f = 0; f < targets.size(); f++) {
 132     if (targets[f].samples == 0) continue;
 133     for (auto dst : targets[f].succs) {
 134       auto& arc = *arcs.find(Arc(f, dst));
 135       fprintf(
 136         file,
 137         "f%lu -> f%u [label=\"normWgt=%.3lf,weight=%.0lf,callOffset=%.1lf\"];"
 138         "\n",
 139         f,
 140         dst,
 141         arc.normalizedWeight,
 142         arc.weight,
 143         arc.avgCallOffset);
 144     }
 145   }
 146   fprintf(file, "}\n");
 147   fclose(file);
 148 }
 149
 150 }}
 151
 152 #endif