subversion-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From stef...@apache.org
Subject svn commit: r1340874 - /subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c
Date Mon, 21 May 2012 00:14:20 GMT
Author: stefan2
Date: Mon May 21 00:14:20 2012
New Revision: 1340874

URL: http://svn.apache.org/viewvc?rev=1340874&view=rev
Log:
For large commits that contain deletions, fetch_all_changes
dominates the commit performance because it uses an O(n^2)
to eliminate sub-path changes to deleted nodes.

Since switching to an O(n log n) implementation is non-trivial,
the next best thing is to minimize the operations within the
inner loop.

* subversion/libsvn_fs_fs/fs_fs.c
  (fetch_all_changes): tune

Modified:
    subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c

Modified: subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c?rev=1340874&r1=1340873&r2=1340874&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/fs_fs.c Mon May 21 00:14:20 2012
@@ -4851,20 +4851,30 @@ fetch_all_changes(apr_hash_t *changed_pa
         {
           apr_hash_index_t *hi;
 
+          /* a potential child path must contain at least 2 more chars
+             (the path separator plus at least one char for the name)
+          */
+          apr_ssize_t min_child_len = strlen(change->path) + 2;
+
+          /* CAUTION: This is the inner loop of an O(n^2) algorithm.
+             The number of changes to process may be >> 1000.
+             Therefore, keep the inner loop as tight as possible.
+          */
           for (hi = apr_hash_first(iterpool, changed_paths);
                hi;
                hi = apr_hash_next(hi))
             {
               /* KEY is the path. */
-              const char *path = svn__apr_hash_index_key(hi);
-              apr_ssize_t klen = svn__apr_hash_index_klen(hi);
-
-              /* If we come across our own path, ignore it. */
-              if (strcmp(change->path, path) == 0)
-                continue;
-
-              /* If we come across a child of our path, remove it. */
-              if (svn_dirent_is_child(change->path, path, iterpool))
+              const char *path;
+              apr_ssize_t klen;
+              apr_hash_this(hi, (const void **)&path, &klen, NULL);
+
+              /* If we come across a child of our path, remove it.
+                 Call svn_dirent_is_child only if there is a chance that
+                 this is actually a sub-path.
+               */
+              if (   klen >= min_child_len
+                  && svn_dirent_is_child(change->path, path, iterpool))
                 apr_hash_set(changed_paths, path, klen, NULL);
             }
         }



Mime
View raw message