FB13 slower than FB11

[Dean]

I'm posting this again -- first post seems to have gone nowhere.

I just tried FB13 on the quicksort routines that were the
subject of the SORTING ARRAYS thread -- and I am finding
that FB13 is consistently 21% slower than FB11.
Same exact code.

Are there some new compile switches I should be using
to disable anything that is causing unnecessary overhead?

What can I do to get the same performance?


Dean

[Z!re]

Make both versions of the program available, as well as sourcecode


In my experience, 0.13 is faster than 0.12, which was faster than 0.11

[Dean]

Here's the code -- borrowed from the net, with a few
tweaks. This was the only example I tried so far with version 13.
I used 3000000 (three million) elements for my test.

Dean

'===========================================================================
' Subject: BUBBLE SORT VS. QUICK SORT Date: 05-30-98 (11:50)
' Author: Steve Gomez Code: QB, QBasic, PDS
' Origin: alt.lang.basic Packet: ALGOR.ABC
'===========================================================================
'From: cowboy@nwlink.com (Steve Gomez-Fox)

'> bigger the number of number/letters, the slower and slower it goes!
'> The code's pathetic over 1000 numbers! The question posed is, where is
'> a faster way to sort then just a N ^ 2 (I think that's what it appears

'Below find a program I put together to compare sorting speeds using
'the Bubble Sort algorithm and the Quick Sort algorithm. You will be
'amazed by the difference. The downside to Quick Sort is that the code
'is longer, it must be in a SUB because it is recursive, and being
'recursive, it uses up stack space. But, if you are sorting more than
'a handful of elements, you will find it is well worth it.

'Results on my P166

'Elements Bubble Sort Quick Sort
'-----------------------------------
' 1000 1.81 sec 0.05 sec
' 5000 45.09 sec 0.28 sec
' 10000 182.24 sec 0.50 sec
' 15000 407.43 sec 0.83 sec


' QSORT.BAS
'=============

DECLARE SUB QuickSort (qsLeft AS LONG, qsRight AS LONG)

DIM Elements AS LONG
DIM SHARED qsArray() AS STRING * 7 'DataType of array being sorted
DIM TI1 AS DOUBLE
DIM TI2 AS DOUBLE

CLS

INPUT "Number of elements (2 to 10000000)", Elements
IF Elements < 2 OR Elements > 10000000 THEN PRINT "Out of range"

Elements = Elements - 1

PRINT "Starting time "; timer
TI1 = timer

DIM qsArray(Elements) AS STRING * 7
DIM qsTime AS DOUBLE
DIM RandInt AS STRING
DIM Index AS LONG
DIM QS AS STRING

FOR Index = Elements to 1 step - 1
QS = ltrim$(str$(Index))
IF LEN(QS) < 7 THEN QS = QS + STRING$(7-LEN(QS), " ")
qsArray(Index) = QS

'FOR Index = 0 TO Elements
'RandInt = LEFT$(LTRIM$(STR$(RND * 1000000)),7)
'IF LEN(RandInt) < 7 then RandInt = RandInt + STRING$(7-LEN(RandInt), " ")
'qsArray(Index) = RandInt
NEXT Index

CLS
PRINT "Sorting"; Elements + 1; "elements"
PRINT


PRINT "Executing the Quick Sort"
qsTime = TIMER
'Call QuickSort initially with the lowest and highest
'bounds of the array
QuickSort LBOUND(qsArray), UBOUND(qsArray)
qsTime = TIMER - qsTime
PRINT "Sort completed in "; qsTime; " seconds"
FOR Index = LBOUND(qsArray) TO UBOUND(qsArray) - 1
IF qsArray(Index) > qsArray(Index + 1) THEN PRINT "Error": END
NEXT Index
PRINT "Sort verified correct"
PRINT

TI2 = TIMER
PRINT "Total time "; TI2-TI1

INPUT "Hit return...",g$

SUB QuickSort (qsLeft AS LONG, qsRight AS LONG)
'SHARED qsArray() AS LONG 'DataType of array being sorted

DIM NewLeft AS LONG
DIM NewRight AS LONG
DIM Center AS LONG
DIM CtrVal AS STRING * 7 'DataType of array being sorted

IF qsLeft < qsRight THEN
'Select the element halfway between qsLeft and qsRight
'for comparison
Center = (qsLeft + qsRight) / 2
CtrVal = qsArray(Center)

'Move this center element out of the way
SWAP qsArray(qsRight), qsArray(Center)
NewLeft = qsLeft
NewRight = qsRight

DO
'Look for an element to the left of center that should
'be to the right
DO WHILE NewLeft < NewRight AND qsArray(NewLeft) <= CtrVal
NewLeft = NewLeft + 1
LOOP

'Look for an element to the right of center that should be
'to the left
DO WHILE NewRight > NewLeft AND qsArray(NewRight) >= CtrVal
NewRight = NewRight - 1
LOOP

' If NewLeft < NewRight, we found two elements to swap
IF NewLeft < NewRight THEN
SWAP qsArray(NewLeft), qsArray(NewRight)
END IF
LOOP WHILE NewLeft < NewRight

'Move the center element back into place
SWAP qsArray(NewLeft), qsArray(qsRight)

' Sort the two sections that the above code has left out
IF (NewLeft - qsLeft) < (qsRight - NewLeft) THEN
QuickSort qsLeft, NewLeft - 1
QuickSort NewLeft + 1, qsRight
ELSE
QuickSort NewLeft + 1, qsRight
QuickSort qsLeft, NewLeft - 1
END IF
END IF
END SUB

[v3cz0r]

It's certainly not slower than 0.12, the string descriptor was changed in 0.12, it has a field more and 12.5% more memory is allocated for every string (to speed up concatenation), depending on how Windows is allocating these 3 million strings, there will be a hit.

[dumbledore]

the crt's qsort() method still works as fast as ever... did you try it out?

here's it implemented in your original code:

Code:

'$include: "crt.bi"
DIM X AS LONG
DIM Y AS LONG
DIM Z AS LONG
DIM S AS STRING
DIM TI1 AS DOUBLE
DIM TI2 AS DOUBLE

X = 3000000

DIM MyArray(X) AS STRING * 7

PRINT "Started loading array in descending order..."
FOR Z = X TO 1 STEP -1
S = LTRIM$(STR$(Z))
IF LEN(S) < 7 THEN S = S + STRING$(7 - LEN(S), " ")
Y = Y + 1
MyArray(Y) = S
NEXT Z

PRINT "Started to sort array in ascending order..."
TI1 = TIMER
'ARRAY SORT MyArray() : 'PB built in sorting function
qsort(@MyArray(0),ubound(MyArray),sizeof(MyArray(0)),@strcmp) 'assumes array has constant length
TI2 = TIMER

PRINT "Time to sort array = ";TI2 - TI1; " seconds."
INPUT "Hit return to quit...", S

2.5779 seconds