From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Arthur Miller Newsgroups: gmane.emacs.devel Subject: empty-directory predicate, native implementation Date: Tue, 13 Oct 2020 04:22:36 +0200 Message-ID: Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="24539"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Oct 13 04:38:52 2020 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kSADD-0006Jx-SP for ged-emacs-devel@m.gmane-mx.org; Tue, 13 Oct 2020 04:38:51 +0200 Original-Received: from localhost ([::1]:47128 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kSADC-0006Du-Ss for ged-emacs-devel@m.gmane-mx.org; Mon, 12 Oct 2020 22:38:50 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:48362) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kSAC9-0005nI-2u for emacs-devel@gnu.org; Mon, 12 Oct 2020 22:37:45 -0400 Original-Received: from mail-db8eur05olkn2048.outbound.protection.outlook.com ([40.92.89.48]:4448 helo=EUR05-DB8-obe.outbound.protection.outlook.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kSAC6-0002io-D0 for emacs-devel@gnu.org; Mon, 12 Oct 2020 22:37:44 -0400 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=di2TZ6sFNNh6zWsKwafJAUTjWC57i8y0GEdhjaAkleCthgfXbD/OxHDOXKisYm4gE8D4XOB1RzsYt5TRnpCi8uYmddxrjdxzXRCclwGPxzf6hyNOceOSZCFa7fYT2jkc2d7shmJRFlzOWoXe3Bt5JSLikZNL/icDbIeu6MmmdfmhT4wVp3ovrP9AB/FVv1KaGIQJxoLnMbquNC4XbSCqXmMmGy7UqWMyhwr2Bi2BFRTCyRMwDcWWQEG9KOobgeu3bkSLzfIvef5zVIm73w7/qt4wlpmTDKq2sZF2YB26F2qOP1k3deo9KwFC/uyLlm6uem6iCrSaNsAKkbdBxj56eg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=kRC6gwsNyW0yYnLxSzw+WYyh8EnVy1ziFZkgaH7W640=; b=hTJPiilr2S77bMM+GUjCvjCDhDVNAGUzm2cCw2uNPzI652kq8Au+LQ7FRsZL3mmbC5QtgJQiKMjTF3kGDbLxoGfdPikaLuwCa8mYvJMD+FzXvNWDRAtmZz5AtFs7HH1I740Wn8eSFb0iy0kAOt+qodthRB+E5+v8Ebzbqw77EHZAln2zgXMg/cBtDzESrNoBy97ihijyQj8y1EHzGlJ33R/PEAPkLSW58OaPK5HkK9tJdRAXL6QnLl1X2DekSQGblQWIY9kYKC8Z4hJJ41obpQikzaDCA2J6JliCSXODXSVebGDPBIP/WPsIEWOB1spNYzWtNxXbi7lOlT97a7b3Fw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=live.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=kRC6gwsNyW0yYnLxSzw+WYyh8EnVy1ziFZkgaH7W640=; b=TGknDVZoqyh4CdB9CKEDSqOrBOqhabLpShBaFnZdyOB5G4hiJvsjwvVGokJfsAWbo6oMQUHeQK/I64uC9lxiYpv1m5I0qB507dhmoHhxdvh3V+q62h3gGVXUVG/aX8XtkTnE38+TWoiFxUe0szcAbsxgZU3KI0WHATKpuN0eNuto/MF58jbmNaLfWG6tjzqZSslkKUq4EHi0X7/PTuIv66OdyYeABzRhW0A+Q49CE0nA8H5qWyi9vMlw5fN0jJltyKQF2Zp0GAvDSJdlhworbY8IkOGy8t+8rTutUB77AGsiwT7lcIOAMdgeEVhhlGgvu1At60VcudTchL+gepm42Q== Original-Received: from DB8EUR05FT018.eop-eur05.prod.protection.outlook.com (2a01:111:e400:fc0f::51) by DB8EUR05HT061.eop-eur05.prod.protection.outlook.com (2a01:111:e400:fc0f::250) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3455.23; Tue, 13 Oct 2020 02:22:38 +0000 Original-Received: from VI1PR06MB4526.eurprd06.prod.outlook.com (2a01:111:e400:fc0f::52) by DB8EUR05FT018.mail.protection.outlook.com (2a01:111:e400:fc0f::63) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3455.23 via Frontend Transport; Tue, 13 Oct 2020 02:22:38 +0000 X-IncomingTopHeaderMarker: OriginalChecksum:7A4AF740A0B5DFCC0173AAABDC3CA5F4E062CDF2AA3D95F0A09DFA82CADAE985; UpperCasedChecksum:66223B3B883A7DEA1886280DB2A8AB3499EC30D1BB09D4D2CEF134CECC020EAC; SizeAsReceived:7212; Count:43 Original-Received: from VI1PR06MB4526.eurprd06.prod.outlook.com ([fe80::b547:51cd:16c5:4487]) by VI1PR06MB4526.eurprd06.prod.outlook.com ([fe80::b547:51cd:16c5:4487%7]) with mapi id 15.20.3455.029; Tue, 13 Oct 2020 02:22:38 +0000 X-TMN: [OpHB+L96J4tU+QlGAdrlJmvgNpZbBD+y] X-ClientProxiedBy: AM5PR04CA0026.eurprd04.prod.outlook.com (2603:10a6:206:1::39) To VI1PR06MB4526.eurprd06.prod.outlook.com (2603:10a6:803:ac::17) X-Microsoft-Original-Message-ID: <87zh4qeufn.fsf@live.com> X-MS-Exchange-MessageSentRepresentingType: 1 Original-Received: from pascal.homepc (90.230.29.56) by AM5PR04CA0026.eurprd04.prod.outlook.com (2603:10a6:206:1::39) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3455.21 via Frontend Transport; Tue, 13 Oct 2020 02:22:37 +0000 X-MS-PublicTrafficType: Email X-IncomingHeaderCount: 43 X-EOPAttributedMessage: 0 X-MS-Office365-Filtering-Correlation-Id: 957b22cc-8037-4b2c-3c9f-08d86f1eda30 X-MS-TrafficTypeDiagnostic: DB8EUR05HT061: X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: oTsO4X/CNp8tMg7xgafDfbgLu8jwRL1C+1LEtg75bmqb2fPpX3BVbZCVYjvg2SjvRkKmxSxfk4ZVt7vmO4aopCgL+PEGYMRh07FJ41hXWB7ffjCK6gqjRmyAadY5dz5HlIxbJnlGQKnOrkhg/bomPRboAmPkEUiT+AQia9zObrT1TCYHCaTExs2GQuQjarFMls+wrEABJOAHwEnP5FRgIA== X-MS-Exchange-AntiSpam-MessageData: Nc02PA/6EWIkc1LVJEODRqPR9XJflscT9I6b7km896BEPPJg+tgi0lIX8ckP4QEy39jmidAvXcuB0dsUpqjP5d0IebX7qPctvXgXOJ4oq51vmVux3178avu1W9WlSmlHUDENQgLG7sgdf5rPb9B2Kw== X-OriginatorOrg: live.com X-MS-Exchange-CrossTenant-Network-Message-Id: 957b22cc-8037-4b2c-3c9f-08d86f1eda30 X-MS-Exchange-CrossTenant-OriginalArrivalTime: 13 Oct 2020 02:22:37.9997 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-CrossTenant-AuthSource: DB8EUR05FT018.eop-eur05.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: Internet X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB8EUR05HT061 Received-SPF: pass client-ip=40.92.89.48; envelope-from=arthur.miller@live.com; helo=EUR05-DB8-obe.outbound.protection.outlook.com X-detected-operating-system: by eggs.gnu.org: First seen = 2020/10/12 22:37:40 X-ACL-Warn: Detected OS = Windows NT kernel [generic] [fuzzy] X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, MSGID_FROM_MTA_HEADER=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:257510 Archived-At: --=-=-= Content-Type: text/plain 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? --=-=-= Content-Type: text/plain Content-Disposition: attachment; filename=dired-mark-empty.el Content-Description: dired-mark-empty.el (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)) --=-=-= Content-Type: text/x-patch Content-Disposition: attachment; filename=dired.patch Content-Description: dired.patch --- 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 #include +#include #ifdef HAVE_PWD_H #include @@ -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. --=-=-=--