Just ran across this post where Felix shares some wisdom he gained while re-writing CakePHP‘s Set::extract() (code) method to make it faster and add some XPath 2.0 support.

If you need a function to have the highest performance, try to express it non-recursively. It can make a 500% difference.

Now I thought the 500% speed gain (and associated fewer CPU cycles) was a number he grabbed out of the air or it was based on comparisons with the previous Set::extract() method and very specific to that case. It surely would not apply to any algorithm in general as some are much more complex than others.

While it may not apply to any algorithm in general it may apply to similar algorithms. So I benchmarked the new Set::extract() against a library I remembered called JSONPath (code) which also allows you to extract data from nested arrays using a string selector. JSONPath uses recursion just like the old Set::extract() method.

I used the second $users array from here and ran the following two tests:

// Simple
Set::extract('/User/name', $users);
jsonPath($users, "$..User.name");
 
// Complex
Set::extract('/User/Item[id>2]/name', $users);
jsonPath($users, "$..User.Item.[?(@['id']>2)].name");

Both of these tests generate the same output so they are a pretty good comparison for the underlying algorithms. Running them 100 times each gives the following result:

[TABLE=1]

Lo and behold! The speed difference is ~500%!

Now that is a funny answer to my question! NOTE: The two libraries (and old Set::extract()) have different features and cannot be compared like this. The 500% is only applicable for this specific example but take it to show that recursion should definitely be evaluated when looking for speed gain. The cost for less recursion may be less modularity and extensibility, but that is a tradeoff you always need to make.

Now don’t use these figures to choose between Set::extract() and JSONPath. They work very differently internally. JSONPath uses a lot of recursion and jumping around but it also uses a lot of regular expression matching which is notoriously slow in PHP.

JSONPath has a very academic background and illustrates some neat concepts. If someone was to take it and put a practical spin on it with some performance improvements (reducing recursiveness!?) and new features, it could make for an even better library to extract data from arrays.