https://github.com/zhuwanhong updated https://github.com/llvm/llvm-project/pull/219633
>From 406b1ed451a447eebbaca518f9ced3d72721239a Mon Sep 17 00:00:00 2001 From: zhuwanhong <[email protected]> Date: Sat, 29 Aug 2026 14:56:59 +0900 Subject: [PATCH] [lldb] Fix quadratic behavior in VariableList::AppendVariablesIfUnique MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ## Summary `VariableList::AppendVariablesIfUnique()` deduplicates by scanning the destination list linearly for every element it inserts, so appending N variables costs O(N²). `SBFrame::FindValue()` calls it with the frame's entire variable list which, when `get_file_globals` is set, contains every global and static of the compile unit. `StackFrame` objects are rebuilt every time the process stops, so this merge is redone on every stop. ## Impact Seen through CodeLLDB on Windows (MSVC/PDB target, ~110 loaded modules, a very large translation unit). A single watch expression naming an identifier that does not exist in the current frame made `SBFrame::FindValue(name, eValueTypeVariableGlobal)` take **2.7–3.4 s, on every stop**. Watch expressions are re-evaluated at each stop, so single-stepping went from ~0.15 s to ~2.9 s per step. Timings taken around the SB API calls (seconds): ``` find=0.013 findvalue=3.384 varpath=0.026 eval=2.670 find=0.000 findvalue=2.937 varpath=0.015 find=0.001 findvalue=2.703 varpath=0.028 find=0.000 findvalue=2.822 varpath=0.018 ``` `find` is `SBFrame::FindVariable()`, `varpath` is `SBFrame::GetValueForVariablePath()`, `eval` is `SBFrame::EvaluateExpression()`, and `findvalue` is ```python for val_type in [eValueTypeVariableGlobal, eValueTypeVariableStatic, eValueTypeRegister, eValueTypeConstResult]: val = frame.FindValue(name, val_type) ``` The cost repeats identically on every stop. That rules out the one-time parsing done by `CompileUnit::GetVariableList()`, whose result is cached on the CompileUnit; what is repeated is the work done on the freshly created `StackFrame`. ## Where `SBFrame::FindValue()`, for `eValueTypeVariableGlobal` / `eValueTypeVariableStatic`: ```cpp if (sc.block) sc.block->AppendVariables(..., &variable_list); if (base_value_type == eValueTypeVariableGlobal || base_value_type == eValueTypeVariableStatic || include_synthetic_vars) { const bool get_file_globals = true; VariableList *frame_vars = frame->GetVariableList(get_file_globals, include_synthetic_vars, nullptr); if (frame_vars) frame_vars->AppendVariablesIfUnique(variable_list); // <-- quadratic } ``` `lldb/source/Symbol/VariableList.cpp`: ```cpp size_t VariableList::AppendVariablesIfUnique(VariableList &var_list) { const size_t initial_size = var_list.GetSize(); iterator pos, end = m_variables.end(); for (pos = m_variables.begin(); pos != end; ++pos) var_list.AddVariableIfUnique(*pos); // linear scan per insertion return var_list.GetSize() - initial_size; } bool VariableList::AddVariableIfUnique(const lldb::VariableSP &var_sp) { if (FindVariableIndex(var_sp) == UINT32_MAX) { ... } } uint32_t VariableList::FindVariableIndex(const VariableSP &var_sp) { iterator pos, end = m_variables.end(); for (pos = m_variables.begin(); pos != end; ++pos) { if (pos->get() == var_sp.get()) return std::distance(m_variables.begin(), pos); } return UINT32_MAX; } ``` ## This patch Collect the destination list's contents into a set once, making the merge O(N + M). Behaviour is unchanged: deduplication is by `Variable *` identity, exactly as `FindVariableIndex()` does, and insertion order is preserved. Patch attached (`lldb-variablelist-quadratic.patch`). The other batch helpers, `AppendVariablesIfUnique(const RegularExpression &, ...)` and `AppendVariablesWithScope()`, share the pattern. They are filtered, so N is usually smaller; left alone here to keep the change minimal. ## Caveats - I have not built or tested LLDB with this change. It is small and behaviour-preserving, but it has not been compiled. - The attribution is from code reading plus the per-stop repetition of the cost, not from a profiler: LLDB's own `log timers` accounts for only ~2 ms across several steps, because neither `SBFrame::FindValue()` nor the Clang expression path carries `LLDB_SCOPED_TIMER` instrumentation. ## Related, not addressed here On the same target, `SBFrame::EvaluateExpression()` takes ~2.7 s to report `use of undeclared identifier`, also repeated on every stop. Repeating the same evaluation within one stop is fast; after the process resumes and stops again it is slow once more. A valid native expression such as `1+1` evaluates instantly, so this is not expression-parser startup cost. That looks like a separate issue. --- lldb/source/Symbol/VariableList.cpp | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) diff --git a/lldb/source/Symbol/VariableList.cpp b/lldb/source/Symbol/VariableList.cpp index b9f2494d4a5bd..d81f183964279 100644 --- a/lldb/source/Symbol/VariableList.cpp +++ b/lldb/source/Symbol/VariableList.cpp @@ -13,6 +13,8 @@ #include "lldb/Symbol/Function.h" #include "lldb/Utility/RegularExpression.h" +#include "llvm/ADT/SmallPtrSet.h" + using namespace lldb; using namespace lldb_private; @@ -90,9 +92,16 @@ VariableSP VariableList::FindVariable(ConstString name, size_t VariableList::AppendVariablesIfUnique(VariableList &var_list) { const size_t initial_size = var_list.GetSize(); - iterator pos, end = m_variables.end(); - for (pos = m_variables.begin(); pos != end; ++pos) - var_list.AddVariableIfUnique(*pos); + // Collect the variables already in `var_list` once, instead of rescanning it + // for every insertion. AddVariableIfUnique() searches linearly, which makes + // this loop quadratic, and this function is called with entire compile unit + // variable lists -- see SBFrame::FindValue(). + llvm::SmallPtrSet<Variable *, 32> seen; + for (const lldb::VariableSP &var_sp : var_list.m_variables) + seen.insert(var_sp.get()); + for (const lldb::VariableSP &var_sp : m_variables) + if (seen.insert(var_sp.get()).second) + var_list.m_variables.push_back(var_sp); return var_list.GetSize() - initial_size; } _______________________________________________ lldb-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
