empty-directory predicate, native implementation

[Arthur Miller <arthur.miller@live.com>]

[-- Attachment #1: Type: text/plain, Size: 1704 bytes --]

It is easy to check for an empty dir in elisp; we can just list files
and check if there is a list or not:

  (null (directory-files directory-name nil nodots t)))

where nodots is just regex to omit dot files (from dired+).

But then this is quite inneficient. We are listing all files in each
dir since directory-files will return entire content of directory. Also
we are matching every filename to a regex just to eliminate first two.
Alternative would be to take length and see if it is > 2; but then we
would iterate whole list twice. So I can't see anything avialable in
dired/elisp and I think a predicate implemented in low-level is better solution.
We are really interested just to see if there is some file; so we can
just open dir, and read first few entries, if there is more then 2 files
(. and .. on *nix) we can just abort and return true.

I have tested an idea with getdents (Linux syscall) and I can see
difference. Attached is a patch for dired.c and a test file to play with
some benchmark.

In somewhat synthetic test where I just looped a "lisp" and "native"
predicate over a several hundred directories, I can see quite drammatic
difference in performance. On a directory with something about ~800
subdirs, native prediate takes ~0.002s while lisp predicate goes in ~0.01s.

I have made also a small test to mark empty dirs in dired, and there I
see some difference. On same directory, I get consistently
~2.4s for lisp version and ~2s for native version.

This isn't any kind of drammatic difference for most use; file I/O
is dominated by disk access anyway, but i still don't like to spend cpu
on unnecessary evaluations, so I wonder if we could get native predicate
in elisp? 


[-- Attachment #2: dired-mark-empty.el --]
[-- Type: text/plain, Size: 2175 bytes --]

(require 'dired)

(defvar nodots "^\\([^.]\\|\\.\\([^.]\\|\\..\\)\\).*")

(defun dired-go-to-first ()
    (interactive)
    (goto-char (point-min))
    (dired-next-line 1)
    (skip-chars-forward " \n\t"))

(defun dired-go-to-last ()
    (interactive)
    (goto-char (point-max))
    (dired-next-line -1)
    (skip-chars-forward " \n\t"))

(defun dired-is-empty-p (directory-name)
  (null (directory-files directory-name nil nodots t)))

(defun directory-number-files (directory-name &optional omit-filter)
  (length (directory-files directory-name nil omit-filter t)))

(defun dired-mark-empty-dirs ()
  (interactive)
  (when (equal major-mode 'dired-mode)
    (let ((curr-dir))
      (save-excursion
        (dired-go-to-first)
        
        (while (not (eobp))
          (setq curr-dir (dired-file-name-at-point))
          (cond ((or (null curr-dir)
                     (string= curr-dir ".")
                     (string= curr-dir ".."))
                     ;; do nothing here
                 )
                ((file-directory-p curr-dir)
                 (when (dired-is-empty-p curr-dir)
                   (dired-mark 1)
                   (dired-previous-line 1))))
          (dired-next-line 1))))))

(defun dired-mark-empty-dirs-native ()
  (interactive)
  (when (equal major-mode 'dired-mode)
    (let ((curr-dir))
      (save-excursion
        (dired-go-to-first)
        
        (while (not (eobp))
          (setq curr-dir (dired-file-name-at-point))
          (cond ((or (null curr-dir)
                     (string= curr-dir ".")
                     (string= curr-dir ".."))
                     ;; do nothing here
                 )
                ((file-directory-p curr-dir)
                 (when (directory-empty-p curr-dir)
                   (dired-mark 1)
                   (dired-previous-line 1))))
          (dired-next-line 1))))))

;;(benchmark-run-compiled 10 (directory-empty-p "/some/directory/here"))
;;(benchmark-run-compiled 10 (dired-is-empty-p "/some/directory/here"))

;; must be in some dired buffer for this
;;(benchmark-run-compiled 10 (dired-mark-empty-dirs))
;;(benchmark-run-compiled 10 (dired-mark-empty-dirs-native))

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: dired.patch --]
[-- Type: text/x-patch, Size: 2749 bytes --]

--- src/dired.c	2020-10-13 04:08:36.028838472 +0200
+++ ../dired.c	2020-10-13 04:07:48.374572510 +0200
@@ -21,6 +21,7 @@
 #include <config.h>
 
 #include <sys/stat.h>
+#include <sys/syscall.h>
 
 #ifdef HAVE_PWD_H
 #include <pwd.h>
@@ -39,6 +40,7 @@
 #include "systime.h"
 #include "buffer.h"
 #include "coding.h"
+#include "blockinput.h"
 
 #ifdef MSDOS
 #include "msdos.h"	/* for fstatat */
@@ -929,7 +931,7 @@
   struct stat s;
 
   /* An array to hold the mode string generated by filemodestring,
-     including its terminating space and null byte.  */
+     including its terminating space and NUL byte.  */
   char modes[sizeof "-rwxr-xr-x "];
 
   char *uname = NULL, *gname = NULL;
@@ -1078,6 +1080,50 @@
   return groups;
 }
 
+typedef struct dirent* pdirent;
+DEFUN ("directory-empty-p", Fdirectory_empty_p,
+       Sdirectory_empty_p, 1, 1, 0,
+       doc: /* Returns t if directory DIRNAME does not contain any
+       user files (special files . and .. are excluded
+       automatically), nil otherwise. */)
+(Lisp_Object dirname)
+{
+        #define BSIZE 1024
+        char buf[BSIZE];
+        const char* name;
+        int fd, n = 0, p = 0, c = 0;
+        pdirent d;
+
+        if(!STRINGP(dirname))
+                error("Directory name not a string object.");
+        
+        dirname = Fexpand_file_name(dirname, Qnil);
+        name = SSDATA(dirname);
+
+        fd = open (name, O_RDONLY | O_DIRECTORY);
+
+        if( fd == -1 )
+                error("Can't open directory.");
+
+        //block_input();
+        /* 32-bit version of getdents should be good enough;
+           we are just looking at first 3 files*/
+        n = syscall(SYS_getdents,fd,buf, BSIZE);
+        if(n == -1)
+                error("Can't read directory data.");
+
+        while(p < n && c < 3) {
+                d = (pdirent) (buf + p);
+                p += d->d_reclen;
+                c++;
+        }
+        //unblock_input();
+        
+        close(fd);
+        return (c > 2) ? Qnil : Qt;
+}
+
+
 void
 syms_of_dired (void)
 {
@@ -1089,7 +1135,8 @@
   DEFSYM (Qfile_attributes_lessp, "file-attributes-lessp");
   DEFSYM (Qdefault_directory, "default-directory");
   DEFSYM (Qdecomposed_characters, "decomposed-characters");
-
+  DEFSYM (Qdirectory_empty_p, "directory-empty-p")
+          
   defsubr (&Sdirectory_files);
   defsubr (&Sdirectory_files_and_attributes);
   defsubr (&Sfile_name_completion);
@@ -1098,6 +1145,7 @@
   defsubr (&Sfile_attributes_lessp);
   defsubr (&Ssystem_users);
   defsubr (&Ssystem_groups);
+  defsubr (&Sdirectory_empty_p);
 
   DEFVAR_LISP ("completion-ignored-extensions", Vcompletion_ignored_extensions,
 	       doc: /* Completion ignores file names ending in any string in this list.