Are algorithm benchmarks in PHP pointless?

Question

As PHP is simpler for me I wished to benchmark algorithms in it for fun, and I chose to do factorials.

The recursive function completely flunked in speed when I got up to 80! compared to the iterative method, and it gradually skyrocketed upwards while iterative had a steady line, actually it is something like this (x = factorial, y = seconds):

But in C/Java (which I just implemented the test in) show the same results to be only 1-5% off from eachother, almost the same speed.

Is it just useless to benchmark algorithms in this manner in scripting languages?

EDIT: For NullUserException:

function factrec($x) {
    if($x <= 1) {
        return $x;
    } else {
        return $x * factrec($x - 1);
    }
}

Answer 1

In my opinion, if I were to test the algorithm itself I'd go for C/C++, to get the "raw power" it can give in optimal conditions.

On the other hand, if I had to choose which algorithm works best in a certain condition, I'd try to replicate at best such condition. Does it has to be put in a PHP application? Let test it in PHP, with the structures provided by PHP. Does it need to work with STL containers? I'll test in this condition, and not just with arrays. IMHO testing in the real conditions is the key for getting meaningful results. After getting such results, another good thing to do is to tweak such conditions (as far as you can change them in the project) and see what effects you get, to find the best conditions-algorithm couple.

Answer 2

It's absolutely not pointless to benchmark algorithms in a scripting language. After doing the benchmarks, which implementation of factorial would you use in PHP? (assuming that you couldn't use the builtin one for some reason.)

It is fairly pointless to benchmark in a language that has significantly different features than the one that you want to implement the algorithm in though. Here, the relative cost of function calls and if statements in PHP is skewing the results significantly (or this is my best guess anyways). If you are careful to understand why this is happening and avoid it, it can still be fruitful though: differences will be more exaggerated as you noticed. It comes down to if it's easier to write it in the target language or work around the differences.

A simple calculation of complexity of the algorithm should be enough to decide which one to use, or at least narrow down the selections.

---

As Mike Axiak points out in the comments, you are not even testing different algorithms here, you are testing two different implementations of the same algorithm: keep a running product over i from n to 1. Doing this in a different language than the target is almost always pointless.

Answer 3

A recursive versus iterative implementation should have no real impact on the asymptotic behavior of a particular algorithm. In some languages (scala, Scheme, Lua, Standard ML, Mozart/Oz, erlang), the two can actually be written to perform exactly the same. That is, the following scheme code:

(define factorial
  (lambda (n acc)
    (if (= n 0) acc
        (factorial (- n 1) (* n acc)))))
(factorial 5 1)
-> 120

will not use a stack, and hence perform the same as an iterative approach. (This is called tail call optimization, and is invoked in such a language when you perform tail recursion.)

Answer 4

Benchmarking is never pointless. If you have some code, written in whatever language, that's too slow for your application, you figure out the bottlenecks. Looking at those bottlenecks, you look for solutions. One solution may be to use a different formulation of the algorithm, or even rewrite in a different language.

I don't know a thing about PHP, so I have no idea if recursion is handled well in that environment, but I have the impression that it's not a good choice for implementing heavy-duty repetitive math...

Answer 5

You're running against PHP's problem with being poor at recursion. It's not usually the kind of thing people would select PHP to do. Always pick the best tool for the job.

Answer 6

Considering the point of the exercise was fun, it can't be pointless! But trying to get PHP to perform recursive calculations could be an indication that you're just about ready to try a functional programming language. Have you seen Haskell? Tail call optimization, anyone?

C'mon, join the dark side.

Answer 7

Java and C are orders of magnitude faster than PHP.
You'll need to increase your input size significantly to see the results.

Besides, as Aaron McSmooth said, it's pointless to benchmark algorithms in a language other than the one you are planning to use it on.

I am not sure, but I doubt PHP does tail call optimization. Regardless, using a tail recursive function should improve your recursive function's performance quite a bit:

function factorial($n, $product) {
    if ($n < 1)
        return $product;
    else
        return factorial($n-1, $product*$n);
}

print(factorial(80, 1));