2

I want to get in a huge directory the first file which satisfies some condition, something like

(require 'seq)
(require 'f)


(defun lazy-filter-file (pred path)
  (car (seq-filter pred (f--files path t))))

(setq fake-filter-file-fn (lambda (x) x))
(lazy-filter-file fake-filter-file-fn path)

And I want to know whether f--files will walk the whole directory, or just find the first file which satisfied the condition and stops. And can you also explain why?

If not lazy, how can I make it lazy?

4

The question misses the point. Sure, suppose you do (car huge-list), the evaluator will eval huge-list by checking for its type, finding that it's a symbol, looking it up in the environment and returning the bound value (a list object that has been created earlier). However, by that point the huge list has already been generated. Evaluating it over and over again won't change anything about this fact. Even if we were evaluating a list literal, we'd just get a pointer back to the object that was created at read time. (car (huge-list)) isn't much different, here car would get a Lisp object and evaluating it will return it unchanged.

The point of lazy data structures is deferring the creation of the huge list as long as possible. What you really want is a function that when given a directory, produces one directory item at a time, allowing you to stop early. Unfortunately such a thing doesn't exist. The closest thing to this is the readdir function in C which isn't directly exposed to users, directory-files (used by f--files and everything else) is using it to create the full list. The only thing you can do to limit this list is using the match argument to only list files matching the given regular expression. Or write an Emacs module that gives you readdir. If you're absolutely sure it's a performance issue (have you proven it by measuring?), you know what to do...

  • Thank you very much, for explaining so carefully. Can you give me some further advice for how to create lazy list in Emacs Lisp? – cmal Sep 30 '18 at 6:59
  • 3
    C-h i g (elisp)Generators – phils Sep 30 '18 at 7:35
2

The Lisp interpreter always evaluates the arguments before it passes them to the function you're calling, so the answer is that yes, the entire list will be generated first, and then car will select the first element of it.

This may or may not be a performance problem. If the test you're doing on each file name is expensive, then you might want to go to some effort to avoid it. However, in most cases, it's not any more work to get all of the file names from a directory listing than it is to get just the first one.

Most of the time, however, it's not a performance problem. Imagine that the directory list is just a normal text file containing all of the file names. Files on your disk are stored in 4 KB blocks, and any read at the beginning of the file has to request at least one whole block. This will frequently give you the whole list of names, unless that list is pretty long. Additionally, your operating system knows that if you're reading one block of the file then you're very likely to want to read the next few blocks as well. It will generally extend any read that you do to pre-fetch the next few blocks. Finally, there is a certain round-trip time that you will have to wait any time you ask for blocks from a disk. You pay that same cost whether you asked for one block or many sequential blocks. It is therefore much more cost-effective to read many sequential blocks at once than it is to read one block at a time. This is still true even if the disk is an SSD and not a mechanical disk. All of this together means that it is usually fastest to read the whole directory list even if sometimes you only want the first entry.

  • This is one of the reasons why lazy sequences in languages like Clojure use chunking internally. The core machinery fetches a chunk of values if needed, the higher-level functions fetch the next unread item from that chunk. – wasamasa Sep 30 '18 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.