Patchwork [4,of,4] treemanifest: make treemanifest.matches() faster

login
register
mail settings
Submitter Drew Gottlieb
Date March 31, 2015, 10:29 p.m.
Message ID <f9aab64dc4e7009cef4b.1427840954@waste.org>
Download mbox | patch
Permalink /patch/8402/
State Accepted
Commit a2292da6d821beb0c846eafe3a1edafa22608302
Headers show

Comments

Drew Gottlieb - March 31, 2015, 10:29 p.m.
# HG changeset patch
# User Drew Gottlieb <drgott@google.com>
# Date 1427764259 25200
#      Mon Mar 30 18:10:59 2015 -0700
# Node ID f9aab64dc4e7009cef4b27e1f513bc15b2abbacc
# Parent  0a665bd18b18eb6a27e82475ad13810378637478
treemanifest: make treemanifest.matches() faster

By converting treemanifest.matches() into a recursively additivie operation,
it becomes O(n).

The old matches function made a copy of the entire manifest and deleted
files that didn't match. With tree manifests, this was an O(n log n) operation
because del() was O(log n).

This change speeds up the command
  "hg status --rev .^ 'relglob:*.js'
on the Mozilla repo, now taking 2.53s, down from 3.51s.
Martin von Zweigbergk - March 31, 2015, 10:34 p.m.
I've already reviewed this and it looks good to me.

On Tue, Mar 31, 2015 at 3:32 PM Drew Gottlieb <drgott@google.com> wrote:

> # HG changeset patch
> # User Drew Gottlieb <drgott@google.com>
> # Date 1427764259 25200
> #      Mon Mar 30 18:10:59 2015 -0700
> # Node ID f9aab64dc4e7009cef4b27e1f513bc15b2abbacc
> # Parent  0a665bd18b18eb6a27e82475ad13810378637478
> treemanifest: make treemanifest.matches() faster
>
> By converting treemanifest.matches() into a recursively additivie
> operation,
> it becomes O(n).
>
> The old matches function made a copy of the entire manifest and deleted
> files that didn't match. With tree manifests, this was an O(n log n)
> operation
> because del() was O(log n).
>
> This change speeds up the command
>   "hg status --rev .^ 'relglob:*.js'
> on the Mozilla repo, now taking 2.53s, down from 3.51s.
>
> diff --git a/mercurial/manifest.py b/mercurial/manifest.py
> --- a/mercurial/manifest.py
> +++ b/mercurial/manifest.py
> @@ -522,11 +522,28 @@
>          if match.always():
>              return self.copy()
>
> -        m = self.copy()
> -        for fn in m.keys():
> -            if not match(fn):
> -                del m[fn]
> -        return m
> +        return self._matches(match)
> +
> +    def _matches(self, match):
> +        '''recursively generate a new manifest filtered by the match
> argument.
> +        '''
> +
> +        ret = treemanifest(self._dir)
> +
> +        for fn in self._files:
> +            fullp = self._subpath(fn)
> +            if not match(fullp):
> +                continue
> +            ret._files[fn] = self._files[fn]
> +            if fn in self._flags:
> +                ret._flags[fn] = self._flags[fn]
> +
> +        for dir, subm in self._dirs.iteritems():
> +            m = subm._matches(match)
> +            if not m._isempty():
> +                ret._dirs[dir] = m
> +
> +        return ret
>
>      def diff(self, m2, clean=False):
>          '''Finds changes between the current manifest and m2.
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
>
Matt Mackall - March 31, 2015, 10:39 p.m.
On Tue, 2015-03-31 at 17:29 -0500, Drew Gottlieb wrote:
> # HG changeset patch
> # User Drew Gottlieb <drgott@google.com>
> # Date 1427764259 25200
> #      Mon Mar 30 18:10:59 2015 -0700
> # Node ID f9aab64dc4e7009cef4b27e1f513bc15b2abbacc
> # Parent  0a665bd18b18eb6a27e82475ad13810378637478
> treemanifest: make treemanifest.matches() faster

These are queued for default, thanks.

Patch

diff --git a/mercurial/manifest.py b/mercurial/manifest.py
--- a/mercurial/manifest.py
+++ b/mercurial/manifest.py
@@ -522,11 +522,28 @@ 
         if match.always():
             return self.copy()
 
-        m = self.copy()
-        for fn in m.keys():
-            if not match(fn):
-                del m[fn]
-        return m
+        return self._matches(match)
+
+    def _matches(self, match):
+        '''recursively generate a new manifest filtered by the match argument.
+        '''
+
+        ret = treemanifest(self._dir)
+
+        for fn in self._files:
+            fullp = self._subpath(fn)
+            if not match(fullp):
+                continue
+            ret._files[fn] = self._files[fn]
+            if fn in self._flags:
+                ret._flags[fn] = self._flags[fn]
+
+        for dir, subm in self._dirs.iteritems():
+            m = subm._matches(match)
+            if not m._isempty():
+                ret._dirs[dir] = m
+
+        return ret
 
     def diff(self, m2, clean=False):
         '''Finds changes between the current manifest and m2.