Digital C code gen

Anything QL Software or Programming Related.
User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Digital C code gen

Post by bwinkel67 »

Been playing around with Digital C 'SE' to see how well it does code generation. Already known of a few cases where it isn't optimal:
  • the while loop in same form as for loop generates smaller code: i.e. for (i=0; i<10; i++) { } not same code size as i=0; while (i<10) { i++; }
  • a boolean expression with only &&'s is better expressed with consecutive if's: i.e. if (a==10 && b==10) not same code size as if (a==10) if (b==10)
  • array indexing is not very efficient - better to sometimes use pointer arithmetic
Interestingly I did find a case where the code generated seems to have been optimized...the two samples below generate exactly the same size executable, so a consecutive jump has been removed. The second example runs faster since it avoids cascading jumps.


The code below will do a double-jump from the end of the nested if, over its else and then over the parent's else. It's runtime is 216 seconds:

Code: Select all

#include "stdio_h"

main()
{
   long i, t, a, b, c;
   
   a = b = c = 10;
   t = date();
   for (i=0; i<1000000; i++)
   {
      if (a == 10)
      {
         if (b == 10)
            { c++; }
         else
            { c--; }
      }
      else
         { c--; }
         
     c++;
  }
  printf("Stop %ld\n", date()-t);
}

The example below adds a jump to optimize...it runs 4 seconds faster (212 seconds)

Code: Select all

#include "stdio_h"

main()
{
   long i, t, a, b, c;
   
   a = b = c = 10;
   t = date();
   for (i=0; i<1000000; i++)
   {
      if (a == 10)
      {
         if (b == 10)
            { c++;  goto skip;}
         else
            { c--; }
      }
      else
         { c--; }
         
     skip: c++;
  }
  printf("Stop %ld\n", date()-t);
}

I made sure there wasn't anything weird going on so I created this version just to check the code size and indeed this one generated 4 more bytes in the executable (didn't run it since it executes differently):

Code: Select all

#include "stdio_h"

main()
{
   long i, t, a, b, c;
   
   a = b = c = 10;
   t = date();
   for (i=0; i<1000000; i++)
   {
      if (a == 10)
      {
         if (b == 10)
            { goto skip; c++; }
         else
            { c--; }
      }
      else
         { c--; }
         
     skip: c++;
  }
  printf("Stop %ld\n", date()-t);
}


swensont
Forum Moderator
Posts: 252
Joined: Tue Dec 06, 2011 3:30 am
Location: SF Bay Area
Contact:

Re: Digital C code gen

Post by swensont »

Well, the source code is available if you feel like digging more into the code generator. See Dilwn's page to find it.

Tim


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: Digital C code gen

Post by bwinkel67 »

swensont wrote:Well, the source code is available if you feel like digging more into the code generator. See Dilwn's page to find it.

Tim
I've looked at it...it's not the easiest to understand. I do have Hendrix book on Small C so I should take a look at it as it may do a better job since it does come with source code.

I think I've found the portion of the parser that correlates to the optimization I pointed out (in parser_cc1.c), though it doesn't align quite fully with what I'm seeing. It seems to show that optimization for the "goto skip;" that I had inserted. So in Small C, an if/else seems to be handled with this function during parse:

Code: Select all

doif()   {
   int   flab1, flab2;
   flab1 = getlabel();
   test(flab1, YES);
   statement();
   if (amatch("else",4) == 0) {
      postlabel(flab1);
      return;
      }
   flab2 = getlabel();
   if ((lastst != STRETURN) & (lastst != STGOTO)) jump(flab2);
   postlabel(flab1);
   statement();
   postlabel(flab2);
   }
The doif() function seems to look for a RETURN or GOTO as the last statement in the IF part and if it doesn't see that it inserts a jump to the label past the ELSE...this all makes sense and seems to be that optimization I spoke about. However, I have tried the RETURN in the same spot as well and it still seems to increase the code size so not sure why since it seems to be checking for either. I'll have to try a few more examples.

BTW, I think the single & is just a cute (and perhaps more efficient way) to do an AND. It's bitwise but if you have an equality on either side you'll evaluate to 0 or 1 so a bitwsise AND should give you the same thing (but maybe is faster?).


Derek_Stewart
Font of All Knowledge
Posts: 3928
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Re: Digital C code gen

Post by Derek_Stewart »

Hi,

There early version of Dr Dobbs Journal on Archive.org discussing Small C and other interting items.


Regards,

Derek
User avatar
NormanDunbar
Forum Moderator
Posts: 2251
Joined: Tue Dec 14, 2010 9:04 am
Location: Leeds, West Yorkshire, UK
Contact:

Re: Digital C code gen

Post by NormanDunbar »

There's a freely available ISO file (ready to burn to a CD) with lots of Small-C stuff at https://www.drdobbs.com/developer-netwo ... /184415519 incluing the "Small-C Handbook".

It's not a very big file. 10Mb uncompressed.

Cheers,
Norm.


Why do they put lightning conductors on churches?
Author of Arduino Software Internals
Author of Arduino Interrupts

No longer on Twitter, find me on https://mastodon.scot/@NormanDunbar.
Derek_Stewart
Font of All Knowledge
Posts: 3928
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Re: Digital C code gen

Post by Derek_Stewart »

Hi,

I have downloaded the CDROM ISO, interesting stuff there.

I have also previousily downloaded all the Dr Dobbs magazines from Archive.org, but the magazines were in year PDF file, so quite unmanageable, I have converted the each year to single month issue files.

If anyone is interested, I will post a a Mega Link for download.


Regards,

Derek
swensont
Forum Moderator
Posts: 252
Joined: Tue Dec 06, 2011 3:30 am
Location: SF Bay Area
Contact:

Re: Digital C code gen

Post by swensont »

The book "Dr. Dobb's Toolbook of C" is pretty much on Small-C, including the Small-Mac assembler and Small-Tools for text processing. It's a good inch thick. Back in the day I was all into Small-C, but because the source was available (and I doubt I would have look at the source).


swensont
Forum Moderator
Posts: 252
Joined: Tue Dec 06, 2011 3:30 am
Location: SF Bay Area
Contact:

Re: Digital C code gen

Post by swensont »

Looking at that CD ISO, the directory "ARTICLES" is the articles published in the "Tookbook of C". I've compared it with the hard copy version that I have.

Tim


User avatar
bwinkel67
QL Wafer Drive
Posts: 1187
Joined: Thu Oct 03, 2019 2:09 am

Re: Digital C code gen

Post by bwinkel67 »

Wow, lots of resources available. I had the Hendrix book back in the day...haven't looked at it in a long time but it is still sitting on my shelf.


Derek_Stewart
Font of All Knowledge
Posts: 3928
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Re: Digital C code gen

Post by Derek_Stewart »

Hi,

I used Small C on a Memotech MTX512 with disc drives, running CP/M which ran very nicely.

I might revisit the old CP/M system which I liked about, no GUI mess about with...


Regards,

Derek
Post Reply