TweetFollow Us on Twitter

Inline Code
Volume Number:1
Issue Number:9
Column Tag:Forth Forum

"Inline Code for MacForth"

By Jörg Langowski, Chemical Engineer, Fed. Rep. of Germany, MacTutor Editorial Board

Speeding up Forth with Inline Code

When you use your computer for applications that require a lot of data shuffling and calculations, work with large arrays and matrices and so on, you tend to become a little paranoid about speed. Although Forth code is very compact through its threaded structure, and word execution (i.e. subroutine calling) is reasonably well optimized in MacForth (see MacTutor V1 No2), I have always felt uncomfortable with the overhead that goes into the execution of a simple word like DROP, whose 'active part' consists of one 16-bit word of machine code.

Just as a reminder: when the Forth em executes the token for DROP in a definition, it calls a subroutine that looks like this:

DROP  ADDQ.L#4,A7
 JMP  (A4)

So it is a simple 4-byte increment of the stack pointer that does the DROP job. But, then the next token has to be fetched and executed by jumping to the NEXT routine, whose address is contained in A4, the base pointer. This makes for a several hundred precent overhead, as compared to the increment itself. This overhead is not so dramatic with other words, but it is still there: and all in all the Sieve benchmark needs 21 seconds to run in MacForth, compare this to 9 seconds in compiled C (Consulair).

How can we speed up the code? After all, we have complete control over what goes into the dictionary and could put the machine code that we need right in there, no need for time-expensive subroutine calling. This is what the Forth 2.0 assembler enables you to do. However, if you create a piece of code in Forth assembler, it tends to look much more cryptic than 'normal' assembler, which after all is readable with adequate documentation.

It would be much nicer if we had a means to create the assembly code that corresponds to a DROP by writing a similar word, such as %DROP: something like a macro. No need to worry about which registers to use, and you could use 'almost normal' Forth code for writing your routine.

It shouldn't be that difficult to persuade the Forth system to execute machine code that is embedded in a definition. Every Forth word starts with at least one executable piece of machine code, trap calls for Forth-defined words such as colon definitions and 'real' 68000 code for machine code definitions. However, this gives you either machine code or Forth, not both. Our goal is to define words that allow switching between 68000 and Forth code within one definition. Similar words do exist in the Forth 2.0 assembler, but it lacks a set of macros that allow you to write inline Forth code instead of assembly code. Furthermore, you cannot define control structures that easily.

Assume we have Forth code that looks like this:

 ...
 <token 1>
 <token 2>
 <token X>
 <machine instruction 1>
 <machine instruction 2>
 ...

etc. This sequence of instruction will get executed just fine if <token X> is a word that transfers execution to the word just following. We'll call this word >CODE and define it as follows:

: >CODE 
    here 2+ make.token w, [compile] [ ;
    immediate

This word, which is executed during compilation, takes the next free address in the dictionary, adds 2 (this is where execution of the machine code is to start) and compiles this address as a token into the dictionary. Since a token just tells the Forth interpreter 'jump to the address that I refer to', machine code execution will start at the address following >CODE.

This is what happens at execution time. At compilation time, the words following >CODE in the input stream are executed, not compiled (this is what the [COMPILE] [ does). Therefore, if the words following >CODE are macros that stuff assembly code into the dictionary, you have your inline code right there.

We'll get to those macros in a minute. First, what remains is the problem how to get out of the machine code. You might recall that all machine-level Forth definitions finish with a

 JMP  (A4)

and the NEXT routine, pointed to by A4, gets the next token from the Forth code. The pointer to the next token is in register A3. Unfortunately, after we executed >CODE, A3 remained unchanged and still points to the word following the >CODE token. Which is 68000 code and certainly nothing that the interpreter will swallow. Therefore we have to reset A3 before we jump back into the Forth interpreter. This is what the word >FORTH does:

: >FORTH 47fa0004 , 4ed4 w, [compile] ] ;

 LEA  4(PC),A3
 JMP  (A4)

Remember, when >FORTH appears in the input stream, we are still in execution mode, from the preceding >CODE (unless we mixed things up). So >FORTH gets executed when used in a definition; it assembles code that loads A3 with the address following the JMP, then executes the JMP. Then the mode is switched back to regular Forth compilation again.

Between >CODE and >FORTH we can now place our macros that generate inline machine code corresponding to Forth primitives. The code for any of the primitives is found very easily by disassembling from the original Forth system. Of course, you may define your own code, use different registers than the MacForth definitions do or optimize the code. For instance, the built-in multiplication routine is a prime candidate for removing overhead. The routine *, which calls the multiplication primitive, M*, always does a 32- by 32-bit multiply and then drops the upper 32 bits of the double precision product. Some sloppiness on the part of Creative Solutions, I presume. Of course, a direct 16- by 16-bit multiply would be much faster.

I have written the macros in hex code, so that they'll work without the assembler, in case you are using Forth 1.1. The machine code is given as a comment in the program text.

Literals

The %LIT and %WLIT macros serve as a means to put constants and addresses on the stack. They compile a long move, resp. word move instruction with the number on the stack at compilation time compiled as the data word(s) following the instruction. So the way to put the address of a variable on the stack in inline code is just to write: <variable> %LIT.

Control Structures

The goal was to speed up the Sieve benchmark (as an example). Of course, the code would be far from optimal if we still had to use the Forth control structures; they should be coded inline, too. This means we have to keep track of addresses that we want to branch to.

The program below provides two examples, %IF...%THEN...%ELSE and %DO...%LOOP. The other control structures are not included, since they weren't necessary for this particular example. But after reading through, you should be able to write your own code for that.

%IF compiles a branch which is taken when the number on top of stack is zero. This branch has a zero displacement when first compiled. At the same time, the dictionary address is pushed on the compilation time stack (HERE). When %THEN is encountered, the branch displacement is calculated and put into the correct address. Same holds for %ELSE, only that another unconditional branch is compiled that is taken at the end of the %IF part. This branch is resolved at the %THEN.

The code compiled by %DO takes the initial and final values from the stack and puts them on the return stack. During compilation, HERE is put on the stack as a reference for the backward branch taken by %LOOP. %LOOP compiles code that increments the loop counter by one and tests it against the limit; if it is still below the limit, the backward branch is taken (calculated at compilation time). %+LOOP behaves just like %LOOP, only that the increment is the number on top of stack. Note that there is one difference between %+LOOP and the usual Forth +LOOP: while the latter works with positive and negative loop increments, ours works only with positive. I did this in the interest of speed.

The Sieve Benchmark

With all these macros available we can now recode the Sieve of Erastothenes prime number benchmark into inline machine code. The changes that have to be made to the Forth code are only minor ones. At the point where the inline code is supposed to start, we insert >CODE; all Forth words thereafter are inline macros. They are distinguished from the regular Forth words by the preceding percent sign. When the inline part ends, we write >FORTH to jump back into interpreter mode.

The resulting code works (!!) and executes in 9.7 seconds, as compared to 21 seconds for the Forth code.

Inline compiler definitions ( 060585 jl )

(c) June 1985 MacTutor by J. Langowski

This code is meant as an example for speeding up time-critical Forth code through the insertion of inline machine code. The words defined here are by no means a complete Forth compiler. No attempt was made to use the same words as standard Forth and do context switching; I felt that this would have been a) more complicated and b) actually confusing, because you tend to lose track of when you are in inline mode and when in interpreted Forth mode. Therefore, all inline words are compiled into the standard Forth vocabulary and have the names of the corresponding Forth words preceded by a '%'. The only control structures are %IF...%ELSE...%THEN and %DO...%LOOP/%+LOOP, where the %+LOOP works only for positive increments. You are encouraged to build other control structures, using the same principles.

( inline assembly macros)  ( 060285 jl )
hex
: >code here 2+ make.token w, [compile] [ ;  
immediate

: >forth 47fa0004 , 4ed4 w, [compile] ] ;
{LEA  4(PC),A3 }
{JMP  (A4)} 
: %swap 202f0004 , 2f570004 , 2e80 w, ;
{MOVE.L 4(A7),D0 }
{MOVE.L (A7),4(A7) }
{MOVE.L D0,(A7)  }
 
: %drop 588f w, ; { ADDQ.L  #4,A7  }
: %dup 2f17 w, ;  { MOVE.L  (A7),-(A7) }
: %over 2f2f0004 , ; { MOVE.L 4(A7),-(A7) }

: %+! 205f201f , d190 w, ;
{MOVE.L (A7)+,A0 }
{MOVE.L (A7)+,D0 }
{ADD.L  D0,(A0)  }

: %rot 202f0008 , 2f6f0004 , 0008 w,
       2f570004 , 2e80 w, ;
{MOVE.L 8(A7),D0 }
{MOVE.L 4(A7),8(A7)}
{MOVE.L (A7),4(A7) }
{MOVE.L D0,(A7)  }

: %+ 201fd197 , ;  
{MOVE.L (A7)+,D0 }
{ADD.L  D0,(A7)  }
  
: %- 201f9197 , ;
{MOVE.L (A7),D0  }
{SUB.L  D0,(A7)  }

: %i 2f16 w, ;     { MOVE.L   (A6),-(A7) }
: %j 2f2e0008 , ;  { MOVE.L  8(A6),-(A7) }
: %k 2f2e0010 , ;  { MOVE.L 16(A6),-(A7) }
{ %k is a word that does not exist in 
  MacForth, but is very useful to extract 
  a loop index one level further down    }

: %i+ 2017d096 , 2e80 w, ;
{MOVE.L (A7),D0  }
{ADD.L  (A6),D0  }
{MOVE.L D0,(A7)  }

: %c@ 42802057 , 10102e80 , ;
{CLR.L  D0}
{MOVE.L (A7),A0  }
{MOVE.B (A0),D0  }
{MOVE.L D0,(A7)  }
  
: %w@ 20574257 , 3f500002 , ;
{MOVE.L (A7),A0  }
{CLR.W  (A7)}
{MOVE (A0),2(A7) }

: %@ 20572e90 , ;
{MOVE.L (A7),A0  }
{MOVE.L (A0),(A7)}
  
: %c! 205f201f , 1080 w, ;
{MOVE.L (A7)+,A0 }
{MOVE.L (A7)+,D0 }
{MOVE.B D0,(A0)  }

: %w! 205f201f , 3080 w, ;
{MOVE.L (A7)+,A0 }
{MOVE.L (A7)+,D0 }
{MOVE D0,(A0)  }
   
: %! 205f209f , ;
{MOVE.L (A7)+,A0 }
{MOVE.L (A7)+,(A0) }

: %>r 2d1f w, ;  { MOVE.L  (A7)+,-(A6)  }  
: %r> 2f1e w, ;  { MOVE.L  (A6)+,-(A7)  }

: %ic!  201f2056 , 1080 w, ;
{MOVE.L (A7)+,D0 }
{MOVE.L (A6),A0  }
{MOVE.B D0,(A0)  }

: %lit 2f3c w, , ;
{MOVE.L #xxxx,-(A7)}
{ where xxxx is compiled from the stack 
  into the next four bytes }
  
: %wlit 3f3c w, w, ;
{MOVE #xxxx,-(A7)}
{ and compile top of stack into next word }

: %< 4280bf8f , 6c025380 , 2f00 w, ;
{CLR.L  DO}
{CMPM.L (A7)+,(A7)+}
{BGE  M1}
{SUBQ.L #1,D0  }
{ M1  MOVE.LD0,-(A7) }

: %> 4280bf8f , 6f025380 , 2f00 w, ;
{CLR.L  DO}
{CMPM.L (A7)+,(A7)+}
{BLE  M1}
{SUBQ.L #1,D0  }
{ M1  MOVE.LD0,-(A7) }

: %= 4280bf8f , 66025380 , 2f00 w, ;
{CLR.L  DO}
{CMPM.L (A7)+,(A7)+}
{BNE  M1}
{SUBQ.L #1,D0  }
{ M1  MOVE.LD0,-(A7) }

: %0= 42804a97 , 66025380 , 2e80 w, ;
{CLR.L  D0}
{TST.L  (A7)}
{BNE  M1}
{SUBQ.L #1,D0  }
{ M1  MOVE.LD0,-(A7) }

: %0< 42804a97 , 6a025380 , 2e80 w, ;
{CLR.L  D0}
{TST.L  (A7)}
{BPL  M1}
{SUBQ.L #1,D0  }
{ M1  MOVE.LD0,-(A7) }

: %0> 42804a97 , 6f025380 , 2e80 w, ;
{CLR.L  D0}
{TST.L  (A7)}
{BLE  M1}
{SUBQ.L #1,D0  }
{ M1  MOVE.LD0,-(A7) }

: %and 201fc197 , ;
{MOVE.L (A7)+,D0 }
{AND.L  D0,(A7)  }
  
: %or 201f8197 , ;
{MOVE.L (A7)+,D0 }
{OR.L D0,(A7)  }

: %if 4a9f6700 , here 0 w, ;
{TST.L  (A7)+  }
{BEQ  xxxx}
{ xxxx is a 16 bit displacement that is 
  resolved by %THEN   }

: %then here over - swap w! ;
: %else 6000 w, here 0 w, swap %then ;
{BRA  xxxx}
{ resolves preceding %IF and leaves new
  empty unconditional branch to be filled
  by %THEN     }

: %do 2d2f0004 , 2d1f588f , here ;
{MOVE.L 4(A7),-(A6)}
{MOVE.L (A7)+,-(A6)}
{ADDQ.L #4,A7  }
{ leaves HERE on the stack for back branch
  by %LOOP or %+LOOP      }

: %loop 5296204e , b1886e00 , 
                 here - w, ddfc w, 8 , ;
{ADDQ.L #1,(A6)  }
{MOVE.L A6,A0  }
{CMPM.L (A0)+,(A0)+}
{BGT  xxxx}
{ADDA.L #8,A6  }
{ the last instruction cleans up the return
  stack. Branch resolved in this word     }

: %+loop 201fd196 , 204e w, b1886e00 , 
                 here - w, ddfc w, 8 , ;
{MOVE.L (A7)+,D0 }
{ADD.L  D0,(A6)  }
{MOVE.L A6,A0  }
{CMPM.L (A0)+,(A0)+}
{BGT  xxxx}
{ADDA.L #8,A6  }

decimal

( Eratosthenes Sieve Benchmark,
             inline code) ( 060285 jl )
 8192 constant size  
 create flags  size allot
: primes   flags  size 01 fill 
  >code 0 %lit size %lit 0 %lit
    %do  flags %lit %i+ %c@
       %if 3 %lit %i+ %i+ %dup %i+ 
             size %lit %<
         %if size %lit flags %lit %+ 
           %over %i+ flags %lit %+
           %do 0 %lit %ic! %dup %+loop
         %then %drop 1 %lit %+
       %then
    %loop >forth . ." primes  "  ;
 : 10times    
   1 sysbeep 10 0 do  primes cr loop
   1 sysbeep ;

( Eratosthenes Sieve Benchmark,
                standard version)
 8192 constant size       
 create flags  size allot
: primes flags size 01 fill 
  0  size 0  
    do  flags  i+ c@
      if  3 i+ i+ dup i+  size <  
         if  size flags +  over i+  flags +
             do  0 ic!  dup  +loop
         then  drop 1+  
       then
    loop  . ." primes  "  ;
 : 10times    
   1 sysbeep 10 0 do  primes cr loop  
   1 sysbeep ;
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Little Snitch 3.5.3 - Alerts you about o...
Little Snitch gives you control over your private outgoing data. Track background activity As soon as your computer connects to the Internet, applications often have permission to send any... Read more
Cocktail 8.4 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
PDFKey Pro 4.3 - Edit and print password...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Kodi 15.0.beta1 - Powerful media center...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
DiskCatalogMaker 6.4.12 - Catalog your d...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast. Finder-like intuitive look and feel. Super-fast search algorithm. Can compress catalog data... Read more
Macs Fan Control 1.3.0.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
Lyn 1.5.11 - Lightweight image browser a...
Lyn is a lightweight and fast image browser and viewer designed for photographers, graphic artists and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it... Read more
NeoOffice 2014.11 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
LaunchBar 6.4 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Remotix 3.1.4 - Access all your computer...
Remotix is a fast and powerful application to easily access multiple Macs (and PCs) from your own Mac. Features Complete Apple Screen Sharing support - including Mac OS X login, clipboard... Read more

Crossy Road Devs Hipster Whale are Bring...
Hipster Whale, the minds behind the rather popular (and rather great) Crossy Road, have teamed-up with Bandai Namco to create PAC-MAN 256: an absolutely bonkers looking maze runner chaser thing. | Read more »
Meet the New Spotify Music
Spotify Music  has a lot going on. They're introducing 3 new modes to serve all your musical needs, with the "Now" start page  gives you curated playlists based on your particular tastes. As you listen the app will learn more about your tastes and... | Read more »
What the Apple Watch Gets Right, and Wha...
| Read more »
Celebrate PAC-MAN's 35th Birthday W...
BANDAI NAMCO Entertainment America is celebrating PAC-MAN's 35th anniversary by releasing updates for PAC-MAN and PAC-MAN Lite for iOS. [Read more] | Read more »
Strike Wing Episode 2 has Landed on the...
Strike Wing: Raptor Rising is an exciting space combat simulator by Crescent Moon Games, which was recently updated to continue the story with Episode 2. [Read more] | Read more »
Kiqplan Expands its Interactive Coaching...
The makers of Fitbug have been hard at work on their Kiqplan lineup, and have added four new summer themed plans to help you get the most out of your workout. [Read more] | Read more »
Make a Photobook in Minutes with Pictyea...
What happens when you can't stop taking photos and have an urge to create a photobook? Pictyear saves the day. [Read more] | Read more »
This Week at 148Apps: May 18-22, 2015
May Days at 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above the... | Read more »
Biz Builder Delux (Games)
Biz Builder Delux 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Ah, there's nothing like the rhythmic bustle of a burgeoning business burg... especially when you're the one building it... | Read more »
Auroch Digital is Bringing Back Games Wo...
| Read more »

Price Scanner via MacPrices.net

New 13-inch 2.9GHz Retina MacBook Pro on sale...
B&H Photo has the 13″ 2.9GHz/512GB Retina MacBook Pro on sale for $1699.99 including free shipping plus NY tax only. Their price is $100 off MSRP, and it’s the lowest price for this model from... Read more
12-inch MacBook stock status for Monday, May...
The new 12″ Retina MacBooks are still on backorder at The Apple Store with a 3-5 week waiting period. However, a few models are in stock today at Apple resellers. Stock is limited, so act now if you’... Read more
New 27-inch 3.3GHz 5K iMac in stock with free...
Adorama has the new 27″ 3.3GHz 5K iMac in stock today for $1999 including free shipping plus NY & NJ sales tax only. Adorama will include a free copy of Apple’s 3-year AppleCare Protection Plan. Read more
Memorial Day Weekend Sale: New 27-inch 3.3GHz...
Best Buy has the new 27″ 3.3GHz 5K iMac on sale for $1899.99 this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary... Read more
OtterBox Maximizes Portability, Productivity...
From the kitchen recipe book to the boarsroom presentation, the OtterBox Agility Tablet System turns tablets into one of the most versatile pieces of handheld technology available. Available now, the... Read more
Launch of New Car App Gallery and Open Develo...
Automatic, a company on a mission to bring the power of the Internet into every car, has announced the launch of the Automatic App Gallery, an app store for nearly every car or truck on the road... Read more
Memorial Day Weekend Sale: 13-inch 1.6GHz Mac...
Best Buy has the new 13″ 1.6GHz/128GB MacBook Air on sale for $849 on their online store this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders... Read more
Memorial Day Weekend Sale: 27-inch 3.5GHz 5K...
Best Buy has the 27″ 3.5GHz 5K iMac on sale for $2099.99 this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary.... Read more
Sale! 16GB iPad mini 3 for $349, save $50
B&H Photo has the 16GB iPad mini 3 WiFi on sale for $349 including free shipping plus NY sales tax only. Their price is $50 off MSRP, and it’s the lowest price available for this model. Read more
Price drop on 2014 15-inch Retina MacBook Pro...
B&H Photo has dropped prices on 2014 15″ Retina MacBook Pros by $200. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799.99 save $200 - 15″ 2.5GHz... Read more

Jobs Board

Architect / Senior Software Engineer, *Apple...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
*Apple* Pay Support Readiness Project Manage...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
Hardware Design Validation Engineer - *Apple...
**Job Summary** The Apple Watch team is looking for a Hardware Design Validation Engineer. This person will be part of the Apple Watch hardware team with Read more
Sr. Payment Program Manager, *Apple* Pay -...
**Job Summary** Apple Pay is an exciting environment and a…devices in a simple, private and secure way. The Apple Pay Team is looking for an experienced Senior Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.