summary refs log tree commit diff
path: root/gnu/packages/sssd.scm
diff options
context:
space:
mode:
authorChristopher Baines <mail@cbaines.net>2017-06-19 08:14:43 +0100
committerLudovic Courtès <ludo@gnu.org>2017-07-25 23:24:16 +0200
commitf135b4ae8397d2c501150d3ead3e0603e770ce3f (patch)
treee28318a7a29db971d289f78d716ec73adbd78818 /gnu/packages/sssd.scm
parent84620dd0c4f8f96cfdafb9a3ce8cce5d36a52b03 (diff)
downloadguix-f135b4ae8397d2c501150d3ead3e0603e770ce3f.tar.gz
git-download: Speed up 'git-predicate'.
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-predicate'
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 the
repository, this meant that the time taken to use 'git-predicate' to traverse
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 vhash
using the inode value as the key. This should perform roughly in constant
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 stored 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 shape of
the tree, but it should be an improvement on searching through the list of all
files.

* guix/git-download.scm (files->directory-tree, directory-in-tree?): New
procedures.
(git-predicate): Compute DIRECTORY-TREE.  Turn INODES into a vhash.
Adjust body of lambda accordingly.

Co-authored-by: Ludovic Courtès <ludo@gnu.org>
Diffstat (limited to 'gnu/packages/sssd.scm')
0 files changed, 0 insertions, 0 deletions