variable as index of array of types - performance issue

General FreeBASIC programming questions.
cbruce
Posts: 136
Joined: Sep 12, 2007 19:13
Location: Dallas, Texas

variable as index of array of types - performance issue

Postby cbruce » May 08, 2018 20:56

.
FreeBASIC Compiler - Version 1.06.0 (11-29-2017), built for win64 (64bit)
Windows 10

I am seeing a performance issue when accessing a member of an array of nested
TYPEs
... whenever I use a variable for the array index.

If I use an individual variable of that TYPE - or an array member of that TYPE that is
being indexed by a literal value - either one achieves much better performance.

I tried similar scenarios with simple numeric arrays - but no problems there.

Example results - (edited):

Code: Select all

Note: three runs ... Each test runs 1 billion iterations:

D:\FreeBASICx64\00_BRUCE>macro_arg__array_index_problem.exe

MACRO ... Using a variable as the TYPE array index causes a large overhead.

FUNCTION ... Although the overhead of the function stack has the largest impact on
             performance in this execution of the algorithm... using a variable as
             the TYPE array index still causes a noticeable overhead in the
             algorithms performance.


1.0 ... parameter => nested TYPE single instance
2.0 ... parameter => nested TYPE array member instance - literal  as index
3.0 ... parameter => nested TYPE array member instance - variable as index


             -----------------------
1.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 7.278534743469209 seconds ... "
2.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 7.315351489465684 seconds ... "
3.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 12.31469192402437 seconds ... "
             --------------------------
1.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.38987335748971 seconds ... "
2.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.41212320979685 seconds ... "
3.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 13.02056969562545 seconds ... "

             -----------------------
1.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 7.464423599652946 seconds ... "
2.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 7.40475267637521 seconds ... "
3.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 12.42926799412817 seconds ... "
             --------------------------
1.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.52589482115582 seconds ... "
2.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.60203798254952 seconds ... "
3.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 13.67634915141389 seconds ... "

             -----------------------
1.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 7.403423885349184 seconds ... "
2.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 7.272508698049933 seconds ... "
3.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 12.34838109090924 seconds ... "
             --------------------------
1.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.42778676282615 seconds ... "
2.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.44876095233485 seconds ... "
3.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 13.03863485297188 seconds ... "


Code: Select all

' This test rig compiles and runs.

type ABC_t
    A as ULongInt = 6364136223846793005ull
    B as ulongint = 8274873888393933ull
    C as ulongint = 9877772622288ull
end type

type ABCx2_t
    ABC(1 to 2) as ABC_t
end type


#macro MACRO_ARG__ARRAY_INDEX_PROBLEM(m_abcx2, m_result_ulongint)
    scope
        dim pB1 as ulongint = m_abcx2.ABC(1).B
            m_abcx2.ABC(1).B = (m_abcx2.ABC(1).B * m_abcx2.ABC(1).A) + m_abcx2.ABC(1).C
            dim as ulong xx1   = (((pB1 shr 18u) xor pB1) shr 27u)
            dim as ulong rr1 = (pB1 shr 59u)
        '
        dim pB2 as ulongint = m_abcx2.ABC(2).B
            m_abcx2.ABC(2).B = (m_abcx2.ABC(2).B * m_abcx2.ABC(2).A) + m_abcx2.ABC(2).C
            dim as ulong xx2   = (((pB2 shr 18u) xor pB2) shr 27u)
            dim as ulong rr2 = (pB2 shr 59u)
        '
        dim tmp_U32_tmp as ulong = (xx1 shr rr1) or (xx1 shl ((-rr1) and 31))
        '
        m_result_ulongint = (tmp_U32_tmp shl 32) or _
                         ((xx2 shr rr2) or (xx2 shl ((-rr2) and 31)))
    end scope
#endmacro


FUNCTION FUNCTION_ARG__ARRAY_INDEX_PROBLEM(f_abcx2 AS ABCx2_t) as ulongint
'    scope
        dim pB1 as ulongint = f_abcx2.ABC(1).B
            f_abcx2.ABC(1).B = (f_abcx2.ABC(1).B * f_abcx2.ABC(1).A) + f_abcx2.ABC(1).C
            dim as ulong xx1   = (((pB1 shr 18u) xor pB1) shr 27u)
            dim as ulong rr1 = (pB1 shr 59u)
        '
        dim pB2 as ulongint = f_abcx2.ABC(2).B
            f_abcx2.ABC(2).B = (f_abcx2.ABC(2).B * f_abcx2.ABC(2).A) + f_abcx2.ABC(2).C
            dim as ulong xx2   = (((pB2 shr 18u) xor pB2) shr 27u)
            dim as ulong rr2 = (pB2 shr 59u)
        '
        dim tmp_U32_tmp as ulong = (xx1 shr rr1) or (xx1 shl ((-rr1) and 31))
        '
        dim U64_tmp as ulongint = (tmp_U32_tmp shl 32) or _
                         ((xx2 shr rr2) or (xx2 shl ((-rr2) and 31)))
        '
        return U64_tmp
'    end scope
END FUNCTION


dim ABCx2 as ABCx2_t
ABCx2.ABC(2).B = 2377828209872ull
ABCx2.ABC(2).C = 3494323282998989ull

dim array_ABCx2(1 to 5) as ABCx2_t
array_ABCx2(1).ABC(2).B = 3894398729278888828ull
array_ABCx2(1).ABC(2).C = 8973897239023902444ull

dim jjjj as integer = 1

dim MAX_iterations as ulongint = 1000000000 '1 billion
dim U64 as ulongint

print
print

print "             ==>> MACRO version <<=="
print "             -----------------------"
print "1.0 ... parameter => nested TYPE single instance"
print "2.0 ... parameter => nested TYPE array member instance - literal  as index"
print "3.0 ... parameter => nested TYPE array member instance - variable as index"
print
        ' -------------------------------
print "1.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time =";
dim xtime as double = timer

        For i as ulongint = 1 To MAX_iterations
            MACRO_ARG__ARRAY_INDEX_PROBLEM(ABCx2, U64)
        next

print timer - xtime; " seconds ... """
        ' -------------------------------
print "2.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time =";
xtime = timer

        For i as ulongint = 1 To MAX_iterations
            MACRO_ARG__ARRAY_INDEX_PROBLEM(array_ABCx2(1), U64)
        next

print timer - xtime; " seconds ... """
        ' -------------------------------
print "3.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time =";
xtime = timer

        For i as ulongint = 1 To MAX_iterations
            MACRO_ARG__ARRAY_INDEX_PROBLEM(array_ABCx2(jjjj), U64)
        next

print timer - xtime; " seconds ... """
        ' -------------------------------
print
print "MACRO ... Using a variable as the TYPE array index causes a large overhead."


print

print "             ==>> FUNCTION version <<=="
print "             --------------------------"
print "1.0 ... parameter => nested TYPE single instance"
print "2.0 ... parameter => nested TYPE array member instance - literal  as index"
print "3.0 ... parameter => nested TYPE array member instance - variable as index"
print
        ' -------------------------------
print "1.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time =";
xtime = timer

        For i as ulongint = 1 To MAX_iterations
            U64 = FUNCTION_ARG__ARRAY_INDEX_PROBLEM(ABCx2)
        next

print timer - xtime; " seconds ... """
        ' -------------------------------
print "2.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time =";
xtime = timer

        For i as ulongint = 1 To MAX_iterations
            U64 = FUNCTION_ARG__ARRAY_INDEX_PROBLEM(array_ABCx2(1))
        next

print timer - xtime; " seconds ... """
        ' -------------------------------
print "3.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time =";
xtime = timer

        For i as ulongint = 1 To MAX_iterations
            U64 = FUNCTION_ARG__ARRAY_INDEX_PROBLEM(array_ABCx2(jjjj))
        next

print timer - xtime; " seconds ... """
        ' -------------------------------
print
print "FUNCTION ... Although the overhead of the function stack has the largest impact on"
print "             performance in this execution of the algorithm... using a variable as"
print "             the TYPE array index still causes a noticeable overhead in the "
print "             algorithms performance."

print
print

.
Last edited by cbruce on May 08, 2018 21:03, edited 1 time in total.
paul doe
Posts: 1064
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: variable as index of array of types - performance issue

Postby paul doe » May 08, 2018 21:03

cbruce wrote:.
FreeBASIC Compiler - Version 1.06.0 (11-29-2017), built for win64 (64bit)
Windows 10.

Compiler switches?

This is the result I get when compiling with -gen gcc -Wc -Ofast:

Code: Select all

             ==>> MACRO version <<==
             -----------------------
1.0 ... parameter => nested TYPE single instance
2.0 ... parameter => nested TYPE array member instance - literal  as index
3.0 ... parameter => nested TYPE array member instance - variable as index

1.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 0 seconds ... "
2.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 0.4411302515291027 seconds ... "
3.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 0.4191049316068529 seconds ... "

MACRO ... Using a variable as the TYPE array index causes a large overhead.

             ==>> FUNCTION version <<==
             --------------------------
1.0 ... parameter = nested TYPE single instance
2.0 ... parameter = nested TYPE array member instance - literal  as index
3.0 ... parameter = nested TYPE array member instance - variable as index

1.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 0 seconds ... "
2.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 0.4196574196175789 seconds ... "
3.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 0.4208474665138056 seconds ... "

FUNCTION ... Although the overhead of the function stack has the largest impact on
             performance in this execution of the algorithm... using a variable as
             the TYPE array index still causes a noticeable overhead in the
             algorithms performance.

As you can see, the 'macro' version is getting optimized away, so perhaps you'll want to code a more meaningful example of the perceived issue?
Last edited by paul doe on May 08, 2018 21:07, edited 1 time in total.
cbruce
Posts: 136
Joined: Sep 12, 2007 19:13
Location: Dallas, Texas

Re: variable as index of array of types - performance issue

Postby cbruce » May 08, 2018 21:06

Using WinFBE... just "-s console" as far as I can see.

Compiler log:

Code: Select all

FreeBASIC Compiler - Version 1.06.0 (11-29-2017), built for win64 (64bit)
Copyright (C) 2004-2016 The FreeBASIC development team.
standalone
target:       win64, x86-64, 64bit
compiling:    D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.bas -o D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.c (main module)
compiling C:  D:\FreeBASICx64\bin\win64\gcc.exe -m64 -march=x86-64 -S -nostdlib -nostdinc -Wall -Wno-unused-label -Wno-unused-function -Wno-unused-variable -Wno-unused-but-set-variable -Wno-main -Werror-implicit-function-declaration -O0 -fno-strict-aliasing -frounding-math -fno-math-errno -fwrapv -fno-exceptions -fno-unwind-tables -fno-asynchronous-unwind-tables -masm=intel "D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.c" -o "D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.asm"
assembling:   D:\FreeBASICx64\bin\win64\as.exe --64 --strip-local-absolute "D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.asm" -o "D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.o"
linking:      D:\FreeBASICx64\bin\win64\ld.exe -m i386pep -o "D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.exe" -subsystem console "D:\FreeBASICx64\lib\win64\fbextra.x" --stack 1048576,1048576 -s -L "D:\FreeBASICx64\lib\win64" -L "." "D:\FreeBASICx64\lib\win64\crt2.o" "D:\FreeBASICx64\lib\win64\crtbegin.o" "D:\FreeBASICx64\lib\win64\fbrt0.o" "D:\FreeBASICx64\00_BRUCE\macro_arg__array_index_problem.o" "-(" -lfb -lgcc -lmsvcrt -lkernel32 -luser32 -lmingw32 -lmingwex -lmoldname -lgcc_eh "-)" "D:\FreeBASICx64\lib\win64\crtend.o"
paul doe
Posts: 1064
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: variable as index of array of types - performance issue

Postby paul doe » May 08, 2018 21:17

cbruce wrote:Using WinFBE... just "-s console" as far as I can see.

These are my results using just -s console:

Code: Select all

             ==>> MACRO version <<==
             -----------------------
1.0 ... parameter => nested TYPE single instance
2.0 ... parameter => nested TYPE array member instance - literal  as index
3.0 ... parameter => nested TYPE array member instance - variable as index

1.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 24.43513275545411 seconds ... "
2.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 24.29442932335951 seconds ... "
3.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 52.96722881179448 seconds ... "

MACRO ... Using a variable as the TYPE array index causes a large overhead.

             ==>> FUNCTION version <<==
             --------------------------
1.0 ... parameter = nested TYPE single instance
2.0 ... parameter = nested TYPE array member instance - literal  as index
3.0 ... parameter = nested TYPE array member instance - variable as index

1.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 41.42177190326765 seconds ... "
2.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 41.36851045166986 seconds ... "
3.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 45.86574966573971 seconds ... "

FUNCTION ... Although the overhead of the function stack has the largest impact on
             performance in this execution of the algorithm... using a variable as
             the TYPE array index still causes a noticeable overhead in the
             algorithms performance.

I don't see a problem with the 'function' version...
cbruce
Posts: 136
Joined: Sep 12, 2007 19:13
Location: Dallas, Texas

Re: variable as index of array of types - performance issue

Postby cbruce » May 08, 2018 21:31

.
WOW! Thanks Paul! This "learning new things every day" thing is going to kill me yet...
paul doe
Posts: 1064
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: variable as index of array of types - performance issue

Postby paul doe » May 08, 2018 21:32

cbruce wrote:.
WOW! Thanks Paul! This "learning new things every day" thing is going to kill me yet...

You're welcome (for what, I have no idea) LOL =D
cbruce
Posts: 136
Joined: Sep 12, 2007 19:13
Location: Dallas, Texas

Re: variable as index of array of types - performance issue

Postby cbruce » May 08, 2018 21:36

.
I had no idea what combination of the 1000 fbc.exe command line options to use that would get me that kind of performance improvement.
fxm
Posts: 9466
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: variable as index of array of types - performance issue

Postby fxm » May 08, 2018 21:38

fbc 64-bit with no option:

Code: Select all

             ==>> MACRO version <<==
             -----------------------
1.0 ... parameter => nested TYPE single instance
2.0 ... parameter => nested TYPE array member instance - literal  as index
3.0 ... parameter => nested TYPE array member instance - variable as index

1.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 8.215720837830304 seconds ... "
2.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 7.187694886675672 seconds ... "
3.0 - MACRO_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.87568720527816 seconds ... "

MACRO ... Using a variable as the TYPE array index causes a large overhead.

             ==>> FUNCTION version <<==
             --------------------------
1.0 ... parameter = nested TYPE single instance
2.0 ... parameter = nested TYPE array member instance - literal  as index
3.0 ... parameter = nested TYPE array member instance - variable as index

1.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 9.939705769827924 seconds ... "
2.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 10.01307924736284 seconds ... "
3.0 - FUNCTION_ARG__ARRAY_INDEX_PROBLEM ==> run time = 11.67213022264514 seconds ... "

FUNCTION ... Although the overhead of the function stack has the largest impact on
             performance in this execution of the algorithm... using a variable as
             the TYPE array index still causes a noticeable overhead in the
             algorithms performance.
paul doe
Posts: 1064
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: variable as index of array of types - performance issue

Postby paul doe » May 08, 2018 21:47

cbruce wrote:.
I had no idea what combination of the 1000 fbc.exe command line options to use that would get me that kind of performance improvement.

Oh, that =D

Bear in mind those are command line parameters passed to GCC. The -Wc fbc command line option is used to pass parameters to the GCC backend. It just so happens those are the parameters I use the most.

Have a look at this: Optimization options for GCC. Use whatever works best for you ;)

Return to “General”

Who is online

Users browsing this forum: No registered users and 4 guests