QSort 32 bit vs 64 bit FB

General FreeBASIC programming questions.
Dinosaur
Posts: 1190
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 20, 2016 18:46

Hi All

I am converting a rather large program from Win XP embedded to Linux.
On my Laptop I have 32 bit Linux Mint and of course FB 32 bit installed, and it compiled and ran ok.
On my Industrial Fitlet I have 64 bit Linux & FB installed and there it compiles, but fails when it tries to access msort.c

FreeBASIC Compiler - Version 1.04.0 (10-01-2015), built for linux-x86_64 (64bit)


The code for the sort routine I got from someone on the Forum a long time ago.
I know there may be better sort routines but really don't want to modify the program.

Code: Select all

Declare Sub Sort overload (sortArray() As String )
Sub Sort overload (sortArray() As String )
   Dim As Long arrayLength = Ubound( sortArray ) - Lbound( sortArray ) + 1
   QSort(  @sortArray( 0 ), arrayLength, 12, ProcPtr(String_Compare) )
End Sub


And this is where I call it from.

Code: Select all

Sub GetFileList
    Dim FileNaam As ZString * 17
    Dim FileSpec As String
    Dim As Long FileCount, FileNbr,SF,Xr
    FileSpec = Paths.Root + "/recipes/*.JVP"
    FileNaam = Dir(FileSpec, 55 )
    FileCount = 0
    Do                                    'Firstly count how many files
        FileNaam = Dir( )                           'look for next FileNaam
        FileCount += 1                              'update number of files found.       
    Loop While Len(FileNaam) > 0
    Dim As String SortArray(FileCount)            'Then Dim array to that lenth
    'Now do it again
    FileSpec = Paths.Root + "/recipes/*.JVP"
    FileNaam = Dir(FileSpec, 55 )
    FileArray.Nbr  = FileCount
    FileCount = 0
    If FileArray.Nbr > 0 Then
        If FileArray.Nbr < 500 Then         
            For Xr = 1 To FileArray.Nbr
                SortArray(Xr) = FileNaam               'save each FileNaam
                FileNaam = Dir( )                           'look for next FileNaam
            Next
        EndIf
    EndIf
   Sort (SortArray())                        'now get the names sorted.
   'If FileExists(ErrControl.ErrFile) Then
       If FileArray.Nbr > 0 Then
            If FileArray.Nbr < 500 Then    
               For Xr = 1 To FileArray.Nbr
                  FileArray.Name(Xr) = SortArray(Xr)
               Next
           Endif
       EndIf
   'EndIf
End Sub


I suspect that the problem is 64 bit version of FB has a different sort routine in the library, so can SKS advise me how to solve this problem.

Regards
fxm
Posts: 9123
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: QSort 32 bit vs 64 bit FB

Postby fxm » Nov 20, 2016 19:26

Size of string descriptor = 3 Integers (12 Bytes for 32-bit, 24 Bytes for 64-bit)

Code: Select all

Declare Sub Sort overload (sortArray() As String )
Sub Sort overload (sortArray() As String )
   Dim As Long arrayLength = Ubound( sortArray ) - Lbound( sortArray ) + 1
   QSort(  @sortArray( 0 ), arrayLength, 3*Sizeof(Integer), ProcPtr(String_Compare) )
End Sub
Dinosaur
Posts: 1190
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 20, 2016 19:35

Hi All

fxm, thank you for that.
Such an easy fix when you know what you are doing.

Regards
fxm
Posts: 9123
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: QSort 32 bit vs 64 bit FB

Postby fxm » Nov 20, 2016 19:46

More readable:

Code: Select all

Declare Sub Sort overload (sortArray() As String )
Sub Sort overload (sortArray() As String )
   Dim As Long arrayLength = Ubound( sortArray ) - Lbound( sortArray ) + 1
   QSort(  @sortArray( 0 ), arrayLength, Sizeof( sortArray( 0 ) ), ProcPtr(String_Compare) )
End Sub


[edit]
Corrected typo:
Sizeof( array( 0 ) )
Sizeof( sortArray( 0 ) )
Last edited by fxm on Nov 20, 2016 20:50, edited 3 times in total.
Dinosaur
Posts: 1190
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 20, 2016 19:53

Hi All

Even better, as then I don't have to modify it for 32 bit operation.
Thank you.

Regards
fxm
Posts: 9123
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: QSort 32 bit vs 64 bit FB

Postby fxm » Nov 20, 2016 19:58

Each array element is a string descriptor containing 3 fields (pointer to the first string character, the string size, the allocated memory size), so:
- first pointer address = first array element address
- offset between pointers = array element size.
Dinosaur
Posts: 1190
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 20, 2016 20:08

Hi All

fxm, the original error was raised by Allegro.
At this point I don't know where the Qsort routine resides.
Is it part of Allegro or FB. (I guess not FB as there was no reference to it.

Where would I find a description of the the calling protocol ?

Regards
fxm
Posts: 9123
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: QSort 32 bit vs 64 bit FB

Postby fxm » Nov 20, 2016 20:14

MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: QSort 32 bit vs 64 bit FB

Postby MichaelW » Nov 22, 2016 13:14

qsort and bsearch are CRT functions exported from msvcrt.dll:

qsort

bsearch

The functions require a type-specific external comparison function which, because it is called from an inner loop, makes the functions relatively slow.

A type-specific sort function would be more efficient.
Dinosaur
Posts: 1190
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 22, 2016 13:53

Hi All

Thanks for those links MichaelW, they explain the sort routine really well.
Because I never wrote this part, I never fully understood it.

The only conflict in the description is

width
Element size in bytes.

I guess that is Integers now.

Regards
dodicat
Posts: 5913
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Postby dodicat » Nov 22, 2016 14:23

Windows:
Here is the msvcrt.dll qsort, called by #include "crt/stdlib.bi"

Linux I believe can use the C language qsort in a similar way, possibly using inbuilt Gcc., but I have not used Linux for a few years.

Datatype as string here:

Code: Select all



#include "crt/stdlib.bi"

type datatype as string

Function callback Cdecl(n1 As Any Ptr,n2 As Any Ptr) As Long
    If *Cptr(DataType Ptr,n1) < *Cptr(DataType Ptr,n2) Then Return -1  'CHANGE TO  1 FOR SORTING DOWN
    If *Cptr(DataType Ptr,n1) > *Cptr(DataType Ptr,n2) Then Return  1  'CHANGE TO -1 FOR SORTING DOWN
End Function

sub sort(s() as DataType) 
qsort( @s(Lbound(s)),(Ubound(s)-Lbound(s)+1),Sizeof(s),@callback)
end sub


'=======================  EXAMPLE ===================================
#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))
#define q IntRange(97,122)         'lcase alphabet
#define RandomString chr(q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q)

                print "__________original _____________"
                Dim As Long num=100
                dim as long n
               
                Redim As string s(num)
               
                For n =lbound(s) To ubound(s)
                    s(n)=RandomString 'max allowed chr( ... )=32?
                    print s(n)
                Next n
                print
                print "__________sorted _______________"
                print
                dim as double t1=timer
                sort(s())
                dim as double t2=timer
                For n =lbound(s) To ubound(s)
                    Print s(n)
                Next
                print
                print "Time taken "; t2-t1
                Sleep
               
 


And a standard quicksort, no external library, datatype string.:

Code: Select all

type datatype as string

 Sub sort(array() As DataType,begin As Long=0,Finish As Long=-1)
            If begin>finish Then begin=Lbound(array):Finish=Ubound(array)
            Dim As Long i=begin,j=finish
            static As DataType x :x=array(((I+J)\2))
                While I <= J
                While array(I) < X :I+=1:Wend 'CHANGE TO > FOR SORTING DOWN
                While array(J) > X :J-=1:Wend 'CHANGE TO < FOR SORTING DOWN
                        If I<=J Then Swap array(I),array(J): I+=1:J-=1
                Wend
                    If J >begin Then  sort(array(),begin,J)
                    If I <Finish Then sort(array(),I,Finish)
End Sub

'=======================  EXAMPLE ===================================
#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))
#define q IntRange(97,122)
#define RandomString chr(q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,32,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q)

                print "__________original _____________"
                Dim As Long num=100
                dim as long n
               
                Redim As string s(num)
               
                For n =lbound(s) To ubound(s)
                    s(n)=RandomString ' Question --- max allowed chr( ... )=32?
                    print s(n)
                Next n
                print
                print "__________sorted _______________"
                print
                dim as double t1=timer
                sort(s())
                dim as double t2=timer
                For n =lbound(s) To ubound(s)
                    Print s(n)
                Next
                print
                print "Time taken "; t2-t1
                Sleep

The standard quicksort is slightly faster on this box-(not much).
64 bit FreeBASIC is faster than 32 bit FreeBASIC for these sorts.
Dinosaur
Posts: 1190
Joined: Jul 24, 2005 1:13
Location: Searcy AR USA
Contact:

Re: QSort 32 bit vs 64 bit FB

Postby Dinosaur » Nov 22, 2016 15:35

Hi All

Thanks for that dodicat, I will investigate using the latter, which will mean library changes won't bother me.
The sort routine is used to display filenames on the screen in a concrete plant which are numerical names.
So instead of having to look for a number (about 400 on the screen) they can pick it from the rough area.


Regards
MrSwiss
Posts: 3215
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: QSort 32 bit vs 64 bit FB

Postby MrSwiss » Nov 22, 2016 18:17

@Dinosaur,
Dinosaur wrote:The only conflict in the description is: width = Element size in bytes.
No conflict. Explanation:
In case of a String: length of String, since a single String (of String-Array) has to have a defined length.
Aka: fixed length String = 1 Element (Size) of String-Array.
If you want to sort UIntegers: 4 Byte on FBC 32, 8 Byte on FBC 64; better defined as: SizeOf(UInteger).
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: QSort 32 bit vs 64 bit FB

Postby MichaelW » Nov 24, 2016 9:09

For the CRT qsort, when sorting numeric arrays the comparison function need only return the result of a subtraction operation:

Code: Select all

#include "crt.bi"

''-----------------------------------------------
'' Long instead of integer so the code will work
'' without alteration on 32-bit and 64-bit FB.
''-----------------------------------------------

function compare cdecl( p1 as any ptr, p2 as any ptr ) as long
    return *cptr(long ptr, p1) - *cptr(long ptr, p2)
end function

dim as long numarray(0 to 99)

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

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

print

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

sleep

Change the order of the subtraction operation to change the order of the sort.

For sorting arrays of null-terminated strings, the comparison function must return the same value that the appropriate CRT string comparison function would return.
dodicat
Posts: 5913
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: QSort 32 bit vs 64 bit FB

Postby dodicat » Nov 24, 2016 14:23

The qsort routine lies deep within a C compiler or a C runtime.
It lies mysteriously out of our reach (or most of our reaches anyways), but the compare (callback) function is written in FreeBASIC and thus can be customised in millions of ways.
Here is an example for big integers.

Code: Select all


#include "crt/stdlib.bi"

type datatype as string


Function callback Cdecl(n1 As Any Ptr,n2 As Any Ptr) As Long
    dim as long k=1   'CHANGE TO -1 FOR SORTING DOWN
    If len(*Cptr(DataType Ptr,n1)) < len(*Cptr(DataType Ptr,n2)) Then Return -k
    If len(*Cptr(DataType Ptr,n1)) > len(*Cptr(DataType Ptr,n2)) Then Return  k
    if (*Cptr(DataType Ptr,n1)) > (*Cptr(DataType Ptr,n2)) Then Return  k  else return -k
End Function

sub sort(s() as DataType) 
qsort( @s(Lbound(s)),(Ubound(s)-Lbound(s)+1),Sizeof(s),@callback)
end sub


#define Intrange(f,l) int(Rnd*((l+1)-(f))+(f))
#define q IntRange(48,57)         'digit
#define RandomString chr(q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q,q)

 
                print "__________original _____________"
                Dim As Long num=150
                dim as long n
               
                Redim As datatype s(num)
               
                For n =lbound(s) To ubound(s)
                    s(n)=RandomString 'max allowed chr( ... )=32?
                    s(n)+=RandomString
                    dim as string tmp=(mid(s(n),1,Intrange(1,64)))
                    s(n)=iif(len(tmp)=1,tmp,ltrim(tmp,"0"))
                    if len(s(n))=0 then s(n)="0"
   
                    print s(n)
                Next n
                print
                print "__________sorted _______________"
                print
                dim as double t1=timer
                sort(s())
                dim as double t2=timer
                For n =lbound(s) To ubound(s)
                    Print s(n)
                Next
                print
                print "Time taken "; t2-t1
                Sleep   


For fun only.

Return to “General”

Who is online

Users browsing this forum: No registered users and 5 guests