Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #4358 > unrolled thread

PLASMA 2.0

Back to article view | Back to comp.sys.apple2.programmer

Contents

  PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-16 11:43 -0700
    Re: PLASMA 2.0 Steve Nickolas <usotsuki@buric.co> - 2018-03-16 20:47 -0400
      Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-17 07:06 -0700
    Re: PLASMA 2.0 John Brooks <jbrooks@blueshiftinc.com> - 2018-03-16 18:00 -0700
      Re: PLASMA 2.0 Antoine Vignau <antoine.vignau@laposte.net> - 2018-03-16 22:18 -0700
        Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-17 07:36 -0700
      Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-17 07:34 -0700
        Re: PLASMA 2.0 Michael J. Mahon <mjmahon@aol.com> - 2018-03-17 10:05 -0500
          Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-17 20:56 -0700
            Re: PLASMA 2.0 Michael J. Mahon <mjmahon@aol.com> - 2018-03-18 00:59 -0500
              Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-18 07:47 -0700
                Re: PLASMA 2.0 Michael J. Mahon <mjmahon@aol.com> - 2018-03-21 00:23 -0500
        Re: PLASMA 2.0 John Brooks <jbrooks@blueshiftinc.com> - 2018-03-18 01:10 -0700
          Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-18 08:06 -0700
            Re: PLASMA 2.0 John Brooks <jbrooks@blueshiftinc.com> - 2018-03-18 12:20 -0700
              Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-18 13:56 -0700
                Re: PLASMA 2.0 John Brooks <jbrooks@blueshiftinc.com> - 2018-03-18 17:35 -0700
    Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-23 13:32 -0700
      Re: PLASMA 2.0 Antoine Vignau <antoine.vignau@laposte.net> - 2018-03-23 14:07 -0700
        Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-23 17:22 -0700
    Re: PLASMA 2.0 Michael Mann <gmail@ware4.com> - 2018-03-23 16:44 -0700
      Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-23 17:20 -0700
        Re: PLASMA 2.0 mmphosis <mmphosis@macgui.com> - 2018-03-24 01:13 +0000
          Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-23 19:09 -0700
        Re: PLASMA 2.0 Steve Nickolas <usotsuki@buric.co> - 2018-03-23 21:55 -0400
          Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-23 19:12 -0700
            Re: PLASMA 2.0 Antoine Vignau <antoine.vignau@laposte.net> - 2018-03-24 00:34 -0700
              Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-24 07:51 -0700
    Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-28 15:39 -0700
      Re: PLASMA 2.0 Michael J. Mahon <mjmahon@aol.com> - 2018-03-28 20:52 -0500
        Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-29 07:17 -0700
          Re: PLASMA 2.0 Zellyn <zellyn@gmail.com> - 2018-03-29 08:12 -0700
            Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-29 22:19 -0700
    Re: PLASMA 2.0 Tom Porter <laseractiveguy@gmail.com> - 2018-03-28 23:02 -0700
      Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-29 07:21 -0700
    Re: PLASMA 2.0 "Frank M." <frank_o_rama@hotmail.com> - 2018-03-29 08:25 -0700
      Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-29 22:21 -0700
      Re: PLASMA 2.0 "Frank M." <frank_o_rama@hotmail.com> - 2018-04-01 07:48 -0700
        Re: PLASMA 2.0 "Michael J. Mahon" <mjmahon@aol.com> - 2018-04-01 13:12 -0700
          Re: PLASMA 2.0 Brian Patrie <bpatrie@bellsouth.spamisicky.net> - 2018-04-02 00:02 -0500
            Re: PLASMA 2.0 Brian Patrie <bpatrie@bellsouth.spamisicky.net> - 2018-04-03 00:07 -0500
              Re: PLASMA 2.0 MG <guidero@gmail.com> - 2018-04-02 22:35 -0700
              Re: PLASMA 2.0 Michael J. Mahon <mjmahon@aol.com> - 2018-04-03 13:47 -0500
                Re: PLASMA 2.0 Brian Patrie <bpatrie@bellsouth.spamisicky.net> - 2018-04-04 04:38 -0500
    Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-30 15:46 -0700
      Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-03-31 13:25 -0700
    Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-04-12 18:43 -0700
    Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-04-14 08:43 -0700
      Re: PLASMA 2.0 Michael J. Mahon <mjmahon@aol.com> - 2018-04-14 21:26 -0500
        Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-04-15 07:35 -0700
          Re: PLASMA 2.0 "Michael J. Mahon" <mjmahon@aol.com> - 2018-04-15 16:24 -0700
            Re: PLASMA 2.0 Michael Pohoreski <michael.pohoreski@gmail.com> - 2018-04-23 23:01 -0700
      Re: PLASMA 2.0 John Brooks <jbrooks@blueshiftinc.com> - 2018-04-15 00:24 -0700
        Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-04-15 08:10 -0700
          Re: PLASMA 2.0 John Brooks <jbrooks@blueshiftinc.com> - 2018-04-15 10:22 -0700
            Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-04-15 13:00 -0700
              Re: PLASMA 2.0 John Brooks <jbrooks@blueshiftinc.com> - 2018-04-15 15:17 -0700
    PLASMA 2.0 Michael Pohoreski <michael.pohoreski@gmail.com> - 2018-04-24 08:54 -0700
      Re: PLASMA 2.0 David Schmenk <dschmenk@gmail.com> - 2018-04-25 06:37 -0700

Page 1 of 3  [1] 2 3  Next page →

#4358 — PLASMA 2.0

With the development of PLASMA version 1.x pretty much wrapped up, I've been focussing on the next version. I expected making significant updates to PLASMA to take months of slow progress. In truth it ended up taking just a few weeks. I simply got too excited by the results I was getting. I thought I would update the state of PLASMA's development to get feedback (and show off a little). Putting version 1.x to bed has allowed the opportunity to work with other 6502 platforms in the main repository. I tested out a Commodore 64 port (boy, do I appreciate the Apple II now!) and SteveF has been updating the BBC "Beeb" port.

Many of the improvements were made available when I restructured the compiler to operate on opcode sequence lists (before committing them to the output buffer). Originally this was for implementing the peephole optimizer, but I should have taken more advantage in the version 1.x tree in retrospect. It was easier than anticipated to re-order the code sequences even though the compiler is just a single pass.

So, here is a list, in no particular order, of the version 2 improvements to date:

1. Re-code FOR/NEXT with new opcodes. Uses a little more evaluation stack, but works faster by keeping the terminal value and the working value on the evaluation stack. New opcodes for INCBRLE (increment, branch less than), ADDBRLE (for STEP values other than one), DECBRGE, SUBBRGE (the DOWNTO variants). These opcodes are FOR/NEXT specific and pop the two values off the evaluation stack when the loop terminates. There is a BRGT/BRLT at the top of the FOR/NEXT loop to check for cases where the starting value already exceeds the terminal value. This is optimized out when the values are known a-priori. The only real difference in usage from version 1 is that the loop variable won't have the final value after the loop exits. I only had two instances in my code where this mattered. Easy to work around for a big speed improvement.

2. Re-code WHILE/LOOP to test the ending condition at the bottom of the loop instead of the top. This involves one branch to the test before entering the loop, but only one branch at the bottom (much like the REPEAT/UNTIL). The version 1 had the test at the top and required an unconditional branch at the bottom.

3. Logical AND and OR are now short-circuiting instead of calculating the entire expression and ANDing/ORing the results together. New branch opcode BRAND and BROR look at the left-hand side of the expression and skip the right-hand side if it can. If not, pop the left-hand side and let the right-hand side be the result.

4. All new switch/select/case implementation. A caseblock of values and branch targets lets the entire switch/select/case comparison happen in the VM at once. In version 1, this was a slightly optimized string of IF/THEN/ELSEs. Now, duplicate cases can be flagged for an error (yep, caught a couple in my code). Falling through one case to the next doesn't invovle any penalty like version 1. Max number of cases is 256. That should be enough.

5. New BREQ and BRNE opcodes combine the very common ISEQ+BRFLS/BRTU and ISNE+BRFLS/BRTRU sequences.

6. More constant opcodes. CN - Constant Nybble, encodes values 0-15 in a single byte. MINUS_ONE ($FFFF) is a single byte opcode. ADDI, SUBI, ANDI, ORI are immediate versions of the ADD, SUB, AND and OR. The immediate value is a byte only (most of the cases).

7. One of the most common sequences is a load, followed by ADD (add or indexed byte array) or IDXW (indexed word array). So common, that I experimentally added versions of ADD and IDXW that combined the load value variants. Four new versions of ADD and IDXW from local/global bye/word.  It was a big impact to the VM size but the performance boost was significant so I kept them. It required much reworking of the Apple 3 VM, as it is very spaced constrained the way I have it implementd (6K for CMDSYS+VM). To fit it in the Apple 3, it has a sub-optimal implementation. But the Apple 2 still had room, and it flies.


Some of these improvements came from re-thinking my approach to code generation with the help of code sequences. FOR/NEXT and WHILE/LOOP were direct consequences of that. The switch/select/case was something I always wanted to fix with a caseblock (the JVM has something very similar). The opcode improvements came from getting statistics on opcode frequqency, then looking for common sequences involving those opcodes. The peephole optimizer then was updated to take advantage of the more efficient opcodes. The basic code generator didn't have to change, just the optimizer. It was interesting to see how the statistics changed with each addition.

For some perspective, the Sieve of Eratosthenes benchmark on my 64K Apple ][ was able to calculate all 1899 primes in just about 20 seconds on the PLASMA 1.0 Developer Preview. With all the help here, the version 1 release was about 17.5 seconds. Currently, version 2 is just under 15 seconds :-)

You can check out all the updates and disk images on GitHub: https://github.com/dschmenk/PLASM then select the devel branch.

Dave...

[toc] | [next] | [standalone]

#4359

I definitely should figure out how to implement this on the C64, 128 and 
Plus/4, although I have almost no familiarity with coding for those. XD

On the plus side, they could share a disk the same way the Apple ][ and 
/// versions can.

-uso.

[toc] | [prev] | [next] | [standalone]

#4366

On Friday, 16 March 2018 17:47:48 UTC-7, Steve Nickolas  wrote:
> I definitely should figure out how to implement this on the C64, 128 and 
> Plus/4, although I have almost no familiarity with coding for those. XD
> 
> On the plus side, they could share a disk the same way the Apple ][ and 
> /// versions can.
> 
> -uso.

That would be fantastic! The thing I struggle with most is the cumbersome disk I/O. The bank switching isn't all that different amongst 6502 machines - they all have to figure out a mechanism to swap ROM and HW in and out.

Dave...

[toc] | [prev] | [next] | [standalone]

#4360

On Friday, March 16, 2018 at 11:43:35 AM UTC-7, David Schmenk wrote:
> With the development of PLASMA version 1.x pretty much wrapped up, I've been focussing on the next version. I expected making significant updates to PLASMA to take months of slow progress. In truth it ended up taking just a few weeks. I simply got too excited by the results I was getting. I thought I would update the state of PLASMA's development to get feedback (and show off a little). Putting version 1.x to bed has allowed the opportunity to work with other 6502 platforms in the main repository. I tested out a Commodore 64 port (boy, do I appreciate the Apple II now!) and SteveF has been updating the BBC "Beeb" port.
> 
> Many of the improvements were made available when I restructured the compiler to operate on opcode sequence lists (before committing them to the output buffer). Originally this was for implementing the peephole optimizer, but I should have taken more advantage in the version 1.x tree in retrospect. It was easier than anticipated to re-order the code sequences even though the compiler is just a single pass.
> 
> So, here is a list, in no particular order, of the version 2 improvements to date:
> 
> 1. Re-code FOR/NEXT with new opcodes. Uses a little more evaluation stack, but works faster by keeping the terminal value and the working value on the evaluation stack. New opcodes for INCBRLE (increment, branch less than), ADDBRLE (for STEP values other than one), DECBRGE, SUBBRGE (the DOWNTO variants). These opcodes are FOR/NEXT specific and pop the two values off the evaluation stack when the loop terminates. There is a BRGT/BRLT at the top of the FOR/NEXT loop to check for cases where the starting value already exceeds the terminal value. This is optimized out when the values are known a-priori. The only real difference in usage from version 1 is that the loop variable won't have the final value after the loop exits. I only had two instances in my code where this mattered. Easy to work around for a big speed improvement.
> 
> 2. Re-code WHILE/LOOP to test the ending condition at the bottom of the loop instead of the top. This involves one branch to the test before entering the loop, but only one branch at the bottom (much like the REPEAT/UNTIL). The version 1 had the test at the top and required an unconditional branch at the bottom.
> 
> 3. Logical AND and OR are now short-circuiting instead of calculating the entire expression and ANDing/ORing the results together. New branch opcode BRAND and BROR look at the left-hand side of the expression and skip the right-hand side if it can. If not, pop the left-hand side and let the right-hand side be the result.
> 
> 4. All new switch/select/case implementation. A caseblock of values and branch targets lets the entire switch/select/case comparison happen in the VM at once. In version 1, this was a slightly optimized string of IF/THEN/ELSEs. Now, duplicate cases can be flagged for an error (yep, caught a couple in my code). Falling through one case to the next doesn't invovle any penalty like version 1. Max number of cases is 256. That should be enough.
> 
> 5. New BREQ and BRNE opcodes combine the very common ISEQ+BRFLS/BRTU and ISNE+BRFLS/BRTRU sequences.
> 
> 6. More constant opcodes. CN - Constant Nybble, encodes values 0-15 in a single byte. MINUS_ONE ($FFFF) is a single byte opcode. ADDI, SUBI, ANDI, ORI are immediate versions of the ADD, SUB, AND and OR. The immediate value is a byte only (most of the cases).
> 
> 7. One of the most common sequences is a load, followed by ADD (add or indexed byte array) or IDXW (indexed word array). So common, that I experimentally added versions of ADD and IDXW that combined the load value variants. Four new versions of ADD and IDXW from local/global bye/word.  It was a big impact to the VM size but the performance boost was significant so I kept them. It required much reworking of the Apple 3 VM, as it is very spaced constrained the way I have it implementd (6K for CMDSYS+VM). To fit it in the Apple 3, it has a sub-optimal implementation. But the Apple 2 still had room, and it flies.
> 
> 
> Some of these improvements came from re-thinking my approach to code generation with the help of code sequences. FOR/NEXT and WHILE/LOOP were direct consequences of that. The switch/select/case was something I always wanted to fix with a caseblock (the JVM has something very similar). The opcode improvements came from getting statistics on opcode frequqency, then looking for common sequences involving those opcodes. The peephole optimizer then was updated to take advantage of the more efficient opcodes. The basic code generator didn't have to change, just the optimizer. It was interesting to see how the statistics changed with each addition.
> 
> For some perspective, the Sieve of Eratosthenes benchmark on my 64K Apple ][ was able to calculate all 1899 primes in just about 20 seconds on the PLASMA 1.0 Developer Preview. With all the help here, the version 1 release was about 17.5 seconds. Currently, version 2 is just under 15 seconds :-)
> 
> You can check out all the updates and disk images on GitHub: https://github.com/dschmenk/PLASM then select the devel branch.
> 
> Dave...

Wow, those sound like great optimizations Dave!

Any idea how this compares to the older version of PLASMA which could generate native code?

Now I wonder how fast the GS could calc the Sieve benchmark, both native and via bytecode...

-JB

[toc] | [prev] | [next] | [standalone]

#4362

A good candidate for https://rosettacode.org/wiki/Sieve_of_Eratosthenes

[toc] | [prev] | [next] | [standalone]

#4368

On Friday, 16 March 2018 22:18:33 UTC-7, Antoine Vignau  wrote:
> A good candidate for https://rosettacode.org/wiki/Sieve_of_Eratosthenes

Absolutely! I'll submit my PLASMA version and compare with the AppleSoft and 6502 assembly.

Dave...

[toc] | [prev] | [next] | [standalone]

#4367

On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> 
> Wow, those sound like great optimizations Dave!
> 
> Any idea how this compares to the older version of PLASMA which could generate native code?
> 
> Now I wonder how fast the GS could calc the Sieve benchmark, both native and via bytecode...
> 
> -JB

Thanks John - as a matter of fact, I still have a few natively compiled programs on one machine. The easiest to compare is RODs colors. Version 2 runs about 80% the speed of the native version. It is important to note that ROD is very multiply and divide intensive, sort of the great equalizer. But even still, getting pretty close for that case, and its 248 bytes vs ~2K bytes in size.

Generating native 65816/65802 code from byte code seems almost trivial. The only mismatch comes the 6502 centric evaluation stack implementation. The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for evaluation. So it has to copy values back and forth between function calls. Some code that uses a lot of function calls will actually run faster on the 6502, others that use larger and more complex routines like the compiler run much faster on the 65802. Sieve doesn't make many function calls and is compute bound - it would make an excellent candidate for native code generation.

Some of the code crunching I had to do on the Apple 3, and your discussion on code sequence optimizations, really has me thinking on how to take a hybrid approach to a JIT. I am wrapping up some optimizations to the case block processing (I order the case values from lowest to highest so it can early exit if it finds the search value is less than the case value) and then I'm going to start experimenting with native and hybrid code.

Dave...

[toc] | [prev] | [next] | [standalone]

#4369

David Schmenk <dschmenk@gmail.com> wrote:
> On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
>> 
>> Wow, those sound like great optimizations Dave!
>> 
>> Any idea how this compares to the older version of PLASMA which could
>> generate native code?
>> 
>> Now I wonder how fast the GS could calc the Sieve benchmark, both native
>> and via bytecode...
>> 
>> -JB
> 
> Thanks John - as a matter of fact, I still have a few natively compiled
> programs on one machine. The easiest to compare is RODs colors. Version 2
> runs about 80% the speed of the native version. It is important to note
> that ROD is very multiply and divide intensive, sort of the great
> equalizer. But even still, getting pretty close for that case, and its
> 248 bytes vs ~2K bytes in size.
> 
> Generating native 65816/65802 code from byte code seems almost trivial.
> The only mismatch comes the 6502 centric evaluation stack implementation.
> The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for
> evaluation. So it has to copy values back and forth between function
> calls. Some code that uses a lot of function calls will actually run
> faster on the 6502, others that use larger and more complex routines like
> the compiler run much faster on the 65802. Sieve doesn't make many
> function calls and is compute bound - it would make an excellent
> candidate for native code generation.
> 
> Some of the code crunching I had to do on the Apple 3, and your
> discussion on code sequence optimizations, really has me thinking on how
> to take a hybrid approach to a JIT. I am wrapping up some optimizations
> to the case block processing (I order the case values from lowest to
> highest so it can early exit if it finds the search value is less than
> the case value) and then I'm going to start experimenting with native and hybrid code.
> 
> Dave...
> 

A hybrid approach can be extremely beneficial. 

JIT code generation is the “modern” way to do this, allowing a memory limit
to be set and doing the best you can within that limit. 

An older, more participative approach is to allow the programmer to specify
for each procedure whether it should compile to byte code or native code
(or even a threaded hybrid). To determine where it’s worth making the
space-for-speed tradeoff, profiling is provided. 

In the 1960s, the compiler firm Digitek used this approach to build some of
the fastest, most compact compilers ever. 

Since most code spends over 90% of its time in less than 10% of its code, a
relatively small space investment can produce practically native code
performance. 

This is especially true for code that does a lot of error handling or
interaction, since the performance of error handling and interactive  code
is seldom an issue.

-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#4372

On Saturday, 17 March 2018 08:05:18 UTC-7, mjm...@aol.com  wrote:
> David Schmenk <dschmenk@gmail.com> wrote:
> > On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> >> 
> >> Wow, those sound like great optimizations Dave!
> >> 
> >> Any idea how this compares to the older version of PLASMA which could
> >> generate native code?
> >> 
> >> Now I wonder how fast the GS could calc the Sieve benchmark, both native
> >> and via bytecode...
> >> 
> >> -JB
> > 
> > Thanks John - as a matter of fact, I still have a few natively compiled
> > programs on one machine. The easiest to compare is RODs colors. Version 2
> > runs about 80% the speed of the native version. It is important to note
> > that ROD is very multiply and divide intensive, sort of the great
> > equalizer. But even still, getting pretty close for that case, and its
> > 248 bytes vs ~2K bytes in size.
> > 
> > Generating native 65816/65802 code from byte code seems almost trivial.
> > The only mismatch comes the 6502 centric evaluation stack implementation.
> > The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for
> > evaluation. So it has to copy values back and forth between function
> > calls. Some code that uses a lot of function calls will actually run
> > faster on the 6502, others that use larger and more complex routines like
> > the compiler run much faster on the 65802. Sieve doesn't make many
> > function calls and is compute bound - it would make an excellent
> > candidate for native code generation.
> > 
> > Some of the code crunching I had to do on the Apple 3, and your
> > discussion on code sequence optimizations, really has me thinking on how
> > to take a hybrid approach to a JIT. I am wrapping up some optimizations
> > to the case block processing (I order the case values from lowest to
> > highest so it can early exit if it finds the search value is less than
> > the case value) and then I'm going to start experimenting with native and hybrid code.
> > 
> > Dave...
> > 
> 
> A hybrid approach can be extremely beneficial. 
> 
> JIT code generation is the “modern” way to do this, allowing a memory limit
> to be set and doing the best you can within that limit. 
> 
> An older, more participative approach is to allow the programmer to specify
> for each procedure whether it should compile to byte code or native code
> (or even a threaded hybrid). To determine where it’s worth making the
> space-for-speed tradeoff, profiling is provided. 

That was the first approach I took with PLASMA. The downside is that you have to compile to the least common denominator, not knowing which processor variant it will be run on.

> 
> In the 1960s, the compiler firm Digitek used this approach to build some of
> the fastest, most compact compilers ever. 
> 

My good friend, Tom Lahey, worked at Digitek implementing their early FORTAN compilers before starting Lahey Computer Systems. We often discuss compiler tech at our Thursday morning coffee meetings. Well ahead of the times with their technology.

> Since most code spends over 90% of its time in less than 10% of its code, a
> relatively small space investment can produce practically native code
> performance. 
> 

It will be an interesting tradeoff in speed/size. I really like the density byte code provides. The speedup is going to have to be significant to make it worthwhile. I made it easy to write routines in assembly, but even there, assembly takes up so much more space.

> This is especially true for code that does a lot of error handling or
> interaction, since the performance of error handling and interactive  code
> is seldom an issue.

Hopefully having a library of optimized routines will cover 90% of the performance cases.  I think the self-hosted PLASMA compiler is going to be the test case for experimentation.

> 
> -- 
> -michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

You headed up the  RISC-PA compiler group at HP, right? 

Dave...

[toc] | [prev] | [next] | [standalone]

#4373

David Schmenk <dschmenk@gmail.com> wrote:
> On Saturday, 17 March 2018 08:05:18 UTC-7, mjm...@aol.com  wrote:
>> David Schmenk <dschmenk@gmail.com> wrote:
>>> On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
>>>> 
>>>> Wow, those sound like great optimizations Dave!
>>>> 
>>>> Any idea how this compares to the older version of PLASMA which could
>>>> generate native code?
>>>> 
>>>> Now I wonder how fast the GS could calc the Sieve benchmark, both native
>>>> and via bytecode...
>>>> 
>>>> -JB
>>> 
>>> Thanks John - as a matter of fact, I still have a few natively compiled
>>> programs on one machine. The easiest to compare is RODs colors. Version 2
>>> runs about 80% the speed of the native version. It is important to note
>>> that ROD is very multiply and divide intensive, sort of the great
>>> equalizer. But even still, getting pretty close for that case, and its
>>> 248 bytes vs ~2K bytes in size.
>>> 
>>> Generating native 65816/65802 code from byte code seems almost trivial.
>>> The only mismatch comes the 6502 centric evaluation stack implementation.
>>> The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for
>>> evaluation. So it has to copy values back and forth between function
>>> calls. Some code that uses a lot of function calls will actually run
>>> faster on the 6502, others that use larger and more complex routines like
>>> the compiler run much faster on the 65802. Sieve doesn't make many
>>> function calls and is compute bound - it would make an excellent
>>> candidate for native code generation.
>>> 
>>> Some of the code crunching I had to do on the Apple 3, and your
>>> discussion on code sequence optimizations, really has me thinking on how
>>> to take a hybrid approach to a JIT. I am wrapping up some optimizations
>>> to the case block processing (I order the case values from lowest to
>>> highest so it can early exit if it finds the search value is less than
>>> the case value) and then I'm going to start experimenting with native and hybrid code.
>>> 
>>> Dave...
>>> 
>> 
>> A hybrid approach can be extremely beneficial. 
>> 
>> JIT code generation is the “modern” way to do this, allowing a memory limit
>> to be set and doing the best you can within that limit. 
>> 
>> An older, more participative approach is to allow the programmer to specify
>> for each procedure whether it should compile to byte code or native code
>> (or even a threaded hybrid). To determine where it’s worth making the
>> space-for-speed tradeoff, profiling is provided. 
> 
> That was the first approach I took with PLASMA. The downside is that you
> have to compile to the least common denominator, not knowing which
> processor variant it will be run on.

Clearly, the compiler needs to know the target, either implicitly, because
this version compiles to this platform, or because the “compile” directive
specifies the target. 

>> In the 1960s, the compiler firm Digitek used this approach to build some of
>> the fastest, most compact compilers ever. 
>> 
> 
> My good friend, Tom Lahey, worked at Digitek implementing their early
> FORTAN compilers before starting Lahey Computer Systems. We often discuss
> compiler tech at our Thursday morning coffee meetings. Well ahead of the
> times with their technology.

Indeed!  Their technology was inspired by their first FORTRAN compiler for
the SDS 940, which implemented “Programmed OPerators” (POPs) that vectored
to software implementations. 

After producing a very compact compiler that ran entirely in memory faster
than any other compiler for the machine, their reputation spread quickly.
;-) And they realized that their architecture could be implemented without
relying on hardware-supported POP calls.

>> Since most code spends over 90% of its time in less than 10% of its code, a
>> relatively small space investment can produce practically native code
>> performance. 
>> 
> 
> It will be an interesting tradeoff in speed/size. I really like the
> density byte code provides. The speedup is going to have to be
> significant to make it worthwhile. I made it easy to write routines in
> assembly, but even there, assembly takes up so much more space.

Let’s say that native code is ten times larger than bytecode, but five
times faster. Then if 10% of an app is compiled to native code, resulting
in what was 90% of the execution time running in one-fifth the time, the
app now runs in (10+90/5)/100 of the original time, or 0.3 of the original
time and the application size is 10%*5 + 90%, or 140% of its original size.


Three times faster for a 40% increase in size is a good tradeoff if there
is sufficient memory. 

>> This is especially true for code that does a lot of error handling or
>> interaction, since the performance of error handling and interactive  code
>> is seldom an issue.
> 
> Hopefully having a library of optimized routines will cover 90% of the
> performance cases.  I think the self-hosted PLASMA compiler is going to
> be the test case for experimentation.

That’s a great test case, and the natural choice. 
>> 
>> -- 
>> -michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com
> 
> You headed up the  RISC-PA compiler group at HP, right? 

Yes, it was my privilege to lead the PA-RISC architecture team, but it was
a joint effort of very talented team members. 

We made all our decisions based on performance / complexity measurements
for a large sample of application code (thus the “precision” of Precision
Architecture), and we always worked to consensus, never “majority rules”.
(In fact, I consider this the distinction between a team and a committee.
;-)

I also led the HP-UX (Unix) lab in the beginning, and the compiler lab up
until the first release. It is a humbling and very rewarding experience to
work with such excellent people. 

-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#4375

On Saturday, 17 March 2018 22:59:18 UTC-7, mjm...@aol.com  wrote:
> David Schmenk <dschmenk@gmail.com> wrote:
> > On Saturday, 17 March 2018 08:05:18 UTC-7, mjm...@aol.com  wrote:
> >> David Schmenk <dschmenk@gmail.com> wrote:
> >>> On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> >>>> 
> >>>> Wow, those sound like great optimizations Dave!
> >>>> 
> >>>> Any idea how this compares to the older version of PLASMA which could
> >>>> generate native code?
> >>>> 
> >>>> Now I wonder how fast the GS could calc the Sieve benchmark, both native
> >>>> and via bytecode...
> >>>> 
> >>>> -JB
> >>> 
> >>> Thanks John - as a matter of fact, I still have a few natively compiled
> >>> programs on one machine. The easiest to compare is RODs colors. Version 2
> >>> runs about 80% the speed of the native version. It is important to note
> >>> that ROD is very multiply and divide intensive, sort of the great
> >>> equalizer. But even still, getting pretty close for that case, and its
> >>> 248 bytes vs ~2K bytes in size.
> >>> 
> >>> Generating native 65816/65802 code from byte code seems almost trivial.
> >>> The only mismatch comes the 6502 centric evaluation stack implementation.
> >>> The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for
> >>> evaluation. So it has to copy values back and forth between function
> >>> calls. Some code that uses a lot of function calls will actually run
> >>> faster on the 6502, others that use larger and more complex routines like
> >>> the compiler run much faster on the 65802. Sieve doesn't make many
> >>> function calls and is compute bound - it would make an excellent
> >>> candidate for native code generation.
> >>> 
> >>> Some of the code crunching I had to do on the Apple 3, and your
> >>> discussion on code sequence optimizations, really has me thinking on how
> >>> to take a hybrid approach to a JIT. I am wrapping up some optimizations
> >>> to the case block processing (I order the case values from lowest to
> >>> highest so it can early exit if it finds the search value is less than
> >>> the case value) and then I'm going to start experimenting with native and hybrid code.
> >>> 
> >>> Dave...
> >>> 
> >> 
> >> A hybrid approach can be extremely beneficial. 
> >> 
> >> JIT code generation is the “modern” way to do this, allowing a memory limit
> >> to be set and doing the best you can within that limit. 
> >> 
> >> An older, more participative approach is to allow the programmer to specify
> >> for each procedure whether it should compile to byte code or native code
> >> (or even a threaded hybrid). To determine where it’s worth making the
> >> space-for-speed tradeoff, profiling is provided. 
> > 
> > That was the first approach I took with PLASMA. The downside is that you
> > have to compile to the least common denominator, not knowing which
> > processor variant it will be run on.
> 
> Clearly, the compiler needs to know the target, either implicitly, because
> this version compiles to this platform, or because the “compile” directive
> specifies the target. 
> 
> >> In the 1960s, the compiler firm Digitek used this approach to build some of
> >> the fastest, most compact compilers ever. 
> >> 
> > 
> > My good friend, Tom Lahey, worked at Digitek implementing their early
> > FORTAN compilers before starting Lahey Computer Systems. We often discuss
> > compiler tech at our Thursday morning coffee meetings. Well ahead of the
> > times with their technology.
> 
> Indeed!  Their technology was inspired by their first FORTRAN compiler for
> the SDS 940, which implemented “Programmed OPerators” (POPs) that vectored
> to software implementations. 
> 
> After producing a very compact compiler that ran entirely in memory faster
> than any other compiler for the machine, their reputation spread quickly.
> ;-) And they realized that their architecture could be implemented without
> relying on hardware-supported POP calls.
> 
> >> Since most code spends over 90% of its time in less than 10% of its code, a
> >> relatively small space investment can produce practically native code
> >> performance. 
> >> 
> > 
> > It will be an interesting tradeoff in speed/size. I really like the
> > density byte code provides. The speedup is going to have to be
> > significant to make it worthwhile. I made it easy to write routines in
> > assembly, but even there, assembly takes up so much more space.
> 
> Let’s say that native code is ten times larger than bytecode, but five
> times faster. Then if 10% of an app is compiled to native code, resulting
> in what was 90% of the execution time running in one-fifth the time, the
> app now runs in (10+90/5)/100 of the original time, or 0.3 of the original
> time and the application size is 10%*5 + 90%, or 140% of its original size.
> 
> 
> Three times faster for a 40% increase in size is a good tradeoff if there
> is sufficient memory. 
> 
> >> This is especially true for code that does a lot of error handling or
> >> interaction, since the performance of error handling and interactive  code
> >> is seldom an issue.
> > 
> > Hopefully having a library of optimized routines will cover 90% of the
> > performance cases.  I think the self-hosted PLASMA compiler is going to
> > be the test case for experimentation.
> 
> That’s a great test case, and the natural choice. 
> >> 
> >> -- 
> >> -michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com
> > 
> > You headed up the  RISC-PA compiler group at HP, right? 
> 
> Yes, it was my privilege to lead the PA-RISC architecture team, but it was
> a joint effort of very talented team members. 
> 
> We made all our decisions based on performance / complexity measurements
> for a large sample of application code (thus the “precision” of Precision
> Architecture), and we always worked to consensus, never “majority rules”.
> (In fact, I consider this the distinction between a team and a committee.
> ;-)
> 
> I also led the HP-UX (Unix) lab in the beginning, and the compiler lab up
> until the first release. It is a humbling and very rewarding experience to
> work with such excellent people. 
> 
> -- 
> -michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

You should join Tom and me for Thursday morning coffee! We'd probably be there all day.

Dave...

[toc] | [prev] | [next] | [standalone]

#4403

David Schmenk <dschmenk@gmail.com> wrote:
> On Saturday, 17 March 2018 22:59:18 UTC-7, mjm...@aol.com  wrote:
>> David Schmenk <dschmenk@gmail.com> wrote:
>>> On Saturday, 17 March 2018 08:05:18 UTC-7, mjm...@aol.com  wrote:
>>>> David Schmenk <dschmenk@gmail.com> wrote:
>>>>> On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
>>>>>> 
>>>>>> Wow, those sound like great optimizations Dave!
>>>>>> 
>>>>>> Any idea how this compares to the older version of PLASMA which could
>>>>>> generate native code?
>>>>>> 
>>>>>> Now I wonder how fast the GS could calc the Sieve benchmark, both native
>>>>>> and via bytecode...
>>>>>> 
>>>>>> -JB
>>>>> 
>>>>> Thanks John - as a matter of fact, I still have a few natively compiled
>>>>> programs on one machine. The easiest to compare is RODs colors. Version 2
>>>>> runs about 80% the speed of the native version. It is important to note
>>>>> that ROD is very multiply and divide intensive, sort of the great
>>>>> equalizer. But even still, getting pretty close for that case, and its
>>>>> 248 bytes vs ~2K bytes in size.
>>>>> 
>>>>> Generating native 65816/65802 code from byte code seems almost trivial.
>>>>> The only mismatch comes the 6502 centric evaluation stack implementation.
>>>>> The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for
>>>>> evaluation. So it has to copy values back and forth between function
>>>>> calls. Some code that uses a lot of function calls will actually run
>>>>> faster on the 6502, others that use larger and more complex routines like
>>>>> the compiler run much faster on the 65802. Sieve doesn't make many
>>>>> function calls and is compute bound - it would make an excellent
>>>>> candidate for native code generation.
>>>>> 
>>>>> Some of the code crunching I had to do on the Apple 3, and your
>>>>> discussion on code sequence optimizations, really has me thinking on how
>>>>> to take a hybrid approach to a JIT. I am wrapping up some optimizations
>>>>> to the case block processing (I order the case values from lowest to
>>>>> highest so it can early exit if it finds the search value is less than
>>>>> the case value) and then I'm going to start experimenting with native and hybrid code.
>>>>> 
>>>>> Dave...
>>>>> 
>>>> 
>>>> A hybrid approach can be extremely beneficial. 
>>>> 
>>>> JIT code generation is the “modern” way to do this, allowing a memory limit
>>>> to be set and doing the best you can within that limit. 
>>>> 
>>>> An older, more participative approach is to allow the programmer to specify
>>>> for each procedure whether it should compile to byte code or native code
>>>> (or even a threaded hybrid). To determine where it’s worth making the
>>>> space-for-speed tradeoff, profiling is provided. 
>>> 
>>> That was the first approach I took with PLASMA. The downside is that you
>>> have to compile to the least common denominator, not knowing which
>>> processor variant it will be run on.
>> 
>> Clearly, the compiler needs to know the target, either implicitly, because
>> this version compiles to this platform, or because the “compile” directive
>> specifies the target. 
>> 
>>>> In the 1960s, the compiler firm Digitek used this approach to build some of
>>>> the fastest, most compact compilers ever. 
>>>> 
>>> 
>>> My good friend, Tom Lahey, worked at Digitek implementing their early
>>> FORTAN compilers before starting Lahey Computer Systems. We often discuss
>>> compiler tech at our Thursday morning coffee meetings. Well ahead of the
>>> times with their technology.
>> 
>> Indeed!  Their technology was inspired by their first FORTRAN compiler for
>> the SDS 940, which implemented “Programmed OPerators” (POPs) that vectored
>> to software implementations. 
>> 
>> After producing a very compact compiler that ran entirely in memory faster
>> than any other compiler for the machine, their reputation spread quickly.
>> ;-) And they realized that their architecture could be implemented without
>> relying on hardware-supported POP calls.
>> 
>>>> Since most code spends over 90% of its time in less than 10% of its code, a
>>>> relatively small space investment can produce practically native code
>>>> performance. 
>>>> 
>>> 
>>> It will be an interesting tradeoff in speed/size. I really like the
>>> density byte code provides. The speedup is going to have to be
>>> significant to make it worthwhile. I made it easy to write routines in
>>> assembly, but even there, assembly takes up so much more space.
>> 
>> Let’s say that native code is ten times larger than bytecode, but five
>> times faster. Then if 10% of an app is compiled to native code, resulting
>> in what was 90% of the execution time running in one-fifth the time, the
>> app now runs in (10+90/5)/100 of the original time, or 0.3 of the original
>> time and the application size is 10%*5 + 90%, or 140% of its original size.
>> 
>> 
>> Three times faster for a 40% increase in size is a good tradeoff if there
>> is sufficient memory. 
>> 
>>>> This is especially true for code that does a lot of error handling or
>>>> interaction, since the performance of error handling and interactive  code
>>>> is seldom an issue.
>>> 
>>> Hopefully having a library of optimized routines will cover 90% of the
>>> performance cases.  I think the self-hosted PLASMA compiler is going to
>>> be the test case for experimentation.
>> 
>> That’s a great test case, and the natural choice. 
>>>> 
>>>> -- 
>>>> -michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com
>>> 
>>> You headed up the  RISC-PA compiler group at HP, right? 
>> 
>> Yes, it was my privilege to lead the PA-RISC architecture team, but it was
>> a joint effort of very talented team members. 
>> 
>> We made all our decisions based on performance / complexity measurements
>> for a large sample of application code (thus the “precision” of Precision
>> Architecture), and we always worked to consensus, never “majority rules”.
>> (In fact, I consider this the distinction between a team and a committee.
>> ;-)
>> 
>> I also led the HP-UX (Unix) lab in the beginning, and the compiler lab up
>> until the first release. It is a humbling and very rewarding experience to
>> work with such excellent people. 
>> 
>> -- 
>> -michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com
> 
> You should join Tom and me for Thursday morning coffee! We'd probably be there all day.
> 
> Dave...
> 

;-)

-- 
-michael - NadaNet 3.1 and AppleCrate II:  http://michaeljmahon.com

[toc] | [prev] | [next] | [standalone]

#4374

On Saturday, March 17, 2018 at 7:34:29 AM UTC-7, David Schmenk wrote:
> On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> > 
> > Wow, those sound like great optimizations Dave!
> > 
> > Any idea how this compares to the older version of PLASMA which could generate native code?
> > 
> > Now I wonder how fast the GS could calc the Sieve benchmark, both native and via bytecode...
> > 
> > -JB
> 
> Thanks John - as a matter of fact, I still have a few natively compiled programs on one machine. The easiest to compare is RODs colors. Version 2 runs about 80% the speed of the native version. It is important to note that ROD is very multiply and divide intensive, sort of the great equalizer. But even still, getting pretty close for that case, and its 248 bytes vs ~2K bytes in size.
> 
> Generating native 65816/65802 code from byte code seems almost trivial. The only mismatch comes the 6502 centric evaluation stack implementation. The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for evaluation. So it has to copy values back and forth between function calls. Some code that uses a lot of function calls will actually run faster on the 6502, others that use larger and more complex routines like the compiler run much faster on the 65802. Sieve doesn't make many function calls and is compute bound - it would make an excellent candidate for native code generation.
> 
> Some of the code crunching I had to do on the Apple 3, and your discussion on code sequence optimizations, really has me thinking on how to take a hybrid approach to a JIT. I am wrapping up some optimizations to the case block processing (I order the case values from lowest to highest so it can early exit if it finds the search value is less than the case value) and then I'm going to start experimenting with native and hybrid code.
> 
> Dave...

Couldn't the 65816 runtime also use zero page expression eval instead of the stack? Wouldn't that be faster?

My 65816 assembly sieve code takes ~25ms (40 sieves per second on the GS).

-JB

[toc] | [prev] | [next] | [standalone]

#4376

On Sunday, 18 March 2018 01:10:56 UTC-7, John Brooks  wrote:
> On Saturday, March 17, 2018 at 7:34:29 AM UTC-7, David Schmenk wrote:
> > On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> > > 
> > > Wow, those sound like great optimizations Dave!
> > > 
> > > Any idea how this compares to the older version of PLASMA which could generate native code?
> > > 
> > > Now I wonder how fast the GS could calc the Sieve benchmark, both native and via bytecode...
> > > 
> > > -JB
> > 
> > Thanks John - as a matter of fact, I still have a few natively compiled programs on one machine. The easiest to compare is RODs colors. Version 2 runs about 80% the speed of the native version. It is important to note that ROD is very multiply and divide intensive, sort of the great equalizer. But even still, getting pretty close for that case, and its 248 bytes vs ~2K bytes in size.
> > 
> > Generating native 65816/65802 code from byte code seems almost trivial. The only mismatch comes the 6502 centric evaluation stack implementation. The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for evaluation. So it has to copy values back and forth between function calls. Some code that uses a lot of function calls will actually run faster on the 6502, others that use larger and more complex routines like the compiler run much faster on the 65802. Sieve doesn't make many function calls and is compute bound - it would make an excellent candidate for native code generation.
> > 
> > Some of the code crunching I had to do on the Apple 3, and your discussion on code sequence optimizations, really has me thinking on how to take a hybrid approach to a JIT. I am wrapping up some optimizations to the case block processing (I order the case values from lowest to highest so it can early exit if it finds the search value is less than the case value) and then I'm going to start experimenting with native and hybrid code.
> > 
> > Dave...
> 
> Couldn't the 65816 runtime also use zero page expression eval instead of the stack? Wouldn't that be faster?

This was the big decision when I implemented the 65802 VM. What worked really well on the 6502, a zero page split LSB/MSB stack, didn't offer much opportunity for the 16 bit operations of the 65802. One of the things that confounded me with the 65802 was the pain of loading an 8 bit value into a 16 bit accumulator. The 65802 did add a bunch of nice HW stack operations. Most of the PLASMA opcodes match very nicely to these instructions. Since PLASMA doesn't know if a function call is to a 6502 native routine or a PLASMA routine, the 65802 version has to build the zero page eval stack from the HW stack. Maybe its time to sick qkumba on it.

> 
> My 65816 assembly sieve code takes ~25ms (40 sieves per second on the GS).

:-) So your saying there's a chance?!?! (with apologies to Dumb and Dumber).

> 
> -JB

Dave....

[toc] | [prev] | [next] | [standalone]

#4377

On Sunday, March 18, 2018 at 8:06:07 AM UTC-7, David Schmenk wrote:
> On Sunday, 18 March 2018 01:10:56 UTC-7, John Brooks  wrote:
> > On Saturday, March 17, 2018 at 7:34:29 AM UTC-7, David Schmenk wrote:
> > > On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> > > > 
> > > > Wow, those sound like great optimizations Dave!
> > > > 
> > > > Any idea how this compares to the older version of PLASMA which could generate native code?
> > > > 
> > > > Now I wonder how fast the GS could calc the Sieve benchmark, both native and via bytecode...
> > > > 
> > > > -JB
> > > 
> > > Thanks John - as a matter of fact, I still have a few natively compiled programs on one machine. The easiest to compare is RODs colors. Version 2 runs about 80% the speed of the native version. It is important to note that ROD is very multiply and divide intensive, sort of the great equalizer. But even still, getting pretty close for that case, and its 248 bytes vs ~2K bytes in size.
> > > 
> > > Generating native 65816/65802 code from byte code seems almost trivial. The only mismatch comes the 6502 centric evaluation stack implementation. The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for evaluation. So it has to copy values back and forth between function calls. Some code that uses a lot of function calls will actually run faster on the 6502, others that use larger and more complex routines like the compiler run much faster on the 65802. Sieve doesn't make many function calls and is compute bound - it would make an excellent candidate for native code generation.
> > > 
> > > Some of the code crunching I had to do on the Apple 3, and your discussion on code sequence optimizations, really has me thinking on how to take a hybrid approach to a JIT. I am wrapping up some optimizations to the case block processing (I order the case values from lowest to highest so it can early exit if it finds the search value is less than the case value) and then I'm going to start experimenting with native and hybrid code.
> > > 
> > > Dave...
> > 
> > Couldn't the 65816 runtime also use zero page expression eval instead of the stack? Wouldn't that be faster?
> 
> This was the big decision when I implemented the 65802 VM. What worked really well on the 6502, a zero page split LSB/MSB stack, didn't offer much opportunity for the 16 bit operations of the 65802. One of the things that confounded me with the 65802 was the pain of loading an 8 bit value into a 16 bit accumulator. The 65802 did add a bunch of nice HW stack operations. Most of the PLASMA opcodes match very nicely to these instructions. Since PLASMA doesn't know if a function call is to a 6502 native routine or a PLASMA routine, the 65802 version has to build the zero page eval stack from the HW stack. Maybe its time to sick qkumba on it.
> 
> > 
> > My 65816 assembly sieve code takes ~25ms (40 sieves per second on the GS).
> 
> :-) So your saying there's a chance?!?! (with apologies to Dumb and Dumber).
> 
> > 
> > -JB
> 
> Dave....

Here is the sieve benchmark optimized for the GS:

https://groups.google.com/forum/#!topic/comp.sys.apple2/aMK1OjyVjxI

-JB

[toc] | [prev] | [next] | [standalone]

#4379

On Sunday, 18 March 2018 12:20:40 UTC-7, John Brooks  wrote:
> On Sunday, March 18, 2018 at 8:06:07 AM UTC-7, David Schmenk wrote:
> > On Sunday, 18 March 2018 01:10:56 UTC-7, John Brooks  wrote:
> > > On Saturday, March 17, 2018 at 7:34:29 AM UTC-7, David Schmenk wrote:
> > > > On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> > > > > 
> > > > > Wow, those sound like great optimizations Dave!
> > > > > 
> > > > > Any idea how this compares to the older version of PLASMA which could generate native code?
> > > > > 
> > > > > Now I wonder how fast the GS could calc the Sieve benchmark, both native and via bytecode...
> > > > > 
> > > > > -JB
> > > > 
> > > > Thanks John - as a matter of fact, I still have a few natively compiled programs on one machine. The easiest to compare is RODs colors. Version 2 runs about 80% the speed of the native version. It is important to note that ROD is very multiply and divide intensive, sort of the great equalizer. But even still, getting pretty close for that case, and its 248 bytes vs ~2K bytes in size.
> > > > 
> > > > Generating native 65816/65802 code from byte code seems almost trivial. The only mismatch comes the 6502 centric evaluation stack implementation. The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for evaluation. So it has to copy values back and forth between function calls. Some code that uses a lot of function calls will actually run faster on the 6502, others that use larger and more complex routines like the compiler run much faster on the 65802. Sieve doesn't make many function calls and is compute bound - it would make an excellent candidate for native code generation.
> > > > 
> > > > Some of the code crunching I had to do on the Apple 3, and your discussion on code sequence optimizations, really has me thinking on how to take a hybrid approach to a JIT. I am wrapping up some optimizations to the case block processing (I order the case values from lowest to highest so it can early exit if it finds the search value is less than the case value) and then I'm going to start experimenting with native and hybrid code.
> > > > 
> > > > Dave...
> > > 
> > > Couldn't the 65816 runtime also use zero page expression eval instead of the stack? Wouldn't that be faster?
> > 
> > This was the big decision when I implemented the 65802 VM. What worked really well on the 6502, a zero page split LSB/MSB stack, didn't offer much opportunity for the 16 bit operations of the 65802. One of the things that confounded me with the 65802 was the pain of loading an 8 bit value into a 16 bit accumulator. The 65802 did add a bunch of nice HW stack operations. Most of the PLASMA opcodes match very nicely to these instructions. Since PLASMA doesn't know if a function call is to a 6502 native routine or a PLASMA routine, the 65802 version has to build the zero page eval stack from the HW stack. Maybe its time to sick qkumba on it.
> > 
> > > 
> > > My 65816 assembly sieve code takes ~25ms (40 sieves per second on the GS).
> > 
> > :-) So your saying there's a chance?!?! (with apologies to Dumb and Dumber).
> > 
> > > 
> > > -JB
> > 
> > Dave....
> 
> Here is the sieve benchmark optimized for the GS:
> 
> https://groups.google.com/forum/#!topic/comp.sys.apple2/aMK1OjyVjxI
> 
> -JB

You won on speed, but PLASMA is only 150 bytes ;-) That is, quite possibly, the most obscure assembly code I've ever seen. And I've worked on Windows display drivers.

Dave...

[toc] | [prev] | [next] | [standalone]

#4380

On Sunday, March 18, 2018 at 1:56:20 PM UTC-7, David Schmenk wrote:
> On Sunday, 18 March 2018 12:20:40 UTC-7, John Brooks  wrote:
> > On Sunday, March 18, 2018 at 8:06:07 AM UTC-7, David Schmenk wrote:
> > > On Sunday, 18 March 2018 01:10:56 UTC-7, John Brooks  wrote:
> > > > On Saturday, March 17, 2018 at 7:34:29 AM UTC-7, David Schmenk wrote:
> > > > > On Friday, 16 March 2018 18:00:58 UTC-7, John Brooks  wrote:
> > > > > > 
> > > > > > Wow, those sound like great optimizations Dave!
> > > > > > 
> > > > > > Any idea how this compares to the older version of PLASMA which could generate native code?
> > > > > > 
> > > > > > Now I wonder how fast the GS could calc the Sieve benchmark, both native and via bytecode...
> > > > > > 
> > > > > > -JB
> > > > > 
> > > > > Thanks John - as a matter of fact, I still have a few natively compiled programs on one machine. The easiest to compare is RODs colors. Version 2 runs about 80% the speed of the native version. It is important to note that ROD is very multiply and divide intensive, sort of the great equalizer. But even still, getting pretty close for that case, and its 248 bytes vs ~2K bytes in size.
> > > > > 
> > > > > Generating native 65816/65802 code from byte code seems almost trivial. The only mismatch comes the 6502 centric evaluation stack implementation. The 6502 uses a ZP evaluation stack and the 65802 uses the HW stack for evaluation. So it has to copy values back and forth between function calls. Some code that uses a lot of function calls will actually run faster on the 6502, others that use larger and more complex routines like the compiler run much faster on the 65802. Sieve doesn't make many function calls and is compute bound - it would make an excellent candidate for native code generation.
> > > > > 
> > > > > Some of the code crunching I had to do on the Apple 3, and your discussion on code sequence optimizations, really has me thinking on how to take a hybrid approach to a JIT. I am wrapping up some optimizations to the case block processing (I order the case values from lowest to highest so it can early exit if it finds the search value is less than the case value) and then I'm going to start experimenting with native and hybrid code.
> > > > > 
> > > > > Dave...
> > > > 
> > > > Couldn't the 65816 runtime also use zero page expression eval instead of the stack? Wouldn't that be faster?
> > > 
> > > This was the big decision when I implemented the 65802 VM. What worked really well on the 6502, a zero page split LSB/MSB stack, didn't offer much opportunity for the 16 bit operations of the 65802. One of the things that confounded me with the 65802 was the pain of loading an 8 bit value into a 16 bit accumulator. The 65802 did add a bunch of nice HW stack operations. Most of the PLASMA opcodes match very nicely to these instructions. Since PLASMA doesn't know if a function call is to a 6502 native routine or a PLASMA routine, the 65802 version has to build the zero page eval stack from the HW stack. Maybe its time to sick qkumba on it.
> > > 
> > > > 
> > > > My 65816 assembly sieve code takes ~25ms (40 sieves per second on the GS).
> > > 
> > > :-) So your saying there's a chance?!?! (with apologies to Dumb and Dumber).
> > > 
> > > > 
> > > > -JB
> > > 
> > > Dave....
> > 
> > Here is the sieve benchmark optimized for the GS:
> > 
> > https://groups.google.com/forum/#!topic/comp.sys.apple2/aMK1OjyVjxI
> > 
> > -JB
> 
> You won on speed, but PLASMA is only 150 bytes ;-) That is, quite possibly, the most obscure assembly code I've ever seen. And I've worked on Windows display drivers.
> 
> Dave...

Removing both the unrolled and self-modified code slows the sieve code by 2x, but the size drops to 66 bytes. See the post in the other thread for code & details.

The sieve algorithm fits the 65816 instruction set pretty nicely.

-JB
@JBrooksBSI

[toc] | [prev] | [next] | [standalone]

#4422

PLASMA 2.0 gets a JIT compiler

The Holy Grail of interpreted languages has come to PLASMA. A JIT (Just In Time) compiler that compiles PLASMA bytecode to optimized 6502 machine code on the fly is working in the 2.0 development branch. This was a slightly non-trivial task given the challenges of working on such a limited environment, but it was definitely an interesting exercise. I thought I would share the implementation for your enjoyment.

First off, I'm working on the PLASM 2.0 development branch on GitHub. The relevant file is: https://github.com/dschmenk/PLASMA/blob/devel/src/libsrc/apple/jit.pla

The requirement for JIT compiling is a 128K Apple //e or //c. I'll get it working on the Apple /// later, with a 65802 version after that.

The JIT compiler is simply a PLASMA module loaded at boot time that sits as a wedge between the VM and running modules. The VM will invoke the JIT compiler when it matches a set of criteria for a routine, compiling the bytecode routine to native 6502, patching the function call, and calling the newly minted 6502 routine.

Here are the gory details:

When PLASMA loads a module, it creates a stub function for each bytecode routine that simply calls a page 3 vector. The page 3 vector enables the Language Card (where the VM resides) and calls into the VM. The VM extracts the bytecode address from the call address. Because PLASMA can execute bytecode out of Auxiliary, or extended memory, it needs an address for the routine in Main, or global memory. The reason is that any routine can be implemented in machine code (residing in main/global memory) or bytecode (in any meory). But addresses have to be in main/global memory, so the stub provides the main/global address for bytecode routines. With the JIT version of PLASMA, this stub is slightly expanded to contain some runtime statistics and point to a page 3 vector that jumps to the JIT interpreter entrypoint.

The JIT VM has three tuneable parameters it uses for determining when to call the JIT compiler: warmup count, call count, and maximum routine size. During load time, each routine size is calculated and checked against a maximum value. If too big, it is just interpreted. Otherwise, it's stub points to the JIT VM, and it's call count is initialized. Every time a module is loaded, the warmup count is reset in anticipation of initialization code being called. Tuning these three values gives great control of when the JIT compiler will be activated.

When a function is called, it vectors to the VMs JIT interpreter entrypoint that first checks the warmup counter. If not zero, it decrements it. Once that warmup counter reaches zero, it will then count down a per-routine counter. Before the counters reach zero, the VM simpy interprets the bytecode routine like normal. Once the per-routine counter reaches zero, the VM calls the JIT compiler.

The JIT compiler is given a buffer (about 4K currently) that is set aside at boot time for the compilation destination. Once it is full, all other routines passed to the JIT entrypoint are simply patched to call the normal interpreter entrypoint, never to bother the JIT compiler again. The JIT compiler has to do a little housekeeping before jumping into to compiling the bytecodes. First, the bytecode routine is copied out of Auxiliary RAM into a temp buffer. Second, the routine is scanned, looking for all the branch destinations. This is required so that later compiler optimizations know where the optimization fences are. It also has to mark where data is while scanning executable code. Once the housekeeping is done, the fun starts.

There are three type of optimizations done by the compiler to improve the quality of generated code. First, the Y register is loaded with zero at the beginning of the routine and used often for filling MSBytes of byte values. Certain operations will temporarilly use Y, but quickly reload it with zero. The 65C02 CPU does have some handy STZ opcodes for storing zero to memory, but the 6502 doesn't. It turns out that using Y for zero has a lot of uses and a significant performance enhancement. The bytecode interpreter uses Y as a LSByte for the Emulated Instruction Pointer, but that isn't required for native code. I don't see any reason to make a 65C02 specific version of the compiler.

Second, the Evaluation Stack Pointer is virtualized. The X register contains the ESP, 
and in normal operation is incremented and decremented as values are pushed and popped. This operation can be virtualized and the address of the stack can be manipulated to access the stack values. Only when optimization fences or control flow changes does the virtual stack pointer and the X register need to be synced. This saves a great deal of X register thrashing that is so common in stack based VMs.

Third, the Accuulator caches the LSByte of the Top-Of-Evaluation-Stack. Often, the LSByte of the TOS never has to be fetched from or stored to the stack. Especially when operating on BYTE sized memory values, the compiler is particularly efficient.

Lastly, the instruction set and compiler for PLASMA have significanlty improved for version 2.0. Some of these improvements were with native code generation in mind, even while helping interpreter performance.

There is still a lot to do. The JIT compiler module is about 14K which is pretty big. I haven't spent any time working on size, getting it functional was hard enough. Now though, I have a target of less than 8K which I think that is doable. I believe the Apple II will have a JIT enabled VM for 128K machines, and the regular VM for all machines. The Apple /// will always have the JIT compiler integrated once 2.0 releases. And then I have to experiment with the 65802/65816 version. That should prove enlightening.

Dave...

[toc] | [prev] | [next] | [standalone]

#4423

Great work!
av

[toc] | [prev] | [next] | [standalone]

#4431

On Friday, 23 March 2018 14:07:33 UTC-7, Antoine Vignau  wrote:
> Great work!
> av

Thanks Antoine. I know you and Dagen are waiting for the IIGS version.

Dave...

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.sys.apple2.programmer

csiph-web