Skip to content

Commit 5e266e0

Browse files
authored
Single-pass MemoryFileSystem.find() to avoid quadratic listing (#2055)
1 parent 19a042b commit 5e266e0

3 files changed

Lines changed: 173 additions & 0 deletions

File tree

‎docs/source/changelog.rst‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,13 @@
11
Changelog
22
=========
33

4+
Dev
5+
---
6+
7+
Enhancements
8+
9+
- Single-pass ``MemoryFileSystem.find()`` to avoid O(n_dirs * n_entries) listing; ``ls()`` previously scanned the whole store once per directory, now one pass over the flat store suffices (#2055)
10+
411
2026.6.0
512
--------
613

‎fsspec/implementations/memory.py‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,79 @@ def _strip_protocol(cls, path):
4040
path = path.lstrip("/").rstrip("/")
4141
return "/" + path if path else ""
4242

43+
def find(self, path, maxdepth=None, withdirs=False, detail=False, **kwargs):
44+
# The base implementation calls ls() once per directory, and each ls()
45+
# scans the whole (global) store, giving O(n_dirs * n_entries) behaviour
46+
# for a tree. Since the store is a flat mapping of every path, the same
47+
# result can be produced with a single pass over it.
48+
if maxdepth is not None and maxdepth < 1:
49+
raise ValueError("maxdepth must be at least 1")
50+
path = self._strip_protocol(path)
51+
if path in self.store:
52+
# path is itself a file
53+
if not detail:
54+
return [path]
55+
filelike = self.store[path]
56+
return {
57+
path: {
58+
"name": path,
59+
"size": filelike.size,
60+
"type": "file",
61+
"created": filelike.created.timestamp(),
62+
}
63+
}
64+
65+
# Uniform prefix so that the search root "" (the filesystem root) and a
66+
# nested path are handled the same way; rel depth is rel.count("/") + 1.
67+
prefix = path + "/" if path else "/"
68+
out = {}
69+
dirs = {}
70+
71+
def add_ancestor_dirs(name):
72+
# Register every directory implied between ``path`` and ``name`` that
73+
# is within maxdepth, mirroring how walk() surfaces implied dirs.
74+
idx = name.rfind("/")
75+
while idx > len(path):
76+
parent = name[:idx]
77+
if parent in dirs:
78+
break
79+
rel = parent[len(prefix) :]
80+
if maxdepth is None or rel.count("/") + 1 <= maxdepth:
81+
dirs[parent] = {"name": parent, "size": 0, "type": "directory"}
82+
idx = parent.rfind("/")
83+
84+
# `store` is shared by every MemoryFileSystem instance, so iterate a
85+
# snapshot: a concurrent create/delete would otherwise raise
86+
# "dictionary changed size during iteration". ls() does the same.
87+
for name, filelike in tuple(self.store.items()):
88+
if not name.startswith(prefix):
89+
continue
90+
rel = name[len(prefix) :]
91+
if withdirs:
92+
add_ancestor_dirs(name)
93+
if maxdepth is not None and rel.count("/") + 1 > maxdepth:
94+
continue
95+
out[name] = {
96+
"name": name,
97+
"size": filelike.size,
98+
"type": "file",
99+
"created": filelike.created.timestamp(),
100+
}
101+
102+
if withdirs:
103+
# Explicitly-created (possibly empty) directories live in pseudo_dirs.
104+
for pdir in self.pseudo_dirs:
105+
if pdir and pdir.startswith(prefix):
106+
add_ancestor_dirs(pdir + "/")
107+
out.update(dirs)
108+
# Mirror the base find(): include the search root itself when it is
109+
# a directory (needed for posix glob compliance).
110+
if path != "" and self.isdir(path):
111+
out[path] = self.info(path)
112+
113+
names = sorted(out)
114+
return {name: out[name] for name in names} if detail else names
115+
43116
def ls(self, path, detail=True, **kwargs):
44117
path = self._strip_protocol(path)
45118
if path in self.store:

‎fsspec/implementations/tests/test_memory.py‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
import pytest
55

66
from fsspec.implementations.local import LocalFileSystem, make_path_posix
7+
from fsspec.implementations.memory import MemoryFileSystem
78

89

910
def test_1(m):
@@ -407,3 +408,95 @@ def test_open_path_windows(m):
407408
f.write(b"some\nlines\nof\ntext")
408409

409410
assert m.read_text(path) == "some\nlines\nof\ntext"
411+
412+
413+
def test_find_matches_generic(m):
414+
# MemoryFileSystem overrides find() with a single-pass implementation; make
415+
# sure it agrees with the generic ls()-based AbstractFileSystem.find() across
416+
# roots, maxdepth, withdirs and detail.
417+
from fsspec.spec import AbstractFileSystem
418+
419+
for path in [
420+
"/data/a/f1.txt",
421+
"/data/a/f2.txt",
422+
"/data/a/b/deep.txt",
423+
"/data/a/b/c/deepest.txt",
424+
"/data/x.txt",
425+
"/data/y/z.txt",
426+
"/other/o.txt",
427+
]:
428+
m.pipe_file(path, b"hello")
429+
m.mkdir("/data/emptydir") # empty (pseudo) directory
430+
m.mkdir("/data/a/b/emptysub")
431+
432+
for root in ["", "/data", "/data/a", "/data/a/b", "/data/x.txt", "/nope"]:
433+
for maxdepth in [None, 1, 2, 3]:
434+
for withdirs in [False, True]:
435+
for detail in [False, True]:
436+
got = m.find(
437+
root, maxdepth=maxdepth, withdirs=withdirs, detail=detail
438+
)
439+
expected = AbstractFileSystem.find(
440+
m, root, maxdepth=maxdepth, withdirs=withdirs, detail=detail
441+
)
442+
assert got == expected, (root, maxdepth, withdirs, detail)
443+
444+
445+
def test_find_snapshots_store_before_iterating(m):
446+
# `store` is a class attribute shared by every MemoryFileSystem instance, so
447+
# another instance can add or remove a path while find() is walking it.
448+
# ls() iterates over a snapshot for this reason; find() must too, or it dies
449+
# with "dictionary changed size during iteration".
450+
for f in range(5):
451+
m.pipe_file(f"/data/file{f}.txt", b"x")
452+
453+
class MutatesStoreOnRead:
454+
"""Stands in for a real entry, but writes to the store when read.
455+
456+
Reading ``size`` happens inside find()'s loop, so this reproduces a
457+
concurrent write landing mid-iteration without needing a second thread.
458+
"""
459+
460+
def __init__(self, real, store):
461+
self._real = real
462+
self._store = store
463+
self._fired = False
464+
465+
@property
466+
def created(self):
467+
return self._real.created
468+
469+
@property
470+
def size(self):
471+
if not self._fired:
472+
self._fired = True
473+
self._store["/data/concurrent.txt"] = self._real
474+
return self._real.size
475+
476+
real = m.store["/data/file0.txt"]
477+
m.store["/data/file0.txt"] = MutatesStoreOnRead(real, m.store)
478+
479+
out = m.find("/data")
480+
481+
# The snapshot is taken before the concurrent write, so the new path is not
482+
# part of this result; the point is that find() completes instead of raising.
483+
assert "/data/file4.txt" in out
484+
assert len(out) == 5
485+
486+
487+
def test_find_does_not_scan_per_directory(m):
488+
# Regression guard: the old find() called ls() once per directory and each
489+
# ls() re-scanned the whole (global) store, giving O(n_dirs * n_files) work.
490+
# The single-pass implementation must not call ls() at all, so total work
491+
# stays O(n_files) regardless of how many directories there are.
492+
from unittest import mock
493+
494+
for d in range(20):
495+
for f in range(5):
496+
m.pipe_file(f"/data/dir{d}/file{f}.txt", b"x")
497+
498+
with mock.patch.object(MemoryFileSystem, "ls", wraps=m.ls) as spy:
499+
out = m.find("/data")
500+
501+
assert len(out) == 100
502+
assert spy.call_count == 0

0 commit comments

Comments
 (0)