Sort Array

[MichaelW]

Using FreeBASIC Compiler - Version 0.23.0 (08-14-2011) for win32 (target:win32) with -exx I get no errors, but the sorts run ~3x slower.

@MichaelW
'qsort' is not faster (is a fake :))

Yes, I forgot to randomize the array between the sorts, and now that I have for the 1000000-element array, qsort is ~80x slower, and that is with the fastest possible compare function.

The problem is the calls to the compare function. I have a qsort function with an internal compare that I created by modifying the Microsoft qsort source from the PSDK. Using it, in object module form, compiled with the Microsoft compiler and /O2 /G6, with the same 1000000-element array, re-randomized after the first sort, typical results are:

Code: Select all

 0.9495
 0.2975

[Richard]

@ I3I2UI/I0.
Thanks for that. It makes a big difference and puts _qsort back in front.

[fxm]

Using FreeBASIC Compiler - Version 0.23.0 (08-14-2011) for win32 (target:win32) with -exx I get no errors, but the sorts run ~3x slower.

But the sorting does not work!

Code: Select all

'=========================================================================
#include "crt.bi"
'=========================================================================

function compare naked cdecl( byval elem1 as any ptr, _
                              byval elem2 as any ptr ) as integer
  asm
      mov ecx, [esp+4]
      mov edx, [esp+8]
      mov eax, [ecx]
      sub eax, [edx]
      ret
  end asm

end function

'=========================================================================

dim as integer a(0 to 99)

for i as integer = 0 to 99
  a(i) = rnd * 99
  print a(i);chr(9);
next
print

qsort( @a(0), 100, 4, @compare )

for i as integer = 0 to 99
  print a(i);chr(9);
next

sleep

[MichaelW]

Using FreeBASIC Compiler - Version 0.23.0 (08-14-2011) for win32 (target:win32) with -exx I get no errors, but the sorts run ~3x slower.

But the sorting does not work!

It works for me. Here are the results of the code that you posted with -exx (exactly the same as without -exx):

Code: Select all

 33      33      53      75      64      65      29      96      96      94
 53      67      7       66      2       49      4       46      82      81
 89      27      32      47      43      55      87      25      18      54
 38      31      41      27      84      47      28      67      76      47
 34      63      96      41      53      66      71      58      92      80
 78      90      84      28      96      9       60      42      1       97
 1       57      33      78      79      51      71      23      74      40
 78      91      11      41      29      89      77      13      69      5
 27      35      51      6       41      32      1       85      95      18
 54      18      61      94      55      62      78      94      43      92

 1       1       1       2       4       5       6       7       9       11
 13      18      18      18      23      25      27      27      27      28
 28      29      29      31      32      32      33      33      33      34
 35      38      40      41      41      41      41      42      43      43
 46      47      47      47      49      51      51      53      53      53
 54      54      55      55      57      58      60      61      62      63
 64      65      66      66      67      67      69      71      71      74
 75      76      77      78      78      78      78      79      80      81
 82      84      84      85      87      89      89      90      91      92
 92      94      94      94      95      96      96      96      96      97

Could the problem be another -exx related bug?

[Richard]

With recursive algorithms the initialisation code becomes important because it is exercised more than once. Elimination of the Int() function and a divide can squeeze a little more out of _qsort.
Replace;
Dim As Uinteger I = start, J = Finish, X = NumArray(Int((I+J)/2)), A
with;
Dim As Uinteger I = start, J = Finish, x = NumArray((i+j) Shr 1), A

[fxm]

Using FreeBASIC Compiler - Version 0.23.0 (08-14-2011) for win32 (target:win32) with -exx I get no errors, but the sorts run ~3x slower.

But the sorting does not work!

It works for me. Here are the results of the code that you posted with -exx (exactly the same as without -exx):

Code: Select all

 33      33      53      75      64      65      29      96      96      94
 53      67      7       66      2       49      4       46      82      81
 89      27      32      47      43      55      87      25      18      54
 38      31      41      27      84      47      28      67      76      47
 34      63      96      41      53      66      71      58      92      80
 78      90      84      28      96      9       60      42      1       97
 1       57      33      78      79      51      71      23      74      40
 78      91      11      41      29      89      77      13      69      5
 27      35      51      6       41      32      1       85      95      18
 54      18      61      94      55      62      78      94      43      92

 1       1       1       2       4       5       6       7       9       11
 13      18      18      18      23      25      27      27      27      28
 28      29      29      31      32      32      33      33      33      34
 35      38      40      41      41      41      41      42      43      43
 46      47      47      47      49      51      51      53      53      53
 54      54      55      55      57      58      60      61      62      63
 64      65      66      66      67      67      69      71      71      74
 75      76      77      78      78      78      78      79      80      81
 82      84      84      85      87      89      89      90      91      92
 92      94      94      94      95      96      96      96      96      97

Could the problem be another -exx related bug?

It does not work for me:

Code: Select all

 33      33      53      75      64      65      29      96      96      94
 53      67      7       66      2       49      4       46      82      81
 89      27      32      47      43      55      87      25      18      54
 38      31      41      27      84      47      28      67      76      47
 34      63      96      41      53      66      71      58      92      80
 78      90      84      28      96      9       60      42      1       97
 1       57      33      78      79      51      71      23      74      40
 78      91      11      41      29      89      77      13      69      5
 27      35      51      6       41      32      1       85      95      18
 54      18      61      94      55      62      78      94      43      92

 33      33      53      75      64      65      29      43      78      62
 53      67      7       66      2       49      4       46      55      61
 18      27      32      47      43      55      54      25      18      54
 38      31      41      27      18      47      28      67      76      47
 34      63      1       41      53      66      71      58      32      41
 78      6       51      28      35      9       60      42      1       27
 1       57      33      78      5       51      71      23      74      40
 78      69      11      41      29      13      77      89      91      79
 82      81      84      90      80      92      89      85      92      84
 87      94      94      94      95      96      96      96      96      97

• Command executed:
  "D:\Prg\FXM\fbc\fbc.exe" "D:\Prg\FXM\fbc\FBIDETEMP.bas" -exx
  
  Results:
  Compilation successful
  Generated executable: D:\Prg\FXM\fbc\FBIDETEMP.exe
  
  System:
  FBIde: 0.4.6
  fbc: FreeBASIC Compiler - Version 0.23.0 (08-14-2011) for win32 (target:win32)
  OS: Windows XP (build 2600, Service Pack 3)

[fxm]

[Edit]
Message suppressed because erroneous.

[MichaelW]

My previous tests were under Windows 2000, where the EXE worked with or without -exx. But under Windows XP, with -exx when I run the EXE from a command prompt or from a batch file I get:

Aborting due to runtime error 12 ("segmentation violation" signal)…

And if I run the EXE from the desktop by double clicking it, the window closes almost immediately but I can occasionally see the “Aborting due to…” message.

Without -exx the EXE works normally.

I suspect that FBIde is somehow masking the problem.

[fxm]

My previous tests were under Windows 2000, where the EXE worked with or without -exx. But under Windows XP, with -exx when I run the EXE from a command prompt or from a batch file I get:

Aborting due to runtime error 12 ("segmentation violation" signal)…

And if I run the EXE from the desktop by double clicking it, the window closes almost immediately but I can occasionally see the “Aborting due to…” message.

Without -exx the EXE works normally.

I suspect that FBIde is somehow masking the problem.

How to monitor a runtime error, compiling with the option -exx
(I am always using this option)

• Rustic solution :
  Launch your "program.exe" from a (prompt) command window, in order to display the runtime error message.
• Using FBIde :
  Referring to http://www.freebasic.net/forum/viewtopi ... 31#p121731, you can edit the run command menu and enter "cmd /c "<$file>" <$param> & pause", in order that IDE opens a command window, runs the program, and then waits for a keypress before closing.
• Using FreeQ IDE:
  You get automatically a pause (in the command window) after compiling + running with option "-exx", and also you can just select a check-box "Pause after execution" to pause after compile + run (without "-exx")
• Using Geany :
  Basically, the command "Execute" runs the executable file from a terminal window (shell script calling "cmd.exe" set per default in the menu "Edit/Preferences/Tools).
• Using FBEdit :
  Only the rustic solution : launching the executable file from a command window opened with menu "Tools/Command prompt".

[I3I2UI/I0]

I have the same Error as @fxm
Only the 'naked' with '-exx' option makes the mistake.

System:
FBEdit: 1.0.7.6c
fbc: FreeBASIC Compiler - Version 0.23.0 (08-14-2011) for win32 (target:win32)
OS: Windows 7 (Service Pack 1)

edit:

Code: Select all

_Qsort     0.490
ASM_QSort  0.377
RapidSort  0.235
C qsort    0.717

[fxm]

Just a test program to lighten this bug.
8 shortest asm functions, 4 not naked functions and 4 similar naked functions, that just return the value (1234) of the passed data.
Variable or pointer are passed by value or by reference (notation: var/ptr passed byval/byref):
- 'pass_byval_var', 'pass_byval_ptr', 'pass_byref_var', 'pass_byref_ptr'
- 'pass_naked_byval_var', 'pass_naked_byval_ptr', 'pass_naked_byref_var', 'pass_naked_byref_ptr'

Code: Select all

function pass_byval_var cdecl(byval v as integer) as integer
  asm
      mov eax, [v]
      mov [function], eax
  end asm
end function

function pass_byval_ptr cdecl(byval p as integer ptr) as integer
  asm
      mov eax, [p]
      mov eax, [eax]
      mov [function], eax
  end asm
end function

function pass_byref_var cdecl(byref v as integer) as integer
  asm
      mov eax, [v]
      mov eax, [eax]
      mov [function], eax
  end asm
end function

function pass_byref_ptr cdecl(byref p as integer ptr) as integer
  asm
      mov eax, [p]
      mov eax, [eax]
      mov eax, [eax]
      mov [function], eax
  end asm
end function

function pass_naked_byval_var naked cdecl(byval v as integer) as integer
  asm
      mov eax, [esp+4]
      ret
  end asm
end function

function pass_naked_byval_ptr naked cdecl(byval p as integer ptr) as integer
  asm
      mov eax, [esp+4]
      mov eax, [eax]
      ret
  end asm
end function

function pass_naked_byref_var naked cdecl(byref v as integer) as integer
  asm
      mov eax, [esp+4]
      mov eax, [eax]
      ret
  end asm
end function

function pass_naked_byref_ptr naked cdecl(byref p as integer ptr) as integer
  asm
      mov eax, [esp+4]
      mov eax, [eax]
      mov eax, [eax]
      ret
  end asm
end function

dim test as integer = 1234
print pass_byval_var(test); pass_byval_ptr(@test); pass_byref_var(test); pass_byref_ptr(@test)
print pass_naked_byval_var(test); pass_naked_byval_ptr(@test); pass_naked_byref_var(test); pass_naked_byref_ptr(@test)
sleep

- Result when compiling without option '-exx':
1234 1234 1234 1234
1234 1234 1234 1234
=> OK

- Result when compiling with option '-exx':
1234 1234 1234 1234
1234 4219376 4219476 4219576
=>NON OK for the 3 asm naked functions: 'pass_naked_byval_ptr', 'pass_naked_byref_var', 'pass_naked_byref_ptr'.
Only 'pass_naked_byval_var works' (variable naked passed by value).

This defect (with compiler option '-exx') exists since fbc version 0.21.0 where the naked functions appeared.

[MichaelW]

Testing Version 0.23.0 (08-14-2011) for win32 (target:win32), compiling with -exx, the added code is writing to local variables that don’t exist in the naked functions.

Code: Select all

.globl _PASS_BYVAL_VAR
_PASS_BYVAL_VAR:
push ebp
mov ebp, esp
sub esp, 12
push ebx
push esi
push edi
mov dword ptr [ebp-4], 0
push offset _Lt_0008
call _fb_ErrorSetModName@4
mov dword ptr [ebp-8], eax
push offset _Lt_000A
call _fb_ErrorSetFuncName@4
mov dword ptr [ebp-12], eax
.Lt_0006:
mov eax, [ebp+8]
mov [ebp-4], eax
.Lt_0007:
push dword ptr [ebp-12]
call _fb_ErrorSetFuncName@4
push dword ptr [ebp-8]
call _fb_ErrorSetModName@4
mov eax, dword ptr [ebp-4]
pop edi
pop esi
pop ebx
mov esp, ebp
pop ebp
ret

Code: Select all

.globl _PASS_NAKED_BYVAL_VAR
_PASS_NAKED_BYVAL_VAR:
.Lt_001B:
push offset _Lt_0008
call _fb_ErrorSetModName@4
mov dword ptr [ebp-4], eax   <----<<<
push offset _Lt_001E
call _fb_ErrorSetFuncName@4
mov dword ptr [ebp-8], eax   <----<<<
mov eax, [esp+4]
ret
.Lt_001C:
push dword ptr [ebp-8]
call _fb_ErrorSetFuncName@4
push dword ptr [ebp-4]
call _fb_ErrorSetModName@4

IMO naked functions should be exempted from the effects of -exx.

[fxm]

But the two asm listing above correspond to cases which work!

Now below, for asm specialists:
- one case which works: function pass_byval_ptr cdecl(byval p as integer ptr) as integer
- one case which does not work: function pass_naked_byval_ptr naked cdecl(byval p as integer ptr) as integer
Together compiled with option '-exx'.

Code: Select all

function pass_byval_ptr cdecl(byval p as integer ptr) as integer
  asm
      mov eax, [p]
      mov eax, [eax]
      mov [function], eax
  end asm
end function

dim test as integer = 1234
print pass_byval_ptr(@test)

Code: Select all

.globl _PASS_BYVAL_PTR
_PASS_BYVAL_PTR:
push ebp
mov ebp, esp
sub esp, 12
push ebx
push esi
push edi
mov dword ptr [ebp-4], 0
push offset _Lt_0007
call _fb_ErrorSetModName@4
mov dword ptr [ebp-8], eax
push offset _Lt_0009
call _fb_ErrorSetFuncName@4
mov dword ptr [ebp-12], eax
.Lt_0004:
mov eax, [ebp+8]
mov eax, [eax]
mov [ebp-4], eax
.Lt_0005:
push dword ptr [ebp-12]
call _fb_ErrorSetFuncName@4
push dword ptr [ebp-8]
call _fb_ErrorSetModName@4
mov eax, dword ptr [ebp-4]
pop edi
pop esi
pop ebx
mov esp, ebp
pop ebp
ret
.balign 16
_fb_ctor__FBIDETEMP:
push ebp
mov ebp, esp
sub esp, 12
.Lt_0002:
push offset _Lt_000C
call _fb_ErrorSetModName@4
mov dword ptr [ebp-8], eax
push offset _Lt_000E
call _fb_ErrorSetFuncName@4
mov dword ptr [ebp-12], eax
mov dword ptr [ebp-4], 1234
push 1
lea eax, [ebp-4]
push eax
call _PASS_BYVAL_PTR
add esp, 4
push eax
push 0
call _fb_PrintInt@12
.Lt_0003:
push dword ptr [ebp-12]
call _fb_ErrorSetFuncName@4
push dword ptr [ebp-8]
call _fb_ErrorSetModName@4
mov esp, ebp
pop ebp
ret

Code: Select all

function pass_naked_byval_ptr naked cdecl(byval p as integer ptr) as integer
  asm
      mov eax, [esp+4]
      mov eax, [eax]
      ret
  end asm
end function

dim test as integer = 1234
print pass_naked_byval_ptr(@test)

Code: Select all

.globl _PASS_NAKED_BYVAL_PTR
_PASS_NAKED_BYVAL_PTR:
.Lt_0004:
push offset _Lt_0007
call _fb_ErrorSetModName@4
mov dword ptr [ebp-4], eax
push offset _Lt_0009
call _fb_ErrorSetFuncName@4
mov dword ptr [ebp-8], eax
mov eax, [esp+4]
mov eax, [eax]
ret
.Lt_0005:
push dword ptr [ebp-8]
call _fb_ErrorSetFuncName@4
push dword ptr [ebp-4]
call _fb_ErrorSetModName@4
.balign 16
_fb_ctor__FBIDETEMP:
push ebp
mov ebp, esp
sub esp, 12
.Lt_0002:
push offset _Lt_000C
call _fb_ErrorSetModName@4
mov dword ptr [ebp-8], eax
push offset _Lt_000E
call _fb_ErrorSetFuncName@4
mov dword ptr [ebp-12], eax
mov dword ptr [ebp-4], 1234
push 1
lea eax, [ebp-4]
push eax
call _PASS_NAKED_BYVAL_PTR
add esp, 4
push eax
push 0
call _fb_PrintInt@12
.Lt_0003:
push dword ptr [ebp-12]
call _fb_ErrorSetFuncName@4
push dword ptr [ebp-8]
call _fb_ErrorSetModName@4
mov esp, ebp
pop ebp
ret

I think that:
call _fb_ErrorSetFuncName@4
mov dword ptr [ebp-8], eax
overwrites the value '1234'.


A last case which works: function pass_naked_byval_ptr naked cdecl(byval p as integer ptr) as integer, as just above, but compiled without '-exx':

Code: Select all

.globl _PASS_NAKED_BYVAL_PTR
_PASS_NAKED_BYVAL_PTR:
.Lt_0004:
mov eax, [esp+4]
mov eax, [eax]
ret
.Lt_0005:
.balign 16
_fb_ctor__FBIDETEMP:
push ebp
mov ebp, esp
sub esp, 4
.Lt_0002:
mov dword ptr [ebp-4], 1234
push 1
lea eax, [ebp-4]
push eax
call _PASS_NAKED_BYVAL_PTR
add esp, 4
push eax
push 0
call _fb_PrintInt@12
.Lt_0003:
mov esp, ebp
pop ebp
ret

[MichaelW]

But the two asm listing above correspond to cases which work!

The first listing shows what the code is supposed to look like, and the second shows the problem. The code in the second listing, like the code for all of the naked functions, is wrong, whether or not it “works”. The code in the first listing is setting up a stack frame (PUSH EBP MOV EBP, ESP), reserving space on the stack (SUB ESP,12), and then using EBP with negative displacements ( for example [EBP-4]) to access that space. The code in the second listing skips the first two steps, and then uses whatever value happens to be in EBP to read and write memory. This is a serious bug and is very likely the (indirect) source of the "segmentation violation" in the sort code.

[fxm]

But the two asm listing above correspond to cases which work!

The first listing shows what the code is supposed to look like, and the second shows the problem. The code in the second listing, like the code for all of the naked functions, is wrong, whether or not it “works”. The code in the first listing is setting up a stack frame (PUSH EBP MOV EBP, ESP), reserving space on the stack (SUB ESP,12), and then using EBP with negative displacements ( for example [EBP-4]) to access that space. The code in the second listing skips the first two steps, and then uses whatever value happens to be in EBP to read and write memory. This is a serious bug and is very likely the (indirect) source of the "segmentation violation" in the sort code.

You are right, even for the first function 'pass_naked_byval_var naked cdecl(byval v as integer) as integer'.
In fact, for the four naked functions, the local data 'test' is always polluted by the naked function call:

Code: Select all

function pass_naked_byval_var naked cdecl(byval v as integer) as integer
  asm
      mov eax, [esp+4]
      ret
  end asm
end function

dim test as integer = 1234
print pass_naked_byval_var(test)
print test
sleep

Code: Select all

function pass_naked_byval_ptr naked cdecl(byval p as integer ptr) as integer
  asm
      mov eax, [esp+4] 'en esp+20 sans -exx ou en esp+28 (ebp-8) avec -exx
      mov eax, [eax]
      ret
  end asm
end function

dim test as integer = 1234
print pass_naked_byval_ptr(@test)
print test
sleep

Code: Select all

function pass_naked_byref_var naked cdecl(byref v as integer) as integer
  asm
      mov eax, [esp+4]
      mov eax, [eax]
      ret
  end asm
end function

dim test as integer = 1234
print pass_naked_byref_var(test)
print test
sleep

Code: Select all

function pass_naked_byref_ptr naked cdecl(byref p as integer ptr) as integer
  asm
      mov eax, [esp+4]
      mov eax, [eax]
      mov eax, [eax]
      ret
  end asm
end function

dim test as integer = 1234
print pass_naked_byref_ptr(@test)
print test
sleep