https://github.com/zhuwanhong created
https://github.com/llvm/llvm-project/pull/219633
## 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.
>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
