Testing an Algorithms speed. How?

Question

I'm currently testing different algorithms, which determine whether an Integer is a real square or not. During my research I found this question at SOF: Fastest way to determine if an integer's square root is an integer

I'm compareably new to the Programming scene. When testing the different Algorithms that are presented in the question, I found out that this one

bool istQuadratSimple(int64 x)
{
    int32 tst = (int32)sqrt(x);
    return tst*tst == x;
}

actually works faster than the one provided by A. Rex in the Question I posted. I've used an NS-Timer object for this testing, printing my results with an NSLog.

My question now is: How is speed-testing done in a professional way? How can I achieve equivalent results to the ones provided in the question I posted above?

Answer 1

The problem with calling just this function in a loop is that everything will be in the cache (both the data and the instructions). You wouldn't measure anything sensible; I wouldn't do that.

Given how small this function is, I would try to look at the generated assembly code of this function and the other one and I would try to reason based on the assembly code (number of instructions and the cost of the individual instructions, for example).

Unfortunately, it only works in trivial / near trivial cases. For example, if the assembly codes are identical then you know there is no difference, you don't need to measure anything. Or if one code is like the other plus additional instructions; in that case you know that the longer one takes longer to execute. And then there are the not so clear cases... :(
(See the update below.)

You can get the assembly with the -S -emit-llvm flags from clang and with the -S flag from gcc.

Hope this help.

---

---

UPDATE: Response to Prateek's question in the comment "is there any way to determine the speed of one particular algorithm?"

Yes, it is possible but it gets horribly complicated REALLY quick. Long story short, ignoring the complexity of modern processors and simply accumulating some predefined cost associated with the instructions can lead to very very inaccurate results (the estimate off by a factor of 100, due to the cache and the pipeline, among others). If you try take into consideration the complexity of the modern processors, the hierarchical cache, the pipeline, etc. things get very difficult. See for example Worst Case Execution Time Prediction.

Unless you are in a clear situation (trivial / near trivial case), for example the generated assembly codes are identical or one is like the other plus a few instructions, it is also hard to compare algorithms based on their generated assembly.

However, here a simple function of two lines is shown, and for that, looking at the assembly could help. Hence my answer.

Answer 2

I am not sure if there is any professional way of checking the speed (if there is let me know as well). For the method that you directed to in your question I would probably do something this this in java.

package Programs;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class SquareRootInteger {

    public static boolean isPerfectSquare(long n) {
        if (n < 0)
            return false;

        long tst = (long) (Math.sqrt(n) + 0.5);
        return tst * tst == n;
    }

    public static void main(String[] args) {
        long iterator = 1;
        int precision = 10;
        long startTime = System.nanoTime(); //Getting systems time before calling the isPerfectSquare method repeatedly 
        while (iterator < 1000000000) {
            isPerfectSquare(iterator);
            iterator++;
        }
        long endTime = System.nanoTime(); // Getting system time after the 1000000000 executions of isPerfectSquare method
        long duration = endTime - startTime;
        BigDecimal dur = new BigDecimal(duration);
        BigDecimal iter = new BigDecimal(iterator);
        System.out.println("Speed "
                + dur.divide(iter, precision, RoundingMode.HALF_UP).toString()
                + " nano secs"); // Getting average time taken for 1 execution of method.

    }
}

You can check your method in similar fashion and check which one outperforms other.

UPDATE:- As OP might not be comfortable with java I added comments in the code to pass the idea more clearly. And for the down vote I would really appreciate if I can get a constructive feedback on why this was downvoted. Thanks!!

Answer 3

1. Record the time value before your massive calculation and the value after that. The difference is the time executed.
2. Write a shell script where you will run the program. And run 'time ./xxx.sh' to get it's running time.