[lldb] Rate limit progress reports -- different approach [WIP-ish]

[labath]

Summary

Have the Progress class spawn a thread to periodically send progress
reports.

The reporting period could be made configurable, but for now I've
hardcoded it to 100ms. (This is the main WIP part)

It could be argued that creating a thread for progress reporting adds
overhead, but I would counter that by saying "If the task is so fast
that creating a thread noticably slows it down, then it really doesn't
need progress reporting".

For me, this speeds up DWARF indexing by about 1.5% (which is only
slightly above the error bars), but I expect it will have a much bigger
impact in situations where printing a single progress update takes a
nontrivial amount of time.

[JDevlieghere]

Continuing some of the discussion from D150805 here as it mostly relates to this patch:

In D150805#4402906, @labath wrote:

I agree that we should have a rate limiting mechanism very close to the source, to avoid wasting work for events that aren't going to be used.

I'm not sure I (fully) agree with this statement. I may have misunderstood the motivation for D150805, but my understanding was that it was the consumption of the progress events that was too costly, not the generation. Of course this will indirectly make that problem better because of the rate limiting, but as I said in the original review, that still seems like something the consumer should have control over.

I would have assumed that reporting the progress wouldn't be that expensive. Based on the description of this patch, it seems like it's non-trivial, but also not a dominating factor by any means.

This is particularly important for debug info parsing, where we have multiple threads working in parallel and taking a lock even just to check whether we should report something could be a choke point.

Fair enough, but this could be achieved without the rate limiting: the reporting could be an async operation with the thread reporting every event.

I like it because the act of reporting progress does block the reporting thread in any way.

+1 but as I said above this could be orthogonal from rate limiting.

TL;DR I like the async reporting part, not (yet) convinced of the rate limiting "at the source".

[saugustine]

What other progress reporting needs rate limiting?

To the best of my knowledge, we have only identified one location--this one. So I'm not sure a fully general solution is in order here under the YAGNI principle.

I favor rate limiting close to the source because generating events and throwing them away is pure waste and gives an overall sense to the user that lldb is slow.

[JDevlieghere]

In D152364#4406704, @saugustine wrote:

What other progress reporting needs rate limiting?

To the best of my knowledge, we have only identified one location--this one. So I'm not sure a fully general solution is in order here under the YAGNI principle.

I favor rate limiting close to the source because generating events and throwing them away is pure waste and gives an overall sense to the user that lldb is slow.

While generality is part of why I favor doing the rate limiting in the listener, it also means that the listener can decide the rate. For example, VSCode could decide they don't need rate limiting (as is the case today) while the default event handler in LLDB could make a different decision (for example based on whether you're in a fast TTY).

[labath]

In D152364#4406589, @JDevlieghere wrote:

Continuing some of the discussion from D150805 here as it mostly relates to this patch:

In D150805#4402906, @labath wrote:

I agree that we should have a rate limiting mechanism very close to the source, to avoid wasting work for events that aren't going to be used.

I'm not sure I (fully) agree with this statement. I may have misunderstood the motivation for D150805, but my understanding was that it was the consumption of the progress events that was too costly, not the generation. Of course this will indirectly make that problem better because of the rate limiting, but as I said in the original review, that still seems like something the consumer should have control over.

I would have assumed that reporting the progress wouldn't be that expensive. Based on the description of this patch, it seems like it's non-trivial, but also not a dominating factor by any means.

That is correct. It is definitely not as slow as I expected it to be at first.

This is particularly important for debug info parsing, where we have multiple threads working in parallel and taking a lock even just to check whether we should report something could be a choke point.

Fair enough, but this could be achieved without the rate limiting: the reporting could be an async operation with the thread reporting every event.

That's a bit tricky. If you want to guarantee you don't lose any events *and* also not block the "sending" thread , you have to have some sort of a queuing mechanism -- which means you're essentially reimplementing a listener/broadcaster pattern. I'm sure that could be implemented more efficiently that what our current classes do, but I don't think that would be time well spent. And we'd still be generating a lot of events that noone is going to see.

In D152364#4406927, @JDevlieghere wrote:

While generality is part of why I favor doing the rate limiting in the listener, it also means that the listener can decide the rate. For example, VSCode could decide they don't need rate limiting (as is the case today) while the default event handler in LLDB could make a different decision (for example based on whether you're in a fast TTY).

The idea seems nice in principle, but I think the implementation would be somewhat messy. For "normal" events, the goal usually is to send them out as quickly as possible, but in this case we actually want to do the opposite -- force a delay before the receipt (or sending) of a specific event. And as the same listener will be receiving multiple kinds of events, be need this to be configurable on a per-event basis. If I was going down this path, I guess I'd do it by adding some kind of a delay/frequency argument to Listener::StartListeningForEvents function. The listener would remember the requested frequency for a specific type of events as well as the last time that this kind of an event was received, and then the broadcaster would avoid enqueuing these events (and waking up the listener) if the events come faster than that.

Doable, just slightly complicated. We'd also need to figure out what we do with the existing filtering mechanism -- looking at the code, I see that we already have the ability to send "unique" events (Broadcaster::BroadcastEventIfUnique). This is a form of rate-limiting, so I think it'd make sense to merge these. However:

• this behavior is controlled on the broadcaster side
• this actually keeps the first duplicated event, whereas we'd most likely prefer to keep the last one

[labath]

Actually, thinking about these "unique" events, I think it would be worth trying out sending the progress update events as "unique". Depending on where exactly in the pipeline the congestion happens, it might just be enough to fix the immediate problem. If the slow screen updates cause the write(stdout) calls to block, then we will have a queue forming in the listener object. The uniqueness property would help with that as it would collapse that queue into a single event. If the write does not block (and the queue forms somewhere down the line), then we need rate limiting.

[labath]

:(

lldb/include/lldb/Core/Progress.h

 //===-- Progress.h ----------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_CORE_PROGRESS_H
 #define LLDB_CORE_PROGRESS_H
 
+#include "lldb/Host/HostThread.h"
 #include "lldb/Utility/ConstString.h"
 #include "lldb/lldb-types.h"
 #include <atomic>
+#include <future>
 #include <mutex>
 #include <optional>
 
 namespace lldb_private {
 
 /// A Progress indicator helper class.
 ///
 /// Any potentially long running sections of code in LLDB should report
public:
   /// anything nor send any progress updates.
   ///
   /// @param [in] amount The amount to increment m_completed by.
   ///
   /// @param [in] an optional message associated with this update.
   void Increment(uint64_t amount = 1, std::string update = {});
 
 private:
-  void ReportProgress(std::string update = {});
+  void SendPeriodicReports(std::shared_future<void> done);
+  void ReportProgress(std::string update);
   static std::atomic<uint64_t> g_id;
   /// The title of the progress activity.
   std::string m_title;
-  std::mutex m_mutex;
   /// A unique integer identifier for progress reporting.
   const uint64_t m_id;
   /// How much work ([0...m_total]) that has been completed.
-  uint64_t m_completed;
+  std::atomic<uint64_t> m_completed;
   /// Total amount of work, UINT64_MAX for non deterministic progress.
   const uint64_t m_total;
   /// The optional debugger ID to report progress to. If this has no value then
   /// all debuggers will receive this event.
   std::optional<lldb::user_id_t> m_debugger_id;
-  /// Set to true when progress has been reported where m_completed == m_total
-  /// to ensure that we don't send progress updates after progress has
-  /// completed.
-  bool m_complete = false;
+
+  std::mutex m_update_mutex;
+  std::string m_update;
+
+  std::promise<void> m_stop_reporting_thread;
+  HostThread m_reporting_thread;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_CORE_PROGRESS_H

lldb/source/Core/Progress.cpp

 //===-- Progress.cpp ------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Core/Progress.h"
 
 #include "lldb/Core/Debugger.h"
+#include "lldb/Host/ThreadLauncher.h"
+#include "lldb/Utility/LLDBLog.h"
 #include "lldb/Utility/StreamString.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 std::atomic<uint64_t> Progress::g_id(0);
 
 Progress::Progress(std::string title, uint64_t total,
                    lldb_private::Debugger *debugger)
     : m_title(title), m_id(++g_id), m_completed(0), m_total(total) {
   assert(total > 0);
   if (debugger)
     m_debugger_id = debugger->GetID();
-  std::lock_guard<std::mutex> guard(m_mutex);
-  ReportProgress();
+
+  // Using a shared_future because std::function needs to be copyable.
+  if (llvm::Expected<HostThread> reporting_thread =
+          ThreadLauncher::LaunchThread(
+              "<lldb.progress>",
+              [this, future = std::shared_future<void>(
+                         m_stop_reporting_thread.get_future())]() {
+                SendPeriodicReports(future);
+                return lldb::thread_result_t();
+              })) {
+    m_reporting_thread = std::move(*reporting_thread);
+  } else {
+    LLDB_LOG_ERROR(GetLog(LLDBLog::Host), reporting_thread.takeError(),
+                   "failed to launch host thread: {}");
+  }
 }
 
 Progress::~Progress() {
-  // Make sure to always report progress completed when this object is
-  // destructed so it indicates the progress dialog/activity should go away.
-  std::lock_guard<std::mutex> guard(m_mutex);
-  if (!m_completed) {
-    m_completed = m_total;
-    ReportProgress();
+  m_stop_reporting_thread.set_value();
+  if (m_reporting_thread.IsJoinable()) {
+    m_reporting_thread.Join(nullptr);
   }
 }
 
-void Progress::Increment(uint64_t amount, std::string update) {
-  if (amount > 0) {
-    std::lock_guard<std::mutex> guard(m_mutex);
-    // Watch out for unsigned overflow and make sure we don't increment too
-    // much and exceed m_total.
-    if (amount > (m_total - m_completed))
-      m_completed = m_total;
-    else
-      m_completed += amount;
-    ReportProgress(update);
+void Progress::SendPeriodicReports(std::shared_future<void> done) {
+  uint64_t last_completed = 0;
+  Debugger::ReportProgress(m_id, m_title, "", last_completed, m_total,
+                           m_debugger_id);
+
+  while (last_completed != m_total &&
+         done.wait_for(std::chrono::milliseconds(100)) ==
+             std::future_status::timeout) {
+    uint64_t current_completed = m_completed.load();
+    if (current_completed == last_completed)
+      continue;
+
+    if (current_completed == m_total ||
+        current_completed < last_completed /*overflow*/) {
+      break;
     }
+
+    std::string current_update;
+    {
+      std::lock_guard<std::mutex> guard(m_update_mutex);
+      current_update = std::move(m_update);
+      m_update.clear();
+    }
+    Debugger::ReportProgress(m_id, m_title, std::move(current_update),
+                             current_completed, m_total, m_debugger_id);
+    last_completed = current_completed;
+  }
+
+  Debugger::ReportProgress(m_id, m_title, "", m_total, m_total, m_debugger_id);
 }
 
-void Progress::ReportProgress(std::string update) {
-  if (!m_complete) {
-    // Make sure we only send one notification that indicates the progress is
-    // complete.
-    m_complete = m_completed == m_total;
-    Debugger::ReportProgress(m_id, m_title, std::move(update), m_completed,
-                             m_total, m_debugger_id);
+void Progress::Increment(uint64_t amount, std::string update) {
+  if (amount == 0)
+    return;
+  if (!update.empty()) {
+    std::lock_guard<std::mutex> guard(m_update_mutex);
+    m_update = std::move(update);
   }
+  m_completed += amount;
 }