From mboxrd@z Thu Jan 1 00:00:00 1970 From: Christopher Baines Subject: Re: [PATCH] git-download: Speed up 'git-predicate'. Date: Mon, 19 Jun 2017 08:24:24 +0100 Message-ID: References: <20170602070833.25760-1-mail@cbaines.net> <87zidk2c4g.fsf@gnu.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="ff3dIRx967Kkvv5JqbT4uKm1bTVDE8blW" Return-path: Received: from eggs.gnu.org ([2001:4830:134:3::10]:54597) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dMr34-0000kO-QC for guix-devel@gnu.org; Mon, 19 Jun 2017 03:24:36 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dMr30-0003LZ-R3 for guix-devel@gnu.org; Mon, 19 Jun 2017 03:24:34 -0400 In-Reply-To: <87zidk2c4g.fsf@gnu.org> List-Id: "Development of GNU Guix and the GNU System distribution." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-devel-bounces+gcggd-guix-devel=m.gmane.org@gnu.org Sender: "Guix-devel" To: =?UTF-8?Q?Ludovic_Court=c3=a8s?= Cc: guix-devel@gnu.org This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --ff3dIRx967Kkvv5JqbT4uKm1bTVDE8blW Content-Type: multipart/mixed; boundary="QUw5XbaOTj6pgdRqlrcGViiPS1s2cHm2e"; protected-headers="v1" From: Christopher Baines To: =?UTF-8?Q?Ludovic_Court=c3=a8s?= Cc: guix-devel@gnu.org Message-ID: Subject: Re: [PATCH] git-download: Speed up 'git-predicate'. References: <20170602070833.25760-1-mail@cbaines.net> <87zidk2c4g.fsf@gnu.org> In-Reply-To: <87zidk2c4g.fsf@gnu.org> --QUw5XbaOTj6pgdRqlrcGViiPS1s2cHm2e Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 07/06/17 13:52, Ludovic Court=C3=A8s wrote: > Christopher Baines skribis: >=20 >> Adjust 'git-predicate' to use data structures that perform better when= used >> with git repositories with a large number of files. >> >> Previously when matching either a regular file or directory, 'git-pred= icate' >> would search a list with a length equal to the number of files in the >> repository. As a search operation happens for roughly every file in th= e >> repository, this meant that the time taken to use 'git-predicate' to t= raverse >> all the files in a repository was roughly exponential with respect to = the >> number of files in the repository. >> >> Now, for matching regular files or symlinks, 'git-predicate' uses a vh= ash >> using the inode value as the key. This should perform roughly in const= ant >> amount of time, instead of linear with respect to the number of files = in the >> repository. >> >> For matching directories, 'git-predicate' now uses a tree structure st= ored in >> association lists. To check if a directory is in the tree, the tree is= >> traversed from the root. The time complexity of this depends on the sh= ape of >> the tree, but it should be an improvement on searching through the lis= t of all >> files. >=20 > Great, more than welcome it seems. :-) >=20 > Do you know how much the inode optimization vs. the tree structure > contributes to the performance. I've got some more data. I ran the test script for smart-answers, and let it complete this time: real 97m21.291s user 120m50.400s sys 0m31.020s Just applying the inode optimization gives this result: real 90m28.116s user 100m44.784s sys 0m18.524s I'm going to assume that using the tree structure for directories makes up the rest of the difference. This will vary between repositories though, I think smart answers has a unusually large directory to file rat= io. >> * guix/git-download.scm (git-predicate): Use different data structures= to >> speed up 'git-predicate' with a large number of files. >=20 > [...] >=20 >> + (define (create-directory-tree files) >> + (define (directory-lists->tree directory-lists) >> + (map (lambda (top-level-dir) >> + (cons top-level-dir >> + (directory-lists->tree >> + (filter-map >> + (lambda (directory-list) >> + (if (eq? (length directory-list) 1) >> + #f >> + (cdr directory-list))) >> + ;; Find all the directory lists under this top-l= evel-dir >> + (filter >> + (lambda (directory-list) >> + (equal? (car directory-list) >> + top-level-dir)) >> + directory-lists))))) >> + (delete-duplicates >> + (map car directory-lists)))) >> + >> + (directory-lists->tree >> + (filter-map (lambda (path) >> + (let ((split-path (string-split path #\/))) >> + ;; If this is a file in the top of the repositor= y? >> + (if (eq? (length split-path) 1) >> + #f >> + ;; drop-right to remove the filename, as it'= s >> + ;; just the directory tree that's important >> + (drop-right (string-split path #\/) 1)))) >> + files))) >> + >> + (define (directory-in-tree? directory tree) >> + (define (directory-list-in-tree? directory-list tree) >> + (if (eq? (length directory-list) 1) >> + (list? (member (car directory-list) >> + (map car tree))) >> + (and=3D> (find (match-lambda >> + ((top-level-dir . subtree) >> + (equal? top-level-dir >> + (car directory-list)))) >> + tree) >> + (match-lambda >> + ((top-level-dir . subtree) >> + (directory-list-in-tree? (cdr directory-list) >> + subtree)))))) >> + >> + (directory-list-in-tree? (string-split directory #\/) >> + tree)) >=20 > Note that =E2=80=98length=E2=80=99 and =E2=80=98list?=E2=80=99 are O(n)= =2E I think =E2=80=98directory-in-tree?=E2=80=99 > should be written using =E2=80=98match=E2=80=99, which would avoid that= altogether. I've sent an updated patch now, and I think I've made some progress towards this. > Likewise, the (map car =E2=80=A6) call for =E2=80=98match=E2=80=99. :-= ) I'm stuck on this bit though, in the latest patch it reads: (list? (member top-directory (map car tree)) The list? call is just to turn the list or #f returned by member to #t or #f. The (map car tree) converts the tree to a list of top level directories. This bit of code is used when the last directory in the input list has been reached (e.g. when checking for foo/bar/baz top-directory would be baz) so the last check to perform is to check if baz exists at the current level of the tree. Any suggestions on restructuring this? > I find the tree implementation hard to grasp. Perhaps it would help to= > move it outside of the =E2=80=98git-predicate=E2=80=99 function and per= haps decompose it > a bit more? Thoughts? I've moved it directly above git-predicate for now. >> + (inodes-vhash (alist->vhash >> + (map >> + (lambda (file) >> + (let ((stat >> + (lstat (string-append directory "= /" file)))) >> + (cons (stat:ino stat) (stat:dev stat))= )) >> + files))) >=20 > I would call it =E2=80=98inodes=E2=80=99 simply. Also, we could use =E2= =80=98list->set=E2=80=99 from > (guix sets) here. I've made the inodes-vhash -> inodes rename, but I was undecided about using (guix sets), is there a reason you recommended it? Thnaks for your review, Chris --QUw5XbaOTj6pgdRqlrcGViiPS1s2cHm2e-- --ff3dIRx967Kkvv5JqbT4uKm1bTVDE8blW Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- iQJFBAEBCAAvFiEEPonu50WOcg2XVOCyXiijOwuE9XcFAllHfCwRHG1haWxAY2Jh aW5lcy5uZXQACgkQXiijOwuE9XcEVw//Q2UqJqE0FRMzsfNBnm/d35zOu2PZjPjp fP/A9XztZye59UTRHVCqQ+yvtYpFuLqoueOeBdNHsT0ocrNAAwOykzN3YCb0RhZj v/1tOqP1dRWSOEd9oA6CvMnMDISTh9IQIve0wETdWSODl5IW+zoToOVOHQ52Mlu4 xU7Oiuo0+Pikbl2KJMphOsgBFfk0LH4gAcMCUkfZsnc0s83BWizHwO33pbgo7+HT nUaYMwFfEHU0mw5qhchPCvgr6pL04/sIYyJh1gflvmmA1pF46wvTOvpRNEhOTN2v u0yuiKZmMwazF0HeQky5zw7VU+HRO+cdOiEza5AO7H7BO/b8j4zvTeWk3QNmvuFU mIoonuCy7QKRK73YX/DgsHUQ8ZgxTB4+saEUgYTFLocL8SqliFjQ4pejpiD8i8+0 NbaAdS5SXC0/YjP9ZBjLkblgMtBVsExmPRZUOgoCzvAdxZsbI7Nmg4VH5LHUCr9N a6VR+XicgK2ZEJdrNi0v17MFN5UKKhAuDinKo+1UKiWv/Srs0NNRNXqyIbCKZFH5 v4NrhRbEoDiLSnjsqEcxCLzApDQFuk1Qb61pHSKxxJvjPwp3i2gf3U/N2sesbaAG pqaPqUrda8YHz3gy684s+Oe27m7kVDruASdcc+B8eYzUpozMKXlW6XoPsa7or7co 92DsWO4nva0= =iOG1 -----END PGP SIGNATURE----- --ff3dIRx967Kkvv5JqbT4uKm1bTVDE8blW--