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

Re: Why Avoid BASIC on RPi?

Wed Dec 05, 2018 5:29 pm

Paeryn wrote:
Tue Dec 04, 2018 11:56 am
Ah, found out why it was running so slow on mine. My gcc-8.1 is slightly mis-configured (I cross compiled it on my desktop) and doesn't link properly
While the goal of this thread is to compare the expressivity of Basic with other languages in terms of how efficiently various standard algorithms can be coded, keeping a record of performance metrics for openly available code also allows people to confirm correct operation and detect misconfiguration of their personal Pi computers.

Have you tried running my Pi Pie Chart program to see if your new cross compiler is working fine? The reference numbers for the Pi 3B+ for those charts were made with version 6.4 of gcc. I wonder whether 8.2 gives faster run timings.

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

Re: Why Avoid BASIC on RPi?

Wed Dec 05, 2018 6:43 pm

Here are the times for a Pi3B+ at stock settings with gcc 8.2 :-

Code: Select all

pi@pi3:~/pichart-current $ ls
Makefile  fourier.c  lorenz.c  merge.c  pichart.c  pichart.h  sieve.c  util.c
pi@pi3:~/pichart-current $ make
gcc -std=gnu99 -O3 -ffast-math -Wall -lm -o pichart-serial pichart.c util.c sieve.c merge.c fourier.c lorenz.c
gcc -std=gnu99 -O3 -ffast-math -Wall -lm -fopenmp -o pichart-openmp pichart.c util.c sieve.c merge.c fourier.c lorenz.c
pi@pi3:~/pichart-current $ ls
Makefile   lorenz.c  pichart-openmp  pichart.c  sieve.c
fourier.c  merge.c   pichart-serial  pichart.h  util.c
pi@pi3:~/pichart-current $ ./pichart-openmp 
pichart -- Raspberry Pi Performance OPENMP version 23

Prime Sieve          P=14630843 Threads=4 Sec=1.55975 Mops=599.024
Merge Sort           N=16777216 Threads=8 Sec=1.33504 Mops=301.603
Fourier Transform    N=4194304 Threads=4 Sec=2.37177 Mflops=194.527
Lorenz 96            N=32768 K=16384 Threads=4 Sec=3.013 Mflops=1069.11

Making pie charts...done.
pi@pi3:~/pichart-current $ ./pichart-serial 
pichart -- Raspberry Pi Performance Serial version 23

Prime Sieve          P=14630843 Threads=2 Sec=6.2026 Mops=150.635
Merge Sort           N=16777216 Threads=1 Sec=4.97613 Mops=80.9169
Fourier Transform    N=4194304 Threads=1 Sec=6.05902 Mflops=76.1466
Lorenz 96            N=32768 K=16384 Threads=1 Sec=11.0134 Mflops=292.482

Making pie charts...done.
pi@pi3:~/pichart-current $ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/local/libexec/gcc/arm-linux-gnueabihf/8.2.0/lto-wrapper
Target: arm-linux-gnueabihf
Configured with: ../configure --enable-languages=c,c++ --with-cpu=cortex-a53 --with-fpu=neon-fp-armv8 --with-float=hard --build=arm-linux-gnueabihf --host=arm-linux-gnueabihf --target=arm-linux-gnueabihf --enable-checking=no
Thread model: posix
gcc version 8.2.0 (GCC) 
pi@pi3:~/pichart-current $ vcgencmd get_throttled
throttled=0x0
pi@pi3:~/pichart-current $ 
as you can see it didn't throttle. In fact it was quite a light load for a 3B+, the temp (with a heatsink) rose by less than 5C and peaked at 44C during the Lorenz 96 openmp section (I ran it a second time and monitored the temps).

User avatar
Paeryn
Posts: 2565
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Why Avoid BASIC on RPi?

Wed Dec 05, 2018 7:52 pm

ejolson wrote:
Wed Dec 05, 2018 5:29 pm
Paeryn wrote:
Tue Dec 04, 2018 11:56 am
Ah, found out why it was running so slow on mine. My gcc-8.1 is slightly mis-configured (I cross compiled it on my desktop) and doesn't link properly
While the goal of this thread is to compare the expressivity of Basic with other languages in terms of how efficiently various standard algorithms can be coded, keeping a record of performance metrics for openly available code also allows people to confirm correct operation and detect misconfiguration of their personal Pi computers.

Have you tried running my Pi Pie Chart program to see if your new cross compiler is working fine? The reference numbers for the Pi 3B+ for those charts were made with version 6.4 of gcc. I wonder whether 8.2 gives faster run timings.
I didn't cross-compile this program, I cross-compiled gcc-8, I know the compiler works, just that when it tries creating an executable it doesn't prepend the path to the three crt*.o files so fails to find them. The problem was that I originally used gcc-6 to do the final linking which meant that it was using gcc-6's libgcc rather than gcc-8's.

The big difference was the internal __udivmoddi4, that function alone was taking a lot longer. Looking at the code for __udivmoddi, in gcc-8's it's 1064 bytes long whereas in gcc-6's it's only 296 bytes, I assume gcc-8 did a better job of optimising it's library (probably helped that it targeted it for armv8 rather than armv6).

Code: Select all

Profile for fiboA - compiled and linked with gcc-8

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 55.97      9.66     9.66       69   139.93   178.50  mulbnk
 22.33     13.51     3.85                             __udivmoddi4
  9.45     15.14     1.63   797140     0.00     0.00  subbn2
  5.97     16.17     1.03   797177     0.00     0.00  addbn
  4.99     17.03     0.86                             __aeabi_uldivmod
  1.28     17.25     0.22                             __aeabi_ldiv0
  0.06     17.26     0.01                             fibo
  0.00     17.26     0.00        2     0.00     0.00  atobn

Code: Select all

Profile for fiboB - compiled with gcc-8 but linked with gcc-6

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 65.60     24.91    24.91                             __udivmoddi4
 24.40     34.18     9.27       69   134.28   175.46  mulbnk
  4.79     36.00     1.82   797140     0.00     0.00  subbn2
  2.69     37.02     1.02   797177     0.00     0.00  addbn
  2.32     37.90     0.88                             __aeabi_uldivmod
  0.18     37.97     0.07                             __aeabi_ldiv0
  0.08     38.00     0.03                             fibo
  0.00     38.00     0.00        2     0.00     0.00  atobn
As you can see, __udivmoddi4 alone was accounting for about 25 seconds of the whole run with gcc-6's libgcc whereas with gcc-8's libgcc it only accounted for about 4 seconds.
She who travels light — forgot something.

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

Re: Why Avoid BASIC on RPi?

Wed Dec 05, 2018 8:04 pm

jahboater wrote:
Wed Dec 05, 2018 6:43 pm
Here are the times for a Pi3B+ at stock settings with gcc 8.2.
Hm, after dividing by the speeds of the gcc 6.4 compiled version for the 3B+ the results are a bit mixed.

Code: Select all

Sieve:              1.06
Merge Sort:         0.83
Fourier Transform:  1.09
Lorenz 96:          1.02
The merge sort runs slower while the others run faster.

As you have observed, none of the four pichart performance metrics function as stress tests. They are more realistically seen as common algorithms coded in C that reflect application-level performance prior to carefully optimized assembler tuning.

The most effective stress test right now for Pi computers appears to be the HPL high-performance Linpack linked with the OpenBLAS library. HPL achieves more than 6 Gflops which is six times greater than the Gflops attained by the Lorenz 96 code. Stress tests can be extremely important from an engineering point of view to guarantee correct performance of hardware, as demonstrated in this thread. As already stated, that is not the focus of the pichart program.

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

Re: Why Avoid BASIC on RPi?

Wed Dec 05, 2018 8:07 pm

Paeryn wrote:
Wed Dec 05, 2018 7:52 pm
As you can see, __udivmoddi4 alone was accounting for about 25 seconds of the whole run with gcc-6's libgcc whereas with gcc-8's libgcc it only accounted for about 4 seconds.
I hadn't expected that. I wonder if gcc 8.2 also gives the Pi Zero any performance boost.

The profiling results make me think that using 32-bit integers with a smaller base might be worthwhile to avoid the 64-bit division entirely. It would also be nice to break out the time spent in mulbn--I guess it is currently being inlined--to better choose the crossover point between the Karatsuba algorithm and the O(n^2) multiplication.

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 1:52 pm

Had company all day yesterday.

I am running into a few headaches in attempting to convert down to 32-bit integers, which should be simple, though giving me a little difficulty.


@ejolson:
How much of the time is being spent allocating memory and dealocating?
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 2:04 pm

DavidS wrote:
Thu Dec 06, 2018 1:52 pm
Had company all day yesterday.

I am running into a few headaches in attempting to convert down to 32-bit integers, which should be simple, though giving me a little difficulty.


@ejolson:
How much of the time is being spent allocating memory and dealocating?
I think I am going to use your very nice print and add routines to implement the slow Fibinocci and then take the time to go back and forth through all the allocations and dealocations to figure out what allocations are minimally needed so that a one time allocation can be done (instead of this allocate deallocate waste), so I can do a reasonable reimplimentation in BASIC (or C or Assmebly, or any other language).
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 3:00 pm

@ejolson:
Sorry about that, I do not know why my mind had interpreted multiple allocations this morning, I see that you are just pointing into the single alocation done at the beginning.

I must not be all the way awake.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 4:04 pm

DavidS wrote:
Thu Dec 06, 2018 3:00 pm
@ejolson:
Sorry about that, I do not know why my mind had interpreted multiple allocations this morning, I see that you are just pointing into the single alocation done at the beginning.

I must not be all the way awake.
As you've noticed ffree and fmalloc simply move a stack-like pointer up and down in a preallocated array. For this reason it is important that the free operations be done in reverse order so that the last one returns the pointer to where it originally was. Code in-lining followed by data flow analysis should remove any pointer assignments that are immediately overwritten so only code for the last ffree actually remains.
Last edited by ejolson on Thu Dec 06, 2018 4:24 pm, edited 2 times in total.

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 4:11 pm

ejolson wrote:
Thu Dec 06, 2018 4:04 pm
DavidS wrote:
Thu Dec 06, 2018 3:00 pm
@ejolson:
Sorry about that, I do not know why my mind had interpreted multiple allocations this morning, I see that you are just pointing into the single alocation done at the beginning.

I must not be all the way awake.
As you've noticed ffree and fmalloc simply move a stack-like pointer up and down in a preallocated array. For this reason it is important that the free operations be done in reverse order so that the last one returns the pointer to where it originally was. Code in-lining followed by data flow analysis should remove any pointer assignments that are immediately overwritten so only code for the last ffree actually remains.
Thank you.

Though that is one area of compiler optimization I have always disagreed with, data-flow analysis. I have always felt it should be up to the programmer to implement there algorithms well enough that such things are unneeded by the compiler. This is one of those things that I feel very strongly is the problem for the implementing programmer not the compiler, I feel that the compiler doing this kind of thing will make the programmer lazier, and lead to some of the poor code that we see all over the place.

Sorry about the mini rant there. Just one of the tings that gets under my skin a bit.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 4:34 pm

DavidS wrote:
Thu Dec 06, 2018 4:11 pm
ejolson wrote:
Thu Dec 06, 2018 4:04 pm
DavidS wrote:
Thu Dec 06, 2018 3:00 pm
@ejolson:
Sorry about that, I do not know why my mind had interpreted multiple allocations this morning, I see that you are just pointing into the single alocation done at the beginning.

I must not be all the way awake.
As you've noticed ffree and fmalloc simply move a stack-like pointer up and down in a preallocated array. For this reason it is important that the free operations be done in reverse order so that the last one returns the pointer to where it originally was. Code in-lining followed by data flow analysis should remove any pointer assignments that are immediately overwritten so only code for the last ffree actually remains.
Thank you.

Though that is one area of compiler optimization I have always disagreed with, data-flow analysis. I have always felt it should be up to the programmer to implement there algorithms well enough that such things are unneeded by the compiler. This is one of those things that I feel very strongly is the problem for the implementing programmer not the compiler, I feel that the compiler doing this kind of thing will make the programmer lazier, and lead to some of the poor code that we see all over the place.

Sorry about the mini rant there. Just one of the tings that gets under my skin a bit.
In my recollection, the main place these pretend memory allocations are useful is the Karatsuba multiplication algorithm.

In my opinion, data flow analysis is one of the things a computer can do better than a person. In the human-machine partnership it is best if the human focuses on things humans do better than machines. For a compiler without sensible data flow analysis, one could comment out all but the final delbn every place where they appear in sequence. Unfortunately, things would then break if subsequently a different memory allocation method were used in place of the current one.

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 4:58 pm

DavidS wrote:
Thu Dec 06, 2018 4:11 pm
Though that is one area of compiler optimization I have always disagreed with, data-flow analysis. I have always felt it should be up to the programmer to implement there algorithms well enough that such things are unneeded by the compiler. This is one of those things that I feel very strongly is the problem for the implementing programmer not the compiler, I feel that the compiler doing this kind of thing will make the programmer lazier, and lead to some of the poor code that we see all over the place.
I think the programmer should write simple code that's easy to read and understand (and therefore more likely to be correct).
Let the compiler worry about making it fast.

The data-flow analysis done by the compiler enables all sorts of helpful optimizations.
Here is a trivial one:-

Code: Select all

 if( num < 5 )
   return error;
  ....
  ....
  ....
  while( --num > 0 )
     something
The analysis done by the compiler safely allows the slow (two jumps) "while" loop to be replaced by a faster (one jump) "do while" loop where the loop body is executed at least once.

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 6:24 pm

jahboater wrote:
Thu Dec 06, 2018 4:58 pm
I think the programmer should write simple code that's easy to read and understand (and therefore more likely to be correct).
Let the compiler worry about making it fast.
Something might have happened with your code examples as I only see one loop.

Unfortunately, the insertion sort, the multiplication algorithm learned in school, exhaustive search as well as most attempts to calculate anything directly from the mathematical definitions are easier to understand than the efficient algorithms. As compilers are not yet able to identify and replace slow algorithms by fast ones, unless coding trivialities, one needs to think about efficiency first.
Last edited by ejolson on Thu Dec 06, 2018 7:01 pm, edited 1 time in total.

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 6:58 pm

ejolson wrote:
Thu Dec 06, 2018 6:24 pm
jahboater wrote:
Thu Dec 06, 2018 4:58 pm
I think the programmer should write simple code that's easy to read and understand (and therefore more likely to be correct).
Let the compiler worry about making it fast.
Something might have happened with your code examples as I only see one loop.
There is only one loop. its just a trivial example.

Because of the "if( num < 5 ) return" earlier in the code, the compiler knows that num must be 5 or more and the later loop must execute at least 5 times. Therefore it can change the programmers slow "while" loop into a faster "do while" loop.
As you know "do while" executes the loop body at least once - which the compiler now knows is OK because it has deduced the minimum value of num.

Interestingly, I think "assert( num >= 5 )" might have done the some thing.
ejolson wrote:
Thu Dec 06, 2018 6:24 pm
Unfortunately, the insertion sort, the multiplication algorithm learned in school, exhaustive search as well as most attempts to calculate anything directly from the mathematical definitions are easier to understand than the efficient algorithms. As compilers are not yet able to identify and replace slow algorithms by fast ones, unless coding trivialities, one needs to think about efficiency first.
Agreed. I was thinking of more basic stuff like the choice of loop above,
Last edited by jahboater on Thu Dec 06, 2018 7:09 pm, edited 1 time in total.

User avatar
Paeryn
Posts: 2565
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 7:05 pm

<jahboater beat me to repying whilst I was typing but I'll post anyway as it shows how the two jumps become one>
ejolson wrote:
Thu Dec 06, 2018 6:24 pm
jahboater wrote:
Thu Dec 06, 2018 4:58 pm
I think the programmer should write simple code that's easy to read and understand (and therefore more likely to be correct).
Let the compiler worry about making it fast.
Something might have happened with your code examples as I only see one loop.
Jahboater's example only needs one loop. The while() has a conditional jump at the start to exit the loop and an unconditional jump at the end to loop back.

Code: Select all

while (--num > 0) { ... }

Translated to pseudo code asm.

.loop:
  num = num - 1
  if num <= 0
    jmp .end_loop
  ... # Body of while loop
  jmp .loop
.end_loop:
But the compiler can deduce from the earlier test that num is at least 5 at the start so it doesn't need to test initially, the test can be moved to the end as part of the the loop back

Code: Select all

  num = num - 1
.loop:
  ... # body of while loop
  num = num - 1
  if num > 0
    jmp .loop
She who travels light — forgot something.

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 7:10 pm

Exactly, thanks Paeryn for the better explanation.

I think it would reduce further to this:-

Code: Select all

.loop:
  ... # body of while loop
  num = num - 1
  jmp if non zero, .loop
Which is why its sad that RISC V has lost its flags :(

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 7:51 pm

@jahboater
Interesting example, though is it really easier for a programmer to write that than:

Code: Select all

if(num < 5) return error;
/*Do something not effecting value of num ...*/
do{
 --num;
 /*Do something or another*/
}while(num);
Which for is just as easy, and more correct in this case. Most programmers have learned to automatically do this type of thing, it is the obviously better way to do it.


Or an easier yet to read version of the same, that may be able to be improved on depending on what is done inbetween what is here:

Code: Select all

;Assume var num is in R2

  ;... ...
  CMP     R2,#5
  MOVLE   R0,#Error
  LDRLE   R15,[R13],#4

  ;... Do something ...

.lp00
  SUB     R2,R2,#1
  ;... Do something ...
  CMP     R2,#5
  JNE     lp00
  ;... ...
So not a greate example.

Do you by chance have an example that makes a bit more sense?

If there really is something so comlex that it is hard enough to automatically write the algorithm optimally that dataflow profiling makes sense I am interested to hear, always willing to learn.

.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 7:54 pm

jahboater wrote:
Thu Dec 06, 2018 7:10 pm
Exactly, thanks Paeryn for the better explanation.

I think it would reduce further to this:-

Code: Select all

.loop:
  ... # body of while loop
  num = num - 1
  jmp if non zero, .loop
Which is why its sad that RISC V has lost its flags :(
Likely to fail if the value of num is used in the loop, the decrement needs to be at the top of the loop to functionally match the original, the test can be at the bottom
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 8:53 pm

Just got my new RPi 3B+, still running at default clocking for now, watching the tempurature as it goes. Going to need to push it for a while to see where it gets to under heavy loads :) .

1400MHz on an ARMv8 CPU.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 9:33 pm

This is an interesting discussion you have been having whist I was away hacking with my big fibo(4784969) solution. It's a national holiday here so I had some more time to work on it.

DavidS will be angry with me that I seem to have inadvertently been working on this in C++ rather than C as I promised earlier. But bear with me because:

1) Like DavidS I want to get that karatsuba multiplication algorithm straight in my mind and working first. No matter how unoptimized and inefficient that may be. It's easier to do that if you can use C++ operator overloading and write "a + b" or " x * y" where the numbers are your big integer representation. Rather that calling functions that operate on pointers to the big arrays that are your numbers. Then your algorithm can look more or less like it does in the pseudo code presented on wikipedia.

2) Of course every such "+", "*" and whatever operator in C++ then involves a lot of memory allocation and reallocation to move those big number arrays around. Like it does with normal integers. But here the cost is a lot of malloc and memcpy under the hood.

3) The often stated promise of the C++ language is "zero cost abstraction". OK, then it should be possible to express the algorithm abstractly,. like the wikipedia pseudo code, but short circuit the memory management underneath all the big integer maths. Don't make redundant copies, don't rely on "new" and "delete" to manage memory etc. Basically put your own memory management in place to support the number type you have created.

Well, so far this is not working out well. My big integer maths does add and sub OK. Multiplication works some of the time !

If the situation improves I might be brave enough to present some code....

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 10:13 pm

Well it is not really pleasing that you are doing it in C++, though if you can limit the OO stuff in your C++ I can forgive you.

The one thing I wish we had from C++ in standard C is operator overloading, so I understand.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Thu Dec 06, 2018 11:28 pm

DavidS,
Well it is not really pleasing that you are doing it in C++, though if you can limit the OO stuff in your C++ I can forgive you.

The one thing I wish we had from C++ in standard C is operator overloading, so I understand.
Be careful what you wish for.

Operator overloading only makes sense if the programmer can define his own types for the operators to work on. That means having some way to define types, that is to say classes in C++ and other OOP languages. Which immediately pulls in a whole world of complexity.

Anyway that was my plan. I have only one class defined in my solution, the one that represents my big intgers. Only because I want to be able to write "result = a + b" instead of somthing like "sum(a, b, result)"

The idea being that it would be fairly trivial to take the resulting source and recreate it in C if one really wanted to.

Well... I should have stuck to my intuition from years gone by. C++ is a gigantic labarinth of complexity. As soon as you adopt even one little idea from C++ you get sucked into to the whole nightmare of it's machinations. A bottomless pit of dispair.

My current karatsuba multiplication looks like this:

Code: Select all

bint bint::mul (bint& a)
{
    // Ensure operands are same width.
    while (this->width > a.width)
    {
        a.grow();
    }
    while (a.width > this->width)
    {
        this->grow();
    }

    bint result(a.width * 2);

    // The base case, only one element in value, just do the multiply
    if (width == 1)
    {
        int64_t product = value[0] * a.value[0];
        if (product < BASE) {
            result.value[0] = product;
            result.value[1] = 0;
        }
        else
        {
            result.value[0] = (product % BASE);
            result.value[1] = (product / BASE);
        }
        return result; 
    }

    // Calculates the size of the numbers
    int m = (this->width);
    int m2 = m / 2;

    // Split the numbers in the middle
    bint high1 = this->high();
    bint low1 = this->low();
    bint high2 = a.high();
    bint low2 = a.low();
    
    // Do da karatsuba shuffle, yaba daba do !   
    bint z0 = low1 * low2;
    bint z2 = high1 * high2;
    bint s1 = low1 + high1;
    bint s2 = low2 + high2;
    bint z1 = s1 * s2;
    bint t1 = z1 - z2 - z0;
    bint t1Shifted = t1.shift1(m2);
    bint z2Shifted = z2.shift2(m);
    result = z2Shifted + t1Shifted + z0;
    return result; 
}
With another 300 lines of code behind the operator overloading of "+", "-", "*", "=" etc....

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

Re: Why Avoid BASIC on RPi?

Fri Dec 07, 2018 1:18 am

Heater wrote:
Thu Dec 06, 2018 11:28 pm
DavidS,
Well it is not really pleasing that you are doing it in C++, though if you can limit the OO stuff in your C++ I can forgive you.

The one thing I wish we had from C++ in standard C is operator overloading, so I understand.
Be careful what you wish for.

Operator overloading only makes sense if the programmer can define his own types for the operators to work on. That means having some way to define types, that is to say classes in C++ and other OOP languages. Which immediately pulls in a whole world of complexity.
Any definable types, do not need classes. It is done with some non-standard extensions by some C compilers that are only C compiler. Basically any user defined data type can be used for operator overloading in the C compilers that support it (thus a structure type, or a char array type [string] etc can be used with an operator overload).

So it does not require any classes. We already have user data types in C and that is all that is needed.
Anyway that was my plan. I have only one class defined in my solution, the one that represents my big intgers. Only because I want to be able to write "result = a + b" instead of somthing like "sum(a, b, result)"

The idea being that it would be fairly trivial to take the resulting source and recreate it in C if one really wanted to.

Well... I should have stuck to my intuition from years gone by. C++ is a gigantic labarinth of complexity. As soon as you adopt even one little idea from C++ you get sucked into to the whole nightmare of it's machinations. A bottomless pit of dispair.

My current karatsuba multiplication looks like this:

Code: Select all

bint bint::mul (bint& a)
{
    // Ensure operands are same width.
    while (this->width > a.width)
    {
        a.grow();
    }
    while (a.width > this->width)
    {
        this->grow();
    }

    bint result(a.width * 2);

    // The base case, only one element in value, just do the multiply
    if (width == 1)
    {
        int64_t product = value[0] * a.value[0];
        if (product < BASE) {
            result.value[0] = product;
            result.value[1] = 0;
        }
        else
        {
            result.value[0] = (product % BASE);
            result.value[1] = (product / BASE);
        }
        return result; 
    }

    // Calculates the size of the numbers
    int m = (this->width);
    int m2 = m / 2;

    // Split the numbers in the middle
    bint high1 = this->high();
    bint low1 = this->low();
    bint high2 = a.high();
    bint low2 = a.low();
    
    // Do da karatsuba shuffle, yaba daba do !   
    bint z0 = low1 * low2;
    bint z2 = high1 * high2;
    bint s1 = low1 + high1;
    bint s2 = low2 + high2;
    bint z1 = s1 * s2;
    bint t1 = z1 - z2 - z0;
    bint t1Shifted = t1.shift1(m2);
    bint z2Shifted = z2.shift2(m);
    result = z2Shifted + t1Shifted + z0;
    return result; 
}
With another 300 lines of code behind the operator overloading of "+", "-", "*", "=" etc....
Perhaps if you do operator overloading the old fasioned way (from when C++ was in its infancy), using an operator type function instead of a class method? May simplify life a little.

Interesting how far you fell into the C++ pit on this simple of a task, hmm.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Fri Dec 07, 2018 1:43 am

@Heater:
Operator overloading is doable in any language that supports user defined data types, including C. An example of how it is done in some C compilers that bend the rules a little (by allowing operator overloading) is below. Remember that we now have inline functions in C, and operator overloading was considered in the draft for C11 though did not make the cut.

Code: Select all

typedef struct {
  int x;
  int y;
  int col;
} PIX;

//Use + operator to translate one PIX by another.
PIX operator+(PIX *src, PIX *trans){
  PIX t;
  t.x = src->x + trans->x;
  t.y = src->y + trans->y;
}
I have used a few C compilers that allow this, and they were just C compilers with this being the only extra beyond what you would expect from a C compiler. Yes the example is a bit contrived.

Though you can do the exact same thing in C++, and it works (leave out the OO stuff completely).
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Fri Dec 07, 2018 2:17 am

DavidS,
Any definable types, do not need classes. It is done with some non-standard extensions by some C compilers ...
Well, if it is done with "non-standard extensions" then it is not C anumore now is it.
So it does not require any classes. We already have user data types in C and that is all that is needed.
Really? Please demonstrate how.

In the current problem we need to perform arithmetic on arbitrarily big integers, up to a million digits. We need to define operators on that number type, add, subtract, multiply...

So, firstly we need to be able to declare them in a similar way to regular variables in C, for example:

Code: Select all

bint x = 2;
bint y = 3;
bint r;
The we need to be able to do arithmetic on them in the same way we would with C variables, for example:

Code: Select all

r = x * y;
There is no way to do that in C. If you claim that there is then please show an example.
Perhaps if you do operator overloading the old fasioned way (from when C++ was in its infancy), using an operator type function instead of a class method? May simplify life a little.
Please show a simple example of what you mean. An example that we can compile and run with C++ at least as it has been since the first book on it was published by Stroustrap in 1985.
Interesting how far you fell into the C++ pit on this simple of a task
Like I say, if you have a better way to do it then please do show your working.

Return to “Off topic discussion”