Repository navigation
iglob() has misleading documentation (does indeed store names internally) #66363
Description
Activity
roysmith commented
on Aug 8, 2014 roysmithmannequinMannequinAuthorFor background, see:
https://mail.python.org/pipermail/python-list/2014-August/676291.html
In a nutshell, the iglob() docs say, "Return an iterator which yields the same values as glob() without actually storing them all simultaneously." The problem is, internally, it calls os.listdir(), which apparently *does* store the entire list internally, defeating the whole purpose of iglob()
I recognize that iglob() is not going to get fixed in 2.7, but at least the documentation should be updated to point out that it doesn't really do what it says it does. Or rather, it doesn't really not do what it says it doesn't :-)
I agree that the documentation could be improved, but it's not really *wrong*. Consider a glob like "spam/[abc]/*.txt". What iglob does is conceptually closer to:
(1) generate the list of files matching "spam/a/.txt" and yield them;
(2) generate the list of files matching "spam/b/.txt" and yield them;
(3) generate the list of files matching "spam/c/*.txt" and yield themrather than:
(1) generate the list of files matching "spam/a/.txt";
(2) append the files matching "spam/b/.txt";
(3) append the files matching "spam/c/*.txt";
(4) finally yield them(see the source code here: http://hg.python.org/cpython/file/3.4/Lib/glob.py ). I think the documentation is trying to say that iglob doesn't *always* store all the matching files, without implying that it *never* stores all the matching files. I can't think of a clean way to explain that, so a doc patch is welcome.
roysmith commented
on Aug 8, 2014 roysmithmannequinMannequinAuthorThe thread that led to this started out with the use case of a directory that had 200k files in it. If I ran iglob() on that and discovered that it had internally generated a list of all 200k names in memory at the same time, I would be pretty darn surprised, based on what the docs say now.
We're shooting for principle of least astonishment here.
roysmith commented
on Aug 8, 2014 roysmithmannequinMannequinAuthorHow about something like this:
Note: The current iglob() implementation is optimized for the case of many files distributed in a large directory tree. Internally, it iterates over the directory tree, and stores all the names from each directory at once. This will lead to pathologically inefficient behavior when any individual directory has a large number of files in it.
IMO the documentation isn't *wrong*, just misleading :)
What it is saying is that *your program* doesn't have to store the full list returned by iglob before being able to use it (ie: iglob doesn't return a list). It says nothing about what resources are used internally, other than an implied contract that there is *some* efficiency over calling glob; which, as explained above, there is. The fact that the implementation uses lots of memory if any single directory is large is then a performance bug, which can theoretically be fixed in 3.5 using scandir.
The reason iglob was introduced, if you check the revision history, is that glob used to call itself recursively for each sub-directory, which meant it held *all* of the files in *all* of the scanned tree in memory at one time. It is literally true that the difference between glob and iglob is that with iglob your program doesn't have to store the full list of matches from all subdirectories, but talking about "your program" is not something we typically do in python docs, it is implied.
Perhaps in 2.7/3.4 we can mention in the module docs that at most one directory's worth of data will be held in memory during the globbing process, but it feels a little weird to document an implementation detail like that. Still, if someone can come up with improved wording for the docs, we can add it.
Once http://bugs.python.org/issue25596 (switching glob to use scandir) is solved this issue can be closed IMO.
RogerErens commented
on Feb 16, 2018 RogerErensmannequinMannequinhttp://bugs.python.org/issue25596 has been closed...
Unfortunately bpo-25596 didn't change anything about this issue. iglob() still stores names (actually DirEntry objects) of all files in a directory before starting yielding the first of them. Otherwise we cold exceed the limit of open file descriptors.
6 remaining items
How's this going?
I am going to add the bpo-38144 feature first. Then maybe implement a dir_fd based optimization.
Sounds good.
FWIW, and totally off-topic, I find it annoying that pathlib's .glob() method supports ** in patterns, but its cousing .match() does not:
>>> p = pathlib.Path("Lib/test/support/os_helper.py") >>> p.match("Lib/**/*.py") False >>>
- added a commit that references this issue
on Apr 2, 2024 #117472 makes
iglob()less eager. It no longer stores the content of the directory if it is not needed. As result, it starts yielding results earlier (the difference depends on the directory size), but the total iteration time is increased.For example (the first line is main, the second line is the PR):
$ ./python -m timeit -s 'from glob import iglob' 'next(iglob("Lib/*.py"))' 2000 loops, best of 5: 184 usec per loop 5000 loops, best of 5: 80.1 usec per loop $ ./python -m timeit -s 'from glob import glob' 'glob("Lib/*.py")' 1000 loops, best of 5: 286 usec per loop 1000 loops, best of 5: 303 usec per loop $ ./python -m timeit -s 'from glob import iglob' 'next(iglob("Lib/*/*.py"))' 1000 loops, best of 5: 274 usec per loop 1000 loops, best of 5: 199 usec per loop $ ./python -m timeit -s 'from glob import glob' 'glob("Lib/*/*.py")' 100 loops, best of 5: 2.17 msec per loop 100 loops, best of 5: 2.22 msec per loopIt works not only with last patch component, but with last patch component containing wildcards.
$ ./python -m timeit -s 'from glob import iglob' 'next(iglob("Lib/*/__pycache__"))' 2000 loops, best of 5: 147 usec per loop 5000 loops, best of 5: 89.9 usec per loop $ ./python -m timeit -s 'from glob import glob' 'glob("Lib/*/__pycache__")' 1000 loops, best of 5: 308 usec per loop 1000 loops, best of 5: 346 usec per loop
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
Linked PRs