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 #pragma once
  18
  19 #include <string>
  20 #include <unordered_set>
  21 #include <vector>
  22
  23 #include "hphp/util/hash.h"
  24
  25 namespace HPHP::hfsort {
  26
  27 using TargetId = int32_t;
  28 constexpr TargetId InvalidId = -1;
  29
  30 struct Arc {
  31   Arc(TargetId s, TargetId d, double w = 0)
  32       : src(s)
  33       , dst(d)
  34       , weight(w)
  35   {}
  36   Arc(const Arc&) = delete;
  37
  38   friend bool operator==(const Arc& lhs, const Arc& rhs) {
  39     return lhs.src == rhs.src && lhs.dst == rhs.dst;
  40   }
  41
  42   const TargetId src;
  43   const TargetId dst;
  44   mutable double weight;
  45   mutable double normalizedWeight{0};
  46   mutable double avgCallOffset{0};
  47 };
  48
  49 struct ArcHash {
  50   int64_t operator()(const Arc& arc) const {
  51     return hash_int64_pair(int64_t(arc.src), int64_t(arc.dst));
  52   }
  53 };
  54
  55 struct Target {
  56   explicit Target(uint32_t size, uint64_t samples = 0)
  57     : size(size)
  58     , samples(samples)
  59   {}
  60
  61   uint32_t size;
  62   uint64_t samples;
  63
  64   // preds and succs contain no duplicate elements and self arcs are not allowed
  65   std::vector<TargetId> preds;
  66   std::vector<TargetId> succs;
  67 };
  68
  69 struct TargetGraph {
  70   TargetId addTarget(uint32_t size, uint64_t samples = 0);
  71   void setSamples(TargetId id, uint64_t samples);
  72   void addSamples(TargetId id, uint64_t samples);
  73   uint64_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(const 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   Cluster(const std::vector<TargetId>& ids, const TargetGraph& cg);
  87
  88   std::string toString() const;
  89   double density() const;
  90
  91   std::vector<TargetId> targets;
  92   uint32_t samples;
  93   uint32_t size;
  94   bool frozen; // not a candidate for merging
  95 };
  96
  97 /////////////////////////////////////////////////////////////////////////
  98
  99 bool compareClustersDensity(const Cluster& c1, const Cluster& c2);
 100 std::vector<Cluster> clusterize(const TargetGraph& cg);
 101
 102 /*
 103  * HFSortPlus - layout of hot functions with iTLB cache optimization
 104  */
 105 std::vector<Cluster> hfsortPlus(const TargetGraph& cg);
 106
 107 /*
 108  * Pettis-Hansen code layout algorithm
 109  * reference: K. Pettis and R. C. Hansen, "Profile Guided Code Positioning",
 110  *            PLDI '90
 111  */
 112 std::vector<Cluster> pettisAndHansen(const TargetGraph& cg);
 113
 114 /////////////////////////////////////////////////////////////////////////
 115
 116 template<class L>
 117 void TargetGraph::printDot(const char* fileName, L getLabel) const {
 118   FILE* file = fopen(fileName, "wt");
 119   if (!file) return;
 120
 121   fprintf(file, "digraph g {\n");
 122   for (size_t f = 0; f < targets.size(); f++) {
 123     if (targets[f].samples == 0) continue;
 124     fprintf(
 125       file,
 126       "f%lu [label=\"%s\\nsamples=%lu\\nsize=%u\"];\n",
 127       f,
 128       getLabel(f),
 129       targets[f].samples,
 130       targets[f].size);
 131   }
 132   for (size_t f = 0; f < targets.size(); f++) {
 133     if (targets[f].samples == 0) continue;
 134     for (auto dst : targets[f].succs) {
 135       auto& arc = *arcs.find(Arc(f, dst));
 136       fprintf(
 137         file,
 138         "f%lu -> f%u [label=\"normWgt=%.3lf,weight=%.0lf,callOffset=%.1lf\"];"
 139         "\n",
 140         f,
 141         dst,
 142         arc.normalizedWeight,
 143         arc.weight,
 144         arc.avgCallOffset);
 145     }
 146   }
 147   fprintf(file, "}\n");
 148   fclose(file);
 149 }
 150
 151 }