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 ;
 
AAPL
$94.72
Apple Inc.
+0.78
MSFT
$44.83
Microsoft Corpora
-0.01
GOOG
$594.74
Google Inc.
+5.27

MacTech Search:
Community Search:

Software Updates via MacUpdate

Airmail 1.4 - Powerful, minimal email cl...
Airmail is a powerful, minimal mail client.It was designed to retain the same experience with a single or multiple accounts and provide a quick, modern and easy-to-use user experience. Airmail... Read more
Macs Fan Control 1.1.12 - Monitor and co...
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
A Better Finder Rename 9.37 - File, phot...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
MacBook Air EFI Firmware Update 2.9 - Fo...
MacBook Air EFI Firmware Update is recommended for MacBook Air (Mid 2011) models. This update addresses an issue where systems may take longer to wake from sleep than expected and fixes a rare issue... Read more
FileZilla 3.9.0.1 - Fast and reliable FT...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface.Version 3.9.0.1: MSW: Fix installation issue with locked DLLs... Read more
OS X Yosemite 10.10 DP4 - Developer Prev...
Note: This is a Developer Preview. You must be a registered Apple Mac Developer to download this update. OS X Yosemite is Apple's newest operating system for Mac. An elegant design that feels... Read more
FinderPop 2.5.6 - Classic Mac utility, n...
FinderPop is a Universal preference pane that extends OS X's contextual menus using a FinderPop Items folder much as the Apple Menu Items folder used to do for the Apple menu. It has other features... Read more
SpiderOak 5.1.7 - Secure cloud backup, s...
SpiderOak is a multi-platform secure online backup, storage, access, and sharing solution engineered for the consumer and small businesses. You must first sign up to use SpiderOak. Running natively... Read more
Espionage 3.6 - Simple, state of the art...
Espionage offers state-of-the-art encryption and plausible deniability for your confidential data. Sometimes, encrypting your data isn't enough to protect it. That's why Espionage 3 goes beyond data... Read more
calibre 1.45.0 - Complete e-library mana...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more

Latest Forum Discussions

See All

Celebrate Summer With a Cat in the Hat L...
Celebrate Summer With a Cat in the Hat Learning Library Sale Posted by Ellis Spice on July 22nd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
MyTaskList Review
MyTaskList Review By Jennifer Allen on July 22nd, 2014 Our Rating: :: EFFECTIVE IF PLAINUniversal App - Designed for iPhone and iPad It’s not the most stylish of task management apps, but MyTaskList has all the features you could... | Read more »
FlyCraft Herbie: Crazy Machines Review
FlyCraft Herbie: Crazy Machines Review By Jennifer Allen on July 22nd, 2014 Our Rating: :: TRICKY FLYINGUniversal App - Designed for iPhone and iPad A tough game of careful thrusting and navigation, FlyCraft Herbie: Crazy Machines... | Read more »
MTN Review
MTN Review By Jessica Fisher on July 22nd, 2014 Our Rating: :: ADORABLE, SERENE, AND AMUSINGUniversal App - Designed for iPhone and iPad MTN is an adorable, talking pet mountain that is less game and more zen garden.   | Read more »
Fly High with Ninja UP! Now Available o...
Fly High with Ninja UP! Now Available on the App Store Posted by Jessica Fisher on July 22nd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Bio Inc. Review
Bio Inc. Review By Nadia Oxford on July 22nd, 2014 Our Rating: :: SICKENING - IN A COMPELLING WAYUniversal App - Designed for iPhone and iPad Bio Inc is about orchestrating the medical destruction of a single person. If that doesn’... | Read more »
HELMUT Review
HELMUT Review By Andrew Fisher on July 21st, 2014 Our Rating: :: TRUNDLE SIMULATOR 2014Universal App - Designed for iPhone and iPad HELMUT is a fun, fleeting time-sink that offers a momentary distraction and nothing else.   | Read more »
Walkr Review
Walkr Review By Jennifer Allen on July 21st, 2014 Our Rating: :: ORIGINAL WALKINGiPhone App - Designed for the iPhone, compatible with the iPad Walking is a bit more exciting thanks to this planet building/discovering sim reliant... | Read more »
Zombie Commando Review
Zombie Commando Review By Jennifer Allen on July 21st, 2014 Our Rating: :: MINDLESS SLAUGHTERUniversal App - Designed for iPhone and iPad Briefly fun but ultimately forgettable, Zombie Commando will scratch an itch then be... | Read more »
Swords & Poker Adventures Review
Swords & Poker Adventures Review By Jennifer Allen on July 21st, 2014 Our Rating: :: SOULLESS POKER PLAYUniversal App - Designed for iPhone and iPad Swords & Poker Adventures is a mishmash of Poker and RPGing, but it lacks... | Read more »

Price Scanner via MacPrices.net

15-inch 2.0GHz MacBook Pro Retina on sale for...
B&H Photo has the 15″ 2.0GHz Retina MacBook Pro on sale for $1829 including free shipping plus NY sales tax only. Their price is $170 off MSRP. B&H will also include free copies of Parallels... Read more
Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished Mac minis for up to $150 off the cost of new models. Apple’s one-year warranty is included with each mini, and shipping is free: - 2.5GHz Mac... Read more
Twelve South HiRise For MacBook – Height-Adju...
If you use your MacBook as a workhorse desktop substitute, as many of us do, a laptop stand combined with an external keyboard and pointing device are pretty much obligatory if you want to avoid... Read more
Why The Mac Was Not Included In The Apple/IBM...
TUAW’s Yoni Heisler cites Fredrick Paul of Network World whoi blogged last week that the Mac’s conspicuous absence from Apple and IBM’s landmark partnership agreement represents a huge squandered... Read more
Save $100 on 13-inch Retina MacBook Pros, plu...
Adorama has 13″ Retina MacBook Pros on sale for $100 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: - 13″ 2.4GHz/128GB MacBook Pro with Retina Display: $1199 - 13″ 2.... Read more
Blurr it 2.3 for iOS – Quickly Blurs Selected...
Hyderabad, India based TouchLabs has announced a new update of Blurr it 2.3, their photography app for iOS users. Blurr it allows you to blur part of the image to hide potentially sensitive or... Read more
MacBook Airs on sale for $100 off MSRP, start...
Best Buy has the new 2014 MacBook Airs on sale for up to $100 off MSRP on their online store. Choose free home shipping or free local store pickup (if available). Prices valid for online orders only... Read more
Amazon Announces Kindle Unlimited: Unlimited...
Amazon.com has introduced Kindle Unlimited — a new subscription service which allows customers to freely read as much as they want from over 600,000 Kindle books, and listen as much as they want to... Read more
New Linksys Wireless Range Extenders Boost Wi...
Linksys has announced its new lineup of Linksys Wi-Fi Range Extenders. Consumers often experience a weak wireless signal in some parts of their house or apartment caused by blocking elements such as... Read more
MacBook Airs available starting at $719
The Apple Store has Apple Certified Refurbished 2013 & 2012 MacBook Airs in stock today starting at $719. An Apple one-year warranty is included with each MacBook, and shipping is free: 2013... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Sr *Apple* Engineer - IT - Requisition #: -...
For more information about TIAA-CREF, visit our website . The Apple Engineer will provide engineering and third-level incident support for 300- 500 MacOS desktop/laptop Read more
*Apple* Systems Administrator - DISH (United...
…satellite service provider, and Dish is currently looking for an experienced Apple /Mac Systems Administrator. Apple systems administrator will be responsible for Read more
*Apple* Systems Administrator - DISH (United...
…satellite service provider, and Dish is currently looking for an experienced Apple /Mac Systems Administrator. Apple systems administrator will be responsible for Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.