Contact
Site: US UK AU |
Nexcess Blog

Simple Magento Sort Optimization Patch

April 16, 2012 12 Comments RSS Feed

Simple Magento Sort Optimization Patch
While doing some profiling and benchmarking of Magento to test PHP-FPM I found that Magento was spending roughly a quarter of the run time for some page loads on comparing attributes.
Unpatched Profile Graph
This struck me as odd, and so I looked into it more and found that it was specifically on pages with several products (like category pages). Digging into the code, I found this (in app/code/core/Mage/Eav/Model/Entity/Abstract.php):

<br />
    //in the getSortedAttributes method<br />
    uasort($attributes, array($this, 'attributesCompare'));</p>
<p>    //then we have<br />
    public function attributesCompare($attribute1, $attribute2)<br />
    {<br />
     	$sortPath      = sprintf('attribute_set_info/%s/sort', $this-&gt;_sortingSetId);<br />
        $groupSortPath = sprintf('attribute_set_info/%s/group_sort', $this-&gt;_sortingSetId);</p>
<p>        $sort1 =  ($attribute1-&gt;getData($groupSortPath) * 1000) + ($attribute1-&gt;getData($sortPath) * 0.0001);<br />
        $sort2 =  ($attribute2-&gt;getData($groupSortPath) * 1000) + ($attribute2-&gt;getData($sortPath) * 0.0001);</p>
<p>        if ($sort1 &gt; $sort2) {<br />
            return 1;<br />
        } elseif ($sort1 &lt; $sort2) {<br />
            return -1;<br />
        }</p>
<p>        return 0;<br />
    }<br />

This seems pretty straightforward but I wondered why Magento was spending so much time on it, so I looked into what sort algorithm PHP uses for uasort which lead me to the sort page which states that PHP uses Quicksort for most sort operations. Quicksort is good sort algorithm but the problem in this context is that each comparison requires 4 getData calls and some (simple) math, but each element can be compared multiple times so it wastes time doing the exact same operation if it looks at an element more than once.

Since we know that every element will be compared at least once, and that some will be compared multiple times the solution is to pre-compute the comparison values and then sort based on those. This patch does exactly that:

--- magento.orig/app/code/core/Mage/Eav/Model/Entity/Abstract.php	2011-07-26 05:39:19.000000000 -0400<br />
+++ magento/app/code/core/Mage/Eav/Model/Entity/Abstract.php	2012-04-05 15:44:18.012612944 -0400<br />
@@ -549,16 +549,24 @@<br />
         Mage::getSingleton('eav/entity_attribute_set')<br />
             -&gt;addSetInfo($this-&gt;getEntityType(), $attributes, $setId);</p>
<p>+        $sortList      = array();<br />
+        $sortPath      = sprintf('attribute_set_info/%s/sort', $setId);<br />
+        $groupSortPath = sprintf('attribute_set_info/%s/group_sort', $setId);<br />
         foreach ($attributes as $code =&gt; $attribute) {<br />
             /* @var $attribute Mage_Eav_Model_Entity_Attribute_Abstract */<br />
             if (!$attribute-&gt;isInSet($setId)) {<br />
                 unset($attributes[$code]);<br />
+            } else {<br />
+                $sortList[$code] = array($attribute,<br />
+                    ($attribute-&gt;getData($groupSortPath) * 1000) +<br />
+                    ($attribute-&gt;getData($sortPath) * 0.0001));<br />
             }<br />
         }</p>
<p>         $this-&gt;_sortingSetId = $setId;<br />
-        uasort($attributes, array($this, 'attributesCompare'));<br />
-        return $attributes;<br />
+        uasort($sortList, create_function('$a,$b',<br />
+            'return $a[1] &gt; $b[1] ? ($a[1] &lt; $b[1] ? -1 : 0) : 1;'));<br />
+        return array_map(create_function('$a', 'return $a[0];'), $sortList);<br />
     }</p>
<p>     /**

Disclaimer: I have not rigorously tested this patch. It is very simple and doesn’t change the return value of the getSortedAttributes method so it shouldn’t cause any problems but use is at your own risk.

In the regular Magento sample data I was testing against this resulted in a run time reduction of ~1/10 of a second (0.3s to 0.2s) on the /apparel.html category page. This doesn’t sound like much but that page takes about 3 times longer to load than other pages, and on a production site with real data the time savings could be significant since it affects pages with lots of products. For reference, here is the call time graph with the patch (compare the highlighted area to the unpatched graph above):
Patched Profile Graph
In other terms, this results in reliable a ~2 transaction/second increase on the Magento Speed Test with the sample data.

Posted in: Magento