Cautionary tale about optimizing path manipulation.

Cautionary tale about optimizing path manipulation.

BUG=https://code.google.com/p/dart/issues/detail?id=20628
R=nweiz@google.com

Committed: https://code.google.com/p/dart/source/detail?r=39502

[Bob Nystrom, 2014-08-21 22:28:58]

Using substring() assumed the path was perfectly normalized. It wasn't. :(

[nweiz, 2014-08-22 00:00:52]

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
File sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart (right):

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart:533: // Strip off
the path to the package's root direct (and the separator
"direct" -> "directory".

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart:535: var relative =
file.substring(package.dir.length + 1);
We should look for other cases where we make this assumption about
[Directory.list]. It's almost always true that it returns strings that begin
with the input string, but trailing slashes break that invariant.

Alternately, we could replace all these substrings with calls to path.relative
and then work on optimizing that for common cases.

[Bob Nystrom, 2014-08-22 18:09:28]

I slapped together a little profile test case for this code and found:

Current:                471ms
Using path.relative(): 1436ms :(

But if I get rid of the checks for ".dart.js" (which were intended to be
temporary) and then ditch the .expand() stuff, I get:

Using substring:        252ms :)

And then if I go back to using path.relative() there:

Using path.relative:    253ms :D

So we can go back to using path.relative() which handles the trailing "/"
correctly and still have a significant net perf improvement. I don't know why
path.relative() causes a perf hit in the old code but not here. I presume we're
on the threshold of some VM inlining heuristic or something like that.

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
File sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart (right):

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart:533: // Strip off
the path to the package's root direct (and the separator
On 2014/08/22 00:00:52, nweiz wrote:
> "direct" -> "directory".

Done.

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart:535: var relative =
file.substring(package.dir.length + 1);
On 2014/08/22 00:00:52, nweiz wrote:
> We should look for other cases where we make this assumption about
> [Directory.list]. It's almost always true that it returns strings that begin
> with the input string, but trailing slashes break that invariant.
> 
> Alternately, we could replace all these substrings with calls to path.relative
> and then work on optimizing that for common cases.

I did some profiling and tried a bunch of options and came up with, I think,
something better.

[nweiz, 2014-08-22 18:17:40]

The changes you've made LGTM, but I think we've still got other copies of this
bug hiding in the code.

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
File sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart (right):

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart:535: var relative =
file.substring(package.dir.length + 1);
On 2014/08/22 18:09:28, Bob Nystrom wrote:
> On 2014/08/22 00:00:52, nweiz wrote:
> > We should look for other cases where we make this assumption about
> > [Directory.list]. It's almost always true that it returns strings that begin
> > with the input string, but trailing slashes break that invariant.
> > 
> > Alternately, we could replace all these substrings with calls to
path.relative
> > and then work on optimizing that for common cases.
> 
> I did some profiling and tried a bunch of options and came up with, I think,
> something better.

I'm concerned about other places we're using substring after Directory.list and
making the same assumption. I think listDir does something like this for its
whitelisting, for example, and Package.listFiles does it for blacklisting.

[Bob Nystrom, 2014-08-22 19:36:59]

I think the other places are fine. Added one assert() to clarify that.

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
File sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart (right):

https://codereview.chromium.org/485893008/diff/1/sdk/lib/_internal/pub/lib/sr...
sdk/lib/_internal/pub/lib/src/barback/asset_environment.dart:535: var relative =
file.substring(package.dir.length + 1);
On 2014/08/22 18:17:40, nweiz wrote:
> On 2014/08/22 18:09:28, Bob Nystrom wrote:
> > On 2014/08/22 00:00:52, nweiz wrote:
> > > We should look for other cases where we make this assumption about
> > > [Directory.list]. It's almost always true that it returns strings that
begin
> > > with the input string, but trailing slashes break that invariant.
> > > 
> > > Alternately, we could replace all these substrings with calls to
> path.relative
> > > and then work on optimizing that for common cases.
> > 
> > I did some profiling and tried a bunch of options and came up with, I think,
> > something better.
> 
> I'm concerned about other places we're using substring after Directory.list
and
> making the same assumption. I think listDir does something like this for its
> whitelisting, for example, and Package.listFiles does it for blacklisting.

Good call. I went through all of our uses of substring on paths and verified
they handle it correctly. In all other cases, the path had the full original
path as its prefix, so the substring was correct. For example, if you pass
"foo///" to listDir, you'll get result paths like "foo///bar.txt".
Package.listFiles gets similar results from listDir() so it's good too.

[nweiz, 2014-08-22 19:46:15]

lgtm with the added comments we discussed offline.

[Bob Nystrom, 2014-08-22 19:50:40]

Committed patchset #4 manually as 39502 (presubmit successful).