java-topology/docs/tickets/lean4-0007-runtime-process-windows-env-var-quadratic.md

lean4-0007: runtime/process.cpp — O(N²) Windows environment variable inheritance

Target: leanprover/lean4 Severity: LOW-MEDIUM CWE: CWE-407 (Inefficient Algorithmic Complexity) MOAD: MOAD-0001 (A Sedimentary Defect) File: src/runtime/process.cpp:247–254 Language: C++ Platform: Windows only Status: open

Description

When spawning child processes on Windows with inherit_env=true, the runtime iterates all inherited environment variable keys and checks each against new_env_vars (an unordered_map) using .count({key_begin, key_end}). This constructs a temporary std::string from a char range per iteration. With N environment variables and M override vars, cost is O(N × M) due to repeated string construction and hash lookup inside the loop.

Root Cause

// runtime/process.cpp:237–254
std::unordered_map<std::string, option_ref<string_ref>> new_env_vars;
// ... populate new_env_vars from explicit overrides ...

while (*key_begin) {
    char *key_end = strchr(key_begin, '=');
    char *entry_end = key_end + strlen(key_end);
    if (!new_env_vars.count({key_begin, key_end})) {   // constructs std::string each iteration
        new_envp = std::copy(key_begin, entry_end + 1, new_envp);
    }
    key_begin = entry_end + 1;
}

.count({key_begin, key_end}) constructs a std::string on each of N iterations. The map itself is O(1) per lookup, but string construction is non-trivial. On systems with 200–500 env vars, this is measurable.

Fix

Use std::string_view for the key lookup (C++17), or pre-build a std::unordered_set<std::string> from new_env_vars keys before the loop and use .count() on it with a string_view. The std::string allocation per iteration is the waste to eliminate.

// Build key set once, outside loop
std::unordered_set<std::string> override_keys;
for (auto const & kv : new_env_vars) override_keys.insert(kv.first);

while (*key_begin) {
    char *key_end = strchr(key_begin, '=');
    std::string_view key(key_begin, key_end - key_begin);
    if (!override_keys.count(std::string(key))) {  // still O(1), one alloc per lookup
        ...
    }
}

Severity Note

Windows-only code path. Environment variable counts rarely exceed 500. Impact is real but not critical. Low priority compared to lean4-0001 and lean4-0004.