Dmitry Gutov <dmitry@gutov.dev> writes:

>> (my-bench 10 "/usr/src/linux/" "")
>> 
>> (("built-in" . "Elapsed time: 7.034326s (3.598539s in 14 GCs)")
>>   ("built-in no filename handler alist" . "Elapsed time: 5.907194s (3.698456s in 15 GCs)")
>>   ("with-find" . "Elapsed time: 6.078056s (4.052791s in 16 GCs)")
>>   ("with-find-p" . "Elapsed time: 4.496762s (2.739565s in 11 GCs)")
>>   ("with-find-sync" . "Elapsed time: 3.702760s (1.715160s in 7 GCs)"))
>
> Thanks, for the extra data point in particular. Easy to see how it 
> compares to the most efficient use of 'find', right (on GNU/Linix, at 
> least)?
>
> It's also something to note that, GC-wise, numbers 1 and 2 are not the 
> worst: the time must be spent somewhere else.

Indeed. I did more detailed analysis in
https://yhetil.org/emacs-devel/87cz0p2xlc.fsf@localhost/

Main contributors in the lisp versions are (in the order from most
significant to less significant) (1) file name handlers; (2) regexp
matching of the file names; (3) nconc calls in the current
`directory-files-recursively' implementation.

I have modified `directory-files-recursively' to avoid O(N^2) `nconc'
calls + bypassing regexp matches when REGEXP is nil.

Here are the results (using the attached modified version of your
benchmark file):

(my-bench 10 "/usr/src/linux/" "")
(("built-in" . "Elapsed time: 7.285597s (3.853368s in 6 GCs)")
 ("built-in no filename handler alist" . "Elapsed time: 5.855019s (3.760662s in 6 GCs)")
 ("built-in non-recursive no filename handler alist" . "Elapsed time: 5.817639s (4.326945s in 7 GCs)")
 ("built-in non-recursive no filename handler alist + skip re-match" . "Elapsed time: 2.708306s (1.871665s in 3 GCs)")
 ("with-find" . "Elapsed time: 6.082200s (4.262830s in 7 GCs)")
 ("with-find-p" . "Elapsed time: 4.325503s (3.058647s in 5 GCs)")
 ("with-find-sync" . "Elapsed time: 3.267648s (1.903655s in 3 GCs)"))

 (let ((gc-cons-threshold most-positive-fixnum))
   (my-bench 10 "/usr/src/linux/" ""))
(("built-in" . "Elapsed time: 2.754473s")
 ("built-in no filename handler alist" . "Elapsed time: 1.322443s")
 ("built-in non-recursive no filename handler alist" . "Elapsed time: 1.235044s")
 ("built-in non-recursive no filename handler alist + skip re-match" . "Elapsed time: 0.750275s")
 ("with-find" . "Elapsed time: 1.438510s")
 ("with-find-p" . "Elapsed time: 1.200876s")
 ("with-find-sync" . "Elapsed time: 1.349755s"))

If we forget about GC, Elisp version can get fairly close to GNU find.
And if we do not perform regexp matching (which makes sense when the
REGEXP is ""), Elisp version is faster.