[Finder] Optimize the hot-path #15826

nicolas-grekas · 2015-09-17T12:30:34Z

Q	A
Bug fix?	yes
New feature?	no
BC breaks?	no
Deprecations?	no
Tests pass?	yes
Fixed tickets	#15824
License	MIT
Doc PR	-

A significant part of the perf gain in #15802 was related to filters not being applied recursively...
#15824 fixing this, performance dropped again.

This PR optimizes the hot path by replacing a regexp test by a simple isset when possible.
Blackfire diff after #15824 is the following:
https://blackfire.io/profiles/compare/9e489018-998d-4acb-92a0-46011828e83b/graph

preg_match is not called anymore, and Symfony\Component\Finder\Iterator\RecursiveDirectoryIterator::current() is also cut by two.

When this isset optimization is disabled and replaced by a concatenation of all the regexps patterns in a single bigger one, the gain is still significant but lower:
https://blackfire.io/profiles/compare/db86b80e-b63e-4fc9-9ff3-9ed32baeb948/graph

This makes me think that an other and last round of optimization is possible by merging all regexps in one in MultiplePcreFilterIterator filters. If someone wants to work on this, please do it :)

stof · 2015-09-17T12:48:31Z

This makes me think that an other and last round of optimization is possible by merging all regexps in one in MultiplePcreFilterIterator filters. If someone wants to work on this, please do it :)

this is quite hard to do though, as it is not just a matter of concatenating regexes (combining regexes is very hard to do, and almost impossible in case complex regexes are involved)

stof · 2015-09-17T12:56:10Z

src/Symfony/Component/Finder/Iterator/RecursiveDirectoryIterator.php

@@ -73,6 +87,9 @@ public function getChildren()
            if ($children instanceof self) {
                // parent method will call the constructor with default arguments, so unreadable dirs won't be ignored anymore
                $children->ignoreUnreadableDirs = $this->ignoreUnreadableDirs;
+                $children->subPath = $children->getSubPath();


Please add a command before this to explain it is a performance optimization to avoid redoing the same work in all childrens

stof · 2015-09-17T12:58:36Z

@nicolas-grekas this seems to make PHP segfault

stof · 2015-09-17T13:06:01Z

@nicolas-grekas can you post the profiling and benchmarking results of the ExcludeDirectoryFilter optimization you posted, as this is a totally different optimization than the initial one ?

stof · 2015-09-17T14:13:21Z

src/Symfony/Component/Finder/Iterator/RecursiveDirectoryIterator.php

@@ -31,6 +31,10 @@ class RecursiveDirectoryIterator extends \RecursiveDirectoryIterator
     */
    private $rewindable;

+    private $rootPath;
+    private $subPath;
+    private $directorySeparator = '/';


please add some documentation on them to make the code understandable by someone reading the code later

nicolas-grekas · 2015-09-17T14:27:42Z

@stof the profiling of the ExcludeDirectoryFilter is embedded in the above profiles: you need to click on the "current" node (bottom right) then on the magnifying glass on the left box to draw the graph around this node.

nicolas-grekas · 2015-09-17T14:46:13Z

src/Symfony/Component/Finder/Iterator/RecursiveDirectoryIterator.php

@@ -31,6 +31,11 @@ class RecursiveDirectoryIterator extends \RecursiveDirectoryIterator
     */
    private $rewindable;

+    // these 3 properties take part of the performance optimization to avoid redoing the same work in all iterations
+    private $rootPath;
+    private $subPath = false;


null is the return value of $this->getSubPath() on hhvm, thus requiring false here as "not set" placeholder

nicolas-grekas · 2015-09-17T14:48:04Z

   1010 files
    110 directories
     10 iterations
      6 cases
      2 adapters

            case             php        gnu_find
               0          92,396          33,565
               1          99,673          32,776
               2         103,553          54,970
               3         102,736          61,805
               4         105,615          19,072
               5         107,359          35,432

      0 Find files by name containing a*
      1 Find files by name containing a* not containing *a
      2 Find files by name containing ~^a.*~ not containing ~.*a$~
      3 Find files by path containing a*
      4 Find files by path containing a* not containing *a
      5 Find files by path containing ~^a.*~ not containing ~.*a$~

See #15802 (comment) for comparison.

stof · 2015-09-18T08:27:32Z

src/Symfony/Component/Finder/Expression/Regex.php

@@ -61,7 +61,7 @@ class Regex implements ValueInterface
     */
    public static function create($expr)
    {
-        if (preg_match('/^(.{3,}?)([imsxuADU]*)$/', $expr, $m)) {
+        if (preg_match('/^(.{2,}?)([imsxuADU]*)$/', $expr, $m)) {


what is the reason for this change ?

the regex class rejects empty expressions //, but it should not, they are perfectly valid

stof · 2015-09-18T08:28:18Z

src/Symfony/Component/Finder/Iterator/ExcludeDirectoryFilterIterator.php

+            }
+        }
+        if ($patterns) {
+            $this->excludedPattern = '#(^|/)('.implode('|', $patterns).')(/|$)#';


I suggest using non-capturing groups here. It will make the regex matching more efficient (the regex engine will not need to capture the groups)

stof · 2015-09-18T08:55:27Z

👍 on this one

nicolas-grekas · 2015-09-18T09:57:37Z

hhvm fixed, good to merge
Status: reviewed

fabpot · 2015-09-18T10:01:42Z

Thank you @nicolas-grekas.

This PR was merged into the 2.3 branch. Discussion ---------- [Finder] Optimize the hot-path | Q | A | ------------- | --- | Bug fix? | yes | New feature? | no | BC breaks? | no | Deprecations? | no | Tests pass? | yes | Fixed tickets | #15824 | License | MIT | Doc PR | - A significant part of the perf gain in #15802 was related to filters not being applied recursively... #15824 fixing this, performance dropped again. This PR optimizes the hot path by replacing a regexp test by a simple `isset` when possible. Blackfire diff after #15824 is the following: https://blackfire.io/profiles/compare/9e489018-998d-4acb-92a0-46011828e83b/graph `preg_match` is not called anymore, and `Symfony\Component\Finder\Iterator\RecursiveDirectoryIterator::current()` is also cut by two. When this `isset` optimization is disabled and replaced by a concatenation of all the regexps patterns in a single bigger one, the gain is still significant but lower: https://blackfire.io/profiles/compare/db86b80e-b63e-4fc9-9ff3-9ed32baeb948/graph This makes me think that an other and last round of optimization is possible by merging all regexps in one in MultiplePcreFilterIterator filters. If someone wants to work on this, please do it :) Commits ------- f156de6 [Finder] Optimize the hot-path

carsonbot added the Status: Needs Review label Sep 17, 2015

stof reviewed Sep 17, 2015
View reviewed changes

nicolas-grekas force-pushed the finder-perf branch from 8bb0769 to 0b8bbd9 Compare September 17, 2015 13:01

nicolas-grekas force-pushed the finder-perf branch 12 times, most recently from cd91ade to 8611f74 Compare September 17, 2015 14:12

stof reviewed Sep 17, 2015
View reviewed changes

nicolas-grekas force-pushed the finder-perf branch from 8611f74 to 468e27d Compare September 17, 2015 14:40

nicolas-grekas reviewed Sep 17, 2015
View reviewed changes

nicolas-grekas force-pushed the finder-perf branch 4 times, most recently from 099a761 to 5f3aac2 Compare September 17, 2015 17:40

carsonbot added Status: Needs Work and removed Status: Needs Review labels Sep 17, 2015

stof reviewed Sep 18, 2015
View reviewed changes

nicolas-grekas force-pushed the finder-perf branch from 5f3aac2 to a066f93 Compare September 18, 2015 08:48

nicolas-grekas mentioned this pull request Sep 18, 2015

[Finder] Merge regexps for performance #15828

Closed

nicolas-grekas force-pushed the finder-perf branch 3 times, most recently from 29281f2 to 5b6ac40 Compare September 18, 2015 09:33

[Finder] Optimize the hot-path

f156de6

nicolas-grekas force-pushed the finder-perf branch from 5b6ac40 to f156de6 Compare September 18, 2015 09:36

carsonbot added Status: Reviewed and removed Status: Needs Work labels Sep 18, 2015

fabpot merged commit f156de6 into symfony:2.3 Sep 18, 2015

nicolas-grekas deleted the finder-perf branch September 18, 2015 10:03

supre mentioned this pull request Oct 23, 2015

Fix for broken paths introduced after Symfony upgraded to 2.7.5. Codeception/Codeception#2478

Merged

OndraM mentioned this pull request Dec 10, 2015

Upgrade to Symfony 3 lmc-eu/steward#41

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

[Finder] Optimize the hot-path #15826

[Finder] Optimize the hot-path #15826

Uh oh!

nicolas-grekas commented Sep 17, 2015

Uh oh!

stof commented Sep 17, 2015

Uh oh!

stof Sep 17, 2015

Uh oh!

stof commented Sep 17, 2015

Uh oh!

stof commented Sep 17, 2015

Uh oh!

stof Sep 17, 2015

Uh oh!

nicolas-grekas commented Sep 17, 2015

Uh oh!

nicolas-grekas Sep 17, 2015

Uh oh!

nicolas-grekas commented Sep 17, 2015

Uh oh!

stof Sep 18, 2015

Uh oh!

nicolas-grekas Sep 18, 2015

Uh oh!

stof Sep 18, 2015

Uh oh!

stof commented Sep 18, 2015

Uh oh!

nicolas-grekas commented Sep 18, 2015

Uh oh!

fabpot commented Sep 18, 2015

Uh oh!

Uh oh!

Uh oh!

[Finder] Optimize the hot-path #15826

[Finder] Optimize the hot-path #15826

Uh oh!

Conversation

nicolas-grekas commented Sep 17, 2015

Uh oh!

stof commented Sep 17, 2015

Uh oh!

stof Sep 17, 2015

Choose a reason for hiding this comment

Uh oh!

stof commented Sep 17, 2015

Uh oh!

stof commented Sep 17, 2015

Uh oh!

stof Sep 17, 2015

Choose a reason for hiding this comment

Uh oh!

nicolas-grekas commented Sep 17, 2015

Uh oh!

nicolas-grekas Sep 17, 2015

Choose a reason for hiding this comment

Uh oh!

nicolas-grekas commented Sep 17, 2015

Uh oh!

stof Sep 18, 2015

Choose a reason for hiding this comment

Uh oh!

nicolas-grekas Sep 18, 2015

Choose a reason for hiding this comment

Uh oh!

stof Sep 18, 2015

Choose a reason for hiding this comment

Uh oh!

stof commented Sep 18, 2015

Uh oh!

nicolas-grekas commented Sep 18, 2015

Uh oh!

fabpot commented Sep 18, 2015

Uh oh!

Uh oh!