git.sesse.net Git - nageru/blob - nageru/queue_length_policy.h

   1 #ifndef _QUEUE_LENGTH_POLICY_H
   2 #define _QUEUE_LENGTH_POLICY_H 1
   3
   4 #include <stddef.h>
   5 #include <stdint.h>
   6
   7 #include <atomic>
   8 #include <chrono>
   9 #include <deque>
  10 #include <set>
  11 #include <string>
  12 #include <utility>
  13 #include <vector>
  14
  15 // A class to estimate the future jitter. Used in QueueLengthPolicy (see below).
  16 //
  17 // There are many ways to estimate jitter; I've tested a few ones (and also
  18 // some algorithms that don't explicitly model jitter) with different
  19 // parameters on some real-life data in experiments/queue_drop_policy.cpp.
  20 // This is one based on simple order statistics where I've added some margin in
  21 // the number of starvation events; I believe that about one every hour would
  22 // probably be acceptable, but this one typically goes lower than that, at the
  23 // cost of 2–3 ms extra latency. (If the queue is hard-limited to one frame, it's
  24 // possible to get ~10 ms further down, but this would mean framedrops every
  25 // second or so.) The general strategy is: Take the 99.9-percentile jitter over
  26 // last 5000 frames, multiply by two, and that's our worst-case jitter
  27 // estimate. The fact that we're not using the max value means that we could
  28 // actually even throw away very late frames immediately, which means we only
  29 // get one user-visible event instead of seeing something both when the frame
  30 // arrives late (duplicate frame) and then again when we drop.
  31 class JitterHistory {
  32 private:
  33         static constexpr size_t history_length = 5000;
  34         static constexpr double percentile = 0.999;
  35         static constexpr double multiplier = 2.0;
  36
  37 public:
  38         void register_metrics(const std::vector<std::pair<std::string, std::string>> &labels);
  39         void unregister_metrics(const std::vector<std::pair<std::string, std::string>> &labels);
  40
  41         void clear() {
  42                 history.clear();
  43                 orders.clear();
  44                 expected_timestamp = std::chrono::steady_clock::time_point::min();
  45         }
  46         void frame_arrived(std::chrono::steady_clock::time_point now, int64_t frame_duration, size_t dropped_frames);
  47         std::chrono::steady_clock::time_point get_expected_next_frame() const { return expected_timestamp; }
  48         double estimate_max_jitter() const;
  49
  50 private:
  51         // A simple O(k) based algorithm for getting the k-th largest or
  52         // smallest element from our window; we simply keep the multiset
  53         // ordered (insertions and deletions are O(n) as always) and then
  54         // iterate from one of the sides. If we had larger values of k,
  55         // we could go for a more complicated setup with two sets or heaps
  56         // (one increasing and one decreasing) that we keep balanced around
  57         // the point, or it is possible to reimplement std::set with
  58         // counts in each node. However, since k=5, we don't need this.
  59         std::multiset<double> orders;
  60         std::deque<std::multiset<double>::iterator> history;
  61
  62         std::chrono::steady_clock::time_point expected_timestamp = std::chrono::steady_clock::time_point::min();
  63         int64_t last_duration = 0;
  64
  65         // Metrics. There are no direct summaries for jitter, since we already have latency summaries.
  66         std::atomic<int64_t> metric_input_underestimated_jitter_frames{0};
  67         std::atomic<double> metric_input_estimated_max_jitter_seconds{0.0 / 0.0};
  68 };
  69
  70 // For any card that's not the master (where we pick out the frames as they
  71 // come, as fast as we can process), there's going to be a queue. The question
  72 // is when we should drop frames from that queue (apart from the obvious
  73 // dropping if the 16-frame queue should become full), especially given that
  74 // the frame rate could be lower or higher than the master (either subtly or
  75 // dramatically). We have two (conflicting) demands:
  76 //
  77 //   1. We want to avoid starving the queue.
  78 //   2. We don't want to add more delay than is needed.
  79 //
  80 // Our general strategy is to drop as many frames as we can (helping for #2)
  81 // that we think is safe for #1 given jitter. To this end, we measure the
  82 // deviation from the expected arrival time for all cards, and use that for
  83 // continuous jitter estimation.
  84 //
  85 // We then drop everything from the queue that we're sure we won't need to
  86 // serve the output in the time before the next frame arrives. Typically,
  87 // this means the queue will contain 0 or 1 frames, although more is also
  88 // possible if the jitter is very high.
  89 class QueueLengthPolicy {
  90 public:
  91         QueueLengthPolicy() {}
  92
  93         void register_metrics(const std::vector<std::pair<std::string, std::string>> &labels);
  94         void unregister_metrics(const std::vector<std::pair<std::string, std::string>> &labels);
  95
  96         // Call after picking out a frame, so 0 means starvation.
  97         // Note that the policy has no memory; everything is given in as parameters.
  98         void update_policy(std::chrono::steady_clock::time_point now,
  99                            std::chrono::steady_clock::time_point expected_next_input_frame,
 100                            int64_t input_frame_duration,
 101                            int64_t master_frame_duration,
 102                            double max_input_card_jitter_seconds,
 103                            double max_master_card_jitter_seconds);
 104         unsigned get_safe_queue_length() const { return safe_queue_length; }
 105
 106 private:
 107         unsigned safe_queue_length = 0;  // Can never go below zero.
 108
 109         // Metrics.
 110         std::atomic<int64_t> metric_input_queue_safe_length_frames{1};
 111 };
 112
 113 #endif  // !defined(_QUEUE_LENGTH_POLICY_H)