Support computing percentiles on a rolling window of samples

cc/scheduler/rolling_sample_window.h

Index: cc/scheduler/rolling_sample_window.h
diff --git a/cc/scheduler/rolling_sample_window.h b/cc/scheduler/rolling_sample_window.h
new file mode 100644
index 0000000000000000000000000000000000000000..5e7aa4695ee13e31fc1b35cb5bfadb8f87d4c8a2
--- /dev/null
+++ b/cc/scheduler/rolling_sample_window.h
@@ -0,0 +1,44 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CC_SCHEDULER_ROLLING_SAMPLE_WINDOW_H_
+#define CC_SCHEDULER_ROLLING_SAMPLE_WINDOW_H_
+
+#include <list>
+#include <set>
+
+#include "base/time.h"
+#include "cc/base/cc_export.h"
+
+namespace cc {
+
+// Stores a limited number of samples. When the maximum size is reached, each
+// insertion results in the deletion of the oldest remaining sample.
+class CC_EXPORT RollingSampleWindow {

[brianderson, 2013/05/31 18:42:05]

If we are going to use a generic class name like this, should we make it a
template?

Otherwise, should we rename the class to something like RollingTimeDeltaWindow
or RollingTimeDeltaHistory?

[ajuma, 2013/05/31 20:41:11]

Renamed to RollingTimeDeltaHistory.

+ public:
+  explicit RollingSampleWindow(size_t max_size);
+
+  ~RollingSampleWindow();
+
+  void InsertSample(base::TimeDelta time);
+
+  void Clear();
+
+  // Returns the smallest base::TimeDelta that is greater than or equal to
+  // the specified percent of samples.
+  base::TimeDelta Percentile(double percent) const;
+
+ private:
+  typedef std::multiset<base::TimeDelta> TimeDeltaMultiset;
+
+  TimeDeltaMultiset sample_set_;
+  std::list<TimeDeltaMultiset::iterator> chronological_sample_list_;

[brianderson, 2013/05/31 18:42:05]

Would a std::deque be more efficient? Once it reaches the max size, there
wouldn't have to be any more allocations. Also, a deque would require less
storage.

[ajuma, 2013/05/31 20:41:11]

Changed to a deque.

+  size_t max_size_;
+
+  DISALLOW_COPY_AND_ASSIGN(RollingSampleWindow);
+};
+
+}  // namespace cc
+
+#endif  // CC_SCHEDULER_ROLLING_SAMPLE_WINDOW_H_