StatusTable: Do not use std::partial_sort
Since std::partial_sort is C++17 only, do not use it for Ninja
which should only use C++11.
Implement the sorting feature using a max-priority-queue with
a fixed size, then reversing the results to get the sorted list
of older commands from the input map.
Fuchsia-Only: multiline-status
Change-Id: Iae7618d2513fe095b96bae3dfd8124bf9b0e15e3
Reviewed-on: https://fuchsia-review.googlesource.com/c/third_party/github.com/ninja-build/ninja/+/1037772
Reviewed-by: Tyler Mandry <tmandry@google.com>
Commit-Queue: David Turner <digit@google.com>
diff --git a/src/status_table.cc b/src/status_table.cc
index 8c31d0b..9d56583 100644
--- a/src/status_table.cc
+++ b/src/status_table.cc
@@ -14,7 +14,7 @@
#include "status_table.h"
-#include <algorithm>
+#include <cstdint>
#include "assert.h"
@@ -23,7 +23,10 @@
#endif
StatusTable::StatusTable(const Config& config, AsyncLoop& async_loop)
- : config_(config), async_loop_(async_loop) {}
+ : config_(config), async_loop_(async_loop) {
+ commands_max_queue_.reserve(config_.max_commands);
+ older_commands_.reserve(config_.max_commands);
+}
StatusTable::~StatusTable() = default;
@@ -94,29 +97,49 @@
}
void StatusTable::PrintPending(int64_t cur_time_millis) {
- if (!config_.max_commands)
+ size_t max_commands = config_.max_commands;
+ if (!max_commands)
return;
- // Find the N-th older running edges, where N is max_height_.
- // Reuse the sorted_pending_edges_ vector between calls.
- auto& sorted_commands = sorted_pending_commands_;
- sorted_commands.assign(pending_commands_.begin(), pending_commands_.end());
+ // Find the |max_commands| older running edges, by using a fixed-size
+ // max-priority-queue. Then sort the result from oldest to newest
+ // commands.
- auto less = [](const CommandInfo& a, const CommandInfo& b) -> bool {
- return a.second < b.second;
- };
- size_t count = std::min(sorted_commands.size(), config_.max_commands);
+ // Fill queue with empty items to simplify loop below.
+ assert(commands_max_queue_.empty());
+ commands_max_queue_.resize(max_commands);
+ for (const auto& pair : pending_commands_) {
+ int64_t start_time_ms = pair.second;
+ // If this command is newer than the current top, ignore it
+ // otherwise replace the top with it in the queue.
+ if (start_time_ms < commands_max_queue_.top().start_time_ms) {
+ commands_max_queue_.pop();
+ commands_max_queue_.emplace(pair.first, start_time_ms);
+ }
+ }
- std::partial_sort(sorted_commands.begin(), sorted_commands.begin() + count,
- sorted_commands.end(), less);
+ // Compute the older commands in _decreasing_ starting time,
+ // then parse it in reverse order for printing (to avoid an
+ // std::reverse() call).
+ older_commands_.clear();
+ while (!commands_max_queue_.empty()) {
+ const auto& info = commands_max_queue_.top();
+ // Ignore entries with |command == nullptr|, which happen
+ // when there are less than |config_.max_commands| items in
+ //|pending_commands_|.
+ if (info.command != nullptr)
+ older_commands_.push_back(info);
+ commands_max_queue_.pop();
+ }
std::string pending_line;
- for (size_t n = 0; n < count; ++n) {
- CommandInfo& pair = sorted_commands[n];
+ for (auto info_reverse_it = older_commands_.end();
+ info_reverse_it != older_commands_.begin();) {
+ const CommandInfo& info = *(--info_reverse_it);
// Format the elapsed time in a human friendly format.
char elapsed_buffer[16];
- int64_t elapsed_ms = cur_time_millis - pair.second;
+ int64_t elapsed_ms = cur_time_millis - info.start_time_ms;
if (elapsed_ms < 0) {
snprintf(elapsed_buffer, sizeof(elapsed_buffer), "??????");
} else {
@@ -132,7 +155,7 @@
}
// Get edge description or command.
- std::string description = GetCommandDescription(pair.first);
+ std::string description = GetCommandDescription(info.command);
// Format '<elapsed> | <description>' where <elapsed> is
// right-justified.
@@ -156,6 +179,7 @@
}
// Clear previous lines that are not needed anymore.
+ size_t count = older_commands_.size();
size_t next_height = count;
for (; count < last_command_count_; ++count) {
ClearNextLine();
diff --git a/src/status_table.h b/src/status_table.h
index dbc27c2..c8acb0a 100644
--- a/src/status_table.h
+++ b/src/status_table.h
@@ -19,6 +19,7 @@
#include <stdint.h>
#include <stdio.h>
+#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
@@ -176,12 +177,30 @@
using CommandMap = std::unordered_map<CommandPointer, int64_t>;
CommandMap pending_commands_;
- // Used on each PrintPending() call to minimize heap allocations.
- // Note that CommandMap::value_type.first has type |const Edge* const| and
- // thus CommandMap::value_type is not copyable and cannot be used as an
- // std::vector<> item type.
- using CommandInfo = std::pair<CommandPointer, int64_t>;
- std::vector<CommandInfo> sorted_pending_commands_;
+ // A copyable alternative to CommandMap::value_type, with
+ // default values appropriate for the MaxQueue type below.
+ struct CommandInfo {
+ CommandInfo() = default;
+ CommandInfo(CommandPointer a_command, int64_t a_start_time_ms)
+ : command(a_command), start_time_ms(a_start_time_ms) {}
+
+ CommandPointer command = nullptr;
+ int64_t start_time_ms = INT64_MAX;
+
+ bool operator<(const CommandInfo& other) const {
+ return start_time_ms < other.start_time_ms;
+ }
+ };
+
+ // MaxQueue is a fixed-size max-heap of CommandInfo values, sorted by
+ // their start time (larger start time / newer command at the top).
+ struct MaxQueue : public std::priority_queue<CommandInfo> {
+ void reserve(size_t capacity) { c.reserve(capacity); }
+ void resize(size_t size) { c.resize(size); }
+ };
+
+ MaxQueue commands_max_queue_;
+ std::vector<CommandInfo> older_commands_;
};
#endif // NINJA_STATUS_TABLE_H_
