User avatar
DavidS
Posts: 3691
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Sat Dec 08, 2018 9:28 pm

ejolson wrote:
Sat Dec 08, 2018 7:58 pm
DavidS wrote:
Sat Dec 08, 2018 7:17 pm
Though that could double to present the differences of using differing OS's and toolkits for different implementations.
Agreed, though even a single well-written updated version of Star Trader could demonstrate that BASIC need not be avoided on Raspberry Pi.
Agreed. I vaugly remember these listings from long ago, they were among the introductory material that almos all looked at at one time, not anymore.

It would be interesting to figure out how to integrate graphics, mouse and networking into a game of that kind, it could be quite fun.

I do think it interesting that as I am writing my 3 parallel tutorials for programming for RISC OS using the WIMP in C, BASIC, and Assembly language without using any libraries, it is the C version that has the most assembly in it, with none in the BASIC version and about half as much in the assembly version (is something a bit backwards).
The Raspberry Pi is an ARM computer, that runs many Operating Systems, including Linux, RISC OS, BSD, Pi64 as well as many more.
Soon to add AROS, and TOSARM to the list of operating systems.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sat Dec 08, 2018 9:55 pm

ejolson,
If you are looking for silly mistakes, maybe...
Ouch. That would be a head slapper.
Still, the base might be ten times too big or more to handle all corner cases.
I'll check all this over in the morning.

Thanks for taking the time to look it over.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 1:57 am

I could not sleep. So I found myself making a karatsuba multiplier in Javascript. Looks like it works fine. It's kind of pointless given that JS now supports BigInts but it means I have proved to myself that I can get this damn algorithm working! All straight from the wikipedia pseudo code.

DavidS should be happy, it has no classes, no operator overloads, no external libraries, just plain code, apart from the fact that it is JS but ah well.

At some point I have to get this doing our fibo() challenge but first I have to check my C++ effort against it. The C++ thing will need tweaking to get rid of my crazy notion of all numbers being a power of 2.

This might be simpler to translate to BASIC or whatever other language directly. It's only simple functions doing schoolboy maths in the most part. The karatsuba thing being just calls to those functions.

Here it is:

Code: Select all

//
//
// Karatsaba multiply in javascript
//
//  From pseudo code at: https://en.wikipedia.org/wiki/Karatsuba_algorithm
//

let DIGITS = 7                  // Decimal digits in each big integer array element.
let BASE = Math.pow(10, DIGITS)

function sum(x, y)
{
    let a
    let b

    // Get operands, a being the shorter
    if (x.length > y.length) { 
        a = x
        b = y
    } else {
        a = y
        b = x
    }

    let len = a.length
    let sum = []
    let carry = 0

    for (let i = 0; i < len; i++) {
    
        // Sum the elements with carry
        let s
        if (isNaN(b[i])) {
            s = a[i]
        } else {
            s = a[i] + b[i]
        }       
        s += carry

        // Handle overflow and generate carry
        if (s >= BASE) {
          carry = 1;
          s -= BASE;
        } else {
          carry = 0;
        }

        // Stash result
        sum[i] = s
    }
    // If there is a carry append it to the sum array
    if (carry === 1)
    {
        sum.push(1);
    }
    return sum
}

// Assume that a > b
function sub(a, b) {
    result = []
    let carry = 0;
    for (let i = 0; i < a.length; i++) {
        let x = a[i]
        let y = b[i]

        if (isNaN(y)) {
            y = 0
        }

        if (carry) {
            x--;
        }

        let s;
        if (x < y) {
            s = x + BASE - y
            carry = 1
        } else {
            s = x - y
            carry = 0
        }
        result[i] = s
    }
    return result
}

function simpleMul(a, k) {
    let result = []
    carry = 0
    for (let i = 0; i < a.length; i++) {
        let r = a[i] * k + carry
        if (r < BASE) {
            result[i] = r;
            carry = 0
        }
        else
        {
            carry = Math.floor(r / BASE);
            result[i] = Math.floor(r % BASE);
        }
    }
    if (carry) {
        result.push(carry)
    }
    return result
}

function shift(a, m) {
    return Array(m).fill(0).concat(a)
}

function mul(a, b) {
    let result
    if (a.length === 1) {
        result = simpleMul(b, a[0])
    } else if (b.length === 1) {
        result = simpleMul(a, b[0])
    } else {
        let m = a.length < b.length ? a.length : b.length
        let m2 = (m/2)|0

        let high1 = a.slice(m2, a.length)
        let low1 = a.slice(0, m2)
        let high2 = b.slice(m2, b.length)
        let low2 = b.slice(0, m2)

        let z0 = mul(low1, low2)
        let z1 = mul(sum(low1, high1), sum(low2, high2))
        let z2 = mul(high1, high2)

        let s1 = sub(z1, z2)
        let s2 = sub(s1, z0)

        result = sum(sum(shift(z2, m2 * 2), shift(s2, m2)), z0)
    }
    return result
}

function printBigInteger (k) {
    let digits = "" + k[k.length - 1]
    process.stdout.write(digits); 
    for (let i = k.length - 2; i >= 0; i--) {
        let digits = "" + k[i]
        process.stdout.write(digits.padStart(DIGITS, '0')); 
    }
    process.stdout.write("\n"); 
}

function isEven(n) {
    return (n & 1) === 0;
}
  
let zero = [0];
let one = [1];
let two = [2];

let memo = [zero, one, one]
  
function fibo (n) {
    if (memo[n]) {
        let res = memo[n]
        return res
    }
    let k = (n / 2) | 0
    let fk = fibo(k)
    let fk1 = fibo(k + 1)
    if (isEven(n)) {
        let res = memo[n] = mul(fk, sub(mul(fk1, two,), fk))
        return res
    }
    let res = memo[n] = sum(mul(fk, fk), mul(fk1, fk1))
    return res
}

r = fibo(4784969)
printBigInteger(r)

Just run it under node.js

Code: Select all

$ node karatsuba.js

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 12:55 pm

Yay! My javascript karatsuba calculates fibo(4784969) correctly. I updated the code in the post above.

Code: Select all

$ time node karatsuba.js > fibo_4784969.dat
real    3m23.488s
user    3m19.469s
sys     0m12.797s
$ head -c 32 fibo_4784969.dat
10727395641800477229364813596225
$ tail -c 32 fibo_4784969.dat
4856539211500699706378405156269

User avatar
DavidS
Posts: 3691
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 5:12 pm

Heater wrote:
Sun Dec 09, 2018 12:55 pm
Yay! My javascript karatsuba calculates fibo(4784969) correctly. I updated the code in the post above.

Code: Select all

$ time node karatsuba.js > fibo_4784969.dat
real    3m23.488s
user    3m19.469s
sys     0m12.797s
$ head -c 32 fibo_4784969.dat
10727395641800477229364813596225
$ tail -c 32 fibo_4784969.dat
4856539211500699706378405156269
That is the most C looking JS I have ever seen you post :) . At a quick glance it looks like it should translate to a language that uses 32-bit integer maths without to much trouble.

That looks more understandable than the CPP reck you had up earlier. Good work, I am impressed.
The Raspberry Pi is an ARM computer, that runs many Operating Systems, including Linux, RISC OS, BSD, Pi64 as well as many more.
Soon to add AROS, and TOSARM to the list of operating systems.

ejolson
Posts: 2180
Joined: Tue Mar 18, 2014 11:47 am

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 5:20 pm

Heater wrote:
Sun Dec 09, 2018 12:55 pm
Yay! My javascript karatsuba calculates fibo(4784969) correctly. I updated the code in the post above.

Code: Select all

$ time node karatsuba.js > fibo_4784969.dat
real    3m23.488s
user    3m19.469s
sys     0m12.797s
$ head -c 32 fibo_4784969.dat
10727395641800477229364813596225
$ tail -c 32 fibo_4784969.dat
4856539211500699706378405156269
Nice work. It seems node.js really is your favourite programming language!

Does

let k = (n / 2) | 0

mean integer division? Does Math.floor do something different? Is there a different notation for integer division?

The conditional

if (a.length === 1)

in your Karatsuba multiplication algorithm switches to O(n^2) multiplication only when n is one. Have you tried switching when n<10 instead to see if things run faster? Alternatively, you could inline the n=1 case as in the C++ code.

Using memoization is interesting and makes the use of the doubling formulas clearer. You might also want to check if n-1 and n-2 have already been memoized and if so then use the definition

F(n) = F(n-1) + F(n-2)

to compute F(n) as this case should occur about 50 percent of the time. According to top, how much memory does this program use while running?
Last edited by ejolson on Sun Dec 09, 2018 6:01 pm, edited 5 times in total.

jahboater
Posts: 3282
Joined: Wed Feb 04, 2015 6:38 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 5:46 pm

ejolson wrote:
Sun Dec 09, 2018 5:20 pm
Nice work. It seems node.js really is your favourite programming language!

Does

let k = (n / 2) | 0

mean integer division? Does Math.floor do something different? Is there a different notation for integer division?
I was puzzled by the isNaN tests? Some kind of overflow check?

Integer arithmetic is done by the floating point hardware, giving 52 (53?) bits of precision on a 32-bit platform.
Division gets converted to real floating-point and the "| 0" forces it back to integer mode.

Perhaps dividing by two would be quicker by simply subtracting one from the exponent.
let k = ldexp( n, -1 )
Last edited by jahboater on Sun Dec 09, 2018 6:25 pm, edited 1 time in total.

ejolson
Posts: 2180
Joined: Tue Mar 18, 2014 11:47 am

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 5:58 pm

jahboater wrote:
Sun Dec 09, 2018 5:46 pm
ejolson wrote:
Sun Dec 09, 2018 5:20 pm
Nice work. It seems node.js really is your favourite programming language!

Does

let k = (n / 2) | 0

mean integer division? Does Math.floor do something different? Is there a different notation for integer division?
I was puzzled by the isNaN tests? Some kind of overflow check?

Integer arithmetic is done by the floating point hardware, giving 52 (53?) bits of precision on a 32-bit platform.
Division gets converted to real floating-point and the "| 0" forces it back to integer mode.
Perhaps dividing by two would be quicker by simply subtracting one from the exponent.
Is there a difference between |0 and Math.floor?

If the big numbers are already represented using floating point, it might not be too difficult to implement an FFT-based fast-multiplication subroutine as well.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 7:41 pm

DavidS,
That is the most C looking JS I have ever seen you post :) . At a quick glance it looks like it should translate to a language that uses 32-bit integer maths without to much trouble.
Why thank you.

I was actually trying to make it as clear as possible. So no Javascript features like objects or classes or modern JS function syntax or the optimizations that can be done with typed arrays and such. The intention being to express that pseudo code from wikipedia as clearly as possible. Such that anyone with a passing knowledge of C, C++, Java, C# even Pascal or BASIC would understand it even if they had ever seen JS before.

For my own selfish reasons of course. I want a very clear and working prototype from which to start rewriting my C++ effort.

As such, a translation into BASIC should be a doddle. Perhaps not efficient but getting the job done.
That looks more understandable than the CPP reck you had up earlier.
Ouch!

But there is the thing. In JS you can quickly do this kind of thing and create an easily readable solution without getting bogged down in all the "syntactic noise" of C, C++ or most other languages. Might not be efficient but it looks beautiful.
Good work, I am impressed.
Thanks again. But if you look at it, and look at the karatsuba pseudo code on wikipedia, you see that there is nothing in there except simple schoolboy arithmetic. Even if you don't try to follow why that karatsuba part works. I'm not sure it's totally clear to me now!

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 8:14 pm

ejolson,
Nice work. It seems node.js really is your favourite programming language!
Thanks.

Well, depends what I'm doing I guess. Things like JS and even Python are great for getting your head around and playing with some new algorithm without getting distracted by weird syntax and superfluous crap. When you feel the need for speed it's time to recast in C/C++ or whatever.

Just now my other infatuation is Scala. The easy way to describe hardware for FPGAs.
Does

let k = (n / 2) | 0

mean integer division? Does Math.floor do something different? Is there a different notation for integer division?
It's complicated. But simple...

Numbers in JS are 64 bit floats. That means you can do integer correct arithmetic up to 2 to the power 53 - 1. Something like 9007199254740991.

Of course n/2 might not be an integer so what to do:

1) Use Math.floor. That will give you a correct integer value up to 53 bits:

Code: Select all

> Number.MAX_SAFE_INTEGER
9007199254740991
> Number.MAX_SAFE_INTEGER / 2
4503599627370495.5
> Math.floor(Number.MAX_SAFE_INTEGER / 2)
4503599627370495
2) Use a logical operator like |

Code: Select all

> Number.MAX_SAFE_INTEGER
9007199254740991
> Number.MAX_SAFE_INTEGER / 2
4503599627370495.5
> (Number.MAX_SAFE_INTEGER / 2)|0
-1
Ouch! What happened there?

Thing is logical operators in JS all work on 32 bit values. So the integer in your float gets chopped to 32 bits then the logical operator applied.

That might sound crazy but it makes a lot of sense. It's efficient in the run time, and it enables one to transpile C/C++ code to JS and have it run very efficiently. See Emscripten.

In the case of my n/2 I think 32 bits is enough for the result.

Thanks for the potential optimization tips. I will look at that later. Now it's back to C++.... God rest my soul.

jahboater
Posts: 3282
Joined: Wed Feb 04, 2015 6:38 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 8:39 pm

I don't think using "let k = ldexp( n, -1 )" will work for JS integers.

Code: Select all

>> split 42.0

Sign bit: 0
Exponent: 0x404
Mantissa: 0x15000000000000

>> split 21.0

Sign bit: 0
Exponent: 0x403
Mantissa: 0x15000000000000
As you can see decrementing the exponent divides the floating point number by 2 (because the exponent is in base 2).
But the significand remains the same. I suspect JS never looks at the exponent.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 9:01 pm

jahboater,
I was puzzled by the isNaN tests? Some kind of overflow check?
Dang! You spotted it.

Thing is that during that loop in sum() one is adding together, element for element, two arrays. But they are of different lengths, so at some point the array one is adding has no values.

One could test for that by looking at the array lengths, as one might in C, or just check there is no defined value in the array to be added.

I did that check with isNaN(). At the time I thought that might confuse readers. I have now changed it to "if (b === undefined)" which should be clearer.

"NaN" is really an idea from floating point. The result of a divide by zero and such. So it does not really belong here.
Perhaps dividing by two would be quicker by simply subtracting one from the exponent.
let k = ldexp( n, -1 )

I have no idea.

I would not do it because it obfuscates things for those that don't know what ldexp is. Also modern JS engines tend to be a bit clever about knowing what types one is using and and will optimize for integers anyway. So those values are likely treated as 32 bit integers and the divide by two optimized to a shift anyway.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 9:11 pm

ejolson,
Is there a difference between |0 and Math.floor?
Yes. See above.
If the big numbers are already represented using floating point, it might not be too difficult to implement an FFT-based fast-multiplication subroutine as well.
Oh boy.

It's only a couple of years ago I learned that one could do big multiplies with FFT.

First one has to write the FFT...

It was two or three decades between seeing my first FFT source code, in BASIC, and understanding how the hell that thing crazy thing works! Despite being schooled in the ways of the Fourier Transform in my maths and physics education way back in time. Finally I could write my own FFT from scratch: https://github.com/ZiCog/fftbench

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 9:24 pm

ejolson,
According to top, how much memory does this program use while running?
Hmmm... let's see...

Never more than 1% of my 8GB it seems:

Code: Select all

top - 23:21:21 up 9 days,  7:05,  0 users,  load average: 0.52, 0.58, 0.59
Tasks:  10 total,   2 running,   8 sleeping,   0 stopped,   0 zombie
%Cpu(s): 13.4 us,  5.6 sy,  0.0 ni, 80.8 id,  0.0 wa,  0.2 hi,  0.0 si,  0.0 st
KiB Mem :  8365488 total,  2863140 free,  5272996 used,   229352 buff/cache
KiB Swap: 13928364 total, 13323048 free,   605316 used.  2958760 avail Mem

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
15415 heater    20   0  823636  84616  13176 R 106.3  1.0   0:32.85 node

ejolson
Posts: 2180
Joined: Tue Mar 18, 2014 11:47 am

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 9:31 pm

Heater wrote:
Sun Dec 09, 2018 8:14 pm
ejolson,
Nice work. It seems node.js really is your favourite programming language!
Thanks.

Well, depends what I'm doing I guess. Things like JS and even Python are great for getting your head around and playing with some new algorithm without getting distracted by weird syntax and superfluous crap. When you feel the need for speed it's time to recast in C/C++ or whatever.
My original FreeBASIC code had expressions like

sum(mul(fk, fk), mul(fk1, fk1))

However, the stack overflowed when working with numbers much more than 100000 digits, so I switched to statically allocated temporary variables that were still fine for the Fibonacci doubling-formula recursion. Doing the same with the Karatsuba algorithm was more difficult which is why I left it out.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 10:05 pm

ejolson,

I have no idea what goes on with parameter passing in any kind of BASIC. Are they really passing whole arrays by value, copying the whole thing into the subroutine on the stack. Sounds nuts!

In JS all those parameters being passed are some kind of refence/pointer to the actual array data, which is in heap memory. As such one can make a lot of nested calls before running out of stack.

Similarly, in my C++ effort the big number values are small objects that contain only a pointer to the actuall big integer array allocated on the heap and a size.

Now, in the karatsuba algorithm the size of the big numbers is being halved on each recursion. So starting with a million digits I would only expect a recursion depth of only 20 or so. Hardly anything.

Of course, a lot of that allocating and freeing of temporary big integer values as the algorithm continues is redundant. One can recycle the space used by old values with new values.

It's a bit tricky to do that whilst keeping the expression of the algorithm plain to see.

User avatar
DavidS
Posts: 3691
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 10:19 pm

@Heater:
Since you mention again classes (Thanks for not using them in the JS), why do you use them when you are not using inheratence? It does not make much since considering it is unneeded:

Code: Select all


// In ANSI C89.

typedef struct {
  int x;
  int y;
  int c;
  int (*draw)(PIXEL *this);
  int (*pos)(int x, int y, PIXEL *this);
  void (*getpos)(int *x, int *y, PIXEL *this);
} PIXEL;

PIXEL point = {0,0,0,&mydraw,&mypos,&getpos};

Then when you initialize a variable of the type make sure to point its fucntion pointers to functions that are of the correct form and you can still do something like point.pos(100,100, &point); and make your code as unreadable as C++. And you can still have the private stuff by using static globals.

You can find more examples of doing that kind of thing in the book The C Programming Language, 2nd Edition, ANSI C by Brian W. Kernigham and Dennis M. Ritchie. It is a good book to keep on the bookshelf next to the desk always in arms reach. There examples are even better than mine :) .
The Raspberry Pi is an ARM computer, that runs many Operating Systems, including Linux, RISC OS, BSD, Pi64 as well as many more.
Soon to add AROS, and TOSARM to the list of operating systems.

jdonald
Posts: 80
Joined: Fri Nov 03, 2017 4:36 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 10:37 pm

32-bit vs 64-bit: Here are my apples-to-apples gcc 8.2 tests on a Pi 3B+:

Code: Select all

[email protected]:~$ time ./fibo-armhf | head -c 32
10727395641800477229364813596225
real	0m15.712s
user	0m15.668s
sys	0m0.026s
[email protected]:~$ time ./fibo-armhf | tail -c 32
4856539211500699706378405156269

real	0m15.774s
user	0m15.723s
sys	0m0.035s

Code: Select all

[email protected]:~$ time ./fibo-arm64 | head -c 32
10727395641800477229364813596225
real	0m7.728s
user	0m7.686s
sys	0m0.029s
[email protected]:~$ time ./fibo-arm64 | tail -c 32
4856539211500699706378405156269

real	0m7.785s
user	0m7.745s
sys	0m0.032s
Thanks ejolson for the tip of checking my power supply to avoid throttling from voltage drops. I now get better and much more consistent results +/- 10 ms. Also thanks jahboater for the script to build a custom gcc 8.2.

For compile flags I'm using only -O3 because -march=armv8-a and -mtune=cortex-a53 have no effect. Not only is performance unchanged, but the md5sum of the output binary remains identical. Meanwhile -ffast-math does change the instructions slightly but has no measurable effect on performance.

gcc 8.2 vs gcc 6.3 accounts for about a 0.2 second speedup in the 64-bit case.
jahboater wrote:
Tue Dec 04, 2018 6:41 am
In 64-bit mode on an Odroid C2 at 1.68GHz
...
Correcting for the clock speed difference 1.68/1.4 * 6.24 = 7.488 seconds and 7.788 seconds.
Very close, nice!

jahboater
Posts: 3282
Joined: Wed Feb 04, 2015 6:38 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 11:21 pm

jdonald wrote:
Sun Dec 09, 2018 10:37 pm
For compile flags I'm using only -O3 because -march=armv8-a and -mtune=cortex-a53 have no effect. Not only is performance unchanged, but the md5sum of the output binary remains identical.
Yes, if you have built the compiler yourself then the defaults for -march and -mcpu etc are the same, so there is no need to give them
(see the ./configure line in the script). For the default compiler though which is probably built for ARMv6 (the Pi Zero), you have to tell it to compile for the ARMv8 Pi3. With recent gcc, -march=native and -mtune=native work too.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Sun Dec 09, 2018 11:34 pm

DavidS,
Since you mention again classes ... why do you use them when you are not using inheratence? It does not make much since....
Using classes is nothing to do with inheritance.

In C++ class and struct are almost the same thing. The only difference being the default visibility of items within the class/struct by functions that are not members of the class/struct.
It does not make much since considering it is unneeded:...Then when you initialize a variable of the type make sure to point its fucntion pointers to functions that are of the correct form
Perhaps unneeded but if you define methods in a C++ class/struct then you don't need to "make sure to point its fucntion pointers to functions that are of the correct form" the compiler does it for you.
...and you can still do something like point.pos(100,100, &point); and make your code as unreadable as C++.
Hmm... In c++ you don't need to pass a pointer to the class/struct as a parameter to every function call. The compiler does that for you. So your example would be simply:

Code: Select all

    point.pos(100,100);
I would argue that makes the source less cluttered with redundant junk and more readable.

Code: Select all

And you can still have the private stuff by using static globals.
Except static globals are not the same as private parts of classes/structs. Static globals are common to all instances of the same class/struct, not on a per instance basis.

For sure I love my copy of the white book. Also I have worked on some projects that were very objected oriented, as you describe, in C.

Some years ago when having a similar debate with someone I created an example of the same functionality in C and C++. The C version using structs and pointer parameters and the C++ version using classes and methods. Turned out the compiler generated byte for byte exactly the same instructions for both C and C++ versions! Even I was surprised. Wish I still had that source to show you. Perhaps I should recreate it.

ejolson
Posts: 2180
Joined: Tue Mar 18, 2014 11:47 am

Re: Why Avoid BASIC on RPi?

Mon Dec 10, 2018 2:55 am

jdonald wrote:
Sun Dec 09, 2018 10:37 pm
32-bit vs 64-bit: Here are my apples-to-apples gcc 8.2 tests on a Pi 3B+:

Code: Select all

[email protected]:~$ time ./fibo-armhf | head -c 32
10727395641800477229364813596225
real	0m15.712s
user	0m15.668s
sys	0m0.026s
[email protected]:~$ time ./fibo-armhf | tail -c 32
4856539211500699706378405156269

real	0m15.774s
user	0m15.723s
sys	0m0.035s

Code: Select all

[email protected]:~$ time ./fibo-arm64 | head -c 32
10727395641800477229364813596225
real	0m7.728s
user	0m7.686s
sys	0m0.029s
[email protected]:~$ time ./fibo-arm64 | tail -c 32
4856539211500699706378405156269

real	0m7.785s
user	0m7.745s
sys	0m0.032s
Thanks ejolson for the tip of checking my power supply to avoid throttling from voltage drops. I now get better and much more consistent results +/- 10 ms. Also thanks jahboater for the script to build a custom gcc 8.2.

For compile flags I'm using only -O3 because -march=armv8-a and -mtune=cortex-a53 have no effect. Not only is performance unchanged, but the md5sum of the output binary remains identical. Meanwhile -ffast-math does change the instructions slightly but has no measurable effect on performance.

gcc 8.2 vs gcc 6.3 accounts for about a 0.2 second speedup in the 64-bit case.
jahboater wrote:
Tue Dec 04, 2018 6:41 am
In 64-bit mode on an Odroid C2 at 1.68GHz
...
Correcting for the clock speed difference 1.68/1.4 * 6.24 = 7.488 seconds and 7.788 seconds.
Very close, nice!
Thanks for downloading the Fibonacci code and making a comparison between 32-bit and 64-bit modes. For me this is a real-world application and I find the differences very interesting. I'm also glad you got the power supply fixed. You are the second person who has discovered and corrected a problem with their Raspberry Pi configuration as a result of running that program.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Mon Dec 10, 2018 9:25 am

DavidS,

Your PIXEL class-like-thing in C is terrible:

1) It's wasting a lot of space. Every instance of PIXEL will contain the three pointers to the "method" functions. In C++ classes and structs do not store method pointers in the objects.

2) It's inefficient. Every call to a "method". eg "point.pos(100,100, &point);" is indirect, the pointer to the method has to be fetched from the object first.

There are times when one might want to store functions within structs, when the function pointed to will be determined at or changing during run time. Otherwise it's best to keep then out of there.
Last edited by Heater on Mon Dec 10, 2018 12:58 pm, edited 1 time in total.

jahboater
Posts: 3282
Joined: Wed Feb 04, 2015 6:38 pm

Re: Why Avoid BASIC on RPi?

Mon Dec 10, 2018 9:51 am

Heater wrote:
Mon Dec 10, 2018 9:25 am
1) It's wasting a lot of space. Every instance of PIXEL will contain the three pointers to the "method" functions. In C++ classes and structs do not store method pointers in the objects.

2) It's inefficient. Every call to a "method". eg "point.pos(100,100, &point);" has indirect, the pointer to the method has to be fetched from the object first.
3) the methods cannot be inlined.

Its best to have support in the language.

Heater
Posts: 10290
Joined: Tue Jul 17, 2012 3:02 pm

Re: Why Avoid BASIC on RPi?

Mon Dec 10, 2018 9:55 am

I created a github repository to hold solutions to the fibo(4784969) challenge.

https://github.com/ZiCog/fibo_4784969

Having spent so much messing with this I thought it was time to make it a project.

It's a bit of a mess at the moment. Probably has some junk in it. I'd like to include all the solutions presented here if that is OK with everyone. Plus other interesting bits of code that have popped up in this thread.

So far we only have working solutions in Python, Javascript, and C.

Still waiting on my sorting out my C++ solution (or someone else perhaps) and which ever BASIC dialect DavidS is working on.

User avatar
DavidS
Posts: 3691
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Mon Dec 10, 2018 1:32 pm

heater wrote: DavidS,

Your PIXEL class-like-thing in C is terrible:
Yes it is a terible example, and technicaly not the recommend way to do it, should use a single instance of a second struct type to contain the function pointers for all instances of the data structure, that would better obey the rules. I was just giving a quick and dirty example without using a second structure.
1) It's wasting a lot of space. Every instance of PIXEL will contain the three pointers to the "method" functions. In C++ classes and structs do not store method pointers in the objects.
Yes as said:

You should use a single instance of a second struct type to contain the function pointers for all instances of the data structure, that would better obey the rules. I was just giving a quick and dirty example without using a second structure.
2) It's inefficient. Every call to a "method". eg "point.pos(100,100, &point);" is indirect, the pointer to the method has to be fetched from the object first.
Have you looked at many C++ compilers? Ok newer ones cheat alot to limit this. Though the norm is to use indirection for member methods.

Also if it is compiled on a 32-bit ARM and done correctly the overhead of calling by refernce is equal to the overhead of a direct call (the nice things about having the Program Counter exposed as a user register). So it does not matter either way.
There are times when one might want to store functions within structs, when the function pointed to will be determined at or changing during run time. Otherwise it's best to keep then out of there.
Oh you mean like the methods in a class often are? Most C++ compilers I have examined make a second hidden structure for the function pointers of the member functions, with another copy for each case of overloading from inheritance.

So yes my example is terrible because it wastes memory do to not sepperating the function pointers, which is the wrong way around it. It was a quick and dirty syntax example.
The Raspberry Pi is an ARM computer, that runs many Operating Systems, including Linux, RISC OS, BSD, Pi64 as well as many more.
Soon to add AROS, and TOSARM to the list of operating systems.

Return to “Off topic discussion”