[Courgette] Initial Implementation of LabelManager.

courgette/label_manager.cc

Index: courgette/label_manager.cc
diff --git a/courgette/label_manager.cc b/courgette/label_manager.cc
new file mode 100644
index 0000000000000000000000000000000000000000..fde80f644135b45e61829fe3a2a3ebcf3b3ae33a
--- /dev/null
+++ b/courgette/label_manager.cc
@@ -0,0 +1,87 @@
+// Copyright 2015 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.
+
+#include "courgette/label_manager.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+#include "courgette/consecutive_range_visitor.h"
+
+namespace courgette {
+
+namespace {
+
+bool CompareLabelByRva(const Label& label1, const Label& label2) {
+  return label1.rva_ < label2.rva_;
+}
+
+bool LabelHasZeroCount(const Label& label) {
+  return label.count_ == 0;
+}
+
+}  // namespace
+
+LabelManager::RvaVisitor::~RvaVisitor() { }
+
+LabelManager::LabelManager() { }
+
+LabelManager::~LabelManager() { }
+
+// We wish to minimize peak memory usage here. Analysis: Let
+//   m = number of (RVA) elements in |rva_visitor|,
+//   n = number of distinct (RVA) elements in |rva_visitor|.
+// The final storage is n * sizeof(Label) bytes. During computation we uniquify
+// m RVAs, and count repeats. Taking sizeof(RVA) = 4, an implementation using
+// std::map or std::unordered_map would consume additionally 32 * n bytes.
+// Meanwhile, our std::vector implementation consumes additionally 4 * m bytes
+// For our typical usage (i.e. Chrome) we see m = ~4n, so we use 16 * n bytes of
+// extra contiguous memory during computation. Assuming memory fragmentation
+// would not be an issue, this is much better than using std::map.
+void LabelManager::Read(RvaVisitor* rva_visitor) {
+  // Write all values in |rva_visitor| to |rvas|.
+  size_t num_rva = rva_visitor->Remaining();
+  std::vector<RVA> rvas(num_rva);
+  for (size_t i = 0; i < num_rva; ++i, rva_visitor->Next())
+    rvas[i] = rva_visitor->Get();
+
+  // Sort |rvas|, then count the number of distinct values.
+  typedef ConsecutiveRangeVisitor<std::vector<RVA>::iterator> CRV;

[grt (UTC plus 2), 2015/12/02 19:03:41]

nit:
  using CRV = ConsecutiveRangeVisitor<std::vector<RVA>::iterator>;

[huangs, 2015/12/02 20:51:02]

Done.

+  std::sort(rvas.begin(), rvas.end());
+  size_t num_distinct_rva = 0;
+  for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance())
+    ++num_distinct_rva;
+
+  // Reserve space for |labels_|, populate with sorted RVA and repeats.
+  DCHECK(labels_.empty());

[grt (UTC plus 2), 2015/12/02 19:03:40]

have you tried using a std::deque rather than a std::vector? i wonder if the
properties of a deque would make this "count then reserve then fill" go away.
the code would be a bit simpler.

[huangs, 2015/12/02 20:51:02]

Per discussion, the std::vector implementation is more amenable to the possible
transition to using NoThrowBuffer().  Not doing this yet though, to keep changes
small.

+  labels_.reserve(num_distinct_rva);
+  for (CRV it(rvas.begin(), rvas.end()); it.has_more(); it.advance()) {
+    labels_.push_back(Label(*it.cur()));
+    labels_.back().count_ = it.repeat();
+  }
+}
+
+void LabelManager::RemoveUnderusedLabels(int count_threshold) {
+  Label marker;

[grt (UTC plus 2), 2015/12/02 19:03:40]

unused

[huangs, 2015/12/02 20:51:02]

Removed.

+  if (count_threshold <= 0)
+    return;
+  for (Label& label : labels_) {
+    if (label.count_ < count_threshold)
+      label.count_ = 0;  // Use this as marker for removal.
+  }
+  auto it = std::remove_if(labels_.begin(), labels_.end(), LabelHasZeroCount);

[grt (UTC plus 2), 2015/12/02 19:03:40]

lambda:
[](const Label& l) { return l.count_ == 0; }

[huangs, 2015/12/02 20:51:02]

Woot! Done.

+  if (it != labels_.end()) {
+    labels_.erase(it, labels_.end());
+    // Not calling labels_.shrink_to_fit(), since this may cause reallocation.

[grt (UTC plus 2), 2015/12/02 19:03:41]

shrink_to_fit can't be used in any case since it hasn't been approved for use in
Chromium. i think it's fine to use the normal:
  labels_.erase(std::remove_if(...),
                labels_.end());
and do away with the if(). you could leave a comment on the line above saying
not to shrink if you think that's relevant.

[huangs, 2015/12/02 20:51:02]

Done, making comment more generic.

+  }
+}
+
+// Uses binary search to find |rva|.
+Label* LabelManager::Find(RVA rva) {
+  auto it = std::lower_bound(labels_.begin(), labels_.end(), Label(rva),
+                             CompareLabelByRva);

[grt (UTC plus 2), 2015/12/02 19:03:41]

this is a perfect use of a lambda:
[](const Label& l1, const Label& l2) { return l1.rva_ < l2.rva_; }

[huangs, 2015/12/02 20:51:02]

Done.

+  return it == labels_.end() || it->rva_ != rva ? nullptr : &(*it);
+}
+
+}  // namespace courgette