4

This question is similar to (link) but not exactly what I am looking for. Here is a selection sort I wrote below, it's in Java.

public void sort() {

    int smallIndex;

    for(int i = 0; i < arr.length; i++) {

        smallIndex = i;

        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[smallIndex]) {

                smallIndex = j;
            }
        }

        if(i < smallIndex)
            swap(i, smallIndex);
    }
}

Here is my swap method. 

public void swap(int a, int b) {

    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

I am filling an array with 50,000 random elements between 0 and 999. The method sorts it fine. Each execution is about 1400 milliseconds (1300 - 1500).

Here is a selection sort from a book I was looking at.

public void sortBook() {

    for(int i = 0; i < arr.length; i++) {

        int minPos = minimumPosition(i);
        swap(minPos, i);
    }
}

Here is the minimumPosition method.

public int minimumPosition(int from) {

    int minPos = from;

    for(int i = from + 1; i < arr.length; i++) {

        if(arr[i] < arr[minPos]) {

            minPos = i;
        }
    }

    return minPos;
}

The swap method is the one I am using from above. I am consistently getting around 700 millisecond execution time for this with 50,000 elements with a range of 0 - 999.

My question is why does sort() take almost twice as long to execute as sortBook(). I have stepped through them both on smaller arrays and they seem to take the same amount of steps to do the same thing, sort() only swaps sometimes, the sortBook() swaps every time. To my novice eye, they look to be doing almost the exact same thing.

I don't understand why sort() takes roughly double the time sortBook() does. Anybody have any insights as to why this is the case?

Alex Shesterov
  • 26,085
  • 12
  • 82
  • 103
Joshua Davis
  • 41
  • 1
  • How exactly do you measure the execution times? – RealSkeptic Mar 18 '17 at 18:36
  • Made a StopWatch class that I start before the sort and stop after the sort, then print the time in milliseconds. The times are pretty consistent so I am pretty sure those numbers are correct. – Joshua Davis Mar 18 '17 at 19:13
  • Did you do warmup? Did you try to run the methods in a different order? My results are 561ms for the booksort and 630 for your own. – RealSkeptic Mar 18 '17 at 19:13
  • What does a warmup mean? Here is the code for my stopwatch class, it could be wrong. [StopWatch.java on ideone.com](http://ideone.com/zsZujX) – Joshua Davis Mar 18 '17 at 19:30
  • Try running these with the jvm option `-Xcomp`. The JVM compiles and optimizes dynamically so single runs are a poor way to measure performance, or rather, even more poor than usual. – pvg Mar 18 '17 at 19:40
  • Using the -Xcomp option my method is about 100 ms faster. But I am trying to understand why the methods have such a drastic difference in run times. – Joshua Davis Mar 18 '17 at 19:46
  • I've tested it too and can confirm. The problem is in minimumPosition method. Calling it (instead of using nested cycle) makes algorithm faster. But I can't understand why for now... – Viacheslav Zhukov Mar 18 '17 at 19:52
  • They don't have drastic differences in run times. You just have very naive measurements - as I said, the JVM is a rather complicated dynamic compilation/optimization runtime. If you want to do this properly, use something like this http://openjdk.java.net/projects/code-tools/jmh/ – pvg Mar 18 '17 at 19:54
  • @VyacheslavZhukov because the unit of optimization is a method - in the naive measurement, sort only runs once and is never compiled and optimized. In sortBook, the inner method is called sufficiently often to cross the invocation threshold for JIT'ing. it then gets compiled and optimized and in a single sort invocation, you get something that appears faster. – pvg Mar 18 '17 at 19:55
  • Thanks, Vyacheslav I was kinda thinking the same thing. But really isn't the method just doing the exact same thing I am doing? I am having a hard time understanding why using another helper method (minimumPosition) would make the sort that much faster. – Joshua Davis Mar 18 '17 at 19:56
  • Because it gets compiled to native code. The JVM makes decisions about what to compile on the fly, dynamically, at runtime. Hence the 'just in time' part of 'just in time compilation'. – pvg Mar 18 '17 at 19:57
  • If you want to measure this more accurately, measure the runtime of, say, 10,000 invocations of `sort` and `sortBook`. Put them in a loop and measure that. Reduce the list size to something smaller to keep the total time reasonable. The 2x difference will go away. – pvg Mar 18 '17 at 20:03
  • @pvg thank you. So are you saying my StopWatch class sucks at measuring time? Or that Java is always going to optimize sortBook() and will never optimize sort()? And really the efficiency of both methods is the same, just in Java sortBook() is being optimized to run faster? – Joshua Davis Mar 18 '17 at 20:12
  • @pvg Haha, I already did it :) And you are completely right, the time of sort method became exactly like the time of sortBook method. I think you could post an answer :) – Viacheslav Zhukov Mar 18 '17 at 20:13
  • @pvg Thanks a bunch. I did a loop with 1000 invocations and the time is already starting to even out. Thanks so much, it was really bothering me as both methods really seem alike. And sorry if the question is kinda low level, I really didn't have any clue why that was happening. Thanks again. Thanks to everybody that replied as well. – Joshua Davis Mar 18 '17 at 20:18
  • No, I'm saying your _methodology_ for measuring performance in the JVM is flawed and produces very unreliable results. And yes, the methods have the same average performance. – pvg Mar 18 '17 at 20:18
  • No, it's a perfectly decent question with a somewhat convoluted, non-obvious answer. But it mostly has to do with the details of the JVM than the implementations of the `sort` and `sortBook` as might initially appear. – pvg Mar 18 '17 at 20:19
  • @pvg Can you write an answer detailing the cause? I find it interesting but couldn't get to the bottom of this from the comment thread – Yossi Vainshtein Mar 18 '17 at 21:29
  • @4castle it's not a dupe since it doesn't actually answer this particular question. It's certainly related but the poster did not ask 'how do i write a microbenchmark' at all. – pvg Mar 18 '17 at 21:43
  • @pvg It's the canonical duplicate, because all descriptions of the speed discrepency can be found in the other question's answers. It's not the question which is important when selecting a duplicate, it's the answers. Anyone browsing the site who finds this question would be more helped by the canonical duplicate, because the premise of this question is faulty. – 4castle Mar 18 '17 at 22:25
  • @4castle maybe I'm missing it but this specific effect, which is what the question is about is not described in the answers. This question boils down to 'how come adding a method to my implementation makes something faster'. The premise of the question is not faulty, this is a real, easily observable thing. The questions is about _why_ this happens, not how to avoid it when making measurements. – pvg Mar 18 '17 at 22:43

2 Answers2

0

One of the extra comparison step which i can see in your code base is 

if(i < smallIndex)

Can you please this step and see if you get the same results.

Jason1
  • 101
  • 4
  • The reason I added that was so I was not swapping locations every single time, seemed more like a bubble sort if I did that. Removing it does not change the execution time at all. – Joshua Davis Mar 18 '17 at 19:27
  • I don't know who downvoted this answer. I came to the same conclusion. When benchmarking *correctly*, the OP's method is a little more expensive than the book method, and the difference disappears when the `if` is removed. @JoshuaDavis The chance of the `if` being `false` is very small because of your choice of data. So you are making both comparisons and swaps in every step of the outer loop, whereas the book version just makes the swaps (with very few additional swaps that your `if` catches) and doesn't have the extra comparisons. – RealSkeptic Mar 19 '17 at 11:41
0

Firstly, there is no mathematical reason yours should be any slower than the one from the book, they are ostensibly the same. When I ran these against each other, I got about 400ms for yours and 450 for the books. I think the problem comes from your timing, often variation can be caused by the cpu doing other things while running, so any difference I see dispersal under error analysis. Even the time difference that you identifier is almost meaningless, at this scale it is irrelevant the difference in timing. Furthermore, if efficiency is something that is really important, try implementing heapSort for a fun challenge, and I'd recommend working in c or c++, something which gives better performance. Have fun!

Justin Sanders
  • 313
  • 2
  • 12