Speeding up loadTrees()

[etse1288]

What do you think of the proposal below (by Opus)

Proposal: Speed up SourceLoader::loadTrees() with directory pre-scanning

Problem

loadTrees() in source/driver/SourceLoader.cpp resolves missing module/package
names by probing the filesystem with findBuffer(). For each missing name, it
iterates searchDirectories × searchExtensions and calls sourceManager.readSource()
(which calls openCached()). Even cache hits go through fs::weakly_canonical()
before the lookup, causing a filesystem round trip per probe.

On network filesystems (NFS), each stat()/weakly_canonical() is a ~1–5ms network
call. With M missing names, D search directories, and E extensions, this produces
M × D × E filesystem calls per iteration of the fixpoint loop. A typical case
(50 missing names, 10 directories, 3 extensions) generates ~1,500 NFS round trips
per iteration.

Proposed fix

Replace the per-name probing in findBuffer() with an upfront directory scan.
Scan each search directory once with readdir() (one syscall per directory), build
an in-memory flat_hash_map<string, fs::path> keyed by filename stem, then do O(1)
lookups for each missing name.

Current code (findBuffer, lines 187–205)

SourceBuffer SourceLoader::findBuffer(std::string_view name) const {
    for (auto& dir : searchDirectories) {
        fs::path path(dir);
        path /= name;
        for (auto& ext : searchExtensions) {
            path.replace_extension(ext);
            if (!sourceManager.isCached(path)) {        // weakly_canonical → NFS stat
                auto readResult = sourceManager.readSource(path, nullptr);  // open + read
                if (readResult)
                    return *readResult;
            }
        }
    }
    return {};
}

Proposed replacement

// Called once before the fixpoint loop in loadTrees().
// Scans each search directory and builds a stem → path index.
void SourceLoader::buildLibraryIndex() {
    for (auto& dir : searchDirectories) {
        std::error_code ec;
        for (auto& entry : fs::directory_iterator(dir, ec)) {
            if (!entry.is_regular_file())
                continue;
            auto ext = entry.path().extension().string();
            if (searchExtensions.find(ext) == searchExtensions.end())
                continue;
            auto stem = entry.path().stem().string();
            libraryIndex.try_emplace(stem, entry.path());
        }
    }
}

SourceBuffer SourceLoader::findBuffer(std::string_view name) const {
    auto it = libraryIndex.find(name);
    if (it == libraryIndex.end())
        return {};
    if (sourceManager.isCached(it->second))
        return {};
    auto readResult = sourceManager.readSource(it->second, nullptr);
    return readResult ? *readResult : SourceBuffer{};
}

Add flat_hash_map<std::string, fs::path> libraryIndex; as a member of
SourceLoader, and call buildLibraryIndex() once at the top of loadTrees()
(or lazily on first findBuffer() call).

Impact

Metric	Before	After
Filesystem calls per missing name	D × E stat/canonicalize	0 (map lookup)
Upfront cost	0	D readdir calls (once)
Total for 50 names, 10 dirs, 3 exts	~1,500 stat calls	10 readdir calls
NFS latency (estimated)	1.5–7.5s per iteration	<50ms once

The index also eliminates weakly_canonical() calls on the lookup path since
directory entries from fs::directory_iterator already provide canonical paths.

Notes

• directory_iterator handles the case where a search directory doesn't exist
  (returns empty range with error code).
• If the same stem appears in multiple directories, try_emplace gives priority
  to the first directory in order, matching the current left-to-right search
  behavior.
• The index could optionally be refreshed between fixpoint iterations if library
  directories are expected to change during compilation (unlikely in practice).

[MikePopoloski]

I have not thought much about the details of the proposed fix but it's certainly good to avoid trips to the filesystem and likely a big improvement if your design does a lot of library searching. Is this slowness something you're experiencing yourself with your own projects?