RISC OS; Pros and Cons

A quickly hacked out version of this takes 1.7sec on Squeak on my pi.

At 1.7 seconds.. considerably faster. I wonder why.. is that compiled or interpreted Tim?

... and could you compare that Squeak program running on both RISC OS and Linux?

A quickly hacked out version of this takes 1.7sec on Squeak on my pi.

At 1.7 seconds.. considerably faster. I wonder why.. is that compiled or interpreted Tim?

A bit of adjustment to the BASIC leads to about the same time:

Code: Select all

DEFFNa(m%,n%)
 IF m% ELSE =n%+1
 IF n% ELSE =FNa(m%-1,1)
=FNa(m%-1,FNa(m%,n%-1)

It is possible to squeeze a tiny bit more with a slightly lengthier function.
However, this an extremely poor test for many reasons, not least that the Ackermann function is very simply calculated for any parameters that will actually be useable on a micro-computer:

Code: Select all

DEFFNa(m%,n%)
 CASE m% OF
 WHEN 0:=n%+1
 WHEN 1:=n%+2
 WHEN 2:=2*n%+3
 WHEN 3:=2^(n%+3)-3
 WHEN 4:j%=2:FOR i%=0 TO n%:j%=2^j%:NEXT i%:=j%-3
 ENDCASE
=n%

This fails at (4,3), but used in the original example it is almost instant. KISS - it's the algorithm, not the language.

At 1.7 seconds.. considerably faster. I wonder why.. is that compiled or interpreted Tim?

Squeak is a fairly simple Smalltalk Virtual Machine system; the Smalltalk code is compiled into bytecodes which are kept in nice neat objects within the system, where you can do Interesting Things with them; like decompiling, for example.
I wrote a section of a fairly popular book explaining how it works underneath that - you can buy it from http://www.amazon.com/Squeak-Open-Personal-Computing-Multimedia/dp/0130280917 or read just my section's PDF from http://www.rowledge.org/resources/tim's-Home-page/Squeak/OE-Tour.pdf

Very basically, the stream of byte codes is interpreted one-by-one and bits are pushed and popped, messages are sent (not much like procedure calls but serving a similar need) and results returned. There is a newer version of the Squeak virtual machine that I will be working on getting working on ARM soon that takes those byte codes and translates them to machine code and does some runtime optimisation; on intel Macs it roughly pen tuples compute bound performance. Obviously I/O tends to be bound by memory bandwidth more than anything. Yes, this is a bit like java. Smalltalk has been doing it since 1970, and dynamic translation since '84. (See http://webpages.charter.net/allanms/popl84.pdf for the original paper)

Perhaps the most interesting thing about this Ackermann example is that the Smalltalk capability of handling arbitrarily large integers means you can go a bit further than typical languages. Likewise with factorial, always a fun example. If you use unsigned 32bit ints you can just get away with calculating 12! Doing that in Squeak 1000 times over takes 17mSec.

Now try 45! - which is 119622220865480194561963161495657715064383733760000000000, by the way - that takes 872mSecs for the 1000 times around.

The problem with the Ackermann algorithm is that it tests recursion, this has always been one of the shortcomings of 99% of BASIC interpreters, due to the way they pass parameters to functions/procedures. Hence the other tests that I suggested, these will speak to the standard libraries of BASIC as well as how efficient it is at making system calls. As to a good all around benchmark of an interpreted programming language, due to the differences in languages I do not think that there is one.

The problem with the Ackermann algorithm is that it tests recursion, this has always been one of the shortcomings of 99% of BASIC interpreters, due to the way they pass parameters to functions/procedures. Hence the other tests that I suggested, these will speak to the standard libraries of BASIC as well as how efficient it is at making system calls. As to a good all around benchmark of an interpreted programming language, due to the differences in languages I do not think that there is one.

In the real world BASIC could be asked to something recursive (like Ackermann), so it's as valid a test as any other (we can't always just use algorithms that suit BASIC can we ?). I'd have problems with something like Ackermann being the only test though - so your "shot gun" approach to benchmarking is probably best.

I vaguely recall (in dim distant times when I had more hair...) that some compilers could "spot" common benchmark patterns and optimise for them (can't remember the details though...) - which sort of negated the point in doing the benchmarks in the first case so sometimes some truly random concocted tests can be more valuable !

The real problem with benchmarks is deciding upon meaningful ones. It's startlingly hard and even harder to really pull out any useful information from them.

Trivia like ackermanns, fibonaccis, sieves, dhrystones etc are all about as useful as relying on Clarkson grin-width when flooring the accelerator. Even something seemingly more meaningful like "open a text window, fake-type the Hamlet soliloquy, fake-select the middle 100 words and replace with the Gettysberg address, delete 10 characters from the beginning, middle and end, then search from the start for 'score', replace with '20', save the file" has complications. Does the fake-typing really characterise the work done when a person types; should it be 'typed in' as fast as the system can take it, or with a timed key press profile that reasonably matches a typical user. What is a typical user's typing like? What if only 1 other window is open? How about a hundred? Only one window of this app under test? Or 100?

And then after you've done all this careful work you have people demanding a single number that defines the performance. Insane. As stupid as buying a car based on 0-60 times.

In the real world BASIC could be asked to something recursive (like Ackermann), so it's as valid a test as any other (we can't always just use algorithms that suit BASIC can we ?).

Yes, we can, and should, when they do the same thing.
Recursion is a concise and valuable technique, but it is not common, especially the deep recursion of the Ackermann, which eats up memory. Iteration is usually much faster. Ackermann can be fully realised by iteration, but this does only the tail part, which is fairly transparent, and recognises that n% does not need to be recursed:

Code: Select all

DEFFNa(m%,n%)
 PROCa(m%)
=n%
DEFPROCa(m%)
 WHILE m%
  IF n% THEN n%-=1:PROCa(m%) ELSE n%=1
  m%-=1
 ENDWHILE
 n%+=1
ENDPROC


This goes in 1.2 seconds. Interestingly, implementing a fully iterated solution slows thing right down again. Always the algorithm first, then other speed enhancements.

[rurwin]

The Laws of Optimisation:

1. Don't do it.
2. (For experts only) Don't do it now.

There are cases where recursion is the right solution. For example, I have a situation where I have to read a set of data and put it into an array of structures. I don't know how many data there are, and the only way to find out is to read them. The iterative solution is complex with a lot of alloc and reallocs which take time, copy a lot of data about, are difficult to debug and will probably allocate too much space. The recursive solution recurses through the data. When it reaches the last element it allocates the array and then unwinds, filling in each element in turn. It's short, easy to debug, and probably more efficient than the alternative.

Indeed. I said "Recursion is a concise and valuable technique"
In your example I assume you were programming in C. Is it possible that the compiler reconizes the tail recursion and compiles as an iteration? That is the best of both worlds - clear code and optimised performance. We cannot do that in BASIC, so recursion needs to be used with due regard for the penalties.

And recursion is rarely (if ever) as deep as the Ackermann algorithm. This algorithm is all about its implementation as a recursive algorithm. Recursion is very useful, especially if you need to hack together a quick and dirty compiler, and it needs to be correct to the language. I have done this more times than I care to think about, and I have traced the level of recursion that is reached, and the worst case scenario that I have found possible (though never actually seen) is with a ANSI C compiler (fallowing the rules strictly [including 256 operators per sub expression, 256 sub expressions per expression, 255 parameters, 256 levels of embedded scope, etc]) was 1677216 levels deep recursion. And the most i have ever seen in practice is 14788 levels deep, neither of these comes anywhere near the Ackermann depth for recursion.

There are cases where recursion is the right solution.

Operations on trees always spring to mind Coming back to the original point that started all of this, I still haven't seen any numbers that suggest/prove that ROS as an operating system has a hand in making interpreted languages run faster.

And recursion is rarely (if ever) as deep as the Ackermann algorithm.

You don't program in Lisp, do you?

David S said
Recursion is very useful

pygmy_giant said:

David S said
Recursion is very useful

[pygmy_giant said:

pygmy_giant said:

David S said
Recursion is very useful

pygmy_giant said:

pygmy_giant said:

pygmy_giant said:

David S said
Recursion is very useful

But its also really annoying when done uneccessarily with forum posts!

I last used it to display a long message on a small LCD screen - I wrote a C function to display the first chunk of a passed text string that could fit on the screen, wait for a delay, then call itself again passing on the remainder of that chunk and the time delay. The condition to detect when to stop re-occuring was when there was no message left to display - magic. Saved me so many lines of unneccessary confusing code. I first tried to do this without recursion and tied myself in knots!

I always used a bubble sort to get a good idea of real world performance.
Generate 1000 random number, bubble sort, then print out with timings.
I used to give this to my students to do, of course they first had to find out what a bubble sort was, then flow chart it and code it. Also a good test of a students ability to learn how to optimise code when their mates was running twice as fast. All very RPi.

If anyone is using a bubble sort in the real world, they want a kick up the rear.

If anyone is using a bubble sort in the real world, they want a kick up the rear.

Yes, true, but having students investigate the Bubble Sort (a somewhat simpler proposition than -say- Quicksort or Heap Sort) is still a useful exercise IMHO.

They learn how to study a sorting algorithm and (in addition) mess around with one with a stunningly poor performance O(n2) - so they'll soon find that it's useless with anything other than trivially short lists.

University courses also cover Bubble Sort as well as the other varieties although they know full well no-one is going to employ it "for real" but rather because it has a pedagogical value.

Thanks for Ackermann 's because I'd never even heard of it. What puzzles me most about it is why DavidS's raspi significantly outperforms mine when Ackermanning. Are you sneakily underclocking something DavidS? S'bliddy clever!

Ackermann's as benchmark reflects stack efficacy? Riscos performs how well in that respect to other OS? It does seem best though, in programming terms, to curb recursion when possible.

My rather daft little benchmark does return something very useful when creating high performance code - a measure of how much time code takes to iterate. With that in place one can easily test optimizations against original code - else how does one know? Not that I am capable of creating any high performance code alas and it's great to know that I'm actually communicating with those who are and are working on RiscOSPi. 8)

... What puzzles me most about it is why DavidS's raspi significantly outperforms mine when Ackermanning. Are you sneakily underclocking something DavidS? S'bliddy clever!

Depends very much on what you're doing! Which version, in what language, on what OS?

If anyone is using a bubble sort in the real world, they want a kick up the rear.

Yes, true, but having students investigate the Bubble Sort ... is still a useful exercise IMHO ... they'll soon find that it's useless ...

Oh, absolutely. However, my comment was in response to the following, which made me :shock: (my emphasis)

I always used a bubble sort to get a good idea of real world performance.

If anyone is using a bubble sort in the real world, they want a kick up the rear.

Yes, true, but having students investigate the Bubble Sort ... is still a useful exercise IMHO ... they'll soon find that it's useless ...

Oh, absolutely. However, my comment was in response to the following, which made me (my emphasis)

I always used a bubble sort to get a good idea of real world performance.

Sorry Tufty when read like that I can understand your surprise.

Thanks for Ackermann 's because I'd never even heard of it. What puzzles me most about it is why DavidS's raspi significantly outperforms mine when Ackermanning. Are you sneakily underclocking something DavidS? S'bliddy clever!

Ackermann's as benchmark reflects stack efficacy? Riscos performs how well in that respect to other OS? It does seem best though, in programming terms, to curb recursion when possible.

You do have me curious, I am going have to look at the source for BBC BASIC V and see what is making this difference. My RPi is running withe the ARM at 600MHz, and SDRAM at 500MHz. I do not see how the SDRAM speed could make that much of a difference for this though maybe so, I have tried it with the ARM at 550MHz with the same exact results.