On 07/06/17 13:52, Ludovic Courtès wrote: > Christopher Baines <[email protected]> skribis: > >> 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. > > Great, more than welcome it seems. :-) > > Do you know how much the inode optimization vs. the tree structure > contributes to the performance.
I'll find out the actual times for without both optimizations, and with just one of them and get back to you. >> * guix/git-download.scm (git-predicate): Use different data structures to >> speed up 'git-predicate' with a large number of files. > > [...] > >> + (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-level-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 repository? >> + (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=> (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)) > > Note that ‘length’ and ‘list?’ are O(n). I think ‘directory-in-tree?’ > should be written using ‘match’, which would avoid that altogether. > Likewise, the (map car …) call for ‘match’. :-) That's interesting about length and list, I'll give using match a go and send another patch. > I find the tree implementation hard to grasp. Perhaps it would help to > move it outside of the ‘git-predicate’ function and perhaps decompose it > a bit more? Thoughts? Yeah, the create-directory-tree and directory-in-tree? functions are both general purpose, would you suggest this module, or somewhere else? >> + (inodes-vhash (alist->vhash >> + (map >> + (lambda (file) >> + (let ((stat >> + (lstat (string-append directory "/" >> file)))) >> + (cons (stat:ino stat) (stat:dev stat)))) >> + files))) > > I would call it ‘inodes’ simply. Also, we could use ‘list->set’ from > (guix sets) here. Ah, cool, I'll have a look at sending a updated patch shortly.
signature.asc
Description: OpenPGP digital signature
