• Print

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
    loop
end 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
    loop
end 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

  • Administrator
  • Hero Member
  • *****
  • Posts: 4664
  • QB Forever
    • Email
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  ;D

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

codeguy

  • Hero Member
  • *****
  • Posts: 3552
  • what the h3ll did i name that code?
    • stuff at dkm
    • Email
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, S
DIM a(32767)
quicksort4 a(), 0, 32767
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
LOOP
END 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  ;D
It's only rocket science; it's not Linux!

codeguy

  • Hero Member
  • *****
  • Posts: 3552
  • what the h3ll did i name that code?
    • stuff at dkm
    • Email
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?
    • stuff at dkm
    • Email
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  ;D
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

  • Administrator
  • Hero Member
  • *****
  • Posts: 4664
  • QB Forever
    • Email
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 >>>
    • Pete's Qbasic Site
    • Email
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 Q-Basics Code Demo: Q-Basics.zip
Download QB64 BAT, IconAdder and VBS shortcuts: QB64BAT.zip
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!

  • Print