diff options
author | Christopher Baines <mail@cbaines.net> | 2017-06-19 08:14:43 +0100 |
---|---|---|
committer | Ludovic Courtès <ludo@gnu.org> | 2017-07-25 23:24:16 +0200 |
commit | f135b4ae8397d2c501150d3ead3e0603e770ce3f (patch) | |
tree | e28318a7a29db971d289f78d716ec73adbd78818 /gnu/packages/sssd.scm | |
parent | 84620dd0c4f8f96cfdafb9a3ce8cce5d36a52b03 (diff) | |
download | guix-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