code review 6337043: cmd/go: do not scan whole tree on prefix match

cmd/go: do not scan whole tree on prefix match

A command such as

    go install some.site/some/pkg/...

Currently takes more than 30 seconds to execute in
my machine as it scans the whole $GOPATH/src tree.
With this change it takes 0.1s.

[niemeyer, 2012-06-21 19:22:10]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://go.googlecode.com/hg/

[r, 2012-07-09 22:19:50]

http://codereview.appspot.com/6337043/diff/7001/src/cmd/go/main.go
File src/cmd/go/main.go (right):

http://codereview.appspot.com/6337043/diff/7001/src/cmd/go/main.go#newcode442
src/cmd/go/main.go:442: // Avoid scanning the whole tree if we know where to
look at.
s/ at//
or maybe
Avoid scanning the whole tree if we have a literal prefix to the pattern.

but in any case this smells funny to me. surely if there's no "..." i can do
something fast, but this only does something fast if there *is* a "...". please
explain

[niemeyer, 2012-07-09 22:44:29]

http://codereview.appspot.com/6337043/diff/7001/src/cmd/go/main.go
File src/cmd/go/main.go (right):

http://codereview.appspot.com/6337043/diff/7001/src/cmd/go/main.go#newcode442
src/cmd/go/main.go:442: // Avoid scanning the whole tree if we know where to
look at.
On 2012/07/09 22:19:50, r wrote:
> but in any case this smells funny to me. surely if there's no "..." i can do
> something fast, but this only does something fast if there *is* a "...".
please
> explain

This function runs in three situations: patterns, "all", and "std", with the
latter two being special tokens. We can't speed up "all", "std" was already
handled specially below. This is handling the missing case.

I'll replace the text by your suggestion.

[niemeyer, 2012-07-17 02:51:23]

Hello golang-dev@googlegroups.com, r@golang.org (cc:
golang-dev@googlegroups.com),

Please take another look.

[r, 2012-07-17 03:44:47]

LGTM but let rsc sign off too

[rsc, 2012-07-29 22:48:02]

This doesn't seem right. It handles one important case, but it's not general
enough. What you really want is inside the body, where the other SkipDir cases
are, to have

if !childrenCanMatch(name, pattern) {
    return filepath.SkipDir
}

That would require writing that function, but maybe you could put it in with

func childrenCanMatch(name, pattern string) {
    // TODO: Write less conservative implementation to speed scan.
    return true
}

474 or so says
_, err = build.ImportDir(path, 0)
if err != nil ... { ... }
if match(name) {
    pkgs = append(pkgs, name)
}

It seems reasonable to invert this so that we don't ImportDir on packages we
won't keep:

if !match(name) {
    return nil
}
_, err = build.ImportDir(path, 0)
...

I think that alone will get your 0.1 second speedup, and then we can leave the
full implementation of childrenCanMatch for future work.
474                         _, err = build.ImportDir(path, 0)
 468                         if err != nil && strings.Contains(err.Error(), "no
Go source files") {	 475                         if err != nil &&
strings.Contains(err.Error(), "no Go source files") {
 469                                 return nil	 476                            
    return nil
 470                         }	 477                         }
 471                         if match(name) {	 478                         if
match(name) {
 472                                 pkgs = append(pkgs, name)	 479             
                   pkgs = append(pkgs, name)
 473                         }	 480                         }
 474                         return nil

http://codereview.appspot.com/6337043/diff/15001/src/cmd/go/main.go
File src/cmd/go/main.go (right):

http://codereview.appspot.com/6337043/diff/15001/src/cmd/go/main.go#newcode445
src/cmd/go/main.go:445: prefix, _ = path.Split(pattern[:i])
What if pattern is "x..." ?

[rsc, 2012-07-29 22:48:19]

Ignore the garbage at the bottom of my reply.

[niemeyer, 2012-07-30 05:53:30]

On 2012/07/29 22:48:02, rsc wrote:
> This doesn't seem right. It handles one important case, but it's not general
> enough. What you really want is inside the body, where the other SkipDir cases
> are, to have
(...)
> func childrenCanMatch(name, pattern string) {
>     // TODO: Write less conservative implementation to speed scan.
>     return true
> }

Adding a dummy function that does nothing won't prevent scanning huge trees. The
change I'm suggesting is trivial and works. Once you want to generalize the
suggested logic, it won't be any more expensive to do so.

For these reasons, I disagree with your suggestion.

http://codereview.appspot.com/6337043/diff/15001/src/cmd/go/main.go
File src/cmd/go/main.go (right):

http://codereview.appspot.com/6337043/diff/15001/src/cmd/go/main.go#newcode445
src/cmd/go/main.go:445: prefix, _ = path.Split(pattern[:i])
On 2012/07/29 22:48:02, rsc wrote:
> What if pattern is "x..." ?

prefix will be "", which should work.

[rsc, 2012-08-03 18:24:43]

On 2012/07/30 05:53:30, niemeyer wrote:
> On 2012/07/29 22:48:02, rsc wrote:
> > This doesn't seem right. It handles one important case, but it's not general
> > enough. What you really want is inside the body, where the other SkipDir
cases
> > are, to have
> (...)
> > func childrenCanMatch(name, pattern string) {
> >     // TODO: Write less conservative implementation to speed scan.
> >     return true
> > }
> 
> Adding a dummy function that does nothing won't prevent scanning huge trees.
The
> change I'm suggesting is trivial and works. Once you want to generalize the
> suggested logic, it won't be any more expensive to do so.

Did you try this:

474 or so says
_, err = build.ImportDir(path, 0)
if err != nil ... { ... }
if match(name) {
    pkgs = append(pkgs, name)
}

It seems reasonable to invert this so that we don't ImportDir on packages we
won't keep:

if !match(name) {
    return nil
}
_, err = build.ImportDir(path, 0)
...

That should have a huge impact, since we won't read Go files that can only be
part of packages we don't care about.

[rsc, 2012-08-31 19:59:17]

Gustavo, I think this is in your court.

[niemeyer, 2012-08-31 21:51:48]

On 2012/08/31 19:59:17, rsc wrote:
> Gustavo, I think this is in your court.

Cheers, I'll try to get back to this over the weekend. Things have been a bit
crazy over here, sorry for the lag.

[niemeyer, 2013-04-08 18:27:27]

*** Abandoned ***

[niemeyer, 2013-04-08 18:29:33]

For the record, the approach suggested by Russ is already in. Hopefully it
solves the problem this change intended to address.

[albert.strasheim, 2013-04-08 21:31:37]

Is this about

https://groups.google.com/d/topic/golang-nuts/muDHV2yx6VA/discussion

?

Not quite sure it's fixed if there's still extra system calls being made?