Improve speed of parsing

[mishal]

Improve speed of parsing

[dleffler]

There was a comment on the lessphp repo implying the use of sprintf to concat strings contributed to the slowness?

[mishal]

I haven't looked deeply at the benchmarks yet, but I think that the main problem is in compiling the extends.

If you can help with this I would really appreciate it.

[chrisgraham]

It definitely seems to be extends. I think there's some kind of combinatorial explosion going on here, but I don't have a couple of days to learn the parser / parse tree.

Our LESS is based around bootstrap. Around 3000 braced sections, and around 70 extends, yet somehow it is evaluating 500k matches.

But I really can't comment more on that without being an expert.

[chrisgraham]

I should note that I've been profiling PHP a long time, and the numbers xdebug gives can be somewhat misleading. Function calls are pretty expensive, but the call cost itself doesn't show up directly (you can see it in the grandparent call cumulative cost though). Same goes for basic dereferencing of arrays and objects (either explicitly or in loops).

[mishal]

Thanks for your effort!

The ILess code is direct port of Less.js (started at v1.6), which is now at 2.x version. I haven't looked at what has been changed in the parser code yet.

I want to push ILess forward (compat with new less.js features), so this issue is a minor one, but important one.

[chrisgraham]

I decided to take a closer look at this. The findMatch calls are complex, and called for every selector, for every extend.

Let's say each rule block has 3 selectors, there are 1000 rule blocks, and 100 extends...
3 x 1000 x 50 = 300000

So you see the combinatorial explosion there.

I have done an optimisation. I've spend way too much time on debugging this, so I'm afraid I can't make a tidy pull request. Here's a real ugly diff (I couldn't be bothered to set my indent to match, sorry)...

diff --git a/sources_custom/ILess/Node/Extend.php b/sources_custom/ILess/Node/Extend.php
index e16175e..3324b75 100644
--- a/sources_custom/ILess/Node/Extend.php
+++ b/sources_custom/ILess/Node/Extend.php
@@ -29,6 +29,8 @@ class ILess_Node_Extend extends ILess_Node implements ILess_Node_VisitableInterf
      */
     public $selector;

+        public $pathString='';
+
     /**
      * The option (all)
      *
diff --git a/sources_custom/ILess/Node/Ruleset.php b/sources_custom/ILess/Node/Ruleset.php
index ed21dce..6240c41 100644
--- a/sources_custom/ILess/Node/Ruleset.php
+++ b/sources_custom/ILess/Node/Ruleset.php
@@ -36,6 +36,8 @@ class ILess_Node_Ruleset extends ILess_Node implements ILess_Node_VisitableInter
      */
     public $paths = array();

+        public $pathString='';
+
     /**
      * Strict imports flag
      *
diff --git a/sources_custom/ILess/Visitor/ProcessExtend.php b/sources_custom/ILess/Visitor/ProcessExtend.php
index 4a638fc..a2654d8 100644
--- a/sources_custom/ILess/Visitor/ProcessExtend.php
+++ b/sources_custom/ILess/Visitor/ProcessExtend.php
@@ -196,8 +202,36 @@ class ILess_Visitor_ProcessExtend extends ILess_Visitor
         $allExtends = end($this->allExtendsStack);
         $pathsCount = count($node->paths);

+                 if ($node->pathString=='')
+                 {
+                         foreach ($node->paths as $path)
+                         {
+                               foreach ($path as $selector)
+                               {
+                                       foreach ($selector->elements as $element)
+                                       {
+                                               $node->pathString .= preg_replace('#[^\w]#','',$element->value);
+                                       }
+                               }
+                       }
+               }
+
         // look at each selector path in the ruleset, find any extend matches and then copy, find and replace
         for ($extendIndex = 0, $allExtendCount = count($allExtends); $extendIndex < $allExtendCount; $extendIndex++) {
+                         $extend=$allExtends[$extendIndex];
+                         if ($extend->pathString=='')
+                         {
+                               foreach ($extend->selector->elements as $element)
+                               {
+                                       $extend->pathString .= preg_replace('#[^\w]#','',$element->value);
+                               }
+                       }
+
+                       if (strpos($node->pathString,$extend->pathString)===false)
+                       {
+                               continue;
+                       }
+
             for ($pathIndex = 0; $pathIndex < $pathsCount; $pathIndex++) {
                 $selectorPath = $node->paths[$pathIndex];
                 // extending extends happens initially, before the main pass
@@ -207,7 +241,7 @@ class ILess_Visitor_ProcessExtend extends ILess_Visitor
                 if (end($selectorPath)->extendList) {
                     continue;
                 }
-                $matches = $this->findMatch($allExtends[$extendIndex], $selectorPath);
+                $matches = $this->findMatch($extend, $selectorPath);
                 if ($matches) {
                     foreach ($allExtends[$extendIndex]->selfSelectors as $selfSelector) {
                         $node->paths[] = $this->extendSelector($matches, $selectorPath, $selfSelector);

It works on the basis of cacheing a clumped up copy of each ruleset's selectors. E.g. ".foo .bar, .bar .foo" would clump up to "foobarbarfoo" in pathString. The same is done for the extends. If there's a string overlap, we know we need to then look more carefully within findMatch to see if it really does properly match when evaluating all the individual selector expressions properly.

My optimisation may not be valid in all cases. I think extend allows multiple selectors, in which case an overlap check would need happening for each one. But it's good enough for me, and I think you can clean it up easily enough.

This optimisation got my findMatch calls down from ~500k to ~10k. I think it's improved performance about 60% but I haven't done proper measurements.

I believe there's scope for further optimisation. The node structure is swept multiple times, and goes down to the CSS property level, so it's a huge crawl for bootstrap's LESS code. I can see it's been architected to use a relative abstract clean algorithm, but it'd be far more efficient if it just did book-keeping at the parsing stage. At least noting down the extends at parse rather than recursing back through later (ExtendFinder's independent sweep, initiated at the start of ProcessExtend). Doing recursive calls, looping, and constant unpacking arrays many levels deep, is not going to be fast in a dynamic language like php. Maybe ExtendFinder is the only case to reasonably eliminate, so then I'd recommend optimising the recursion, try and pull out some of the intermediary functions in Visitor.php (function calls are fairly expensive).

[chrisgraham]

I measured the speed boost of the above properly. Compile time reduces by 40%, or 50% if you use trim (with '.# ') instead of preg_replace.

[mishal]

Chris, many thanks for your effort.

The visitor implementation is a direct port of javascript version. I'm slowly working on updates to bring the 2.0 features to Iless and I'm not sure what has changed in the less.js code which I would like to follow.

The less implementation may be updated and we can just use the updates done there and keep the code close to each other.

The js versions:

https://github.com/less/less.js/blob/v1.6.3/lib/less/extend-visitor.js
https://github.com/less/less.js/blob/master/lib/less/visitors/extend-visitor.js:

[chrisgraham]

A quick look at the master link above suggests to me it would benefit from my optimisation also. I can't see any other fix they've made.

I imagine in the JS implementation nobody is crazy enough to do a full bootstrap compile, so they might not have looked at this as closely.

[dleffler]

Is this code going to make it into the repo?

[mishal]

I've created profile for bootstrap3 compilation.

https://blackfire.io/profiles/946e4672-504e-4fac-8dab-869791ccd8a5/graph

I will look at this closer.