Question

http://ideone.com/eNRWK

Why is my isort() much slower than insertion_sort?

Answer 1

EDIT: http://ideone.com/HjOg0 changed a few things.

Turns out they actually have similar performance! It's just that insertion-sort is slow at sorting a million integers :-P

Answer 2

EDIT: Actually, my isort() is slower :(

How do I make it faster?

Answer 3

This is the isort() disassembly:
____________________________________________________________________________________
004015E4 push %ebp
004015E5 mov %esp,%ebp
004015E7 push %edi
004015E8 push %esi
004015E9 push %ebx
004015EA sub $0x4c,%esp
004015ED mov 0x8(%ebp),%eax
004015F0 mov %eax,-0x2c(%ebp)
004015F3 mov 0xc(%ebp),%esi
004015F6 mov %esi,-0x38(%ebp)
004015F9 mov 0x10(%ebp),%eax
004015FC mov %eax,-0x1c(%ebp)
004015FF mov 0x14(%ebp),%esi
00401602 mov %esi,-0x30(%ebp)
00401605 mov %eax,(%esp)
00401608 call 0x408288 <malloc>
0040160D mov %eax,-0x28(%ebp)
00401610 test %eax,%eax
00401612 je 0x4016c1 <isort+221>
00401618 mov -0x2c(%ebp),%eax
0040161B add -0x1c(%ebp),%eax
0040161E mov %eax,-0x34(%ebp)
00401621 sub -0x2c(%ebp),%eax
00401624 xor %edx,%edx
00401626 divl -0x1c(%ebp)
00401629 cmp %eax,-0x38(%ebp)
0040162C jbe 0x4016c1 <isort+221>
00401632 mov -0x1c(%ebp),%esi
00401635 neg %esi
00401637 mov %esi,-0x24(%ebp)
0040163A xchg %ax,%ax
0040163C mov -0x28(%ebp),%edi
0040163F mov -0x34(%ebp),%esi
00401642 mov -0x1c(%ebp),%ecx
00401645 rep movsb %ds:(%esi),%es:(%edi)
00401647 mov -0x34(%ebp),%eax
0040164A cmp %eax,-0x2c(%ebp)
0040164D jae 0x4016d8 <isort+244>
00401653 mov -0x34(%ebp),%esi
00401656 sub -0x1c(%ebp),%esi
00401659 mov %esi,-0x20(%ebp)
0040165C mov -0x34(%ebp),%ebx
0040165F mov %ebx,%edx
00401661 jmp 0x401680 <isort+156>
00401663 nop
00401664 mov %edx,%edi
00401666 mov %ebx,%esi
00401668 mov -0x1c(%ebp),%ecx
0040166B rep movsb %ds:(%esi),%es:(%edi)
0040166D mov -0x24(%ebp),%eax
00401670 add %eax,-0x20(%ebp)
00401673 mov -0x20(%ebp),%eax
00401676 sub -0x24(%ebp),%eax
00401679 cmp %eax,-0x2c(%ebp)
0040167C jae 0x4016d4 <isort+240>
0040167E mov %ebx,%edx
00401680 mov -0x24(%ebp),%esi
00401683 lea (%edx,%esi,1),%ebx
00401686 mov -0x28(%ebp),%esi
00401689 mov %esi,0x4(%esp)
0040168D mov %ebx,(%esp)
00401690 mov %edx,-0x3c(%ebp)
00401693 call *-0x30(%ebp)
00401696 test %eax,%eax
00401698 mov -0x3c(%ebp),%edx
0040169B jg 0x401664 <isort+128>
0040169D mov %edx,%edi
0040169F mov -0x28(%ebp),%esi
004016A2 mov -0x1c(%ebp),%ecx
004016A5 rep movsb %ds:(%esi),%es:(%edi)
004016A7 mov -0x1c(%ebp),%eax
004016AA add %eax,-0x34(%ebp)
004016AD mov -0x34(%ebp),%eax
004016B0 sub -0x2c(%ebp),%eax
004016B3 xor %edx,%edx
004016B5 divl -0x1c(%ebp)
004016B8 cmp -0x38(%ebp),%eax
004016BB jb 0x40163c <isort+88>
004016C1 mov -0x28(%ebp),%esi
004016C4 mov %esi,0x8(%ebp)
004016C7 add $0x4c,%esp
004016CA pop %ebx
004016CB pop %esi
004016CC pop %edi
004016CD leave
004016CE jmp 0x4082e0 <free>
004016D3 nop
004016D4 mov %ebx,%edx
004016D6 jmp 0x40169d <isort+185>
004016D8 mov %eax,%edx
004016DA jmp 0x40169d <isort+185>
_______________________________________________________________________

This is the insertion_sort() disassembly:
_______________________________________________________________________
00401318 push %ebp
00401319 mov %esp,%ebp
0040131B push %edi
0040131C push %esi
0040131D push %ebx
0040131E sub $0x4,%esp
00401321 cmpl $0x1,0xc(%ebp)
00401325 jbe 0x401373 <insertion_sort+91>
00401327 mov 0x8(%ebp),%eax
0040132A mov $0x1,%edi
0040132F nop
00401330 mov 0x4(%eax),%esi
00401333 lea 0x4(%eax),%edx
00401336 mov %edx,-0x10(%ebp)
00401339 mov %edx,%ecx
0040133B mov %edi,%edx
0040133D lea 0x0(%esi),%esi
00401340 mov (%eax),%ebx
00401342 cmp %ebx,%esi
00401344 jge 0x401364 <insertion_sort+76>
00401346 mov %ebx,(%ecx)
00401348 sub $0x4,%eax
0040134B sub $0x4,%ecx
0040134E dec %edx
0040134F jne 0x401340 <insertion_sort+40>
00401351 xor %edx,%edx
00401353 mov 0x8(%ebp),%eax
00401356 mov %esi,(%eax,%edx,1)
00401359 inc %edi
0040135A cmp 0xc(%ebp),%edi
0040135D je 0x401373 <insertion_sort+91>
0040135F mov -0x10(%ebp),%eax
00401362 jmp 0x401330 <insertion_sort+24>
00401364 shl $0x2,%edx
00401367 mov 0x8(%ebp),%eax
0040136A mov %esi,(%eax,%edx,1)
0040136D inc %edi
0040136E cmp 0xc(%ebp),%edi
00401371 jne 0x40135f <insertion_sort+71>
00401373 pop %eax
00401374 pop %ebx
00401375 pop %esi
00401376 pop %edi
00401377 leave
00401378 ret

Answer 4

btw why do they both start the same? :-D

Answer 5

why is there a nop in isort?

Answer 6

Now I get it.... is it because isort() uses a function pointer?

Answer 7

The function pointer might make it 1% slower; looks like your isort() is slower due to all the memcpy() calls. And yeah, an insertion (or bubble) sort is about as slow as you get :).

Answer 8

I don't know about that; even if I replace the assignments in the original insertion_sort() function with memcpy() calls, it runs just as fast. I think there's another reason why isort() is slower :(

Answer 9

lets see what happens if I replace the whole thing by a macro :-D

Answer 10

How much slower is it? I mean, the size calculations you're doing to be able to use a void pointer means more processing, but I would have guessed the two routines would run in the same order of time.

Answer 11

It's about twice as slow as insertion_sort, but I will double check that again.

btw after replacing it by a macro isort is much faster now.

Answer 12

Yeah, the function call mechanism, especially in a tight loop like that, will slow things down a good bit, especially vs. inline code. With the size math and function call overhead, twice the time sounds reasonable, to me.