Best resolution timer

[tabchas]

I am using a call to System.nanoTime() in order to time the speeds of the elemetary sorts. However, the number fluctuates if I run the program repeatedly. What is the reason for this? Shouldn't execution time always be the same? Is there a better way to time execution speed?

[Eranga]

nanoTime() returns the available system timer, in nanoseconds. Obviously when you are running your application repeatedly its not return the same. If you could post some code that you work on we can have a look at it.

[tabchas]

Here is the code that I am implementing:

public class OrderedArray {
    
    int [] array;
    int num_elements = 0;
    int size = 0;
        
    public OrderedArray (int size)
    {
        this.size = size;
        array = new int [size];        
    }
    
    public int search (int key)
    {
        int lowerBound = 0;
        int higherBound = num_elements - 1;
        int binary = 0;
        int count = 0;
        
        while (true)
        {
            binary = (higherBound + lowerBound) / 2;
            
            if (count > num_elements)
                return -1;
            else if (higherBound == lowerBound && array[higherBound] == key)
                return higherBound;
            else if (array[binary] == key)
                return binary;                
            else if (array[binary] < key)
                lowerBound = binary + 1;
            else if (array[binary] > key)
                higherBound = binary - 1;
            
            count += 1;
        }     
    }
    
    public void bubblesort ()
    {
        for (int i = 0; i < num_elements - 1; i++)
        {
            for (int j = 0; j < num_elements - 1; j++)
            {
                if (array[j] > array[j + 1])
                {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
    
    public void selectionsort ()
    {
        int temp;
        
        for (int i = 0; i < num_elements - 1; i++)
        {
            temp = i;
            for (int j = i + 1; j < num_elements; j++)
                if (array[j] < array[temp])
                    temp = j;
            
            int temp2 = array[i];
            array[i] = array[temp];
            array[temp] = temp2;
        }
    }
    
    
    public void insertionsort ()
    {
        boolean x;
        
        for (int i = 1; i < num_elements; i++)
        {
            int temp = array[i];
                
            for (int j = i; j > 0; j--)
            {    
                if (temp < array[j - 1])
                {
                   array[j] = array[j - 1];
                   array[j - 1] = temp;                   
                }
                else
                {
                    array[j] = temp;                    
                    break;
                }            
            }              
        }
    }      
    
    public void insert (int x)
    {
        if (num_elements < size)
        {
            array[num_elements] = x;
            
            num_elements += 1;
            
        }
        else 
            System.out.println("Too many items!");     
    }
    
    public void delete (int x)
    {
        int target_element = search(x);
        
        if (target_element == -1)
            System.out.println("Number cannot be found!");
        else
        {
            array[target_element] = 0;
            
            for (int i = target_element; i < num_elements - 1; i++)
                array[i] = array[i + 1];                
            
            array[num_elements - 1] = 0;
            num_elements -= 1;
        }            
    }   
    
    public void print (String s)
    {   
        long startTime; 
        
        if (s.equals("bubblesort"))
        {        
            startTime = System.nanoTime();
            bubblesort();
            System.out.println("Bubble Sort Time: " + (System.nanoTime() - startTime));
        } 
        else if (s.equals("selectionsort"))
        {
            startTime = System.nanoTime();
            selectionsort();
            System.out.println("Selection Sort Time: " + (System.nanoTime() - startTime));
        }
        else if (s.equals("insertionsort"))
        {
            startTime = System.nanoTime();
            insertionsort();
            System.out.println("Insertion Sort Time: " + (System.nanoTime() - startTime));
        }
        
        if (num_elements != 0)
        {
            System.out.print("[");
        
            for(int i = 0; i < num_elements - 1; i++)
                System.out.printf("%d, ", array[i]);     
        
            System.out.printf("%d]\n", array[num_elements - 1]);     
            
        }
        else 
        {
            System.out.print("[");
        
            for(int i = 0; i < array.length - 1; i++)
                System.out.printf("%d, ", array[i]);     
        
            System.out.printf("%d]\n", array[array.length - 1]);
        }
    }
    
    public void clear ()
    {
        for (int i = 0; i < num_elements; i++)
        {
            array[i] = 0;
        }
        num_elements = 0;
    }
}

To use this class, here is the app for it:

public class OrderedArrayApp {

    public static void main(String[] args) {
        OrderedArrayApp main = new OrderedArrayApp();
        main.initialize();
    }

    private void initialize() {
        
        OrderedArray array = new OrderedArray(40);        
        array.insert(63);
        array.insert(37);
        array.insert(209);
        array.insert(110);
        array.insert(96);
        array.insert(32);
        array.insert(90);
        array.insert(2);
        array.insert(4);
        array.insert(87);
        array.insert(93);
        array.insert(46);
        array.insert(98);
        array.insert(90);
        array.insert(32);
        array.insert(35);
        array.insert(53);
        array.insert(67);
        array.insert(76);
                
        
        array.print("insertionsort");
    }
}

All you have to do is to type "bubblesort", "selectionsort", or "insertionsort" in the parameter of the print method that is being called in OrderedArrayApp. If you look at my print method's code, you can see that I am subtracting the time between the method start and complete times to determine the method execution time.

[Eranga]

What's the results you end up with in print method? Same value?

[tabchas]

If I run 5 times consecutively, I get:

For Bubble Sort, I get: 41052, 38734, 39066, 37742 38404
For Selection Sort, I get: 35093, 34100, 33107, 32776, 33106
For Insertion Sort, I get: 33438, 32114, 33107, 32776, 32114

[Toll]

Given that all OS today (at least as far as I know) are multitasking (i.e. you can do more than one thing at once), execution time will vary slightly due to the overhead and background processes. At least that's my assumption as to why it's happening.

[JosAH]

Timing isn't very accurate, at least on MS Windows machines; ignoring the fact that other tasks may steal some time before a timer can be read the accuracy is in the range +- 10ms for an MS Windows machine; nano timers aren't any better, the numbers are just multiplied by 1000000. Linux claims to be accurate to +- 1 ms. I don't know of any JVM running on a RTOS (Real Time Operating System).

kind regards,

Jos

[Toll]

I can't speak for any other Windows, but it seems like Vista has millisecond accuracy too. I know I used to get increments of 13ms or so in older versions, but right now it seems to count the milliseconds properly. At least it works properly for my framerate-thread, keeping it at 30FPS.

[Tolls]

Also note that the nature of the JVM means it can recompile code as that code runs.
So individual timings (as you're doing above) are not all that useful.

[dlorde]

Timing code this way, even with sub-millisecond resolution, is notoriously difficult due to a whole range of influences, from OS loading to memory management and caching at all levels. To get anything useful, you should write code to repeatedly run each method to be timed for as long as you can bear - for example 10,000 or 100,000 times, then get the average duration to compare.

If possible, do this with a profiling tool - they are written with this kind of measurement in mind and often use clever techniques to minimize the influence of external factors on execution time.

[Toll]

Slightly off-topic, but if you're working with sorting algorithms, I can heartily recommend watching "Sorting out Sorting". It's an old educational movie from the 80's, and you can find it on YouTube. The qualty of the sound and video is what you'd expect from the 80's, but it's a good watch nonetheless.

[dlorde]

Continuing that 'ancient wisdom' line ;), Donald Knuth's 'Searching and Sorting' section from 'The Art of Programming' is a timeless classic. Here are some C implementations of sorting algorithms which shouldn't be too hard to translate: Sorting Knuth