Processing speed comparison

[Kerry Farmer]

I have a proposed project which will use large arrays, extensive string manipulations, sorting, searching etc etc

The arrays could easily be 500,000 elements of a variable size, say an average of 5 characters.

It is obvious (to me at least) that this is an ideal project for PB but is there any difference in the processing speed of PB for Windows over PBCC? If so, is it significant?

Processing speed will be important, although minor advantages will not be significant.

I am not at all concerned about compiling speed.

There will be insignificant use of graphics etc.

Are there any other parameters I should state?

Thank you

[Marco Pontello]

It is obvious (to me at least) that this is an ideal project for PB but is there any difference in the processing speed of PB for Windows over PBCC? If so, is it significant?

Never noticed any differences in this regard. I think they share the same "core".

Bye!

[John Gleason]

I too, like Marco, believe the compiler--CC vs. Win--will make an insignificant difference in code speed. However, you have very small strings there, and if possible, you would get potentially large speed increases if you could treat the strings as quads. The code below demos the difference of quad/8-byte string array handling. One caveat: the strings will be sorted reversed from what you may expect because of how quads (and other numeric types) are stored in memory, eg. as a quad, the string 987654 is sorted as 456789; ABCDEFG would be sorted as GFEDCBA.

#COMPILE EXE
#DIM ALL
%ARRAYSIZE = 2000000                    'you can try various sizes

FUNCTION PBMAIN () AS LONG
    LOCAL ii AS LONG, t1, t2 AS DOUBLE
    LOCAL collateStr AS STRING
    DIM sArr(%ARRAYSIZE)     AS STRING
    DIM quadArr(%ARRAYSIZE) AS QUAD
    
    FOR ii = 0 TO %ARRAYSIZE
       sArr(ii)     = MKQ$(RND*1e18)         '8 chrs long string
       quadArr(ii) =      RND*1e18           '8 chrs long quad
    NEXT
    
    ? "1st, do variable string array..."
    t1 = TIMER
    ARRAY SORT sArr()
    ARRAY SORT sArr(), DESCEND
    ARRAY SORT sArr()
    t1 = TIMER - t1
    ? "Variable string array time: " & FORMAT$(t1, "0.00")
    
    ? "2nd, do quad array..."
    t2 = TIMER
    ARRAY SORT quadArr()
    ARRAY SORT quadArr(), DESCEND
    ARRAY SORT quadArr()
    ? "Variable string array time: " & FORMAT$(t1, "0.00") & $CRLF & _
      "Quad string array time----: " & FORMAT$(TIMER - t2, "0.00")

END FUNCTION

[Gösta H. Lovgren-2]

Very clever

Just tried your code, John. The Quad was 5 times faster. (13 sec vs 2.3) Very clever.

However I played around with your code and got some strange results. The numbers in each array don't match after sorting. Probably as a result of using the Quad.

'

#Compile Exe
#Dim All
%ARRAYSIZE = 2000000                    'you can try various sizes
Function PBMain () As Long
    Local ii As Long, t1, t2 As Double, e As Quad
    Local collateStr As String
    Dim sArr(%ARRAYSIZE)     As String
    Dim quadArr(%ARRAYSIZE) As Quad
    Local s$, m$, eql$
 
    s$ = " ############# "
    For ii = 0 To %ARRAYSIZE     
       e = Rnd*1e18
       sArr(ii)   = Using$(s$, e)'Mkq$(Rnd*1e18)         '8 chrs long string
       quadArr(ii) =  e          'Rnd*1e18               '8 chrs long quad
    Next
 
    'For some reasons, there is no match
    m$ = $CrLf & "Before sorting" & $CrLf 
    For ii = 1 To 10   
       If quadArr(ii)= Val(sarr(ii)) Then
          eql$ = " Match"
         Else
          eql$ = " Don't match"
       End If
 
       m$ = m$ & Using$(s$, quadArr(ii))& sarr(ii) & eql$ & $CrLf 
    Next ii                                           
 
    ? "1st, do variable string array... it'll take 13 secs"
    t1 = Timer
    Array Sort sArr()
    Array Sort sArr(), Descend
    Array Sort sArr()
    t1 = Timer - t1
    ? "Variable string array time: " & Format$(t1, "0.00")
 
    ? "2nd, do quad array..."
    t2 = Timer
    Array Sort quadArr()
    Array Sort quadArr(), Descend
    Array Sort quadArr()
 
    m$ = m$ & "After sorting" & $CrLf 
    For ii = 1 To 10
       If quadArr(ii)= Val(sarr(ii)) Then
          eql$ = " Match"
         Else
          eql$ = " Don't match"
       End If
       m$ = m$ & Using$(s$, quadArr(ii))& sarr(ii) & eql$ & $CrLf 
    Next ii                                           
 
    ? "Variable string array time: " & Format$(t1, "0.00") & $CrLf & _
      "Quad string array time----: " & Format$(Timer - t2, "0.00") & $CrLf & _
       $CrLf & m$
End Function
'

[John Gleason]

got some strange results. The numbers in each array don't match after sorting. Probably as a result of using the Quad.

What you may be seeing, Gösta, could be caused be another point I forgot to mention: if the top bit is set for the quad, it's a negative number and will be sorted as less than strings that are actually smaller "string-wise", or perhaps you might imagine "unsigned quad-wise".

That means for a consistent sort, your top byte can't exceed chr$(127). This may not be a problem, however, if the data sorted is normal text data which won't be greater than 127. I'll look at your code closely and report back.

The quad method is certainly more complicated, but I thought I'd mention it because of the potential speed gains.

[John Gleason]

Welp, after checking the quad sort vs. the string sort, I've got some probably bad news: there is an intrinsic difference in the sort--besides just the reversed byte order--that results in a fundamental sort difference that I can show best by example (sort ascending):

string sort: 11111     quad sort:2
             112                 12
             113                 112
             12                  113
             2                   11111

This may stop you, Kerry, from being able to use the quad technique, but knowing the characteristics of the quad sort, maybe it can still have life.

[Gösta H. Lovgren-2]

Here's the results (which you will see if you run the code I posted):

Before sorting
 201711408422386240  201711408422386240  Match
 519515961171962720  519515961171962720  Match
 132240660741626080  132240660741626080  Match
 874188102101435520  874188102101435520  Match
 24617565409449600  24617565409449600  Match
 475587069509662880  475587069509662880  Match
 951352556673096480  951352556673096480  Match
 318802944969396160  318802944969396160  Match
 769335363094056640  769335363094056640  Match
 689230243569357280  689230243569357280  Match
After sorting
 1976266472320  100000283508510560  Don't match
 4112720424960  100000880020610240  Don't match
 4117842699040  100000945678850720  Don't match
 4719942734080  100001004817833280  Don't match
 5416106347680  100001145447539840  Don't match
 5577690811840  100004544774883840  Don't match
 5736946969600  100004727314105600  Don't match
 6049871349760  100005160379096000  Don't match
 6077811026560  100005177142902080  Don't match
 6345100601280  100005625574714720  Don't match

[John Gleason]

For example, one possible fix for my above example problem would be to pad the data with zeros:

string sort: 00002     quad sort: 00002
             00012                00012
             00112                00112
             00113                00113
             11111                11111

[John Gleason]

Here's the results (which you will see if you run the code I posted):

Yes, that is demonstrating the difference in the quad vs. string sort similar to my example post made just a couple minutes before. It very well could be an insurmountable problem, but maybe somewhere it can be used.

[Michael Mattias]

>the difference in the quad vs. string sort

Expand to 64 bits...
String Signed Binary (SSB) Functions for PB-DOS

(Windows code is same as DOS code here).

[John Gleason]

Expand to 64 bits...
String Signed Binary (SSB) Functions for PB-DOS

And there it is, a potentially insurmountable problem surmounted!

[Michael Mattias]

Under Win/32 you can get rid of the MID$ and CHR$ by using BYTE PTRs (which were not available when the routine was first created); it's always a good idea for performance enhancement to not use string functions when number functions are available to do the job.

For that matter, if you don't mind the string operators, with Intel-format integers STRREVERSE$ results in a "numerically sortable string" but I think that only works with non-negative numbers.

I'd suggest you post your 64-bit version for Windows as a 'reply' to original post so everything is in the same place.


MCM

[Kerry Farmer]

Thank you everybody

My question is now answered for my satisfaction