Why does my array search take 0 nanoseconds after search is looped beyond 2000 times?

Question

I wrote a program for a Java class I am taking to search a String array of 10 elements for a specific target. The program searches for the target from the beginning of the array to the end of the array and then searches from the end of the array to the beginning of the array. Each search is timed and looped 1000 times. After each search method has been looped 1000 times, the fastest search method is chosen to search the array for whatever number of 'reps' I passed as an argument in the main method.

The problem I am having is when I change the number of loops to beyond 2000. From roughly 2100 the time it takes to search the array in nanoseconds is frequently 0. Is this because the JVM has warmed up and the time it takes to search a 10 element array can't be measured in nanoseconds? I realize that probably sounds silly.

I am just going to paste the whole program here for reference(the program is far from complete but compiles and runs):

public class LinearStringSearch {

    // Array filled with random Strings
    String[] randomStrings = {"apple", "yellow", "fire", "wood", "zinc", 
            "ram", "mouse", "fish", "cheese", "dirt"};

    // Save target arguments for global access(console printing purposes)
    int indexOfTarget;
    String target;  
    String target2; 
    long startTime;
    long startTime2;
    long estimatedTime;
    long estimatedTime2;
    long sumForward;
    long sumBackward;
    long counterFrontToEnd;
    long counterEndToFront;
    long counterTied;

    // Arrays for search times
    ArrayList<Long> forwardSearchTimes = new ArrayList<>();
    ArrayList<Long> backwardSearchTimes = new ArrayList<>();

    /**
     * 
     * @param target - the item you want to retrieve from array
     * @param sa - the name of the array
     * @return i - the target, otherwise return error code: -1
     */
    int linearStringSearch(String target, String[] sa) {    

        this.target = target;                                      // set class variable for print access
        startTime = System.nanoTime();                    // Start speed test
        for(int i = 0; i < sa.length; ++i) {
            if (sa[i].equals(target)) {
                estimatedTime = System.nanoTime() - startTime; // End speed test
                indexOfTarget = i; // update index for printing purposes
                forwardSearchTimes.add(estimatedTime);
                System.out.println("Forwards - Target found at index:" + i + " " + estimatedTime);
                return i; // return the index of target
            }  
        }
        return -1; // -1 means that target was not found
    }

    /**
     * 
     * @param target - the item you want to retrieve from array
     * @param sa - the name of the array
     * @return i - the target, otherwise return error code: -1
     */
    int reverseLinearStringSearch(String target, String[] sa) {
        this.target2 = target;                     // set class variable for print access
        startTime2 = System.nanoTime();            // Start speed test

        for(int i = sa.length-1; i >= 0; --i) {
            if (sa[i].equals(target)) {
                estimatedTime2 = System.nanoTime() - startTime2;  // End speed test
                backwardSearchTimes.add(estimatedTime2);
                System.out.println("Backwards: - Target found at index:" + i + " " + ", Time: " + estimatedTime2);
                return i; // return the index of target
            }
        }
        return -1; // -1 means that target was not found
    }

    /**
     * 
     * @param estimatedTime - estimated time of search beginning to end
     * @param estimatedTime2 - estimated time of search end to beginning 
     * @return fastest method 
     */
    public String deduceFastestSearchMethod() {
        if(sumForward < sumBackward) {
            return "Linear search found " + "'"
                + target + "'" + " fastest overall";
        }
        if(sumForward > sumBackward) {
        return "Reverse linear search found " + 
            "'" + target + "'" + " fastest overall";
        }
        return "Same";
    }

    public void counter(){

        if(estimatedTime < estimatedTime2) {    
            counterFrontToEnd++;
        }
        else if(estimatedTime > estimatedTime2) {
            counterEndToFront++;
        }
        else {
            counterTied++;
        }
    }

    // Implement Fisher–Yates shuffle
    public void shuffleArray(String[] sa){      
        Random rnd = new Random();      
        for (int i = sa.length - 1; i > 0; i--){
            int index = rnd.nextInt(i + 1);

            // Simple swap
            String a = sa[index];
            sa[index] = sa[i];
            sa[i] = a;
        }
    }

    /********************************************************Methods for Repetitions**************************************************/

    // Set the number of times each method is called
    public void setReps(String target, String[] sa, long reps) {
        boolean chosenFastest = false;
        boolean forwardsIsFaster = false;

        shuffleArray(sa); // Shuffle the order of Strings in array

        for (int i = 0; i < reps; i++){ 
           if(chosenFastest){
              if(forwardsIsFaster)
                linearStringSearch(target, sa);
              else
                reverseLinearStringSearch(target, sa);
           } 
           else {
             linearStringSearch(target, sa); 
             reverseLinearStringSearch(target, sa);
             counter(); // counts winner
           } 

           if (i == 1000)
              chosenFastest = true;
              if(sumForward < sumBackward) 
                forwardsIsFaster = true;
              System.out.println("Loop #: " + i + "\n");
        }


        System.out.println("Linear search was faster: " + counterFrontToEnd + " times");
        System.out.println("Reverse linear search was faster: " + counterEndToFront + " times");
        System.out.println("Tied: " + counterTied + " times");
        System.out.println("\nTarget " + "'" + target2 + "'" + " found at index: " + indexOfTarget);

        calcSearchTimesForward(reps);
        calcSearchTimesReverse(reps);
    }

    public void calcSearchTimesForward(long reps) {
        sumForward = 0; 
        double average = 0;

        for (Long i : forwardSearchTimes)
            sumForward += i;
            average = (double)sumForward/reps;
            System.out.println("\nAverage speed searching array front to end(" + reps + " trials):" );
        System.out.println("Nanoseconds: " + average);
    }

    public void calcSearchTimesReverse(long reps) {
        sumBackward = 0;
        double average = 0;

        for (Long i : backwardSearchTimes)
            sumBackward += i;
            average = (double)sumBackward/reps;
        System.out.println("\nAverage speed searching array end to front(" + reps + " trials):" );
        System.out.println("Nanoseconds: " + average);  
    }

    /*
     * The target string is searched from the beginning of the array to the end of the array, then
     * from the end of the array to the beginning of the array. 
     * 
     */
    public static void main(String[] args) {

        LinearStringSearch lss = new LinearStringSearch();

        // Set repetitions 
        lss.setReps("mouse", lss.randomStrings, 10000);  // Pass arguments       

        // Print fastest search
        System.out.println();
        System.out.println(lss.deduceFastestSearchMethod());        
    }   
}

Here is the output:

//................

Backwards: - Target found at index:3 , Time: 453 nanoseconds
Loop #: 9992

Backwards: - Target found at index:3 , Time: 0 nanoseconds
Loop #: 9993

Backwards: - Target found at index:3 , Time: 0 nanoseconds
Loop #: 9994

Backwards: - Target found at index:3 , Time: 0 nanoseconds
Loop #: 9995

Backwards: - Target found at index:3 , Time: 0 nanoseconds
Loop #: 9996

Backwards: - Target found at index:3 , Time: 0 nanoseconds
Loop #: 9997

Backwards: - Target found at index:3 , Time: 0 nanoseconds
Loop #: 9998

Backwards: - Target found at index:3 , Time: 0 nanoseconds
Loop #: 9999

Linear search was faster: 432 times
Reverse linear search was faster: 282 times
Tied: 287 times

Target 'mouse' found at index: 3

Average speed searching array front to end(10000 trials):
Nanoseconds: 167.1195

Average speed searching array end to front(10000 trials):
Nanoseconds: 967.341

Linear search found 'mouse' fastest overall

Computers are fast, and clocks don't have a good accuracy. Searching through an array of size 10 (and thus iterating 5 times on average) is an extremely fast task for a modern computer. Use arrays of, let's say 100,000 or 1,000,000 elements. — JB Nizet, Jan 26 '14 at 23:06
I actually don't think that's silly at all. If the size of the array to search is not specified by the assignment, try making it *much* larger. Or even better, make several and randomly choose one for each loop. — William Gaul, Jan 26 '14 at 23:07
Just as the others said above, that code runs fast. I'd also add that that nanotime() is not the best method. From the documentation: _This method provides nanosecond precision, but not necessarily nanosecond accuracy_. — webuster, Jan 26 '14 at 23:13

score 2 · Accepted Answer · edited May 23 '17 at 12:11

Generally, a JVM will implement System.nanoTime() using the most accurate timer the operating system provides, but that usually isn't accurate down to the nano second, not is querying that timer instantenous (on my hardware, it takes 2 microseconds). And even if it were, your program is not guaranteed exclusive use of the hardware by the operating system, i.e. if another process wants the CPU, the operating system may suspend your program for a couple milliseconds to give the other process a chance to run.

Therefore, if you want a reliable benchmark, you can only assume the timer to be accurate to a couple milliseconds. The typical workaround is something like this:

long start = System.nanoTime();
for (int i = 0; i < reps; i++) {
    codeToTest();
}
long end = System.nanoTime();
System.out.println((end - start) / reps + " ns");

where reps is chosen so elapsed time is suitably big.

For a truly good benchmark, you should also take the effects of just in time compilation into account. A quite comprehensive list may be found at How do I write a correct micro-benchmark in Java?

Why does my array search take 0 nanoseconds after search is looped beyond 2000 times?

1 Answers1