timrowledge
Posts: 1345
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: Making readable modifyable code.

Sat Dec 10, 2016 7:38 pm

[quote="Heater"
Smalltalk has a bunch of that stuff just there, built in and working since forever. When you have objects with metadata instead of justplainstrings you can analyse more and better.
Can you give examples of such tools and how they are helpful ?[/quote]
Well the obvious in-your-face one is the code browser. Since classes know what methods they provide you can organise the view to show methods in their proper class. And the metadata about what category each method belongs allows further organisation. Obviously classes understand their place in the hierarchy and can handle being moved when refactored.
Of course, methods are proper objects too, and they know about what variables they use, so you can query what methods use certain variables. That's quite different to string searching dead text. you can find out if a method refers to 'super' and thus refines a method in a superclass. You can ask what class it belongs to, what messages get sent, how many temporary variables or arguments it uses. You can even ask for its source code, assuming the log file holding the plain text is connected. If not, you can ask it to disassemble and provide a reasonable pass at uncommented source. You can find out how much code a method has, both in terms of the textual version and the compiled version. You can even see the compiled version in the code browser if you really want.
You can build queries to find out all methods in classes descended from Foo that use a certain instance variable and send certain message, then browse the results. You can find all the methods implementing a message that have more than x versions known between two dates. That helps with our packages management tools for example.

A bigger and sneakier example is the about-to-be-released background code analyser and optimiser. Since we have all this data about the code - including ways of working out how often any of it is used - we can reason about it and decide whether, when and how to optimise.

Could you do this sort of thing with 'a text editor'? Well, I guess so as long as the editor could actually parse the entire relevant source repository and analyse it appropriately. Seems a lot easier to me to have that information always there, live, integrated into your working tools and intelligible.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

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

Re: Making readable modifyable code.

Sat Dec 10, 2016 8:18 pm

That all sounds great.

But I smell a rat:
...including ways of working out how often any of it is used - we can reason about it and decide whether, when and how to optimise.
As far as I can tell there is no way to know how often anything will be done at run time at compile time.

Or are you saying these optimizations happen at run time. Like they do in modern Javascript run times?
Last edited by Heater on Sun Dec 11, 2016 10:07 am, edited 1 time in total.
Memory in C++ is a leaky abstraction .

timrowledge
Posts: 1345
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: Making readable modifyable code.

Sat Dec 10, 2016 11:39 pm

Heater wrote:Or are you saying these optimizations happen at run time. Like they do in modern Javascript run times?
Similar. Though if I understand correctly (not guaranteed, I don't spend much time worrying about javascript) the JS stuff is all in their VM. The Sista project is almost all written in Smalltalk, running within the main system, though it takes advantage of some changes to the VM to provide useful data for it - like usage counts for basic blocks and so on. It looks likely to at least double performance in general.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

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

Re: Making readable modifyable code.

Sun Dec 11, 2016 1:30 am

timrowledge wrote:Phone? A pretty unusual one... iMac 27".
Do you get anything better at https://squeak.js.org ?
Mini Squeak loads and looks similar to the tiny window at the top of the other page. There is an icon with a keyboard at the bottom, but it doesn't work; therefore, it is impossible to type anything into the session. The EToys link starts loading and seems to make progress, but after about 10 minutes I became impatient and closed it. Your remark about the iMac makes me think you've never navigated a Smalltalk code repository using a web browser on a phone either.

The idea of running a Smalltalk system in a web browser seems similar to Browsix which is a POSIX compatible OS in the browser.

tufty
Posts: 1456
Joined: Sun Sep 11, 2011 2:32 pm

Re: Making readable modifyable code.

Sun Dec 11, 2016 7:35 am

Heater wrote:Can you give examples of such tools and how they are helpful ?
We're both in agreement, I think, that C++ code can be horribly unreadable, with the method definition you're looking for a million miles away somewhere else in something a thousand classes up the hierarchy. It's not a problem restricted to C++, but it's something complex C++ code is prone to, and it's a decent example.

In this case, a hyooge pile of fanfold printouts of the type we used to have when I was doing PL/1 is unlikely to be useful. Hell, they weren't always very useful even back then. One could consider the "live" equivalent of those fanfolds to be the use of `cat'. Using `cat` exclusively to investigate significant amounts of code gets old pretty damn fast.

So, instead of using `cat`, we might use `less`. At least that gives you rudimentary searching within the file, and forwards / backwards scrolling, which is perhaps closer to flicking through the fanfold backwards and forwards with a ruler. But even that's pretty grim for C++.

Getting a bit smarter, we might use `grep` to find potential files of interest, then `less` to investigate them. OK if you're trying to chase down a single, distinctively-named method definition, less OK if it's something like a faulty member initialisation somewhere down the hierarchy, or if you need to go diving down method chains.

So you start using an editor with a bit of language-specific smarts. Maybe `emacs` in c++-mode with speedbar enabled. Now things start getting easier (if "easier" is a word one can apply to emacs). You've got proper search, a certain amount of language smarts, in-project definition lists, perhaps the ability to go backwards and forwards through version control, that sort of thing.

Or you might use Microsoft's Visual Studio. It's apparently extremely good for C++, showing type annotations, links back to definitions, and the like. Never used it myself. Or something like Eclipse, which is a bit of a dog's dinner as far as I'm concerned, but does allow all sorts of refactoring.

You're getting towards something that's usable for C++. And yet you still haven't approached the power of the Smalltalk browser.

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

Re: Making readable modifyable code.

Sun Dec 11, 2016 10:56 am

@timrowledge,

Javascript is intended to be thrown accross the net, as source code, and be run on some unknown machine of unknown architecture. As such it's not really possible to do any optimizing up front.

I know very little of the internals of JS run times but yes they do just-in-time compilation and will optimize the code they generate at run time. Perhaps more importantly they will deoptimize things. For example a function that takes numbers as parameters may have those operations streamlined, but JS is a dynamic language so nothing stops you passing in a string at some point during execution, boom, wrong type all that nice arithmetic code has to be ripped out.

I will wager that a modern JS engine is faster than any Smalltalk :)

@tufty,

Yes, we agree. C++ code can be horrible to read. I'm all in favor of editors and tools that can help one navigate source code. Find syntax errors, undefined symbols, etc, etc.

I'm just not sold on marrying the editor, tools, run time all into a single thing. Especially if you need the the thing to run the code and edit it in any easy way.

@ejolson. On syntax highlighting: Took me a long while to get into syntax highlighting. Now I love it for two major reasons: 1) It allows one to fade into the background the generally useless and misleading comments in the source. So you don't get distracted from what the code actually does. 2) It clearly shows up long and complex strings as separate from the code. Other goodies like highlighting matching braces or syntax errors are a bonus.

Of course some syntax highlighters can make it look as if the cat threw up on the source.
Memory in C++ is a leaky abstraction .

User avatar
PeterO
Posts: 5820
Joined: Sun Jul 22, 2012 4:14 pm

Re: Making readable modifyable code.

Sun Dec 11, 2016 4:20 pm

As a counter example.... Here's some code I've written for a 1960 British computer called an Elliott 803....

Code: Select all

:SETR(MAIN,COPY,SCAN,SHOW,CLR,BIRH3)
:SETS(A1024,B1024,X1,Y1,C4)

:LIST
C
31
992
1
32
10
*

:DEFI(COPY)
0£O
:DO(1024)
BO£AO
1:ON(O)
:REPE
:EXIT
:CLOS


:DEFI(SHOW)

0£O
$74     27:00      0)
:DO(32)
$74     29:74     30)
:DO(32)
$
00      O/30      A
46     2,:74      3
40     3,:74     28
00      O/26      B
22      O:00      0
)
:REPE
:REPE


:EXIT
:CLOS


:DEFI(BIRH)
0£O
:DO(1024)
$
00       O/30       B
03      C0:20      O1
00      O1/40      3,
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (2):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (2):00       0
40     (2):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
40     (1):00       0
)

1)
0£AO
:GOTO(3)

2)
1£AO
:GOTO(3)

3)
1:ON(O)
:REPE

:EXIT
:CLOS

:DEFI(SCAN)
0£O

:DO(32)
:DO(32)

:IF(AO)NOT ZERO:THEN
$
30      O:03      C0
20      X:30       O
03     C1:20       Y
30     C4:00       0
00      O/24       B
30      X:04      C2
03      C:04       Y
20     O1/22       B
30      X:05      C2
03      C:04       Y
20     O1/22       B
30      Y:04      C3
03     C1:20      Y1
30      X:04      Y1
20     O1/22       B
30      X:04      C2
03      C:04      Y1
20     O1/22       B
30      X:05      C2
03      C:04      Y1
20     O1/22       B
30      Y:05      C3
03     C1:20      Y1
30      X:04      Y1
20     O1/22       B
30      X:04      C2
03      C:04      Y1
20     O1/22       B
30      X:05      C2
03      C:04      Y1
20     O1/22       B
)
:,
1:ON(O)

:REPE

:REPE

:EXIT
:CLOS

:DEFI(CLR)
0£O
:DO(1024)
0£AO£BO
1:ON(O)
:REPE


:EXIT
:CLOS



:DEFI(MAIN)

:CLR
1£A0£A31
1£A992£A1023
1£A600£A601£A633£A634£A665

:LOOP
:SHOW
:SCAN
:BIRH
:REPE

:STOP
:CLOS

:STAR(0,MAIN)
::
Perfectly readable :-)
PeterO
Discoverer of the PI2 XENON DEATH FLASH!
Interests: C,Python,PIC,Electronics,Ham Radio (G0DZB),1960s British Computers.
"The primary requirement (as we've always seen in your examples) is that the code is readable. " Dougie Lawson

timrowledge
Posts: 1345
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: Making readable modifyable code.

Sun Dec 11, 2016 6:35 pm

Heater wrote:@timrowledge,

Javascript is intended to be thrown accross the net, as source code, and be run on some unknown machine of unknown architecture. As such it's not really possible to do any optimizing up front.
Indeed - and like so many things about JS it's copied from Smalltalk. Smalltalk has been doing the portability thing since before there was Ethernet, and since that was invented in the same group as Smalltalk they got earlier experience than most.
Heater wrote:I know very little of the internals of JS run times but yes they do just-in-time compilation and will optimize the code they generate at run time. Perhaps more importantly they will deoptimize things. For example a function that takes numbers as parameters may have those operations streamlined, but JS is a dynamic language so nothing stops you passing in a string at some point during execution, boom, wrong type all that nice arithmetic code has to be ripped out.
Err, yes, just like Smalltalk. Dynamic compilation was invented by an old friend and colleague of mine (see "Efficient implementation of the smalltalk-80 system", L.Peter Deutsch & Allan M. Schiffman, POPL '84 Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages) back in 1984.
Heater wrote:I will wager that a modern JS engine is faster than any Smalltalk :)
I wouldn't consider that a safe bet in either direction. JS VMs like the Google V*8 have large teams of very clever people (quite a few of them with experience in Smalltalk VMs) but the Smalltalk world - specifically Squeak - has people like Eliot Miranda, Dan Ingalls, Bert Freudenberg, Clement Bera, Craig Latta - oh and me. We've been doing this a while and we're quite good at it, all in all.
Heater wrote:I'm just not sold on marrying the editor, tools, run time all into a single thing. Especially if you need the the thing to run the code and edit it in any easy way.
You need a way to edit code, whether that is by typing characters, dictating, waving hands in runic patterns or dragging blocks on a screen. You need a tool to take the representation and convert it to a form that can actually be executed. A tool to enable debugging tends to be useful. Tools to keep versions of thecae as you develop and try ideas are good.
I'm not sure I see a great deal of difference between having a single thing like a Smalltalk image with all that included and a single thing like a unix system with all that included. The biggest difference I can see is that the typical unix way doesn't keep any persistent context of where you got to and certainly can't provide platform portability even in the middle of debugging.

But as I've said before, some people love it, some people don't. Some people like old cars, some can't understand the appeal. Some like to woodwork with hand tools, some like power tools.

I think it's worth taking a decent look at things you haven't tried to see it you like them.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

timrowledge
Posts: 1345
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: Making readable modifyable code.

Sun Dec 11, 2016 6:45 pm

ejolson wrote:Your remark about the iMac makes me think you've never navigated a Smalltalk code repository using a web browser on a phone either.
I'm pretty sure that is correct. I *have* run Squeak on an iPhone, many years ago. Probably an early iPhone 3 I think. It wasn't fast (predates the dynamic translation ARM VM for Squeak) and the screen size made it hard to see, but it did work. Unfortunately the iOS rules prevent it from being a 'proper' application as a general system but there are a couple of iPhone apps that are actually written in Squeak. No, I haven't tried any Android version. I know there are people working on one but I have no interest at all in using Android.
ejolson wrote:The idea of running a Smalltalk system in a web browser seems similar to Browsix which is a POSIX compatible OS in the browser.
Well maybe. Not my area of expertise.

The current Squeak-in-a-browser state is basically that you can run the JS written VM with pretty much any image, and you can stay that way or request a download you your local machine in order to run the full CogVM, which is many times faster.
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

jahboater
Posts: 5632
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Making readable modifyable code.

Sun Dec 11, 2016 8:46 pm

Interesting discussion.
timrowledge wrote:
Heater wrote:I will wager that a modern JS engine is faster than any Smalltalk :)
I wouldn't consider that a safe bet in either direction.
Here is the collatz conjecture code from an old thread, tidied up a bit.
The algorithm is trivial so it should be simple to translate into either language.
Perhaps we can see which is really the fastest?

Code: Select all

#include <stdio.h>
#include <inttypes.h>

int
main( void )
{
  int maxsteps = 0;
  int64_t maxval = 0;

  for( int64_t x = 1; x < 10000000; ++x )
  {
    int steps = 0;
    int64_t n = x;

    while( n > 1 )
    {
      if( n & 1 )
        n = 3 * n + 1;
      else
        n /= 2;
      ++steps;
    }

    if( steps > maxsteps )
    {
      maxsteps = steps;
      maxval = x;
    }
  }

  printf( "max %" PRId64 " steps %d\n", maxval, maxsteps );
}
The C version, on a Pi3 at stock speed:

Code: Select all

pi@raspberrypi:~ $ cc -O3 -s -Wextra -Wall -Wconversion collatz.c -o collatz
pi@raspberrypi:~ $ ls -l collatz
-rwxr-xr-x 1 pi pi 3164 Dec 11 20:40 collatz
pi@raspberrypi:~ $ time ./collatz
max 8400511 steps 685

real	0m14.197s
user	0m14.190s
sys	 0m0.000s
Faster when running in 64-bit mode:

tufty
Posts: 1456
Joined: Sun Sep 11, 2011 2:32 pm

Re: Making readable modifyable code.

Mon Dec 12, 2016 6:40 am

I'm wary of benchmarks as a way to measure anything other than the speed of a system when executing that benchmark.

jahboater
Posts: 5632
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Making readable modifyable code.

Mon Dec 12, 2016 9:23 am

tufty wrote:I'm wary of benchmarks as a way to measure anything other than the speed of a system when executing that benchmark.
Well we have a standard platform, the Pi. Hopefully all Pi's with the same config.txt and no other load, will produce reasonably consistent times, at least consistent enough to compare two languages.

How else can you compare the speed of two languages other than with an identical program on the same platform?

Collatz is simple enough that its trivial to implement in any sensible language, and yet not so simple that it all gets optimized out - and it takes a decent amount of time to execute. Its not constrained by memory.

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

Re: Making readable modifyable code.

Mon Dec 12, 2016 11:17 am

For sure one has to be wary of benchmarks. No single benchmark is going to be a sound indicator of whether any language, compiler, OS, machine, etc, is suitable for the application(s) one has to actually create. This should be obvious enough.

The collatz example presented only tests integer arithmetic and simple loop/ conditional handling. So it may be a good indicator of how C, the compiler in use and the machine it runs on can do numeric calculations. It says nothing about the efficiency of function calling, recursion, string handling, array lookup, pointer dereferencing, network/file I/O, threading etc, etc.

Still, such benchmarks are a bit of fun and can be useful indicators of something if you are aware of what that something is.

As such I'd like to propose we make some modifications to the collatz program so as to make it test more language features, whilst at the same time keeping it very simple. For example:

1) Make the generation of numbers to be tested a function that does nothing else but generate that sequence of numbers, for each number to be tested it calls a function to do the actual odd/even test. The begin, end range of the numbers to test, and the function to do the test being passed in as parameters. This adds some testing of function call efficiency.

2) Similarly make the test for greater than maxval an other separate function.

3) Add memoization to the thing. As it stands the thing does a full test on every number. Of course whilst doing that it hits numbers that have already been tested and found to result in reaching one. If we remembered those numbers we could save doing a lot of testing. Such memoization would start to test array lookup (Or whatever it is that is used to store the memo). It should also speed up the algorithm anyway. The memoization thing would of course be in another separate function.

4) Perhaps the memoization thing should store all tested numbers as strings rather than integers.

I think the Smalltalk guys would like this approach. As far as I can tell they really like to separate out every little bit of functionality into a tiny method. I have even heard a Smalltalk guru sugest that no method should be longer than 3 lines !

5) To be really wicked we should insist that this algorithm handle integers of arbitrary size, not just limited to 64 bits. That would separate the men from the boy! (I don't really want to do this)
Memory in C++ is a leaky abstraction .

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

Re: Making readable modifyable code.

Mon Dec 12, 2016 2:49 pm

Hey, we had this conversation before...

My old Javascript collatz does this in about 3.6 seconds! viewtopic.php?p=1026522#p1026522

That is the memoized version. Even the unmemoized version does it in 44.9 seconds, only about 3 times slower than your C code! Not bad.

Code: Select all

'use strict';

var maxsteps = 0;
var maxval = 0;
var s = [];
var x = 1;
var n;
var steps;
s[x] = 0;  // initialize for x=1

while (x < 10000000) {
    steps = 0;
    n = x;
    while (n > 1) {
        if (n & 1)
            n = 3*n + 1;
        else
            n = n / 2;
        steps += 1;
    }
    if (steps > maxsteps) {
        maxsteps = steps;
        maxval = x;
    }
    x += 1;
}
console.log ("max ", maxval, " steps ", maxsteps);
Memory in C++ is a leaky abstraction .

jahboater
Posts: 5632
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Making readable modifyable code.

Mon Dec 12, 2016 3:22 pm

Here is a very crude "functionized" version, your steps 1 and 2.
Execution time is still 14.8 secs in C because they all get inlined into the single main function again and then optimized as before.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <inttypes.h>
#include <stdbool.h>

static int64_t test_number;
static int maxsteps = 0;
static int64_t maxval = 0;

static int64_t
next_number( void )
{
  return ++test_number;
}

static bool
odd( const int64_t n )
{
  return n & 1;
}

static void
check_max( const int64_t test_val, const int steps )
{
  if( steps > maxsteps )
  {
    maxsteps = steps;
    maxval = test_val;
  }
}

static int
test( int64_t n )
{
  int steps = 0;

  while( n > 1 )
  {
    if( odd(n) )
      n = 3 * n + 1;
    else
      n = n / 2;
    ++steps;
  }

  return steps;
}

static void
collatz( const int64_t start, const int64_t limit, int (*const try)(int64_t) )
{
  int64_t x;
  test_number = start - 1;

  while( (x = next_number()) <= limit )
    check_max( x, try(x) );
}

int
main( const int argc, const char *argv[] )
{
  char *tail;
  errno = 0;

  if( argc < 3 )
  {
    fprintf( stderr, "Test start and end missing\n" );
    return EXIT_FAILURE;
  }

    // set start value
  const int64_t test_start = strtoll( argv[1], &tail, 0 );
  if( tail == argv[1] || errno == ERANGE )
  {
    fprintf( stderr, "Test start invalid\n" );
    return EXIT_FAILURE;
  }

    // set end value
  const int64_t test_end = strtoll( argv[2], &tail, 0 );
  if( tail == argv[2] || errno == ERANGE || test_start > test_end )
  {
    fprintf( stderr, "Test end invalid\n" );
    return EXIT_FAILURE;
  }

  collatz( test_start, test_end, test );

  printf( "max %" PRId64 " steps %d\n", maxval, maxsteps );

  return EXIT_SUCCESS;
}
Last edited by jahboater on Mon Dec 12, 2016 3:25 pm, edited 1 time in total.

jahboater
Posts: 5632
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Making readable modifyable code.

Mon Dec 12, 2016 3:24 pm

Heater wrote: That is the memoized version. Even the unmemoized version does it in 44.9 seconds, only about 3 times slower than your C code! Not bad.
Yes, that's very fast indeed. Python is way slower than that.

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

Re: Making readable modifyable code.

Mon Dec 12, 2016 4:20 pm

jahboater wrote:Here is a very crude "functionized" version, your steps 1 and 2.
From a code readability point of view the function-ized version scores much lower than the original version. In my opinion, if adding function calls makes the code more verbose this reduces readability. Benchmarks should perform a definite task and seek the most efficient solution within the constraints agreed upon. In this case, the problem is well defined and the constraint is using a particular programming language on the Pi 3, presumably cooled so it doesn't throttle.

The fact that the maximum value is only 8400511 and that the Pi 3 is running in 32-bit mode makes me wonder why 64-bit integers are used.

User avatar
gordon@drogon.net
Posts: 2020
Joined: Tue Feb 07, 2012 2:14 pm
Location: Devon, UK
Contact: Website

Re: Making readable modifyable code.

Mon Dec 12, 2016 4:38 pm

ejolson wrote: The fact that the maximum value is only 8400511 and that the Pi 3 is running in 32-bit mode makes me wonder why 64-bit integers are used.
I wondered that myself, and coded a 32-bit int version when playing with it earlier and found that the | multiply by 3, add 1 | divide by 2 | cycle overflows a 32-bit integer with sufficiently large values of the loop iteration counter (x). I did an experiment in my RTB just for "lol's" ... It only has 64-bit doubles though, so was considerably slower, but it was an interesting exercise. I have a few little "benchmark" things I use when trying to tune the interpreter...

Code: Select all

maxsteps = 0
maxval = 0

start = time

for x = 1 to 1000000 cycle
  steps = 0
  n = x

  while n > 1 cycle
    if n & 1 then
      n = 3 * n + 1
    else
      n = int (n / 2)
    endif
    steps = steps + 1
  repeat

  if steps > maxsteps then
    maxsteps = steps
    maxval = x
  endif

repeat

et = time
print "Time taken: "; (et - start) / 1000
print "max: "; maxval; ", steps: "; maxsteps
end
It's sufficiently slow to be boring. About 30x slower than C

-Gordon
--
Gordons projects: https://projects.drogon.net/

jahboater
Posts: 5632
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Making readable modifyable code.

Mon Dec 12, 2016 4:57 pm

ejolson wrote:
jahboater wrote:Here is a very crude "functionized" version, your steps 1 and 2.
From a code readability point of view the function-ized version scores much lower than the original version. In my opinion, if adding function calls makes the code more verbose this reduces readability.
Totally agree. All the functions were just there as Heater suggested to test function call overhead in the two languages. The simple version in the first post is clearly far far more readable. We have wandered off-topic rather!
Last edited by jahboater on Mon Dec 12, 2016 5:34 pm, edited 1 time in total.

jahboater
Posts: 5632
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Making readable modifyable code.

Mon Dec 12, 2016 5:16 pm

gordon@drogon.net wrote:
ejolson wrote: The fact that the maximum value is only 8400511 and that the Pi 3 is running in 32-bit mode makes me wonder why 64-bit integers are used.
I wondered that myself, and coded a 32-bit int version when playing with it earlier and found that the | multiply by 3, add 1 | divide by 2 | cycle overflows a 32-bit integer with sufficiently large values of the loop iteration counter (x).
Yes, you are right, only "n" need be 64-bit

Code: Select all

#include <stdio.h>
#include <inttypes.h>

int
main( void )
{
  int maxsteps = 0, maxval = 0;

  for( int x = 1; x < 10000000; ++x )
  {
    int steps = 0;
    int64_t n = x;

    while( n > 1 )
    {
      if( n & 1 )
        n = 3 * n + 1;
      else
        n /= 2;
      ++steps;
    }

    if( steps > maxsteps )
    {
      maxsteps = steps;
      maxval = x;
    }
  }

  printf( "max %d steps %d\n", maxval, maxsteps );
}

User avatar
gordon@drogon.net
Posts: 2020
Joined: Tue Feb 07, 2012 2:14 pm
Location: Devon, UK
Contact: Website

Re: Making readable modifyable code.

Mon Dec 12, 2016 8:14 pm

Heater wrote:For sure one has to be wary of benchmarks. No single benchmark is going to be a sound indicator of whether any language, compiler, OS, machine, etc, is suitable for the application(s) one has to actually create. This should be obvious enough.

The collatz example presented only tests integer arithmetic and simple loop/ conditional handling. So it may be a good indicator of how C, the compiler in use and the machine it runs on can do numeric calculations. It says nothing about the efficiency of function calling, recursion, string handling, array lookup, pointer dereferencing, network/file I/O, threading etc, etc.

Still, such benchmarks are a bit of fun and can be useful indicators of something if you are aware of what that something is.

As such I'd like to propose we make some modifications to the collatz program so as to make it test more language features, whilst at the same time keeping it very simple. For example:
Just pointing out Roy Longbottoms site here and the work he's spent a lifetime on benchmarks - e.g. http://www.roylongbottom.org.uk/Raspber ... hmarks.htm

Linpack and Whetstone, etc. are designed to demonstrate real-life scenarios - mostly aimed at the scientific community though but they're very well established and useful for, well, a benchmark...

One I like that may be more applicable to some systems is the Ackerman function - this really is more a system/compiler recursion stress test than anything in real life though. Here is a C version:

Code: Select all

#include <stdio.h>

double ackermann (double m, double n)
{
  if (m == 0.0)
    return n + 1.0 ;

  if (n == 0.0)
    return ackermann (m -1.0, 1.0) ;

  return ackermann (m - 1.0, ackermann (m, n - 1.0)) ;
}


int main ()
{
  double x, y, z ;

    for (y = 0.0 ; y < 4.0 ; ++y)
    {
      for (x = 0.0 ; x < 10.0 ; ++x)
      {
	z = ackermann (y, x) ;
	printf ("%5d", (int)z) ; fflush (stdout) ;
      }
      printf ("\n") ;
    }

  printf ("Done\n") ;
  return 0 ;
}
This version using doubles - as my RTB doesn't have integer only support and I like to compare it against a sort of equivalent C version. It works just fine with int32's - well up to the limits in that program. Don't try to take y above 3 ...

-Gordon
--
Gordons projects: https://projects.drogon.net/

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

Re: Making readable modifyable code.

Mon Dec 12, 2016 8:24 pm

ejolson,
The fact that the maximum value is only 8400511 and that the Pi 3 is running in 32-bit mode makes me wonder why 64-bit integers are used.
Let's turn this question around.

If you had never seen the Collatz algorithm before, if you had never seen any program run it, then..

1) How would you know how many steps it takes for the iterations to get down to 1? Perhaps it gets into a loop and runs forever. Perhaps it just runs forever as N goes to infinity.

2) How do you know how big N gets? Perhaps it runs away to 10^100 or whatever before dropping back to 1.

If you can answer those questions there is probably a Field's Medal waiting for you (If you are not over 40 years old).

Looked at this way I would say the program as presented is buggy. It does not check for overflow of anything. It presumes you know what will happen before you start!
Memory in C++ is a leaky abstraction .

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

Re: Making readable modifyable code.

Mon Dec 12, 2016 10:20 pm

Heater wrote: Let's turn this question around.

If you had never seen the Collatz algorithm before, if you had never seen any program run it, then..

1) How would you know how many steps it takes for the iterations to get down to 1? Perhaps it gets into a loop and runs forever. Perhaps it just runs forever as N goes to infinity.

2) How do you know how big N gets? Perhaps it runs away to 10^100 or whatever before dropping back to 1.

If you can answer those questions there is probably a Field's Medal waiting for you (If you are not over 40 years old).
It seems I am familiar with the algorithm but was mislead with the variable named "maxval" not actually referring to the maximum value of anything. In particular, it is apparently not the maximum value of n encountered during the run. From a code readability point of view, giving this variable a different name would help.

timrowledge
Posts: 1345
Joined: Mon Oct 29, 2012 8:12 pm
Location: Vancouver Island
Contact: Website

Re: Making readable modifyable code.

Mon Dec 12, 2016 10:44 pm

jahboater wrote:[Collatz is simple enough that its trivial to implement in any sensible language, and yet not so simple that it all gets optimized out - and it takes a decent amount of time to execute. Its not constrained by memory.
And that makes it almost completely useless as a meaningful benchmark. Anything 'trivial' is, well, trivial.

If you want an interesting but still trivial test how about something that actually goes a little beyond 32 int integers

Code: Select all

10000 factorial asString size
That is
work out the *exact* value of 10,000 factorial - no wimping out to floating point
convert to a string - one you could print out
find the size of said string
print that value.

That's 35660 digits long and takes 570 mS on my Pi3. Simply working out the exact value take ~300 mS. I'd post the answer here but it is after all 34Kb long...
Making Smalltalk on ARM since 1986; making your Scratch better since 2012

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

Re: Making readable modifyable code.

Mon Dec 12, 2016 10:47 pm

No, memoization is nothing to do with dynamic programming. It is a technique that can be used any any programming system.

Consider:

You write a function to calculate factorials. You know: 5! = 5 * 4 * 3 * 2 * 1, for example.

As your program is run perhaps that function is called to calculate the factorial of 5. So it does all of the above multiplications.

Later it might be called to calculate the factorial of 6.

What to do?

Do all that multiplication again: 6 * 5 * 4 * 3 * 2 * 1 ?

Or, having remembered the result of factorial 5 just calculate 6 * factorial5.

Boom, by remembering what you did before, what you are asked to do later is much faster.

As you see this is a huge speed boost in the collatz problem as given.

We could calling it "caching ". It's a trade off between speed and memory consumption.
Memory in C++ is a leaky abstraction .

Return to “General programming discussion”