Author Topic: 'dim var as long' vs. var& and implicit declaration  (Read 594 times)

Ed Davis

• Newbie
• Posts: 9
'dim var as long' vs. var& and implicit declaration
« on: August 24, 2010, 06:01:40 AM »
I was intrigued by the recent sorting examples that have been posted.  I was also wondering why quicksort was slower than some of the other sorts.  So, I found a version of quicksort I have used in the past, converted it to BASIC, and inserted it into the test harness provided by codeguy and Zom-B.  And it appears to be faster than the one included.

Wanting to see if I could get it a little more speed out of it, I converted all the implicit declarations similar to "i&" to explicit declarations of "dim i as long".  But this actually made it somewhat slower.  Any ideas why?

Here is the first, fast version, with variables using implicit declaration, and the trailing '&' character:
Code: [Select]
`sub quicksort4(array(), l&, r&)    dim stack_l&(30)    dim stack_r&(30)    sp& =  0    lt& = l&    rt& = r&    do        do while lt& < rt&            n& = rt& - lt& + 1            if n& = 2 then                if array(lt&) > array(rt&) then swap array(lt&), array(rt&)                exit do            end if            if n& = 3 then                m& = lt& + 1                if array(lt&) > array(m&)  then swap array(lt&), array(m&)                if array(lt&) > array(rt&) then swap array(lt&), array(rt&)                if array(m&)  > array(rt&) then swap array(m&),  array(rt&)                exit do            end if            middle = array((lt& + rt&) \ 2)            i& = lt&            j& = rt&            do                while array(i&) < middle: i& = i& + 1: wend                while array(j&) > middle: j& = j& - 1: wend                if i& <= j& then                    if i& < j& then swap array(i&), array(j&)                    i& = i& + 1                    j& = j& - 1                end if            loop while i& <= j&            if j& - lt& < rt& - i& then                if i& < rt& then                    sp& = sp& + 1                    stack_l&(sp&) = i&                    stack_r&(sp&) = rt&                end if                rt& = j&            else                if lt& < j& then                    sp& = sp& + 1                    stack_l&(sp&) = lt&                    stack_r&(sp&) = j&                end if                lt& = i&            end if        loop        if sp& = 0 then exit do        lt& = stack_l&(sp&)        rt& = stack_r&(sp&)        sp& = sp& - 1    loopend sub`
And here is the second, slower version.  The only (intentional) difference is that variables are explicitly declared as long via dim:

Code: [Select]
`sub quicksort4(array(), l as long, r as long)    dim stack_l(30) as long    dim stack_r(30) as long    dim sp as long    dim lt as long    dim rt as long    dim n as long    dim j as long    dim i as long    dim m as long    sp =  0    lt = l    rt = r    do        do while lt < rt            n = rt - lt + 1            if n = 2 then                if array(lt) > array(rt) then swap array(lt), array(rt)                exit do            end if            if n = 3 then                m = lt + 1                if array(lt) > array(m)  then swap array(lt), array(m)                if array(lt) > array(rt) then swap array(lt), array(rt)                if array(m)  > array(rt) then swap array(m),  array(rt)                exit do            end if            middle = array((lt + rt) \ 2)            i = lt            j = rt            do                while array(i) < middle: i = i + 1: wend                while array(j) > middle: j = j - 1: wend                if i <= j then                    if i < j then swap array(i), array(j)                    i = i + 1                    j = j - 1                end if            loop while i <= j            if j - lt < rt - i then                if i < rt then                    sp = sp + 1                    stack_l(sp) = i                    stack_r(sp) = rt                end if                rt = j            else                if lt < j then                    sp = sp + 1                    stack_l(sp) = lt                    stack_r(sp) = j                end if                lt = i            end if        loop        if sp = 0 then exit do        lt = stack_l(sp)        rt = stack_r(sp)        sp = sp - 1    loopend sub`
Thanks for any help!

Pete

• Moderator
• Hero Member
• Posts: 6240
• Cuz I sez so varmint!
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #1 on: August 24, 2010, 10:32:18 AM »

In QuickBasic, DEFINT speeded things up, so I'm wondering if...

DEFLNG A-Z

Would do so as well in your QB64 program.

Just an untested hunch, and welcome to the forum,

Pete
It's only rocket science; it's not Linux!

Galleon

• Hero Member
• Posts: 4664
• QB Forever
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #2 on: August 24, 2010, 11:34:24 AM »
Both implicit and explicit definitions of variables run at exactly the same speed because they generate exactly the same code. It could be in the way you are calling the sub. What type is 'array()' which is passed to the sub?
Something old... Something new... Something borrowed... Something blue...

Ed Davis

• Newbie
• Posts: 9
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #3 on: August 24, 2010, 12:19:39 PM »
Quote from: Galleon on August 24, 2010, 11:34:24 AM
Both implicit and explicit definitions of variables run at exactly the same speed because they generate exactly the same code. It could be in the way you are calling the sub. What type is 'array()' which is passed to the sub?

I wonder why these two routines run at such different speeds then?  Strange.  Is there any way to see the resulting .c or .cpp code that gets passed to gcc/g++?

The test harness is from codeguy's and Zom-B's sorting tester, that was posted in the QB64 sample programs forum in August.  At the beginning of it, it has:

'Choose your array type:
'DEFDBL A-Z
DEFINT A-Z

And a little later:

'The values to sort.
DIM SHARED array(maxCount& - 1)

Thanks for the help!

Pete

• Moderator
• Hero Member
• Posts: 6240
• Cuz I sez so varmint!
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #4 on: August 24, 2010, 12:21:06 PM »
It could also be that when he was testing the second one, he had the other program open, or other windows open, or the IDE open, etc. We need to be sure the test comparison is apples to apples (sorry Micro\$oft, which would be lemons to lemons, and that's not a qualified expression) to be sure of the timing results.

Pete
It's only rocket science; it's not Linux!

Zom-B

• Hero Member
• Posts: 545
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #5 on: August 24, 2010, 05:53:24 PM »
The second example is slower because it executes a bunch of DIM statements at the beginning of each sub call, and there are hundreds of thousands of sub calls for a single sort.

This must be a bug.

DIM isn't actually executed, as variables are just positions reserved on the stack, but for each DIM statement it still generates event trapping code. This is a violation as QB4.5 doesn't do this.

Pete

• Moderator
• Hero Member
• Posts: 6240
• Cuz I sez so varmint!
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #6 on: August 24, 2010, 08:25:07 PM »

I feel violated. - LOL

Pete
It's only rocket science; it's not Linux!

codeguy

• Hero Member
• Posts: 3552
• what the h3ll did i name that code?
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #7 on: August 25, 2010, 10:52:23 AM »
maybe doing the dim var as whatever OUTSIDE quicksort would help as with this recursive routine, this (dim whatever as whatevertype) is executed approximately n log n times and may be the source of your slow-down.
Code: [Select]
`DEFLNG I, J, L, M, N, R, SDIM a(32767)quicksort4 a(), 0, 32767SUB quicksort4 (array(), l, r)DIM stack_l(30)DIM stack_r(30)sp = 0lt = lrt = rDO    DO WHILE lt < rt        n = rt - lt + 1        IF n = 2 THEN            IF array(lt) > array(rt) THEN SWAP array(lt), array(rt)            EXIT DO        END IF        IF n = 3 THEN            m = lt + 1            IF array(lt) > array(m) THEN SWAP array(lt), array(m)            IF array(lt) > array(rt) THEN SWAP array(lt), array(rt)            IF array(m) > array(rt) THEN SWAP array(m), array(rt)            EXIT DO        END IF        middle = array((lt + rt) \ 2)        i = lt        j = rt        DO            WHILE array(i) < middle: i = i + 1: WEND            WHILE array(j) > middle: j = j - 1: WEND            IF i <= j THEN                IF i < j THEN SWAP array(i), array(j)                i = i + 1                j = j - 1            END IF        LOOP WHILE i <= j        IF j - lt < rt - i THEN            IF i < rt THEN                sp = sp + 1                stack_l(sp) = i                stack_r(sp) = rt            END IF            rt = j        ELSE            IF lt < j THEN                sp = sp + 1                stack_l(sp) = lt                stack_r(sp) = j            END IF            lt = i        END IF    LOOP    IF sp = 0 THEN EXIT DO    lt = stack_l(sp)    rt = stack_r(sp)    sp = sp - 1LOOPEND SUB`
« Last Edit: August 25, 2010, 10:57:46 AM by codeguy »
http://denteddisk.forums-free.com/make-an-appointment-with-the-resident-code-guru-f34.html

Pete

• Moderator
• Hero Member
• Posts: 6240
• Cuz I sez so varmint!
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #8 on: August 25, 2010, 10:59:08 AM »

I'm beginning to think my DEFLNG A-Z solution in this thread is the best, despite what Galleon posted about how QB64 compiles all DIM coding styles the same. This is not from any logicial assessment, but because my ego needed to go for a walk.

Pete
It's only rocket science; it's not Linux!

codeguy

• Hero Member
• Posts: 3552
• what the h3ll did i name that code?
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #9 on: August 25, 2010, 11:02:53 AM »
Quote from: Zom-B on August 24, 2010, 05:53:24 PM
The second example is slower because it executes a bunch of DIM statements at the beginning of each sub call, and there are hundreds of thousands of sub calls for a single sort.

This must be a bug.

DIM isn't actually executed, as variables are just positions reserved on the stack, but for each DIM statement it still generates event trapping code. This is a violation as QB4.5 doesn't do this.

don't think this is a bug. it's doing exactly as asked, which is assigning definite types to declared variables, but doing it a bunch of times (n log n best case, n2 worst-case) versus once like we want it to! an optimizing compiler may see this and also move this code outside the quicksort sub as i did!
http://denteddisk.forums-free.com/make-an-appointment-with-the-resident-code-guru-f34.html

codeguy

• Hero Member
• Posts: 3552
• what the h3ll did i name that code?
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #10 on: August 25, 2010, 11:08:58 AM »
Quote from: Pete on August 25, 2010, 10:59:08 AM

I'm beginning to think my DEFLNG A-Z solution in this thread is the best, despite what Galleon posted about how QB64 compiles all DIM coding styles the same. This is not from any logicial assessment, but because my ego needed to go for a walk.

Pete
i think using suffixes rather than implied types (by defstr, etc) is far easier for me. that way i know at a glance EXACTLY what data type i am dealing with. it's a matter of coding style and not a bug. and yes, pete, i agree with your modus operandi concerning this. makes perfect sense to me.
http://denteddisk.forums-free.com/make-an-appointment-with-the-resident-code-guru-f34.html

Zom-B

• Hero Member
• Posts: 545
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #11 on: August 25, 2010, 11:51:20 AM »
Quote from: codeguy on August 25, 2010, 11:02:53 AM
don't think this is a bug. it's doing exactly as asked, which is assigning definite types to declared variables, but doing it a bunch of times (n log n best case, n2 worst-case) versus once like we want it to! an optimizing compiler may see this and also move this code outside the quicksort sub as i did!

Dim should do nothing in run-time. Defining types is something that happens compile-time.

Galleon

• Hero Member
• Posts: 4664
• QB Forever
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #12 on: August 25, 2010, 12:10:30 PM »
I'll look into how we can improve this. In some cases I'm sure optimizations are possible, but in others (such as emulated conventional memory) probably not.
Something old... Something new... Something borrowed... Something blue...

Clippy

• Hero Member
• Posts: 16431
• I LOVE π = 4 * ATN(1)    Use the QB64 WIKI >>>
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #13 on: August 25, 2010, 12:12:15 PM »
How about fixing it so DIM can dimension arrays with a dot variable value? I spent over an hour finding that!
QB64 WIKI: Main Page
Download QB64 DLL files in a ZIP: Program64.zip

Ed Davis

• Newbie
• Posts: 9
Re: 'dim var as long' vs. var& and implicit declaration
« Reply #14 on: August 25, 2010, 01:12:22 PM »
Quote from: codeguy on August 25, 2010, 10:52:23 AM
maybe doing the dim var as whatever OUTSIDE quicksort would help as with this recursive routine, this (dim whatever as whatevertype) is executed approximately n log n times and may be the source of your slow-down.

This version of quicksort is not recursive.  If you look at the code, you'll see that it does not call itself. This is an iterative version of quicksort. The dim's only get executed once.

But thanks anyway!