Bug #70827 for PathTools: [FeatureRequest] Optimise Unix::canonpath

Thu Sep 08 21:33:59 2011 KENTNL [...] cpan.org - Ticket created

Subject:

[FeatureRequest] Optimise Unix::canonpath

XDG/DAGOLDEN Noted last year that File::Spec::Unix::canonpath is a bit of a hotspot,

indeed, simply doing a directory traversal via File::Next, results in this one method accounting for 30% of the processor time.

In my test sample, 100,000 files , for which each and every file name needs canonicalizing.

And this effectively results in 600,000 regular expression substitutions being performed.

I would like to see this performance hump Ironed out, even if it means to get the performance I have to load some external XS module.

Attached: Image showing NYTProf -> kcachegrind showing the hotspot and relevant hot lines.

Subject:

blurrr1.png

Download blurrr1.png
image/png 148.2k

Thu Sep 08 22:58:05 2011 kwilliams [...] cpan.org - Correspondence added

I agree that it would be nice to optimize that spot. But I actually wouldn't expect it to help as much as you predict. I imagine that when traversing 100K files, almost all the time is spent doing system calls, rather than as CPU time in the program. Additionally, none of those regexes are particularly bad, because 4 of them are anchored, none of them capture, and none backtrack (at least not much). As a test, perhaps you could replace canonpath() with a no-op and see how wallclock time is affected in your File::Next test. -Ken

Thu Sep 08 22:58:07 2011 The RT System itself - Status changed from 'new' to 'open'

Thu Sep 08 23:59:37 2011 KENTNL [...] cpan.org - Correspondence added

A proper no-op doesn't prove to be helpful for diagnosing this problem, at least not under File::Next, because if you no-op, file::next never does any traversal.

sub File::Spec::Unix::canonpath {
return "";
}

for i in $(seq 0 10 ); do time perl newer_depends_than.pl ; done 2>&1 | grep real

real    0m0.344s
real    0m0.340s
real    0m0.338s
real    0m0.337s
real    0m0.341s
real    0m0.341s
real    0m0.336s
real    0m0.341s
real    0m0.340s
real    0m0.341s
real    0m0.341s

Closest I can get to a usable no-op is:

sub File::Spec::Unix::canonpath {
return $_[1];
}

for i in $(seq 0 10 ); do time perl newer_depends_than.pl ; done 2>&1 | grep real
real    0m1.595s
real    0m1.593s
real    0m1.594s
real    0m1.600s
real    0m1.629s
real    0m1.592s
real    0m1.644s
real    0m1.603s
real    0m1.678s
real    0m1.620s
real    0m1.597s

And compare vs the stock ::canonpath

for i in $(seq 0 10 ); do time perl newer_depends_than.pl ; done 2>&1 | grep real
real    0m2.857s
real    0m2.812s
real    0m2.943s
real    0m2.825s
real    0m2.846s
real    0m2.836s
real    0m2.856s
real    0m2.832s
real    0m2.847s
real    0m2.817s
real    0m2.838s

That to me looks strongly like there is a significant amount of performance to be made.

For a comparison, I did a very basic replacement of canonpath with just the minimal amount of canonicalisation I thought would be needed,

sub File::Spec::Unix::canonpath {
return unless defined $_[1];
return q{/} if $_[1] eq q{/};

# marginally the fastest of
  # $path =~ /\/\z// , substr( $path, -1, 1, '' ) and $path = substr( $path , .... )
  # but this is likely to be perl specific
    return substr( $_[1], 0, -1 ) if substr( $_[1], -1, 1 ) eq q{/} ;
    return $_[1];
}

for i in $(seq 0 10 ); do time perl newer_depends_than.pl ; done 2>&1 | grep 'real'
real    0m2.401s
real    0m2.384s
real    0m2.507s
real    0m2.472s
real    0m2.388s
real    0m2.369s
real    0m2.378s
real    0m2.392s
real    0m2.389s
real    0m2.379s
real    0m2.398s

So thats roughly an improvement of 14% over the current implementation, but still 50% slower than a "no-op".

Fri Sep 09 00:16:25 2011 kwilliams [...] cpan.org - Correspondence added

Perhaps a better solution would be for File::Next to stop calling canonpath() every time it gets a filename. Why does it need to? Shouldn't it just call canonpath() on the starting point, and then avoid it on all the rest? It's in control of the strings it's creating, it knows it's not inserting any "././" funny stuff.

Fri Sep 09 02:38:58 2011 KENTNL [...] cpan.org - Correspondence added

On 2011-09-09 16:16:25, KWILLIAMS wrote:
Show quoted text

> Perhaps a better solution would be for File::Next to stop calling
> canonpath() every time it gets a
> filename. Why does it need to? Shouldn't it just call canonpath() on
> the starting point, and then
> avoid it on all the rest? It's in control of the strings it's
> creating, it knows it's not inserting any
> "././" funny stuff.

Ah you see, this is a problem , becuse its not actually calling canonpath() directly, its' calling "catdir", which is an incredibly common way that most people use to ensure filesystem portable path handling.

And catdir in turn calls canonpath.

So the only alternative is for File::Next to implement file path concatenation entirely itself, and that to me seems like the wrong approach.

Fri Sep 09 03:11:09 2011 KENTNL [...] cpan.org - Correspondence added

By simply replacing catdir with the following:

sub File::Spec::Unix::catdir {
shift;
return ( join q{/}, @_, '' );

}

Unsurprisingly, I get the fastest times yet:

for i in $(seq 0 10 ); do time perl newer_depends_than.pl ; done 2>&1 | grep 'real'
real    0m1.517s
real    0m1.499s
real    0m1.503s
real    0m1.525s
real    0m1.509s
real    0m1.512s
real    0m1.524s
real    0m1.494s
real    0m1.503s
real    0m1.513s
real    0m1.503s

Though that solution is hardly portable and will let bad paths exist. *( Its fine for my current usecase, but obviously not fine for all )

Fri Sep 09 03:18:25 2011 KENTNL [...] cpan.org - Correspondence added

On 2011-09-09 19:11:09, KENTNL wrote:
Show quoted text

> By simply replacing catdir with the following:
>
> sub File::Spec::Unix::catdir {
> shift;
> return ( join q{/}, @_, '' );
>
> }

Gah. My mistake. Its not fine. I just thought it was but didn't check output.

Needs to be return ( join q{/}, @_ ) to work.

I really need to go and write a proper benchmark testcase for this now :(

Fri Sep 09 03:33:53 2011 KENTNL [...] cpan.org - Correspondence added

                    Rate   catdir canonpath hand_catdir hand_canonpath       nop
catdir          157893/s       --      -35%        -82%           -86%      -95%
canonpath       243439/s      54%        --        -72%           -79%      -92%
hand_catdir     858907/s     444%      253%          --           -25%      -70%
hand_canonpath 1148337/s     627%      372%         34%             --      -60%
nop            2872841/s    1719%     1080%        234%           150%        --

There we go, some concrete numbers we can rely on.

( I didn't realise this so much earlier, but the validity of results affected how much other work File::Next was doing , argh )

Subject:

benchmark.pl

#!/usr/bin/env perl use strict; use warnings; # FILENAME: benchmark.pl # CREATED: 09/09/11 19:18:45 by Kent Fredric (kentnl) <kentfredric@gmail.com> # ABSTRACT: benchmark file::spec functions use File::Spec; sub _do_catdir { File::Spec->catdir('x', 'y'); } sub _do_canonpath { File::Spec->canonpath('x/y'); } sub _handrolled_catdir { shift; join q{/}, @_ ; } sub _handrolled_canonpath { return $_[1]; } sub _do_handrolled_catdir { __PACKAGE__->_handrolled_catdir('x', 'y' ); } sub _do_handrolled_canonpath { __PACKAGE__->_handrolled_canonpath('x/y'); } sub _do_nop { } use Benchmark qw( :all :hireswallclock ); cmpthese( -2 , { nop => sub { _do_nop }, catdir => sub { _do_catdir }, canonpath => sub { _do_canonpath }, hand_catdir => sub { _do_handrolled_catdir }, hand_canonpath => sub { _do_handrolled_canonpath }, });

Sun Nov 24 00:09:27 2013 jkeenan [...] cpan.org - Correspondence added

On Fri Sep 09 03:33:53 2011, KENTNL wrote: Show quoted text

> Rate catdir canonpath hand_catdir hand_canonpath nop > catdir 157893/s -- -35% -82% -86% -95% > canonpath 243439/s 54% -- -72% -79% -92% > hand_catdir 858907/s 444% 253% -- -25% -70% > hand_canonpath 1148337/s 627% 372% 34% -- -60% > nop 2872841/s 1719% 1080% 234% 150% -- > > There we go, some concrete numbers we can rely on. > > ( I didn't realise this so much earlier, but the validity of results > affected > how much other work File::Next was doing , argh )

Is there still a case to be made for optimization of File::Spec::Unix::canonpath()? If not, is this ticket closable? Thank you very much. Jim Keenan

Sun Nov 24 00:48:00 2013 KENTNL [...] cpan.org - Correspondence added

Seems the performance is much better these days.

Did a test bench from 5.8.9 all the way through to 5.19.6

catdir hovered around 300k calls per second
canonpath hovered around 500k calls per second all the way up to 5.19.0

But somewhere after the 5.19.0 , the performance grows substantailly:

5.19.5 and 5.19.6:

catdir 750k calls/sec

canonpath : 2.1 Million calls/sec

The exact place I'm not sure, but my suspicions are COW is to blame for the performance boost ( I only didn't test anything between 5.19.5 and 5.19.0 because I didn't have those targets ready built ).

There's still room for improvement, but the room is much narrower:

hand-written catdir only 129% of catdir ( was ~400% )

hand-written canon path only ~5-20% faster than canonpath ( was ~400% )

Subject:

bench_results.txt

5.10.0-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 301591/s -- -35% -81% -87% -95% canonpath 463494/s 54% -- -71% -80% -92% hand_catdir 1584500/s 425% 242% -- -31% -74% hand_canonpath 2307768/s 665% 398% 46% -- -63% nop 6174903/s 1947% 1232% 290% 168% -- 5.10.1-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 306376/s -- -47% -79% -89% -95% canonpath 579231/s 89% -- -60% -79% -91% hand_catdir 1456068/s 375% 151% -- -46% -77% hand_canonpath 2717946/s 787% 369% 87% -- -57% nop 6273530/s 1948% 983% 331% 131% -- 5.12.5-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 322531/s -- -42% -81% -86% -96% canonpath 555013/s 72% -- -68% -76% -93% hand_catdir 1739107/s 439% 213% -- -24% -78% hand_canonpath 2279513/s 607% 311% 31% -- -71% nop 7837304/s 2330% 1312% 351% 244% -- 5.14.4-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 311909/s -- -38% -82% -88% -95% canonpath 504123/s 62% -- -71% -80% -91% hand_catdir 1756235/s 463% 248% -- -32% -70% hand_canonpath 2579576/s 727% 412% 47% -- -55% nop 5761168/s 1747% 1043% 228% 123% -- 5.16.3-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 241434/s -- -39% -78% -84% -97% canonpath 393214/s 63% -- -64% -74% -95% hand_catdir 1095264/s 354% 179% -- -28% -85% hand_canonpath 1522138/s 530% 287% 39% -- -79% nop 7159443/s 2865% 1721% 554% 370% -- 5.18.0-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 340172/s -- -34% -79% -86% -94% canonpath 519248/s 53% -- -68% -79% -91% hand_catdir 1602636/s 371% 209% -- -36% -71% hand_canonpath 2493232/s 633% 380% 56% -- -56% nop 5605114/s 1548% 979% 250% 125% -- 5.19.0-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 305077/s -- -36% -80% -87% -95% canonpath 477293/s 56% -- -69% -80% -91% hand_catdir 1516860/s 397% 218% -- -36% -73% hand_canonpath 2384597/s 682% 400% 57% -- -57% nop 5557740/s 1722% 1064% 266% 133% -- 5.19.5-pristine ========== Rate catdir hand_catdir canonpath hand_canonpath nop catdir 740250/s -- -52% -65% -71% -88% hand_catdir 1550545/s 109% -- -27% -40% -75% canonpath 2130975/s 188% 37% -- -17% -66% hand_canonpath 2565655/s 247% 65% 20% -- -59% nop 6201842/s 738% 300% 191% 142% -- 5.19.6-pristine ========== Rate catdir hand_catdir canonpath hand_canonpath nop catdir 751539/s -- -56% -67% -68% -88% hand_catdir 1720728/s 129% -- -25% -27% -73% canonpath 2296673/s 206% 33% -- -2% -64% hand_canonpath 2347248/s 212% 36% 2% -- -63% nop 6347759/s 745% 269% 176% 170% -- 5.8.9-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 323371/s -- -30% -79% -84% -94% canonpath 463698/s 43% -- -71% -77% -91% hand_catdir 1571944/s 386% 239% -- -20% -71% hand_canonpath 1976612/s 511% 326% 26% -- -63% nop 5400609/s 1570% 1065% 244% 173% --

Sun Nov 24 04:43:52 2013 KENTNL [...] cpan.org - Correspondence added

Further benching shows the tipping point is 5.19.3.

So not COW, but its been improved =)

5019003delta :

+=item *
+
+L<File::Spec> has been upgraded from 3.41 to 3.44.
+
+The module is now partly implemented in XS, for performance.
+

So looking forward to seeing those changes hit CPAN =).

Sun Nov 24 04:44:32 2013 KENTNL [...] cpan.org - Correspondence added

Subject:

benchmark_5.19.txt

5.19.0-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 337317/s -- -37% -81% -85% -95% canonpath 538842/s 60% -- -70% -76% -92% hand_catdir 1804526/s 435% 235% -- -21% -74% hand_canonpath 2285684/s 578% 324% 27% -- -67% nop 6830032/s 1925% 1168% 278% 199% -- 5.19.1-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 275581/s -- -50% -85% -90% -96% canonpath 548746/s 99% -- -70% -80% -93% hand_catdir 1816513/s 559% 231% -- -34% -75% hand_canonpath 2735414/s 893% 398% 51% -- -63% nop 7395070/s 2583% 1248% 307% 170% -- 5.19.2-pristine ========== Rate catdir canonpath hand_catdir hand_canonpath nop catdir 273763/s -- -49% -85% -89% -96% canonpath 536996/s 96% -- -71% -79% -92% hand_catdir 1852370/s 577% 245% -- -29% -73% hand_canonpath 2596848/s 849% 384% 40% -- -62% nop 6816368/s 2390% 1169% 268% 162% -- 5.19.3-pristine ========== Rate catdir hand_catdir canonpath hand_canonpath nop catdir 775271/s -- -55% -63% -69% -87% hand_catdir 1708119/s 120% -- -19% -32% -72% canonpath 2118067/s 173% 24% -- -16% -65% hand_canonpath 2520615/s 225% 48% 19% -- -59% nop 6120335/s 689% 258% 189% 143% -- 5.19.4-pristine ========== Rate catdir hand_catdir canonpath hand_canonpath nop catdir 794299/s -- -52% -63% -67% -88% hand_catdir 1641139/s 107% -- -24% -32% -76% canonpath 2155368/s 171% 31% -- -11% -69% hand_canonpath 2424831/s 205% 48% 13% -- -65% nop 6893590/s 768% 320% 220% 184% -- 5.19.5-pristine ========== Rate catdir hand_catdir canonpath hand_canonpath nop catdir 780198/s -- -47% -66% -70% -88% hand_catdir 1486080/s 90% -- -36% -42% -77% canonpath 2325129/s 198% 56% -- -10% -63% hand_canonpath 2582699/s 231% 74% 11% -- -59% nop 6351948/s 714% 327% 173% 146% -- 5.19.6-pristine ========== Rate catdir hand_catdir canonpath hand_canonpath nop catdir 805940/s -- -54% -63% -72% -89% hand_catdir 1767778/s 119% -- -19% -38% -76% canonpath 2185156/s 171% 24% -- -23% -71% hand_canonpath 2848126/s 253% 61% 30% -- -62% nop 7487591/s 829% 324% 243% 163% --

Tue Nov 26 18:39:10 2013 jkeenan [...] cpan.org - Requestor JKEENAN added