Help optimizing insertion sort in asm x86

Have you looked at what the C++ compiler is generating?

I suspect the problem is pushing and popping the number of items in the outer loop. I've only limited experience in writing x86 assember, but is there any reason you're not using EDX for the key or N?

Good question. I forgot about EDX at that moment.
Anyway, I made the change and used EDX for the key but there was no difference in the performance unfortunately.

Have you tried looking at the compiler's version?

Yes, I did. It looks quite similar, except that it has more MOV operations than mine and the for loop is done in a different way (that I can't really understand).

I tried my code in a different computer and I realized that, even though it's still slower than the C++ version, the percentage of difference is quite contrasting. In one computer the difference is of more than double, while in the other one the difference is just about 15%... Which is kinda baffling.

What does your C++ code look like? How are you testing it? Can you post your test?

Here's the C++ code:



void InsertionSort(int* vArray, int nNumElements)
{
int j(0), key(0);
for(int i = 1; i < nNumElements; i++)
{
key = vArray;
j = i-1;
while((j>=0) && (vArray[j]>key))
{
vArray[j+1] = vArray[j];
j--;
}
vArray[j+1] = key;
}
}




The test is simple, I make an array with 10,000 random ints, then sort it and time the function. This test is run 100 times and the average time is calculated.

Looking at your original assembler more closely, you're using push and pop to assign values in an inner loop? Avoid this!

int* vSortedArray
[/quote]
This name is misleading - the array isn't sorted until the function returns. I'd call it ... "array".

short sCurrentIndex
[/quote]
Again, misleading - the current indices in this function are i and j. I'd call this "n", "length", "max", something like that.

Also, "short" - you don't want to support sorting more than 32,000 values?

The test is simple, I make an array with 10,000 random ints, then sort it and time the function. This test is run 100 times and the average time is calculated.
[/quote]

I tried my code in a different computer and I realized that, even though it's still slower than the C++ version, the percentage of difference is quite contrasting. In one computer the difference is of more than double, while in the other one the difference is just about 15%... Which is kinda baffling.
[/quote]
You could be spilling outside the cache on one machine, and keeping inside the cache on another. This could "even up" the difference if your version hits memory more often (as it would seem to if it keeps touching the stack).

Try writing the tests to support a variable number of elements and iterations. That way you can test sorting 1,000 elements 1,000,000 times, and 1,000,000 elements 1,000 times, or any other combination. This might be able to prove or disprove the cache theory, by choosing an arrays to fit the various cache sizes on each machine, and seeing what happens when the array doesn't fit on one vs does fit on another.

This function wasn't a separate function, I just had it in the main code, and I had two arrays (an unsorted one that was gonna be kept in order to test it with the different algorithms) and a second array that would be sorted and printed out, so I just called it "vSortedArray".
The current index thing is because I'm using that variable in the code as well (the whole thing is a windows forms program that allows to add numbers to the list, reset the list, choose which algorithms to use, etc).
That's the reason the variables are named like that. If I were to put this as a separate function, of course I would rename it, but for here I just copy pasted and made a fake function header.

I'll edit the post to make the names more readable.

Anyway, back to the assembly… What's wrong with pushing and popping inside the loop? I thought it would be a fast thing, after all, I'm also doing it in my other sorting algorithms and it didn't cause a performance issue.

About the cache thing… I already tried different combinations, I tried combining different array sizes with different loop sizes, I even tried using different numbers for the possibilities of numbers within the array (in order to test arrays with many unique values and arrays with lots of repeated values), and the difference in performance was the same.

Here's a few more ideas to try:

When you're multiplying by a power of two, a left shift is more efficient than a multiply. That's outside the loop though so it won't make much difference, unless the array is very small.

Instead of having an unconditional jump back to the start of the loop, and then immediately doing a test and another jump, consider doing that test at the end of the loop. You can put a jump to that test just before the start of the loop to keep the order of operations the same.

In my experience the compiler will generally turn variables used as array indices into direct pointers when it can. That way there's generally no need to add the start of array offset every time round the loop. That cuts out some extra additions, and more importantly shortens dependency chains. When doing this you'll also need to create a pointer to the end of the array instead of using the count of elements to test against.

Anyway, back to the assembly… What's wrong with pushing and popping inside the loop? I thought it would be a fast thing, after all, I'm also doing it in my other sorting algorithms and it didn't cause a performance issue.
[/quote]

That will read your value and put it on the stack, then read it back from the stack and put it back. It's better to just put it in a register and then move it back to memory.