Improve the performance of isWithin().

Improve the performance of isWithin().

This adds a single-pass fast path function that only bails when it
encounters "." or ".." components in one path but not the other.

This brings isWithin() from about 0.008 iterations/us to about 0.0180 by
the repo's benchmark. It makes it about 11.5x faster on data provided by
@scheglov (see below), which consists of absolute paths that mostly do
not contain one another.

Data: https://github.com/dart-lang/path/issues/7#issuecomment-157856146

Closes #7

R=rnystrom@google.com

Committed: https://github.com/dart-lang/path/commit/e6b55472da7bfcfcc20db163abadfbd7689dd23c

[Bob Nystrom, 2015-11-24 17:22:13]

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart
File lib/src/context.dart (right):

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:542: bool _isWithinFast(String parent, String child) {
Possibly dumb question. How much mileage would we get out of:

bool _isWithinReallFast(String parent, String child) {
  // Child path literally contain the parent.
  if (!child.startsWith(parent)) return null;

  // And not possibly walk back out of the parent.
  if (child.contains("..", parent.length)) return null;

  return true;
}

Are there cases where that gives a false positive? If not, I think this will hit
the very common case with things like Directory.list() where your paths all do
have the same prefix.

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:702: int _checkRemainder(List<int> codeUnits, int index) {
How about _pathDirection()? Something other than "check", which is vague, would
be nice.

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:754: }
Instead of a for loop with a sort of state machine approach to track what you've
read, I think it may be clearer to write this more like an eager lexer that
matches and advances. Something like:

    var i = index;
    while (i < codeUnits.length) {
      // Read the next path component.
      var start = i;
      while (i < codeUnits.length && !style.isSeparator(codeUnits[i])) {
        i++;
      }

      // If we're at the end, stop.
      if (i == codeUnits.length) break;

      // See if the path component is ".", "..", or a name.
      if (i - start == 1 && codeUnits[start] == chars.PERIOD) {
        // Don't change the depth.
      } else if (i - start == 2 &&
          codeUnits[start] == chars.PERIOD &&
          codeUnits[start + 1] == chars.PERIOD) {
        // ".." backs out a directory.
        depth--;

        // If we work back to the root, stop.
        if (depth <= 0) break;
      } else {
        // Step inside a directory.
        depth++;
      }

      // Ignore doubled separators.
      while (i < codeUnits.length && style.isSeparator(codeUnits[i])) {
        i++;
      }
    }

    return depth;

(I haven't tested this at all.)

What do you think?

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:757: // to account for the current component. We have to do
this because depth is counted
Long line.

[Bob Nystrom, 2015-11-24 17:25:32]

Also: benchmark and numbers?

[nweiz, 2015-12-01 00:15:08]

Description was changed from

==========
Improve the performance of isWithin().

This adds a single-pass fast path function that only bails when it
encounters "." or ".." components in one path but not the other.
According to my measurements using data provided by @scheglov, it makes
isWithin() about 11.5x faster.

Data: https://github.com/dart-lang/path/issues/7#issuecomment-157856146

Closes #7

R=rnystrom@google.com
==========

to

==========
Improve the performance of isWithin().

This adds a single-pass fast path function that only bails when it
encounters "." or ".." components in one path but not the other.

This brings isWithin() from about 0.008 iterations/us to about 0.0180 by
the repo's benchmark. It makes it about 11.5x faster on data provided by
@scheglov (see below), which consists of absolute paths that mostly do
not contain one another.

Data: https://github.com/dart-lang/path/issues/7#issuecomment-157856146

Closes #7

R=rnystrom@google.com
==========

[nweiz, 2015-12-01 00:15:15]

> Also: benchmark and numbers?

Done.

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart
File lib/src/context.dart (right):

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:542: bool _isWithinFast(String parent, String child) {
On 2015/11/24 17:22:13, Bob Nystrom wrote:
> Possibly dumb question. How much mileage would we get out of:
> 
> bool _isWithinReallFast(String parent, String child) {
>   // Child path literally contain the parent.
>   if (!child.startsWith(parent)) return null;
> 
>   // And not possibly walk back out of the parent.
>   if (child.contains("..", parent.length)) return null;
> 
>   return true;
> }
> 
> Are there cases where that gives a false positive? If not, I think this will
hit
> the very common case with things like Directory.list() where your paths all do
> have the same prefix.

That gives a false positive for isWithin("/foo/bar", "/foo/barbaz"). It's also a
lot slower than this implementation, despite its simplicity; the big cost is
iterating through the string, and your implementation does it twice instead of
once when it returns "true".

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:702: int _checkRemainder(List<int> codeUnits, int index) {
On 2015/11/24 17:22:13, Bob Nystrom wrote:
> How about _pathDirection()? Something other than "check", which is vague,
would
> be nice.

Done.

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:754: }
On 2015/11/24 17:22:13, Bob Nystrom wrote:
> Instead of a for loop with a sort of state machine approach to track what
you've
> read, I think it may be clearer to write this more like an eager lexer that
> matches and advances. Something like:
> 
>     var i = index;
>     while (i < codeUnits.length) {
>       // Read the next path component.
>       var start = i;
>       while (i < codeUnits.length && !style.isSeparator(codeUnits[i])) {
>         i++;
>       }
> 
>       // If we're at the end, stop.
>       if (i == codeUnits.length) break;
> 
>       // See if the path component is ".", "..", or a name.
>       if (i - start == 1 && codeUnits[start] == chars.PERIOD) {
>         // Don't change the depth.
>       } else if (i - start == 2 &&
>           codeUnits[start] == chars.PERIOD &&
>           codeUnits[start + 1] == chars.PERIOD) {
>         // ".." backs out a directory.
>         depth--;
> 
>         // If we work back to the root, stop.
>         if (depth <= 0) break;
>       } else {
>         // Step inside a directory.
>         depth++;
>       }
> 
>       // Ignore doubled separators.
>       while (i < codeUnits.length && style.isSeparator(codeUnits[i])) {
>         i++;
>       }
>     }
> 
>     return depth;
> 
> (I haven't tested this at all.)
> 
> What do you think?

Done. I also realized that there were some bugs in my logic where this was being
called, so I changed it to return a four-state enum.

https://codereview.chromium.org/1468343002/diff/20001/lib/src/context.dart#ne...
lib/src/context.dart:757: // to account for the current component. We have to do
this because depth is counted
On 2015/11/24 17:22:13, Bob Nystrom wrote:
> Long line.

Acknowledged.

[Bob Nystrom, 2015-12-01 00:38:16]

lgtm

[nweiz, 2015-12-01 04:18:54]

Description was changed from

==========
Improve the performance of isWithin().

This adds a single-pass fast path function that only bails when it
encounters "." or ".." components in one path but not the other.

This brings isWithin() from about 0.008 iterations/us to about 0.0180 by
the repo's benchmark. It makes it about 11.5x faster on data provided by
@scheglov (see below), which consists of absolute paths that mostly do
not contain one another.

Data: https://github.com/dart-lang/path/issues/7#issuecomment-157856146

Closes #7

R=rnystrom@google.com
==========

to

==========
Improve the performance of isWithin().

This adds a single-pass fast path function that only bails when it
encounters "." or ".." components in one path but not the other.

This brings isWithin() from about 0.008 iterations/us to about 0.0180 by
the repo's benchmark. It makes it about 11.5x faster on data provided by
@scheglov (see below), which consists of absolute paths that mostly do
not contain one another.

Data: https://github.com/dart-lang/path/issues/7#issuecomment-157856146

Closes #7

R=rnystrom@google.com

Committed:
https://github.com/dart-lang/path/commit/e6b55472da7bfcfcc20db163abadfbd7689d...
==========

[nweiz, 2015-12-01 04:18:56]

Committed patchset #2 (id:20001) manually as
e6b55472da7bfcfcc20db163abadfbd7689dd23c (presubmit successful).