Why does calling a function take so long?

Question

I have the following implementation of an insertion sort algorithm:

private static void InsertionSort(List<int> array) { for (int i = 1; i < array.Count; ++i) { for (int j = i; j > 0 && array[j - 1] > array[j]; --j) { //swap(array, j, j-1); int temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; } } } private static void swap(List<int> array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } 

When I run my algorithm using swap(array, j, j-1); , it takes much longer (+2 seconds for 50,000 elements) than if I were executing the body inline function.

Why?

Answer 1

It is incorrect to embed the method manually; it is simply not needed. Embedding small methods is one of the standard optimizations performed by jitter. This does not always happen, but in .NET 4.6.1 both x86 and x64 jitters do inline swap () in this code example. And yet, they also unfold the inner loop to produce two swaps per pass, usually hand optimization programmers usually skip.

Correctly comparing a .NET application is not always so straightforward. It is very important to start the Release build of your program. And do not use a debugger. Although the latter is easy to fix, use Tools> Options> Debug> General> Disable JIT Optimization. There is no good reason for his return.

Now you can also see the generated machine code, set a breakpoint on InsertionSort (), and when using this function, use Debug> Windows> Disassembly. People’s eyes usually bleed, but it's pretty easy to see that you get two built-in swaps (). I will spare you the assembly dump, just look. And you should clearly see the difference in measurement. Here is what I get:

Run 5 times using swap () on a list with 50,000 random integers on x64:

 00:00:05.4447216 00:00:05.2928558 00:00:05.6960587 00:00:05.2835343 00:00:05.2809591 

The same tests, but now manual swap ():

 00:00:05.3015856 00:00:05.2877402 00:00:05.6369775 00:00:05.2603384 00:00:05.2616389 

It is taken as long as it should be.

I would refuse to not show the results that I get with List.Sort ():

 00:00:00.0075878 00:00:00.0073398 00:00:00.0076528 00:00:00.0078046 00:00:00.0066319