6502.org • View topic - vino816 Forth design

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Forth

All times are UTC

vino816 Forth design

Page 2 of 3

[ 37 posts ]

Go to page Previous 1, 2, 3 Next

Previous topic | Next topic

Author

Message

Hugh Aguilar

Post subject: Re: vino816 Forth design

Posted: Sun Apr 29, 2018 6:37 pm

Joined: Fri Jun 03, 2016 3:42 am
Posts: 158

barrym95838 wrote:

According to Dr. Brad, Phil Koopman did a study of how often Forth primitives get executed in some "benchmark Forth programs", whatever that means:

1. ENTER (12.21%)
2. EXIT (11.74%)
3. VARIABLE (5.46%)
4. @ (5.40%)
5. 0BRANCH (4.78%)
6. LIT (4.54%)
7. + (4.18%)
8. SWAP (3.90%)
9. R> (3.89%)
10. >R (3.87%)
11. CONSTANT (3.68%)
12. DUP (3.05%)

Note that ENTER, EXIT, R>, and >R combined add up to almost 32% of primitive executions.

I don't know as much as I would like about Forth programming, but if that list is correct, I hesitate to allow myself to be convinced that your PSP in S design is more efficient than PSP in X for STC (even if your compiler is very clever). I started to test-code some comparison primitives so I could hand-compile a small program both ways, but it got too late, so I'll just post this thought and try to share some code tomorrow if I have time between errands.

I wouldn't put too much stock in that list, as it includes compile-time words such as VARIABLE and CONSTANT --- that doesn't make any sense!

I do agree however that my PSP (what I call a data-stack pointer) in S may not be more efficient than PSP in X --- my ENTER and LEAVE may kill the performance gain attained by getting rid of the INX INX and DEX DEX code sequences.

Forth style is to heavily factor the code, meaning that lengthy functions are factored into small functions that call other small functions (this makes testing code easier on the command-line. This means that there are a lot of function calls, so ENTER and LEAVE get executed quite a lot.

Another good point, is that peephole-optimization gets rid of a lot of pushing and pulling of data to the data-stack. Most optimizations involve a "producer" followed by a "consumer." For example:
10 +
Here 10 is the producer, because it pushes data onto the data-stack, and + is the consumer because it pulls data from the data-stack. This actually gets compiled into this:
CLC 10 ADC#

So, it may be better to use X for the data-stack pointer and get rid of ENTER and LEAVE --- none of this vino816 design is written in stone --- it can be changed.

The code I have written now is for the M65c02A --- I use X for the data-stack pointer rather than S even though X is slower and more bloaty (because it needs an OSX prebyte) --- the problem with X being slower and more bloaty is more serious on the 65c816 though, which is why I switched and used S for the data-stack pointer in vino816.

barrym95838 wrote:

It looks like DROP 1 is a good candidate for optimization.

I don't have that one at this time, but it would be easy to add.

This is what I currently have:

Code:

\ These are history variables --- they indicate what the last thing compiled was --- one or none will be set TRUE.
variable ZF-valid?          \ does the zero-flag reflect the D value?
variable flg?
variable not?
variable BEQ?               \ the last instructions was a BEQ but this is not where 1ST-ADR points
variable BNE?               \ the last instructions was a BNE but this is not where 1ST-ADR points
variable JSR?               \ this one preps jump-termination
variable nip?
variable dup?
variable dup-not?
variable over?
variable rover?
variable tuck?
variable swap?
variable rot?
variable J?
variable RR@?
variable R@?  
variable R@-swap?
variable R@-lit? 
variable R@-lit-plus?       \ this one is used when R@ is a pointer to a struct and the literal is a field offset
variable R@-@?
variable lit?
variable lit-lit?           \ this one is used for storing a literal into a literal address, such as for I/O ports
variable lit-plus?
variable lit-over?
variable lit-swap?

I keep track of a history of the last thing compiled --- sometimes none of the above are set, if the last thing compiled isn't something that I do any peephole-optimization on --- it would be an easy matter to add DROP? to the history variables.

Here is an example of a function that does peephole-optimization, meaning that it may back up over the last thing compiled and compile custom code instead:

Code:

: +, ( -- )  
    lit-lit? S@ if
        backup-to-1st  
        1st-val S@  2nd-val S@  +  
        clear-history  literal,  exit then
    lit? S@ if
        backup-to-1st
        clc  1st-val S@ add#
        lit-plus? happened  ZF-valid  exit then
    R@-LIT? S@ if   
        backup-to-2nd
        clc  1st-val S@ add#
        R@-lit-plus? happened  ZF-valid  exit then
    J? S@ if
        backup-to-1st
        clc  3rd add,s
        clear-history  ZF-valid  exit then
    RR@? S@ if
        backup-to-1st
        clc  2nd add,s
        clear-history  ZF-valid  exit then
    R@? S@ if
        backup-to-1st
        clc  1st add,s
        clear-history  ZF-valid  exit then
    R@-swap? S@ if
        backup-to-1st
        clc  1st add,s
        clear-history  ZF-valid  exit then
    R@-@? S@ if
        backup-to-1st
        clc  1st add(,s
        clear-history  ZF-valid  exit then
    clc  sos add,x  
    nip, ;                  \ NIP, corrupts the ZF-flag

You can see in the above that if LIT? is true, then +, backs up over the code that pushes a literal to the data-stack and compiles code that uses the literal value as an operand.

Peephole-optimization is something that can be expanded upon indefinitely --- I have what I intuitively expect to be the common code-sequences --- more can be added.

Top

barrym95838

Post subject: Re: vino816 Forth design

Posted: Mon Apr 30, 2018 5:52 am

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1929
Location: Sacramento, CA, USA

Could it be that Dr. Koopman meant doVAR instead of VARIABLE ? Or am I confirming my ignorance by asking such a question?

Dr. Ertl did a dynamic study of the execution of three rather large Forth programs, looking for repeating patterns in the execution of primitives. Only the middle one uses locals. I talked about it briefly here:

Code:

  Total        cross         gs       prims2x
--------   --------   --------   --------
15143346    5779740    3540682    5822924   NEXTS
--------   --------   --------   --------
 2038446     793119     442464     802863   ;s
 1995025     787457     428114     779454   col:
 1355759     503162     283813     568784   @
  765602     275772     183685     306145   ?branch
  700996     246049     141642     313305   lit
  674069     270409     125561     278099   col: col:
  519952     151876      36627     331449   var:
  515649     208841     126882     179926   dup
  486243     254487     131630     100126   user:
  457720     109479      44542     303699   swap
  419537     156910      98260     164367   +
  402746     208519     109785      84442   user: @
  402579     209151     103852      89576   @ ;s
  401507     174555      73650     153302   ;s ;s
  381210      98308      17331     265571   var: @
  377418     164606      70945     141867   con:
  354087      95407      33153     225527   ;s col:
  309835     182862      60124      66849   >r
  292806     173229      57072      62505   r>
  275656      28804      16214     230638   0=
  251576     126970      68518      56088   user: @ ;s
  248438     121046      70632      56760   col: user:
  248104     120712      70632      56760   col: user: @
  216244     105626      60494      50124   col: col: user: @
  216244     105626      60494      50124   col: col: user:
  212251     104129      58946      49176   col: user: @ ;s
  203922     100088      56464      47370   col: col: user: @ ;s
  199820      91949       8004      99867   col: var:
  196434      55035      27799     113600   and
  192467      68884      21938     101645   c@
  187718      83969      57687      46062   !
  182861      99558      41195      42108   over
  170810      36514      22562     111734   col: lit
  169028      44781      19153     105094   col: con:
  167571      31201      41220      95150   cells
  167474      57880      12340      97254   rot
  165683      82438      47254      35991   2dup
  164287      46640      18903      98744   lit col:
  159526      63073       6175      90278   col: var: @
  153550      49352      10997      93201   ;s col: col:
  149816      73999      49793      26024   dup ?branch
  148765      42409      18509      87847   ?branch lit
  142644      66254      48157      28233   ;s @
  141586      55741      43102      42743   branch
  139323          0     139323          0   @local1
  135658      48991        394      86273   col: col: var:
  132375      53809      51672      26894   ;s dup
  131373      46307          0      85066   col: col: var: @
  129236      46217      24350      58669   +!
  127031      61331      37581      28119   col: col: col:
  124565      73765      22169      28631   r@
  121258      19748      19543      81967   =
  118775      18113      18986      81676   = ?branch
  118088      21332       6278      90478   lit col: col:
  116035      52796      35160      28079   ! ;s
  112276      20152       4945      87179   + swap
  111648      39594      17275      54779   +! ;s
  111423      42444      34770      34209   defer:
  109783      76322      17118      16343   con: col:
  108908      55593      29618      23697   ;s @ ;s
  108895      55520      29678      23697   user: @ ;s @
  108895      55520      29678      23697   col: user: @ ;s @
  108895      55520      29678      23697   col: col: user: @ ;s @
  108895      55520      29678      23697   @ ;s @
  108835      55520      29618      23697   user: @ ;s @ ;s
  108835      55520      29618      23697   col: user: @ ;s @ ;s
  108835      55520      29618      23697   @ ;s @ ;s
  ...

Mike B.

Top

whartung

Post subject: Re: vino816 Forth design

Posted: Mon Apr 30, 2018 10:09 pm

Joined: Sat Dec 13, 2003 3:37 pm
Posts: 1004

Hugh Aguilar wrote:

BTW: William Mensch may have been thinking about Pascal rather than C. If so, then he was thinking about a crippled Pascal that lacks nested functions --- there is no register available for a local-frame pointer --- there were several such crippled Pascals in the 1980s, most notably Borland Turbo Pascal for the Z80 and later the 8088 (the bytecode Pascal for the Apple-II was also crippled afaik, although I never used it).

This:

Code:

program test;

procedure test1;
  procedure test2;
  begin
    writeln('Test 2');
  end;

begin
  writeln('Test 1');
  test2;
end;

begin
  test1;
end.

Compiles and runs just find on TP 3.0 for the Z80.

The UCSD P-System (of which Apple Pascal is an implementation of) has specific instructions in the P-Code to deal with nested procedures and functions.

For example, the LOD instruction takes two parameters. The first is the number of stack frames to skip (the stack frames have pointers to the previous stack frame), and the offset within that frame.

For its time UCSD P-System was pretty sophisticated. It was also self hosted, in that UCSD was used to build UCSD systems, rather than cross compilers on other machines. All of the tools were written in UCSD Pascal (including the Pascal compiler). The interpreters were assembled using the UCSD Assembler. Outside of raw performance, UCSD was hardly crippled. Pascal, out of the box, the standard Pascal can be considered "hobbled" without extensions. But UCSD worked through that. By todays standard, the environment is quite foreign.

Turbo Pascal didn't quite catch up to what UCSD Pascal could do (functionality wise) until TP 3.x. Turbo, though, clearly, prevailed on raw performance and dirt cheap pricing.

Top

barrym95838

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 2:28 am

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1929
Location: Sacramento, CA, USA

The only time I used Pascal was on a CDC Cyber mainframe about 34 years ago, with time-share terminals. I remember that it said "ZURICH" in the header, was single-pass and upper-case only, and the printouts arrived some time after the jobs were batched on 17-inch-wide tractor feed paper, but I don't remember anyone mentioning that it was "hobbled" in any way. Maybe we weren't doing anything advanced enough to notice its limitations ... it was all lower-division Computer Science class assignments.

Mike B.

Top

Hugh Aguilar

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 3:04 am

Joined: Fri Jun 03, 2016 3:42 am
Posts: 158

barrym95838 wrote:

Could it be that Dr. Koopman meant doVAR instead of VARIABLE ? Or am I confirming my ignorance by asking such a question?

You are most likely correct --- he meant doVAR and doCON which are run-time.

I still don't put much stock into lists such as this --- they tend to hide a lot of assumptions --- here, Dr. Koopman is assuming an ITC system that has doVAR and doCON etc..
In an STC system, both addresses and constants are compiled by LITERAL and they presumably get peephole-optimized so the literal datum can be an operand (my peephole-optimizer is very much focused on literals).

I would be more inclined to rely on intuition for what code-sequences or primitives need to be fast ---then, after I had a program that mattered, I would profile it to find out where the time-sinks are, and upgrade the compiler to fix those problems --- assuming that my next program will be similar to this program (not a good assumption), then the compiler should do reasonably well on the next program.
As for other people's programs being similar to my programs, that is a pretty big assumption!

Most compiler-writers focus on getting benchmark programs, such as ye olde Sieve, to compile into efficient code. This is despite the fact that most of those benchmark programs aren't similar to anybody's real-world programs.

Top

Hugh Aguilar

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 3:29 am

Joined: Fri Jun 03, 2016 3:42 am
Posts: 158

whartung wrote:

Hugh Aguilar wrote:

This:

Code:

program test;

procedure test1;
  procedure test2;
  begin
    writeln('Test 2');
  end;

begin
  writeln('Test 1');
  test2;
end;

begin
  test1;
end.

My recollection of the 20th century is pretty fuzzy --- I didn't remember that Turbo Pascal had nested functions.

I have a book (bought it when I was in high-school) on how to write a Pascal compile, and it includes the source-code for a Pascal-S compiler, written in Pascal. What you are describing (the stack frames have pointers to the previous stack frame) was called a "display pointer" in this book. This allows nested functions to have access to the local variables of the parent functions. When I read that book, I had no idea what the purpose of nested functions was --- I didn't figure that out until fairly recently when I learned Factor.

In my TOYF processor design, I have support for quotations. These are anonymous nested functions. They can only be nested one level though (in Pascal-S multiple levels of nesting was allowed). The idea is that a parent function calls a HOF (higher-order-function) and gives it the xt (execution token) of a quotation. The HOF executes the quotation and the quotation has access to the parent function's local variables, despite the fact that the HOF has local variables of its own. Typically the HOF iterates through a data-structure, applying the quotation to each node in the data-structure.

I won't support quotations in vino816 because there is no register available for a local-frame pointer --- I suppose I could use a zero-page pointer, but that would be somewhat slow --- I'm not interested in the 65c816 enough to consider making vino816 anything more than a rudimentary Forth system (and it is unlikely that I will even implement that, as the possibility of having any users is pretty much zilch).
For a micro-controller, quotations are somewhat of an overkill --- you are unlikely to have any data-structures other than arrays --- quotations are really more useful when your program is big enough to have a heap and have data-structures such as lists or binary-trees.

BTW: I have implemented "rquotations" in both VFX and SwiftForth --- these are like quotations except with a minor limitation (their address is not known at compile-time, so they can't be used in <SWITCH constructs).

Top

Hugh Aguilar

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 3:41 am

Joined: Fri Jun 03, 2016 3:42 am
Posts: 158

barrym95838 wrote:

Pascal used to be the language of education --- taught in all the colleges --- now Java is used.

My guess on why Java replaced Pascal, is that Java has security features that prevent programs from accessing data that doesn't belong to the user --- each user gets his own "sandbox."

That mainframe that you are describing was most likely used to store a lot of interesting data --- for example: next week's test including the answers, and the students' grades on the previous tests --- of course, you and I aren't so devious as to write a Pascal program to access this data to ensure an 'A' grade, but a lot of college students are!

Top

Tor

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 7:27 am

Joined: Sun Apr 10, 2011 8:29 am
Posts: 597
Location: Norway/Japan

I can confirm that neither TP nor USCD were crippled in any particular sense, I used both back then. If anything, they were enhanced Pascal dialects (l/O, dynamic strings and arrays etc). And yes they supported nested functions. Without that they wouldn't be Pascal at all and pretty useless.

Top

Dr Jefyll

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 1:44 pm

Joined: Fri Dec 11, 2009 3:50 pm
Posts: 3354
Location: Ontario, Canada

Hugh Aguilar wrote:

barrym95838 wrote:

Could it be that Dr. Koopman meant doVAR instead of VARIABLE ? Or am I confirming my ignorance by asking such a question?

You are most likely correct --- he meant doVAR and doCON which are run-time.

I agree.

Hugh Aguilar wrote:

Most compiler-writers focus on getting benchmark programs, such as ye olde Sieve, to compile into efficient code. This is despite the fact that most of those benchmark programs aren't similar to anybody's real-world programs.

"Most compiler-writers"? Citation needed, but I agree with the point you're making. It is important to approximate real-world programs.

On the topic of real-world programs, I'm reminded of a quotation which (due to faulty memory) I'm forced to paraphrase. "Most computer applications boil down to searching and sorting." That may be an overstatement, but it offers some insight, I think. If anyone can supply the actual quotation and its source, please speak up.

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

Top

whartung

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 4:49 pm

Joined: Sat Dec 13, 2003 3:37 pm
Posts: 1004

Tor wrote:

I can confirm that neither TP nor USCD were crippled in any particular sense, I used both back then. If anything, they were enhanced Pascal dialects (l/O, dynamic strings and arrays etc).

This is what I meant by "hobbled". Pretty much every Pascal that got out in to industry at all had extensions to the standard, and all of the extensions were similar (i.e. strings, I/O, relaxed typing, packaging).

Quote:

And yes they supported nested functions. Without that they wouldn't be Pascal at all and pretty useless.

Dunno about that, used to do a lot of Pascal, and I never used nested procedures/functions.

Top

whartung

Post subject: Re: vino816 Forth design

Posted: Tue May 01, 2018 5:00 pm

Joined: Sat Dec 13, 2003 3:37 pm
Posts: 1004

Hugh Aguilar wrote:

Yeah. No.

CDC NOS was no bastion of a hardened computer system, as most weren't back in the day.

The guys at my school found there share of holes in the system when they wrote a COMPASS simulator (COMPASS was the CDC assembly/machine language). Once they had "their own" personal Cyber, they would step through the assorted system utilities that they had available, and, indeed, they found some cracks to peer through. Some of the guys that did this went to work for CDC.

But they also did a lot through publishing back doors in common "shared" utilities that lots of folks were using. The group would harass particular users. They'd literally have "IF BOB THEN" code in their utilities to target specific people. Ah, college.

Java certainly has security concepts built in to the JVM, but that's not why it's used. Since folks don't develop on timesharing systems any more, that's not a concern.

Top

Hugh Aguilar

Post subject: Re: vino816 Forth design

Posted: Wed May 02, 2018 3:00 am

Joined: Fri Jun 03, 2016 3:42 am
Posts: 158

Dr Jefyll wrote:

Hugh Aguilar wrote:

barrym95838 wrote:

Could it be that Dr. Koopman meant doVAR instead of VARIABLE ? Or am I confirming my ignorance by asking such a question?

You are most likely correct --- he meant doVAR and doCON which are run-time.

I agree.

Hugh Aguilar wrote:

I think that was Donald Knuth in his book: "Sorting and Searching."
This may be true for desktop-computer applications.
This isn't true for micro-controller applications though, which is what vino816 would be used for --- the days of the 65c816 being used as a desktop-computer (Apple-IIgs) are past --- 8-bit processors are still used in micro-controllers though.

My peephole-optimizer is mostly focused on speeding up access to I/O ports, and doing logic on data going in and out --- later on I will add some optimization for circular buffers --- that seems reasonable for a micro-controller.

Top

Tor

Post subject: Re: vino816 Forth design

Posted: Wed May 02, 2018 7:36 am

Joined: Sun Apr 10, 2011 8:29 am
Posts: 597
Location: Norway/Japan

whartung wrote:

Dunno about that, used to do a lot of Pascal, and I never used nested procedures/functions.

I definitely did. I used a structured design approach, and my Pascal code followed the structure. With the design as e.g. warnier-orr diagrams it was natural to implement it that way. A GetWord, for example, would call a GetChar, which would be a function inside GetWord unless it was used elsewhere - in which case, again, the implementation followed the design and they would maybe all be inside a greater module.
As Pascal was designed for that kind of method (design->implementation) it's quite essential.

When I moved to C there was no nesting, so I would split code into many files and use static functions to encapsulate and isolate functions. So, if getchar was only used by getword, getword would be a function in a file and getchar a static function in the same file.

And, of course, for TP and UCSD to be able to compile source from elsewhere they had to be pretty complete Pascal implementations. And they were - I didn't have much problem moving code between VAX Pascal, Norsk Data Pascal, UCSD, and TP. And on PCs many would code and test in TP (fast compilation, so-so runtime speed) and use MS' Pascal (very slow compilation, faster runtime speed) for the final product. Pascal was never as portable as C, but it wasn't bad either.

Top

BigEd

Post subject: Re: vino816 Forth design

Posted: Wed May 02, 2018 9:53 am

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10800
Location: England

Hugh Aguilar wrote:

Dr Jefyll wrote:

...I'm reminded of a quotation which (due to faulty memory) I'm forced to paraphrase. "Most computer applications boil down to searching and sorting." That may be an overstatement, but it offers some insight, I think. If anyone can supply the actual quotation and its source, please speak up. :)

I think that was Donald Knuth in his book: "Sorting and Searching"

Well done, quite so:
"I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!" (Donald Knuth, The Art of Computer Programming, Volume 3, "Sorting and Searching")
[I wasn't able to find the source myself...]

Top

John West

Post subject: Re: vino816 Forth design

Posted: Wed May 02, 2018 10:24 am

Joined: Tue Sep 03, 2002 12:58 pm
Posts: 298

Dr Jefyll wrote:

"Most computer applications boil down to searching and sorting."

BigEd wrote:

"I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!" (Donald Knuth, The Art of Computer Programming, Volume 3, "Sorting and Searching")

It's worth noting that these two quotes are saying opposite things. The first is the one that people often think Knuth was saying, but if you read the preface to Vol. 3, it is clear that he was not. A bit more context makes it clear:

Knuth wrote:

The title “Sorting and Searching” may sound as if this book is only for those systems programmers who are concerned with the preparation of general-purpose sorting routines or applications to information retrieval. But in fact the area of sorting and searching provides an ideal framework for discussing a wide variety of important general issues:

Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching!

A full exploration of sorting and searching will cover virtually everything that is important. None of those things are themselves sorting or searching.

Top

Page 2 of 3

[ 37 posts ]

Go to page Previous 1, 2, 3 Next

Board index » 6502.org Users Forum » Forth

All times are UTC

Who is online

Users browsing this forum: No registered users and 4 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum