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

Groups > comp.lang.forth > #54539 > unrolled thread

CASEs compared

Back to article view | Back to comp.lang.forth

Contents

  CASEs compared "HAA" <someone@microsoft.com> - 2017-01-30 22:34 +1100
    Re: CASEs compared anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-01-30 15:56 +0000
      Re: CASEs compared hughaguilar96@gmail.com - 2017-01-30 09:57 -0800
        Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-01-31 14:26 +1100
          Re: CASEs compared hughaguilar96@gmail.com - 2017-01-31 08:12 -0800
            Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-02-01 11:39 +1100
              Re: CASEs compared hughaguilar96@gmail.com - 2017-01-31 22:37 -0800
                Re: CASEs compared hughaguilar96@gmail.com - 2017-02-01 12:26 -0800
                  Re: CASEs compared hughaguilar96@gmail.com - 2017-02-01 16:50 -0800
                    Re: CASEs compared hughaguilar96@gmail.com - 2017-02-01 18:02 -0800
                  Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-02-02 21:12 +1100
                    Re: CASEs compared hughaguilar96@gmail.com - 2017-02-02 13:46 -0800
                      Re: CASEs compared hughaguilar96@gmail.com - 2017-02-02 17:01 -0800
                      Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-02-04 12:43 +1100
                        Re: CASEs compared hughaguilar96@gmail.com - 2017-02-03 17:52 -0800
                          Re: CASEs compared Alex <alex@rivadpm.com> - 2017-02-04 11:10 +0000
                    Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-02 19:57 -0500
                      Re: CASEs compared hughaguilar96@gmail.com - 2017-02-02 17:05 -0800
                        Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-02 21:55 -0500
                      Re: CASEs compared Mark Wills <markwills1970@gmail.com> - 2017-02-03 02:11 -0800
                        Re: CASEs compared hughaguilar96@gmail.com - 2017-02-03 10:52 -0800
                          Re: CASEs compared hughaguilar96@gmail.com - 2017-02-03 17:38 -0800
                            Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-03 22:08 -0500
                              Re: CASEs compared hughaguilar96@gmail.com - 2017-02-03 21:40 -0800
                                Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-04 01:16 -0500
                        Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-03 14:40 -0500
                          Re: CASEs compared hughaguilar96@gmail.com - 2017-02-03 17:47 -0800
                            Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-03 22:04 -0500
                      Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-02-04 12:39 +1100
                        Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-03 23:32 -0500
                          Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-02-04 22:50 +1100
                            Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-04 11:07 -0500
                              Re: CASEs compared hughaguilar96@gmail.com - 2017-02-04 08:48 -0800
                                Re: CASEs compared Mark Wills <markwills1970@gmail.com> - 2017-02-04 10:01 -0800
                                  Re: CASEs compared rickman <gnuarm@gmail.com> - 2017-02-04 16:43 -0500
                                  Re: CASEs compared hughaguilar96@gmail.com - 2017-02-04 18:53 -0800
                              Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-02-05 19:12 +1100
      Re: CASEs compared "HAA" <someone@microsoft.com> - 2017-01-31 14:25 +1100
    Re: CASEs compared Elliott Chapin <elliott.chapin@gmail.com> - 2017-02-05 08:25 -0800
      Re: CASEs compared Coos Haak <htrofhc@gmail.com> - 2017-02-06 00:42 +0100
    Re: CASEs compared jacko <jackokring@gmail.com> - 2017-02-16 17:46 -0800
      Re: CASEs compared hughaguilar96@gmail.com - 2017-02-17 09:09 -0800

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

#54539 — CASEs compared

hughaguilar96@gmail.com wrote:
> ...
> CASE has to be nested IF statements though, which is horribly inefficient.

Perhaps not.  Below is some test code for VFX.  It compares IF/ELSE Case with
SWITCH from FD 20/3.  The former gave me 10x better speed.  In the FD article
the author states:

"The execution-time behavior of CASE and OF can be optimized until your system
implementor is exhausted and performance will be similar to that of the C version."

The reference to CASE aside (it has no run-time cost) I agree the performance of
IF/ELSE is probably as good as it gets for the general Case.  ENDOF can begin
costing memory if there are many but in that event I would re-organize the code
to use END (assuming that's an option).


\ CASEs compared

( empty) forth definitions decimal

10000000 constant TIMES  \ # loops

include timers.fth
: .timer ( ms -- ) Counter swap - u. ." mS " ;

\ case code from SWITCHBLADE FD20/3

\ Replace LINK@ and LINK, with your favorite list building words.
\ These are the methods used by SwiftForth.
\ : LINK@   @REL ;
\ : LINK,   HERE OVER @REL ,REL SWAP !REL ;
synonym LINK@ @
: LINK,   HERE OVER @ , SWAP ! ;

: SWITCHER ( i*x n head -- j*x )
   DUP CELL+ @ >R ( save default xt)
   BEGIN
      LINK@ ?DUP WHILE ( n a)
      2DUP CELL+ @ = IF ( match)
         NIP CELL+ CELL+ @ EXECUTE
         R> DROP EXIT
      THEN
   REPEAT R> EXECUTE ;

: <SWITCH ( head xt n -- head )   2 PICK LINK,  , , ;

: [SWITCH ( -- head )   CREATE  HERE 0 ,  ' , DOES> SWITCHER ;

: SWITCH] ( head -- )   DROP ;

: RUN: ( head n -- )
   :NONAME [CHAR] ; PARSE EVALUATE POSTPONE ;  ( xt) SWAP <SWITCH ;

: (test1)
  case
    0 of  endof    1 of  endof    2 of  endof    3 of  endof
    4 of  endof    5 of  endof    6 of  endof    7 of  endof
    8 of  endof    9 of  endof
  endcase ;

: test1  cr ." ANS CASE - "
  Counter  TIMES 0 do  9 (test1)  loop  .timer ;

\ labels in reverse order because last is compared first
[SWITCH (test2) NOOP
   9 RUN: ;   8 RUN: ;   7 RUN: ;   6 RUN: ;
   5 RUN: ;   4 RUN: ;   3 RUN: ;   2 RUN: ;
   1 RUN: ;   0 RUN: ;
SWITCH]

: test2  cr ." SWITCH FD20/3 - "
  Counter  TIMES 0 do  9 (test2) loop  .timer ;

\ end

[toc] | [next] | [standalone]

#54545

"HAA" <someone@microsoft.com> writes:
>hughaguilar96@gmail.com wrote:
>> ...
>> CASE has to be nested IF statements though, which is horribly inefficient.
>
>Perhaps not.  Below is some test code for VFX.  It compares IF/ELSE Case with
>SWITCH from FD 20/3.  The former gave me 10x better speed.

Note that the SWITCHER from FD 20/3 also performs a linear search
through the keys; moreover, it uses a linked list for walking through
the keys, and when it has found the right key, it uses a common
EXECUTE to invoke the matchxt; unless you have a very nice pattern in
the things you search for (e.g., always the same), the IF in SWITCHER
is likely to mispredict (~20 cycles penalty), and the EXECUTE is even
more likely to mispredict (another ~20 cycles), in addition to the at
least 4 cycles per tried key for following the linked list.

This is not the kind of thing Hugh Aguilar has in mind.  Also, the
point of VanNorman's SWITCH is not performance, but being able to add
more key-action pairs later; that's why he uses a linked list.

>  In the FD article
>the author states:
>
>"The execution-time behavior of CASE and OF can be optimized until your system
>implementor is exhausted and performance will be similar to that of the C version."

What can be done is one thing.  But is it done?  I don't think so.
And I don't think that it should be done.  If we want something that
does not do a linear search, we should express it directly, instead of
writing an Eaker's CASE and hoping that the compiler will optimize it.

And guess what: If we care about performance, we do.  We just don't do
it by inventing another CASE/SWITCH construct, but we use EXECUTE and
an xt table; or maybe the whole thing is reorganized:

In Gforth 0.7, we have an intelligent COMPILE, that uses Eaker's CASE
to decide how to compile each word type.  In the development version,
each word has a field that says how the word is COMPILE,d, and
COMPILE, now does something like

: compile, ( xt -- )
  xt>compile, @ execute ;

And I think that's why there was never much demand for something
beyond Eaker's CASE.  If there are so many OFs that the linear search
becomes inefficient, idiomatic Forth programming stops putting all
that code in a single word.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

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

#54548

On Monday, January 30, 2017 at 9:30:20 AM UTC-7, Anton Ertl wrote:
> "HAA" <someone@microsoft.com> writes:
> >hughaguilar96@gmail.com wrote:
> >> ...
> >> CASE has to be nested IF statements though, which is horribly inefficient.
> >
> >Perhaps not.  Below is some test code for VFX.  It compares IF/ELSE Case with
> >SWITCH from FD 20/3.  The former gave me 10x better speed.
> 
> Note that the SWITCHER from FD 20/3 also performs a linear search
> through the keys; moreover, it uses a linked list for walking through
> the keys, and when it has found the right key, it uses a common
> EXECUTE to invoke the matchxt; unless you have a very nice pattern in
> the things you search for (e.g., always the same), the IF in SWITCHER
> is likely to mispredict (~20 cycles penalty), and the EXECUTE is even
> more likely to mispredict (another ~20 cycles), in addition to the at
> least 4 cycles per tried key for following the linked list.

I mostly wrote <SWITCH for the purpose of making the ANS-Forth enthusiasts look foolish with their Eaker's CASE that Elizabeth Rather standardized. Actually, I don't make them look foolish --- I'm just a catalyst --- they make themselves look foolish.

Already we have a thread with the title "CASEs compared" that is obviously a response to my <SWITCH but which doesn't compare CASE to <SWITCH --- instead it compares CASE to SWITCH from another "Forth Dimensions" article from the same time period --- the implication here is that CASE provides 10x better speed than my <SWITCH, but this is a straw-man argument.

> This is not the kind of thing Hugh Aguilar has in mind.  Also, the
> point of VanNorman's SWITCH is not performance, but being able to add
> more key-action pairs later; that's why he uses a linked list.

Is this the same Rick vanNorman who wrote SwiftForth?

Why did he use a linked list? Why not a self-balancing binary-tree? Most likely, because he didn't know how to implement a self-balancing binary-tree. If you want to be able to add and remove key-action pairs at run-time, then use my ASSOCIATION.4TH in the novice-package which has been available for several years now --- or use hash tables, like in Lua.

Anyway, generating a jump-table isn't just something that I "have in mind" --- there is a big difference between having code in mind and actually implementing the code --- any fool can have grand ideas in mind, and most do, but only programmers actually implement code.

This <SWITCH seemed like it would be easy when I started, but it took me most of a day to implement because there were multiple bugs that had to get fixed (plus, the original version didn't have a default action but it just aborted when given a mismatch, so the design had a bug too). This is the way of all code! After it is written, everybody says: "Well, that is simple and obvious. What was the big deal? A fast typist could have written it in minutes, and then maybe an hour to test, and done!"

Here is the code that I implemented:
---------------------------------------------------------------------------

\ You can build a colon word called XXX that switches on targ values. This is how:
\ <SWITCH
\ :NONAME ... ;  targ SWOF
\ ...
\ :NONAME ... ;  FAST-SWITCH> xxx  ( targ -- )

\ The colon word XXX executes a table-entry corresponding to the targ value.
\ If there is no match, then the xt value prior to FAST-SWITCH> is executed as the default.

\ The targ values don't have to be provided in any particular order --- they get sorted internally.
\ If a duplicate targ value is provided, SWOF will abort with an error message at compile-time.

\ This is pretty crude because, unlike in C, the table entries can't have common local variables.
\ I would have liked to use my rquotations, but they don't have an xt that is known at compile-time,
\ so it is not possible to build a jump-table at compile-time. They have a "continuation" that is only known at run-time.
\ My <SWITCH that I have here uses :NONAME for the table entries --- they can have common global variables.

\ FAST-SWITCH> uses the targ value as an index to do the table look up. This is very fast.
\ If the range is too large however, then FAST-SWITCH> will abort with an error message to save memory.
\ In this case, use SLOW-SWITCH> instead. This builds a smaller table and uses BSEARCH to look up the table-entry.

\ Set JT-LIMIT to the range that you want FAST-SWITCH> to support.
\ It is currently set at 2^16 so you can have jump-tables with up to 64K entries. These consume a lot of memory.
\ If memory usage is an issue, then set JT-LIMIT to a smaller value. Use SLOW-SWITCH> instead of FAST-SWITCH>.
\ If the jump-table is sparse, SLOW-SWITCH> might be faster because there is less data-cache thrashing.

\ <SWITCH is primarily provided for writing VM simulators.
\ JT-LIMIT is currently set at 2^16, so it supports simulating a micro-processor with 16-bit opcodes (such as the AVR).
\ SLOW-SWITCH> would be needed for a micro-processor with 32-bit opcodes (such as the ARM or MIPS).

\ Some micro-processors (or byte-code VMs) have 8-bit opcodes, but also have post-bytes on some of the opcodes.
\ These variable-sized opcodes could be done with nested FAST-SWITCH> constructs.

list
    w field .xt
    w field .targ
constant jt

: init-jt ( xt targ node -- node )
    init-list >r
    r@ .targ !
    r@ .xt !
    r> ;

: new-jt ( xt targ -- node )
    jt alloc
    init-jt ;

: kill-jt ( head -- )
    each[  dealloc  ]each ;

: show-jt ( head -- )
    each[  cr  .targ @ .  ]each ;

: jt> ( new-node node -- new-node flag )    \ used by INSERT-ORDERED to build an ascending list without duplicates
    .targ @  over .targ @
    2dup = abort" *** <SWITCH structures not allowed to have duplicate targ values ***"
    > ;

: <switch ( -- head )
    nil ;

: swof ( head xt targ -- new-head )
    new-jt                                  \ -- head node
    ['] jt> swap  insert-ordered drop ;

1 16 lshift  value jt-limit                 \ should be at least 256 so we can support byte-code simulators

\ JT-LIMIT is the index that is too big for the jump-table. This can be any reasonable size.
\ The jump-table size is limited so the programmer doesn't accidentally build a jump-table consuming megabytes.
\ I set it at 2^16 to support simulating a micro-processor with 16-bit opcodes.

: fast-switch> { head default | adr offset size -- }    \ stream: name
    align here  to adr
    head .targ @  to offset
    head tail .targ @  offset -  to size
    size jt-limit u> abort" *** FAST-SWITCH> has too large of a range. Use SLOW-SWITCH> instead. ***"
    offset  head each[  >r      \ -- targ
        begin  r@ .targ @  over <> while  default ,  1+  repeat
        r> .xt @ ,  1+  ]each  drop
    : ( targ -- )
        offset lit, -,          \ -- index
        dup,  size lit,  u>,  if,       drop,  default lit, execute,
        else,                           w lit, *,  adr lit, +,  @, execute,         then,  ;,
    head kill-jt ;

: jt-direction ( target mid-element -- -1|0|1 )         \ for use by BSEARCH
    @                                   \ -- target mid-value
    2dup = if  2drop  0 end                             \ note for HAA: I used your END rather than EXIT THEN
    < if  -1  else  1  then ;

: slow-switch> { head default | adr size -- }           \ stream: name
    align here  to adr
    head length  to size
    head each[  dup .targ @ ,  .xt @ ,  ]each
    : ( targ -- )
        adr lit,  size lit,  rot,  d lit,  ['] jt-direction lit,  postpone bsearch
        0=,  if,                        drop,  default lit, execute,
        else,                           w lit, +,  @, execute,                      then,  ;,
    head kill-jt ;

\ Testra had a switch construct written in UR/Forth assembly-language that built two arrays,
\ one of targ values and one of xt values. It generated code that would use SCASW to search the targ values.
\ I recommended using a binary search instead. I was told that SCASW is faster, even though it is sequential.
\ On the 80486, the ciscy instructions did usually provide better performance than hand-written code.
\ Because Testra was into building custom processors, they needed a fast simulator.
\ I didn't use their simulator for the MiniForth though --- I wrote my own in MFX.

\ The best way to write a simulator is to have your assembler not only generate the machine-code
\ for the target processor, but also generate a Forth program on the host machine that simulates it.
\ This generated simulation is much faster than a simulator that looks up opcodes at run-time.
\ This only works if you have the source-code for the target processor program that you are simulating.

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

#54562

hughaguilar96@gmail.com wrote:
> ...
> Why did he use a linked list? Why not a self-balancing binary-tree? Most likely,
> because he didn't know how to implement a self-balancing binary-tree.

Or such effort couldn't be justified on the grounds it would waste resources
for no material gain.

> ...
> \ <SWITCH is primarily provided for writing VM simulators.

Which is far away from the everyday applications to which programmers
will be using Case.  Languages provide for general use.  I don't care for
the way ANS defined Eaker but as for the choice, I don't fault it.

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

#54576

On Monday, January 30, 2017 at 8:24:56 PM UTC-7, HAA wrote:
> hughaguilar96@gmail.com wrote:
> > ...
> > Why did he use a linked list? Why not a self-balancing binary-tree? Most likely,
> > because he didn't know how to implement a self-balancing binary-tree.
> 
> Or such effort couldn't be justified on the grounds it would waste resources
> for no material gain.

Didn't you previously say that his linked-list code was 10 times slower than Eaker's CASE construct? But now you say that there would be "no material gain" from using a self-balancing binary-tree. hmmm...

BTW: If this is Rick van Norman, who later got hired by Elizabeth Rather to write SwiftForth for her, then I find it highly humorous that his SWITCH was 10 times slower than Eaker's CASE --- most programmers would have written something that was faster than CASE given the abysmal bad efficiency of CASE --- this van Norman somehow manages to write a SWITCH that is 10 times slower, and this qualifies him to get hired at Forth Inc.! LOL Maybe this is why SwiftForth was a bug-ridden mess, and provided abysmal performance. Idiots!

> > \ <SWITCH is primarily provided for writing VM simulators.
> 
> Which is far away from the everyday applications to which programmers
> will be using Case.  Languages provide for general use.  I don't care for
> the way ANS defined Eaker but as for the choice, I don't fault it.

The reason why my <SWITCH is cumbersome to use, is because it generates a stand-alone colon word rather than being used inside of a colon word, and the table entries can't share local variables --- CASE is better in both regards.

This isn't my fault though! I couldn't fix these problems because of ANS-Forth's stupid limitations --- ANS-Forth should have supported quotations (not Paysan-faked quotations, but real quotations that access the parent function's local variables) and these quotation should have an xt that is known at compile-time so the jump-table can be built. Because of ANS-Forth's stupid and pointless limitations, the <SWITCH that I wrote was the best that could be done.

ANS-Forth is just a total failure! ANS-Forth is really the most retarded language design in the history of computer programming! To a large extent, the reason why all of the ANS-Forth cult members hate my <SWITCH is because it shines a spotlight on the stupidity of ANS-Forth. Every time that anybody writes working code in ANS-Forth, the programmer does so by working around the stupid and pointless limitations of ANS-Forth --- this is why the ANS-Forth cult members hate and fear working ANS-Forth code --- programming in ANS-Forth inevitably shines a spotlight on the stupidity of ANS-Forth design because the code inevitably is a work-around for Elizabeth Rather's idiotic design decisions.

Anyway, writing simulator for a VM seems like a pretty "everyday application" to me. There are great numbers of C programmers who have written a Forth in C and have used SWITCH (that generates a jump-table) as the basis for this. Most, if not all, did this for the purpose of "proving" that C is the "god language" that all other languages are written in, and that Forth is a toy interpreted language roughly comparable to line-number BASIC. They ask the obvious question: "If Forth is a real language, then why is it impossible to write a C interpreter in Forth?"

Also, a big application area for Forth is FPGA custom processors. These obviously need to be simulated on a desktop-computer. How are you going to make money with Forth if you don't build your own FPGA-based Forth processor? I got hired as a Forth programmer for this purpose. I wouldn't have been hired just to write desktop-computer software --- the days of selling desktop-computer software in shrink-wrapped boxes (such as CompUSA used to sell) were well on their way toward non-existence in 1994, and are totally a thing of the past in 2017.

People who think that CASE is adequate are just writing toy programs that have no speed requirements whatsoever. Anton Ertl's students are in this category --- their programs don't have to compete in the real world --- they only compete against their fellow students, who are also at an abysmal performance level. ANS-Forth is a toy language unsuitable for writing commercial software.

The CASE construct in ANS-Forth is utterly retarded! This is totally pointless --- CASE could have easily been written to generate a jump-table so that it would be efficient --- the fact that CASE wasn't written to generate a jump-table is because Elizabeth Rather doesn't know what a jump-table is; there is no other possible explanation.

The idiotic design of the CASE construct, just by itself, is reason enough to dismiss ANS-Forth as worthless.

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

#54583

hughaguilar96@gmail.com wrote:
> On Monday, January 30, 2017 at 8:24:56 PM UTC-7, HAA wrote:
> > hughaguilar96@gmail.com wrote:
> > > ...
> > > Why did he use a linked list? Why not a self-balancing binary-tree? Most likely,
> > > because he didn't know how to implement a self-balancing binary-tree.
> >
> > Or such effort couldn't be justified on the grounds it would waste resources
> > for no material gain.
>
> Didn't you previously say that his linked-list code was 10 times slower than Eaker's
> CASE construct? But now you say that there would be "no material gain" from using a
> self-balancing binary-tree. hmmm...

Nor can anyone claim there would be material gain unless the speed of the case/switch
was critical to the application.  I accept it wasn't the best Case with which to compare
Eaker but it was all I had at the time and I was curious myself what would be the result.

I've since created a third test which attempts to emulate the run-time of a table-based
C switch of the early 1990's.  It's hand-coded asm to give the best shot at speed.
To use, append it the code I previously posted.

code (exec) ( x table )
  mov   eax, 0 [ebp]
  add   ebp, # 4
  mov   ecx, 0 [ebx]
  mov   edx, ecx
L$1:
  add   ebx, # 4
  cmp   ax, 0 [ebx]
  jz    L$2
  dec   ecx   jnz   L$1  \ faster than loop
\  loop  L$1
  inc   edx  \ default
L$2:
  shl   edx, # 2
  add   edx, ebx
  mov   ebx, 0 [ebp]
  add   ebp, # 4
  jmp   0 [edx]
  next,
end-code

: default ." no match" ;

create TABLE
  10 ,
  0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ,
  ' noop , ' noop , ' noop , ' noop , ' noop ,
  ' noop , ' noop , ' noop , ' noop , ' noop ,
  ' default ,

: test3  cr ." TABLE SWITCH - "
  Counter  TIMES 0 do  9 table (exec) loop  .timer ;

By 2000, Borland's 32-bit Win compiler had thrown out tables for anything that required
comparison.  It used an approach similar to Eaker with the exception that target values
were sorted into smaller groups of a few each for comparison.  The conclusion being
that when down to a few values to compare (which in my experience is most of the time)
a direct compare and branch is best.

> BTW: If this is Rick van Norman, who later got hired by Elizabeth Rather to write
> SwiftForth for her, then I find it highly humorous that his SWITCH was 10 times slower
> than Eaker's CASE
> ...

SwitfForth needed an extensible Case for internal reasons as imagine would VFX.
Both have Eaker of course.

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

#54585

On Tuesday, January 31, 2017 at 5:38:17 PM UTC-7, HAA wrote:
> By 2000, Borland's 32-bit Win compiler had thrown out tables for anything that required
> comparison.  It used an approach similar to Eaker with the exception that target values
> were sorted into smaller groups of a few each for comparison.  The conclusion being
> that when down to a few values to compare (which in my experience is most of the time)
> a direct compare and branch is best.

This sounds a lot like my SLOW-SWITCH> that does a BSEARCH internally --- it might be possible to speed this up by generating code that compares the targ to literal values rather than to table entries (saving a memory access for each comparison) --- I might be able to write this in ANS-Forth, but this is getting complicated and it will result in hugely bloated code (which results in code-cache thrashing), and I do want to release the novice-package in a few days so I'm not going to delve into this. Why don't you do it? I would put that in the novice-package!

I think FAST-SWITCH> that does a direct table look-up is going to be faster than Eaker's CASE --- I already said that the pathological circumstance of having only one table entry (which corresponds to a single IF ELSE THEN construct) is going to be slower --- I would be very dubious that the next step up (two table entries) would be faster with Eaker's CASE because mis-predicted branches are a major speed-killer on the modern x86.

How would you even test something like this? We are talking about a few nanoseconds difference, and factors that you can't control (what is in the code-cache and data-cache) are going to have a big effect.

I like FAST-SWITCH> --- with very little effort I wrote a short meta-compiler that generates very efficient code --- the more table entries that you have, the better it compares, and large <SWITCH constructs with a lot of table entries are what matters in regard to speed (especially for simulating VMs).

> SwitfForth needed an extensible Case for internal reasons as imagine would VFX.
> Both have Eaker of course.

What Forth needs is the quotation --- not the Paysan-faked quotation that lacks access to the parent function's local variables --- the real deal with access to the parent function's local variables and an xt that is known at compile-time.

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

#54588

On Tuesday, January 31, 2017 at 11:37:19 PM UTC-7, hughag...@gmail.com wrote:
> This sounds a lot like my SLOW-SWITCH> that does a BSEARCH internally --- it might be possible to speed this up by generating code that compares the targ to literal values rather than to table entries (saving a memory access for each comparison) --- I might be able to write this in ANS-Forth, but this is getting complicated and it will result in hugely bloated code (which results in code-cache thrashing), and I do want to release the novice-package in a few days so I'm not going to delve into this. Why don't you do it? I would put that in the novice-package!

Unwinding BSEARCH is possible. Certainly an interesting challenge, comparable to solving a black-belt sudoku puzzle! The number of iterations in BSEARCH is lg(n) with N being the number of table entries. Your typical VM is going to have maybe 256 opcodes, so that is 8 iterations of BSEARCH --- unwinding BSEARCH is not going to produce horribly bloated code --- this is within reason.

FAST-SWITCH> is still going to be faster though. If you have memory for your jump-table, then you would normally use FAST-SWITCH> for speed.

Since the title of this thread is "CASEs compared," here is a comparison:

: ccc ( n -- ) 
    case 
    2 of  1  endof 
    3 of  2  endof 
    5 of  3  endof 
    7 of  4  endof 
   11 of  5  endof 
   13 of  6  endof 
   17 of  7  endof 
   19 of  8  endof 
   23 of  9  endof 
   29 of 10  endof 
    -1  swap endcase ;  ok

1 ccc . -1  ok
2 ccc . 1  ok
29 ccc . 10  ok
30 ccc . -1  ok

What usually messes me up when using CASE is that the test value is still on the stack after the last ENDOF and it has to be left on the stack so ENDCASE can discard it. That is why we have a SWAP in there.

<switch  ok-1 
:noname 1  ;  2 swof  ok-1 
:noname 2  ;  3 swof  ok-1 
:noname 3  ;  5 swof  ok-1 
:noname 4  ;  7 swof  ok-1 
:noname 5  ;  11 swof  ok-1 
:noname 6  ;  13 swof  ok-1 
:noname 7  ;  17 swof  ok-1 
:noname 8  ;  19 swof  ok-1 
:noname 9  ;  23 swof  ok-1 
:noname 10  ;  29 swof  ok-1 
:noname -1  ;  fast-switch> sss  ok

1 sss . -1  ok
2 sss . 1  ok
29 sss . 10  ok
30 ccc . -1  ok

This is the same thing using <SWITCH --- notice that the need for SWAP is gone --- this is much more readable code.

Here is what FAST-SWITCH> generates under VFX:

see sss 
SSS 
( 004E3850    83C3FE )                ADD       EBX, -02
( 004E3853    83FB1B )                CMP       EBX, 1B
( 004E3856    0F8610000000 )          JBE/NA    004E386C
( 004E385C    8B5D00 )                MOV       EBX, [EBP]
( 004E385F    8D6D04 )                LEA       EBP, [EBP+04]
( 004E3862    E84DFFFFFF )            CALL      004E37B4
( 004E3867    E911000000 )            JMP       004E387D
( 004E386C    C1E302 )                SHL       EBX, 02
( 004E386F    8B93C0374E00 )          MOV       EDX, [EBX+004E37C0]
( 004E3875    8B5D00 )                MOV       EBX, [EBP]
( 004E3878    8D6D04 )                LEA       EBP, [EBP+04]
( 004E387B    FFD2 )                  CALL      EDX
( 004E387D    C3 )                    NEXT,
( 46 bytes, 13 instructions )
 ok

This is not as well-optimized as I would have hoped. We have a JMP to the NEXT, compiled by ELSE --- this should just be a NEXT, which is both shorter and faster. I can fix this though --- I will change the code generated so that it uses 
IF ... END ... ;
rather than
IF ... ELSE ... THEN ;
This will get rid of that JMP and replace it with NEXT, to provide a slight speed-up.

Another thing I notice about VFX code is that 
LEA EBP, [EBP+04] is used rather than
ADD EBP, 04
I asked about this and I was told:

On Tuesday, February 19, 2013 at 4:43:20 AM UTC-7, Terje Mathisen wrote:
> LEA is slower if/when any involved register has been recently updated!
> 
> I.e. LEA is the addressing part of a load, so it can suffer AGI stalls.
> 
> Terje
> 
> -- 
> - <Terje.Mathisen at tmsw.no>
> "almost all programming can be viewed as an exercise in caching"

LEA doesn't set the flags, so it can parallelize with an instruction after it that does set the flags --- by comparison, ADD sets the flags so it can't parallelize as easily --- but this doesn't matter in most VFX code because there is no instruction setting the flags afterward. I have switched from using LEA to using ADD unless I'm sure the flag contention problem is an issue.

And finally, for entertainment purposes, here is the abysmally inefficient code that CASE generates:

see ccc 
CCC 
( 004E3620    83FB02 )                CMP       EBX, 02
( 004E3623    0F850A000000 )          JNZ/NE    004E3633
( 004E3629    BB01000000 )            MOV       EBX, 00000001
( 004E362E    E9B0000000 )            JMP       004E36E3
( 004E3633    83FB03 )                CMP       EBX, 03
( 004E3636    0F850A000000 )          JNZ/NE    004E3646
( 004E363C    BB02000000 )            MOV       EBX, 00000002
( 004E3641    E99D000000 )            JMP       004E36E3
( 004E3646    83FB05 )                CMP       EBX, 05
( 004E3649    0F850A000000 )          JNZ/NE    004E3659
( 004E364F    BB03000000 )            MOV       EBX, 00000003
( 004E3654    E98A000000 )            JMP       004E36E3
( 004E3659    83FB07 )                CMP       EBX, 07
( 004E365C    0F850A000000 )          JNZ/NE    004E366C
( 004E3662    BB04000000 )            MOV       EBX, 00000004
( 004E3667    E977000000 )            JMP       004E36E3
( 004E366C    83FB0B )                CMP       EBX, 0B
( 004E366F    0F850A000000 )          JNZ/NE    004E367F
( 004E3675    BB05000000 )            MOV       EBX, 00000005
( 004E367A    E964000000 )            JMP       004E36E3
( 004E367F    83FB0D )                CMP       EBX, 0D
( 004E3682    0F850A000000 )          JNZ/NE    004E3692
( 004E3688    BB06000000 )            MOV       EBX, 00000006
( 004E368D    E951000000 )            JMP       004E36E3
( 004E3692    83FB11 )                CMP       EBX, 11
( 004E3695    0F850A000000 )          JNZ/NE    004E36A5
( 004E369B    BB07000000 )            MOV       EBX, 00000007
( 004E36A0    E93E000000 )            JMP       004E36E3
( 004E36A5    83FB13 )                CMP       EBX, 13
( 004E36A8    0F850A000000 )          JNZ/NE    004E36B8
( 004E36AE    BB08000000 )            MOV       EBX, 00000008
( 004E36B3    E92B000000 )            JMP       004E36E3
( 004E36B8    83FB17 )                CMP       EBX, 17
( 004E36BB    0F850A000000 )          JNZ/NE    004E36CB
( 004E36C1    BB09000000 )            MOV       EBX, 00000009
( 004E36C6    E918000000 )            JMP       004E36E3
( 004E36CB    83FB1D )                CMP       EBX, 1D
( 004E36CE    0F850A000000 )          JNZ/NE    004E36DE
( 004E36D4    BB0A000000 )            MOV       EBX, 0000000A
( 004E36D9    E905000000 )            JMP       004E36E3
( 004E36DE    BBFFFFFFFF )            MOV       EBX, FFFFFFFF
( 004E36E3    C3 )                    NEXT,
( 196 bytes, 42 instructions )
 ok

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

#54591

On Wednesday, February 1, 2017 at 1:26:05 PM UTC-7, hughag...@gmail.com wrote:
> This is not as well-optimized as I would have hoped. We have a JMP to the NEXT, compiled by ELSE --- this should just be a NEXT, which is both shorter and faster. I can fix this though --- I will change the code generated so that it uses 
> IF ... END ... ;
> rather than
> IF ... ELSE ... THEN ;
> This will get rid of that JMP and replace it with NEXT, to provide a slight speed-up.

Well, I made the change --- HAA can be proud to see that his END helps VFX generate more efficient code.

I first had to add this to the NOVICE.4TH meta-compiling support stuff:

: end, ( -- )                           \ runtime: --
    postpone end ;

Here is the new version of the two words that I changed:

: fast-switch> { head default | adr offset size -- }    \ stream: name
    align here  to adr
    head .targ @  to offset
    head tail .targ @  offset -  to size
    size jt-limit u> abort" *** FAST-SWITCH> has too large of a range. Use SLOW-SWITCH> instead. ***"
    offset  head each[  >r      \ -- targ
        begin  r@ .targ @  over <> while  default ,  1+  repeat
        r> .xt @ ,  1+  ]each  drop
    : ( targ -- )
        offset lit, -,          \ -- index
        dup,  size lit,  u>,  if,  drop,  default lit, execute,  end,
        w lit, *,  adr lit, +,  @, execute,  ;,
    head kill-jt ;

: slow-switch> { head default | adr size -- }           \ stream: name
    align here  to adr
    head length  to size
    head each[  dup .targ @ ,  .xt @ ,  ]each
    : ( targ -- )
        adr lit,  size lit,  rot,  d lit,  ['] jt-direction lit,  postpone bsearch
        0=,  if,  drop,  default lit, execute,  end,
        w lit, +,  @, execute,  ;,
    head kill-jt ;


Here is a test:

<switch  ok-1 
:noname  1 ;   2 swof  ok-1 
:noname  2 ;   3 swof  ok-1 
:noname  3 ;   5 swof  ok-1 
:noname  4 ;   7 swof  ok-1 
:noname  5 ;  11 swof  ok-1 
:noname  6 ;  13 swof  ok-1 
:noname  7 ;  17 swof  ok-1 
:noname  8 ;  19 swof  ok-1 
:noname  9 ;  23 swof  ok-1 
:noname 10 ;  29 swof  ok-1 
:noname -1 ;  fast-switch> sss  ok

1 sss . -1  ok
2 sss . 1  ok
11 sss . 5  ok
29 sss . 10  ok
30 sss . -1  ok

see sss 
SSS 
( 004E35E0    83C3FE )                ADD       EBX, -02
( 004E35E3    83FB1B )                CMP       EBX, 1B
( 004E35E6    0F860C000000 )          JBE/NA    004E35F8
( 004E35EC    8B5D00 )                MOV       EBX, [EBP]
( 004E35EF    8D6D04 )                LEA       EBP, [EBP+04]
( 004E35F2    E849FFFFFF )            CALL      004E3540
( 004E35F7    C3 )                    NEXT,
( 004E35F8    C1E302 )                SHL       EBX, 02
( 004E35FB    8B934C354E00 )          MOV       EDX, [EBX+004E354C]
( 004E3601    8B5D00 )                MOV       EBX, [EBP]
( 004E3604    8D6D04 )                LEA       EBP, [EBP+04]
( 004E3607    FFD2 )                  CALL      EDX
( 004E3609    C3 )                    NEXT,
( 42 bytes, 13 instructions )
 ok

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

#54592

On Wednesday, February 1, 2017 at 5:50:33 PM UTC-7, hughag...@gmail.com wrote:
> see sss 
> SSS 
> ( 004E35E0    83C3FE )                ADD       EBX, -02
> ( 004E35E3    83FB1B )                CMP       EBX, 1B
> ( 004E35E6    0F860C000000 )          JBE/NA    004E35F8
> ( 004E35EC    8B5D00 )                MOV       EBX, [EBP]
> ( 004E35EF    8D6D04 )                LEA       EBP, [EBP+04]
> ( 004E35F2    E849FFFFFF )            CALL      004E3540
> ( 004E35F7    C3 )                    NEXT,
> ( 004E35F8    C1E302 )                SHL       EBX, 02
> ( 004E35FB    8B934C354E00 )          MOV       EDX, [EBX+004E354C]
> ( 004E3601    8B5D00 )                MOV       EBX, [EBP]
> ( 004E3604    8D6D04 )                LEA       EBP, [EBP+04]
> ( 004E3607    FFD2 )                  CALL      EDX
> ( 004E3609    C3 )                    NEXT,
> ( 42 bytes, 13 instructions )
>  ok

VFX doesn't do jump-termination (ISYS Forth used that term for this optimization and I continue to use the term). VFX does not convert a CALL followed by a RET (called NEXT, above) into a JMP --- SwiftForth does however.

The reason why VFX doesn't do this apparently, is because some words access the return-address on the return-stack. This is highly non-standard! ANS-Forth (section 3.2.3.3.) says:
A program shall not access values on the return stack (using R@, R>, 2R@ or 2R>) that it did not place there using >R or 2>R;

My rquotations access the return-address on the return-stack, which is theoretically non-standard --- this actually works in every ANS-Forth compiler that I'm aware of --- this works in SwiftForth because the word that accesses the return-address is (R:) that is never followed by EXIT so jump-termination never messes it up.

I don't actually know which words in VFX access the return-address on the return-stack --- I haven't studied VFX much so I'm not very familiar with it.

Note that in VFX we have EXECUTE defined like this:

see execute 
EXECUTE 
( 0040965C    53 )                    PUSH      EBX
( 0040965D    8B5D00 )                MOV       EBX, [EBP]
( 00409660    8D6D04 )                LEA       EBP, [EBP+04]
( 00409663    C3 )                    NEXT,
( 8 bytes, 4 instructions )
 ok

It doesn't matter whether jump-termination is done or not, as it is okay to have EXIT after EXECUTE either way (because EXECUTE doesn't access the return-address on the return-stack, but just pushes a new one).

This is inefficient programming however. Pushing anything onto the return-stack messes up the CALL/RET prediction on the modern x86. Ironically, Stephen Pelc has criticized me for using >R etc. unnecessarily (when stack juggling could be done instead), because doing so messes up CALL/RET prediction on the modern x86 --- so he obviously knows about CALL/RET prediction --- but he is guilty of doing this too!

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

#54594

hughaguilar96@gmail.com wrote:
> ...
> Since the title of this thread is "CASEs compared," here is a comparison:
>
> : ccc ( n -- )
>     case
>     2 of  1  endof
>     3 of  2  endof
>     5 of  3  endof
>     7 of  4  endof
>    11 of  5  endof
>    13 of  6  endof
>    17 of  7  endof
>    19 of  8  endof
>    23 of  9  endof
>    29 of 10  endof
>     -1  swap endcase ;  ok
>
> 1 ccc . -1  ok
> 2 ccc . 1  ok
> 29 ccc . 10  ok
> 30 ccc . -1  ok
>
> What usually messes me up when using CASE is that the test value is still on the stack
> after the last ENDOF and it has to be left on the stack so ENDCASE can discard it. That
> is why we have a SWAP in there.

Having the selector left on the stack when all comparisons fail seems natural and
can be useful.  What gets in the way is ENDCASE wanting to DROP it for you.

> <switch  ok-1
> :noname 1  ;  2 swof  ok-1
> :noname 2  ;  3 swof  ok-1
> :noname 3  ;  5 swof  ok-1
> :noname 4  ;  7 swof  ok-1
> :noname 5  ;  11 swof  ok-1
> :noname 6  ;  13 swof  ok-1
> :noname 7  ;  17 swof  ok-1
> :noname 8  ;  19 swof  ok-1
> :noname 9  ;  23 swof  ok-1
> :noname 10  ;  29 swof  ok-1
> :noname -1  ;  fast-switch> sss  ok
>
> 1 sss . -1  ok
> 2 sss . 1  ok
> 29 sss . 10  ok
> 30 ccc . -1  ok
>
> This is the same thing using <SWITCH --- notice that the need for SWAP is gone --- this
> is much more readable code.
>
> Here is what FAST-SWITCH> generates under VFX:
>
> see sss
> SSS
> ( 004E3850    83C3FE )                ADD       EBX, -02
> ( 004E3853    83FB1B )                CMP       EBX, 1B
> ( 004E3856    0F8610000000 )          JBE/NA    004E386C
> ( 004E385C    8B5D00 )                MOV       EBX, [EBP]
> ( 004E385F    8D6D04 )                LEA       EBP, [EBP+04]
> ( 004E3862    E84DFFFFFF )            CALL      004E37B4
> ( 004E3867    E911000000 )            JMP       004E387D
> ( 004E386C    C1E302 )                SHL       EBX, 02
> ( 004E386F    8B93C0374E00 )          MOV       EDX, [EBX+004E37C0]
> ( 004E3875    8B5D00 )                MOV       EBX, [EBP]
> ( 004E3878    8D6D04 )                LEA       EBP, [EBP+04]
> ( 004E387B    FFD2 )                  CALL      EDX
> ( 004E387D    C3 )                    NEXT,
> ( 46 bytes, 13 instructions )
>  ok
>
> This is not as well-optimized as I would have hoped. We have a JMP to the NEXT,
> compiled by ELSE --- this should just be a NEXT, which is both shorter and faster. I
> can fix this though --- I will change the code generated so that it uses
> IF ... END ... ;
> rather than
> IF ... ELSE ... THEN ;
> This will get rid of that JMP and replace it with NEXT, to provide a slight speed-up.
> ...
> And finally, for entertainment purposes, here is the abysmally inefficient code that
> CASE generates:
>
> see ccc
> CCC
> ( 004E3620    83FB02 )                CMP       EBX, 02
> ( 004E3623    0F850A000000 )          JNZ/NE    004E3633
> ( 004E3629    BB01000000 )            MOV       EBX, 00000001
> ( 004E362E    E9B0000000 )            JMP       004E36E3
> < similar code snipped >
> ( 004E36DE    BBFFFFFFFF )            MOV       EBX, FFFFFFFF
> ( 004E36E3    C3 )                    NEXT,
> ( 196 bytes, 42 instructions )
>  ok

Hard to say as not all code generated in the process of compiling SSS has been declared.
I estimate another 60 bytes for the :nonames plus any tables and code that may have been
generated.  A speed test using worst case for CCC (targ=29) would be interesting.
BTW SSS is a separate definition, in which case I would have written:

: ccc ( n -- )
    2 of  1  end
    3 of  2  end
    5 of  3  end
    7 of  4  end
   11 of  5  end
   13 of  6  end
   17 of  7  end
   19 of  8  end
   23 of  9  end
   29 of 10  end
   drop -1 ;

see CCC
CCC
( 004AAFA0    83FB02 )                CMP       EBX, 02
( 004AAFA3    0F8506000000 )          JNZ/NE    004AAFAF
( 004AAFA9    BB01000000 )            MOV       EBX, 00000001
( 004AAFAE    C3 )                    NEXT,
< similar code snipped >
( 004AB036    BBFFFFFFFF )            MOV       EBX, FFFFFFFF
( 004AB03B    C3 )                    NEXT,
( 156 bytes, 42 instructions )
 ok

VFX users could use +SHORT-BRANCHES to reduce it to 116 bytes at a small
cost in speed.

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

#54597

On Thursday, February 2, 2017 at 3:13:19 AM UTC-7, HAA wrote:
> hughaguilar96@gmail.com wrote:
> > What usually messes me up when using CASE is that the test value is still on the stack
> > after the last ENDOF and it has to be left on the stack so ENDCASE can discard it. That
> > is why we have a SWAP in there.
> 
> Having the selector left on the stack when all comparisons fail seems natural and
> can be useful.  What gets in the way is ENDCASE wanting to DROP it for you.

Having the selector available to the default code might be useful --- if for nothing else, it can be looked at after an abort to determine what invalid value caused the abort --- maybe I'll change <SWITCH to do this; I'll think about it.

I agree that having ENDCASE do the DROP internally is what confuses me pretty much every time, and complicates the code. It would have been a better design to require the CASE construct to always have default code, and just tell the programmer to use DROP if he doesn't have anything that he wants to do with the invalid value.

> > <switch  ok-1
> > :noname 1  ;  2 swof  ok-1
> > :noname 2  ;  3 swof  ok-1
> > :noname 3  ;  5 swof  ok-1
> > :noname 4  ;  7 swof  ok-1
> > :noname 5  ;  11 swof  ok-1
> > :noname 6  ;  13 swof  ok-1
> > :noname 7  ;  17 swof  ok-1
> > :noname 8  ;  19 swof  ok-1
> > :noname 9  ;  23 swof  ok-1
> > :noname 10  ;  29 swof  ok-1
> > :noname -1  ;  fast-switch> sss  ok
> >
> > 1 sss . -1  ok
> > 2 sss . 1  ok
> > 29 sss . 10  ok
> > 30 ccc . -1  ok
> >
> > This is the same thing using <SWITCH --- notice that the need for SWAP is gone --- this
> > is much more readable code.
> >
> > Here is what FAST-SWITCH> generates under VFX:
> >
> > see sss
> > SSS
> > ( 004E3850    83C3FE )                ADD       EBX, -02
> > ( 004E3853    83FB1B )                CMP       EBX, 1B
> > ( 004E3856    0F8610000000 )          JBE/NA    004E386C
> > ( 004E385C    8B5D00 )                MOV       EBX, [EBP]
> > ( 004E385F    8D6D04 )                LEA       EBP, [EBP+04]
> > ( 004E3862    E84DFFFFFF )            CALL      004E37B4
> > ( 004E3867    E911000000 )            JMP       004E387D
> > ( 004E386C    C1E302 )                SHL       EBX, 02
> > ( 004E386F    8B93C0374E00 )          MOV       EDX, [EBX+004E37C0]
> > ( 004E3875    8B5D00 )                MOV       EBX, [EBP]
> > ( 004E3878    8D6D04 )                LEA       EBP, [EBP+04]
> > ( 004E387B    FFD2 )                  CALL      EDX
> > ( 004E387D    C3 )                    NEXT,
> > ( 46 bytes, 13 instructions )
> >  ok
> >
> > This is not as well-optimized as I would have hoped. We have a JMP to the NEXT,
> > compiled by ELSE --- this should just be a NEXT, which is both shorter and faster. I
> > can fix this though --- I will change the code generated so that it uses
> > IF ... END ... ;
> > rather than
> > IF ... ELSE ... THEN ;
> > This will get rid of that JMP and replace it with NEXT, to provide a slight speed-up.
> > ...
> > And finally, for entertainment purposes, here is the abysmally inefficient code that
> > CASE generates:
> >
> > see ccc
> > CCC
> > ( 004E3620    83FB02 )                CMP       EBX, 02
> > ( 004E3623    0F850A000000 )          JNZ/NE    004E3633
> > ( 004E3629    BB01000000 )            MOV       EBX, 00000001
> > ( 004E362E    E9B0000000 )            JMP       004E36E3
> > < similar code snipped >
> > ( 004E36DE    BBFFFFFFFF )            MOV       EBX, FFFFFFFF
> > ( 004E36E3    C3 )                    NEXT,
> > ( 196 bytes, 42 instructions )
> >  ok
> 
> Hard to say as not all code generated in the process of compiling SSS has been declared.
> I estimate another 60 bytes for the :nonames plus any tables and code that may have been
> generated.  A speed test using worst case for CCC (targ=29) would be interesting.
> BTW SSS is a separate definition, in which case I would have written:

Well, I assume the :NONAME code is pretty simple, comparable to:

: nnn  10 ;  ok
see nnn 
NNN 
( 004E3630    8D6DFC )                LEA       EBP, [EBP+-04]
( 004E3633    895D00 )                MOV       [EBP], EBX
( 004E3636    BB0A000000 )            MOV       EBX, 0000000A
( 004E363B    C3 )                    NEXT,
( 12 bytes, 4 instructions )
 ok

There is nothing comparable to SEE for xt values, unfortunately.

I don't think any other code is being generated. The jump-table is data not code, so it doesn't count for code-cache thrashing.

> : ccc ( n -- )
>     2 of  1  end
>     3 of  2  end
>     5 of  3  end
>     7 of  4  end
>    11 of  5  end
>    13 of  6  end
>    17 of  7  end
>    19 of  8  end
>    23 of  9  end
>    29 of 10  end
>    drop -1 ;

Your code above does have the advantage over <SWITCH that the table entries (maybe "selection code snippets" would be a better term) can share local variables.

The disadvantage, of course, is that you are doing a sequential search rather than a binary search like in SLOW-SWITCH> --- and FAST-SWITCH> does a table look-up, which is faster than anything.

Your technique is not bad though --- I would use that in cases in which I had local variables, and I had only a few selections (or speed wasn't an issue).

I think you should not use OF though --- this is not ANS-Forth standard --- you could invent a new word such as:

macro: end? ( targ selector -- targ | )   \ leaves the targ if it didn't match
    over = if  drop  ;

I already said this previously:

On Sunday, January 22, 2017 at 7:45:44 PM UTC-7, hughag...@gmail.com wrote:
> How about this for readability?
> 
> macro: <of  over = if  drop  ;  ok
> macro: of>  exit then ;  ok
> : end-of-line? ( char -- 2|1|0 ) 
>     13  <of  2  of> 
>     10  <of  1  of> 
>     drop  0 ;  ok
> 13 end-of-line? . 2  ok
> 12 end-of-line? . 0  ok
> 10 end-of-line? . 1  ok
> 
> But this assumes that we are testing integers. Will we need another set of macros for strings, and another set for floats?
 
> see CCC
> CCC
> ( 004AAFA0    83FB02 )                CMP       EBX, 02
> ( 004AAFA3    0F8506000000 )          JNZ/NE    004AAFAF
> ( 004AAFA9    BB01000000 )            MOV       EBX, 00000001
> ( 004AAFAE    C3 )                    NEXT,
> < similar code snipped >
> ( 004AB036    BBFFFFFFFF )            MOV       EBX, FFFFFFFF
> ( 004AB03B    C3 )                    NEXT,
> ( 156 bytes, 42 instructions )
>  ok
> 
> VFX users could use +SHORT-BRANCHES to reduce it to 116 bytes at a small
> cost in speed.

I just now noticed that VFX generates long branches. I wonder why it does that??? Aren't short branches always better? They are smaller, so this helps to reduce code-cache thrashing and also helps to get more code compiled into trace-code sooner --- afaik, there is no cost in speed.

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

#54599

On Thursday, February 2, 2017 at 2:46:07 PM UTC-7, hughag...@gmail.com wrote:
> Having the selector available to the default code might be useful --- if for nothing else, it can be looked at after an abort to determine what invalid value caused the abort --- maybe I'll change <SWITCH to do this; I'll think about it.

Well, I thought about it --- I rewrote the code so all of the table entries and the default code are given the selector value as a parameter --- the programmer now has to manually DROP it if it is not needed.

I also changed my comments so TARG means the constant that we are comparing against and SELECTOR means the value given at run-time that we are selecting on --- my comments had previously used the term TARG for both, which was confusing.

Here is the new version:


\ ******
\ ****** This is a <SWITCH control-structure like in C that generates a jump-table.
\ ******

\ You can build a colon word called XXX that switches on targ values. This is how:
\ <SWITCH
\ :NONAME ... ;  targ SWOF
\ ...
\ :NONAME ... ;  FAST-SWITCH> xxx  ( selector -- )

\ The colon word XXX executes a table-entry corresponding to the targ value.
\ If there is no match, then the xt value prior to FAST-SWITCH> is executed as the default.
\ All of the table-entries and the default are given the selector value which they DROP if not needed.
\ It was HAA's suggestion that the selector value be provided --- I had dropped it internally previously.

\ The targ values don't have to be provided in any particular order --- they get sorted internally.
\ If a duplicate targ value is provided, SWOF will abort with an error message at compile-time.

\ This is pretty crude because, unlike in C, the table entries can't have common local variables.
\ I would have liked to use my rquotations, but they don't have an xt that is known at compile-time,
\ so it is not possible to build a jump-table at compile-time. They have a "continuation" that is only known at run-time.
\ My <SWITCH that I have here uses :NONAME for the table entries --- they can have common global variables.

\ FAST-SWITCH> uses the selector value as an index to do the table look up. This is very fast.
\ If the range is too large however, then FAST-SWITCH> will abort with an error message to save memory.
\ In this case, use SLOW-SWITCH> instead. This builds a smaller table and uses BSEARCH to look up the table-entry.

\ Set JT-LIMIT to the range that you want FAST-SWITCH> to support.
\ It is currently set at 2^16 so you can have jump-tables with up to 64K entries. These consume a lot of memory.
\ If memory usage is an issue, then set JT-LIMIT to a smaller value. Use SLOW-SWITCH> instead of FAST-SWITCH>.
\ If the jump-table is sparse, SLOW-SWITCH> might be faster because there is less data-cache thrashing.

\ <SWITCH is primarily provided for writing VM simulators.
\ JT-LIMIT is currently set at 2^16, so it supports simulating a micro-processor with 16-bit opcodes (such as the AVR).
\ SLOW-SWITCH> would be needed for a micro-processor with 32-bit opcodes (such as the ARM or MIPS).

\ Some micro-processors (or byte-code VMs) have 8-bit opcodes, but also have post-bytes on some of the opcodes.
\ These variable-sized opcodes could be done with nested FAST-SWITCH> constructs.

list
    w field .xt
    w field .targ
constant jt

: init-jt ( xt targ node -- node )
    init-list >r
    r@ .targ !
    r@ .xt !
    r> ;

: new-jt ( xt targ -- node )
    jt alloc
    init-jt ;

: kill-jt ( head -- )
    each[  dealloc  ]each ;

: show-jt ( head -- )
    each[  cr  .targ @ .  ]each ;

: jt> ( new-node node -- new-node flag )    \ used by INSERT-ORDERED to build an ascending list without duplicates
    .targ @  over .targ @
    2dup = abort" *** <SWITCH structures not allowed to have duplicate targ values ***"
    > ;

: <switch ( -- head )
    nil ;

: swof ( head xt targ -- new-head )
    new-jt                                  \ -- head node
    ['] jt> swap  insert-ordered drop ;

1 16 lshift  value jt-limit                 \ should be at least 256 so we can support byte-code simulators

\ JT-LIMIT is the index that is too big for the jump-table. This can be any reasonable size.
\ The jump-table size is limited so the programmer doesn't accidentally build a jump-table consuming megabytes.
\ I set it at 2^16 to support simulating a micro-processor with 16-bit opcodes.

: fast-switch> { head default | adr offset size -- }    \ stream: name
    align here  to adr
    head .targ @  to offset
    head tail .targ @  offset -  to size
    size jt-limit u> abort" *** FAST-SWITCH> has too large of a range. Use SLOW-SWITCH> instead. ***"
    offset  head each[  >r      \ -- targ
        begin  r@ .targ @  over <> while  default ,  1+  repeat
        r> .xt @ ,  1+  ]each  drop
    : ( selector -- )
        dup, offset lit, -,     \ -- selector index
        dup,  size lit,  u>,  if,  drop,  default lit, execute,  end,
        w lit, *,  adr lit, +,  @, execute,  ;,
    head kill-jt ;

: jt-direction ( target mid-element -- -1|0|1 )         \ for use by BSEARCH
    @                                   \ -- target mid-value
    2dup = if  2drop  0 end                             \ note for HAA: I used your END rather than EXIT THEN
    < if  -1  else  1  then ;

: slow-switch> { head default | adr size -- }           \ stream: name
    align here  to adr
    head length  to size
    head each[  dup .targ @ ,  .xt @ ,  ]each
    : ( selector -- )
        adr lit,  size lit,  rover,  d lit,  ['] jt-direction lit,  postpone bsearch
        0=,  if,  drop,  default lit, execute,  end,
        w lit, +,  @, execute,  ;,
    head kill-jt ;
    
\ char & comment      \ some testing code

<switch
    :noname  cr . ." is the 1st prime number." ;    2 swof
    :noname  cr . ." is the 2nd prime number." ;    3 swof
    :noname  cr . ." is the 3rd prime number." ;    5 swof
    :noname  cr . ." is the 4th prime number." ;    7 swof
    :noname  cr . ." is the 5th prime number." ;   11 swof
    :noname  cr . ." is the 6th prime number." ;   13 swof
    :noname  cr . ." is the 7th prime number." ;   17 swof
    :noname  cr . ." is the 8th prime number." ;   19 swof
    :noname  cr . ." is the 9th prime number." ;   23 swof
    :noname  cr . ." is not in our list of primes." ;       fast-switch> fff
    
<switch
    :noname  cr . ." is the 1st prime number." ;    2 swof
    :noname  cr . ." is the 2nd prime number." ;    3 swof
    :noname  cr . ." is the 3rd prime number." ;    5 swof
    :noname  cr . ." is the 4th prime number." ;    7 swof
    :noname  cr . ." is the 5th prime number." ;   11 swof
    :noname  cr . ." is the 6th prime number." ;   13 swof
    :noname  cr . ." is the 7th prime number." ;   17 swof
    :noname  cr . ." is the 8th prime number." ;   19 swof
    :noname  cr . ." is the 9th prime number." ;   23 swof
    :noname  cr . ." is not in our list of primes" ;        slow-switch> sss
    
&

\ Testra had a switch construct written in UR/Forth assembly-language that built two arrays,
\ one of targ values and one of xt values. It generated code that would use SCASW to search the targ values.
\ I recommended using a binary search instead. I was told that SCASW is faster, even though it is sequential.
\ On the 80486, the ciscy instructions did usually provide better performance than hand-written code.
\ Because Testra was into building custom processors, they needed a fast simulator.
\ I didn't use their simulator for the MiniForth though --- I wrote my own in MFX.

\ The best way to write a simulator is to have your assembler not only generate the machine-code
\ for the target processor, but also generate a Forth program on the host machine that simulates it.
\ This generated simulation is much faster than a simulator that looks up opcodes at run-time.
\ This only works if you have the source-code for the target processor program that you are simulating.

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

#54614

hughaguilar96@gmail.com wrote:
> On Thursday, February 2, 2017 at 3:13:19 AM UTC-7, HAA wrote:
> > ...
> > Hard to say as not all code generated in the process of compiling SSS has been
> > declared.
> > I estimate another 60 bytes for the :nonames plus any tables and code that may have
> > been
> > generated.  A speed test using worst case for CCC (targ=29) would be interesting.
> > BTW SSS is a separate definition, in which case I would have written:
>
> Well, I assume the :NONAME code is pretty simple, comparable to:
>
> : nnn  10 ;  ok
> see nnn
> NNN
> ( 004E3630    8D6DFC )                LEA       EBP, [EBP+-04]
> ( 004E3633    895D00 )                MOV       [EBP], EBX
> ( 004E3636    BB0A000000 )            MOV       EBX, 0000000A
> ( 004E363B    C3 )                    NEXT,
> ( 12 bytes, 4 instructions )
>  ok
>
> There is nothing comparable to SEE for xt values, unfortunately.

There is (DIS).  In the example above you would use:

$004E3630  (dis)

> I don't think any other code is being generated. The jump-table is data not code, so it
> doesn't count for code-cache thrashing.

Adds to the byte count since we're comparing.  The subroutine referenced by
CALL 004E37B4 would be unique to switch SSS - no?

> ...
> I think you should not use OF though --- this is not ANS-Forth standard --- you could
> invent a new word such as:
>
> macro: end? ( targ selector -- targ | )   \ leaves the targ if it didn't match
>     over = if  drop  ;

My reasons for not doing so are twofold.  I don't use an optimizing compiler.  ANS
doesn't own OF.

> ...
> > VFX users could use +SHORT-BRANCHES to reduce it to 116 bytes at a small
> > cost in speed.
>
> I just now noticed that VFX generates long branches. I wonder why it does that???
> Aren't short branches always better? They are smaller, so this helps to reduce
> code-cache thrashing and also helps to get more code compiled into trace-code sooner
> --- afaik, there is no cost in speed.

Based on my measurement shorts were slower using old cpu.  YMMV

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

#54616

On Friday, February 3, 2017 at 6:42:13 PM UTC-7, HAA wrote:
> hughaguilar96@gmail.com wrote:
> > There is nothing comparable to SEE for xt values, unfortunately.
> 
> There is (DIS).  In the example above you would use:
> 
> $004E3630  (dis)

Thanks for the tip --- I didn't know about (DIS) --- I'm not very familiar with VFX.

> > I think you should not use OF though --- this is not ANS-Forth standard --- you could
> > invent a new word such as:
> >
> > macro: end? ( targ selector -- targ | )   \ leaves the targ if it didn't match
> >     over = if  drop  ;
> 
> My reasons for not doing so are twofold.  I don't use an optimizing compiler.  ANS
> doesn't own OF.

ANS-Forth does own OF --- it is in the ANS-Forth document.

> > > VFX users could use +SHORT-BRANCHES to reduce it to 116 bytes at a small
> > > cost in speed.
> >
> > I just now noticed that VFX generates long branches. I wonder why it does that???
> > Aren't short branches always better? They are smaller, so this helps to reduce
> > code-cache thrashing and also helps to get more code compiled into trace-code sooner
> > --- afaik, there is no cost in speed.
> 
> Based on my measurement shorts were slower using old cpu.  YMMV

I really don't think that short branches are slower --- all multi-pass assemblers compile short branches when possible --- most likely the reason why VFX doesn't is because its assembler is single-pass.

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

#54624

On 2/4/2017 01:52, hughaguilar96@gmail.com wrote:
>> My reasons for not doing so are twofold.  I don't use an optimizing compiler.  ANS
>> doesn't own OF.
> ANS-Forth does own OF --- it is in the ANS-Forth document.
>

Standards don't own anything. They assign meaning to words like OF that 
everyone can understand.

-- 
Alex

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

#54598

On 2/2/2017 5:12 AM, HAA wrote:
> hughaguilar96@gmail.com wrote:
>> ...
>> Since the title of this thread is "CASEs compared," here is a comparison:
>>
>> : ccc ( n -- )
>>     case
>>     2 of  1  endof
>>     3 of  2  endof
>>     5 of  3  endof
>>     7 of  4  endof
>>    11 of  5  endof
>>    13 of  6  endof
>>    17 of  7  endof
>>    19 of  8  endof
>>    23 of  9  endof
>>    29 of 10  endof
>>     -1  swap endcase ;  ok
>>
>> 1 ccc . -1  ok
>> 2 ccc . 1  ok
>> 29 ccc . 10  ok
>> 30 ccc . -1  ok
>>
>> What usually messes me up when using CASE is that the test value is still on the stack
>> after the last ENDOF and it has to be left on the stack so ENDCASE can discard it. That
>> is why we have a SWAP in there.
>
> Having the selector left on the stack when all comparisons fail seems natural and
> can be useful.  What gets in the way is ENDCASE wanting to DROP it for you.

I've thought the same thing.  Would it make sense for the selector to be 
held on the return stack so that it can be be accessible and out of the 
way?  Every iteration of "OF" requires an OVER for the comparison, R@ 
isn't really any harder and the ENDCASE still removes it.  In fact, 
rather than have OF remove the selector with a DROP, it can be left on 
the return stack until jumping to the ENDCASE where it is removed.  That 
saves a bit of code.  It would be a change to the standard of course.

-- 

Rick C

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

#54600

On Thursday, February 2, 2017 at 5:57:05 PM UTC-7, rickman wrote:
> On 2/2/2017 5:12 AM, HAA wrote:
> > hughaguilar96@gmail.com wrote:
> >> ...
> >> Since the title of this thread is "CASEs compared," here is a comparison:
> >>
> >> : ccc ( n -- )
> >>     case
> >>     2 of  1  endof
> >>     3 of  2  endof
> >>     5 of  3  endof
> >>     7 of  4  endof
> >>    11 of  5  endof
> >>    13 of  6  endof
> >>    17 of  7  endof
> >>    19 of  8  endof
> >>    23 of  9  endof
> >>    29 of 10  endof
> >>     -1  swap endcase ;  ok
> >>
> >> 1 ccc . -1  ok
> >> 2 ccc . 1  ok
> >> 29 ccc . 10  ok
> >> 30 ccc . -1  ok
> >>
> >> What usually messes me up when using CASE is that the test value is still on the stack
> >> after the last ENDOF and it has to be left on the stack so ENDCASE can discard it. That
> >> is why we have a SWAP in there.
> >
> > Having the selector left on the stack when all comparisons fail seems natural and
> > can be useful.  What gets in the way is ENDCASE wanting to DROP it for you.
> 
> I've thought the same thing.  Would it make sense for the selector to be 
> held on the return stack so that it can be be accessible and out of the 
> way?  Every iteration of "OF" requires an OVER for the comparison, R@ 
> isn't really any harder and the ENDCASE still removes it.  In fact, 
> rather than have OF remove the selector with a DROP, it can be left on 
> the return stack until jumping to the ENDCASE where it is removed.  That 
> saves a bit of code.  It would be a change to the standard of course.

Write an RfD for your suggestion to be put in Forth-200x!

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

#54603

On 2/2/2017 8:05 PM, hughaguilar96@gmail.com wrote:
> On Thursday, February 2, 2017 at 5:57:05 PM UTC-7, rickman wrote:
>> On 2/2/2017 5:12 AM, HAA wrote:
>>> hughaguilar96@gmail.com wrote:
>>>> ...
>>>> Since the title of this thread is "CASEs compared," here is a comparison:
>>>>
>>>> : ccc ( n -- )
>>>>     case
>>>>     2 of  1  endof
>>>>     3 of  2  endof
>>>>     5 of  3  endof
>>>>     7 of  4  endof
>>>>    11 of  5  endof
>>>>    13 of  6  endof
>>>>    17 of  7  endof
>>>>    19 of  8  endof
>>>>    23 of  9  endof
>>>>    29 of 10  endof
>>>>     -1  swap endcase ;  ok
>>>>
>>>> 1 ccc . -1  ok
>>>> 2 ccc . 1  ok
>>>> 29 ccc . 10  ok
>>>> 30 ccc . -1  ok
>>>>
>>>> What usually messes me up when using CASE is that the test value is still on the stack
>>>> after the last ENDOF and it has to be left on the stack so ENDCASE can discard it. That
>>>> is why we have a SWAP in there.
>>>
>>> Having the selector left on the stack when all comparisons fail seems natural and
>>> can be useful.  What gets in the way is ENDCASE wanting to DROP it for you.
>>
>> I've thought the same thing.  Would it make sense for the selector to be
>> held on the return stack so that it can be be accessible and out of the
>> way?  Every iteration of "OF" requires an OVER for the comparison, R@
>> isn't really any harder and the ENDCASE still removes it.  In fact,
>> rather than have OF remove the selector with a DROP, it can be left on
>> the return stack until jumping to the ENDCASE where it is removed.  That
>> saves a bit of code.  It would be a change to the standard of course.
>
> Write an RfD for your suggestion to be put in Forth-200x!

I read your Wikipedia talk page entries for the slide rule page.  Funny 
how much that worked out like things do here.  What do you think is the 
common connection?  Does the Forth community control Wikipedia as well?

-- 

Rick C

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

#54607

On Friday, 3 February 2017 00:57:05 UTC, rickman  wrote:
> On 2/2/2017 5:12 AM, HAA wrote:
> > hughaguilar96@gmail.com wrote:
> >> ...
> >> Since the title of this thread is "CASEs compared," here is a comparison:
> >>
> >> : ccc ( n -- )
> >>     case
> >>     2 of  1  endof
> >>     3 of  2  endof
> >>     5 of  3  endof
> >>     7 of  4  endof
> >>    11 of  5  endof
> >>    13 of  6  endof
> >>    17 of  7  endof
> >>    19 of  8  endof
> >>    23 of  9  endof
> >>    29 of 10  endof
> >>     -1  swap endcase ;  ok
> >>
> >> 1 ccc . -1  ok
> >> 2 ccc . 1  ok
> >> 29 ccc . 10  ok
> >> 30 ccc . -1  ok
> >>
> >> What usually messes me up when using CASE is that the test value is still on the stack
> >> after the last ENDOF and it has to be left on the stack so ENDCASE can discard it. That
> >> is why we have a SWAP in there.
> >
> > Having the selector left on the stack when all comparisons fail seems natural and
> > can be useful.  What gets in the way is ENDCASE wanting to DROP it for you.
> 
> I've thought the same thing.  Would it make sense for the selector to be 
> held on the return stack so that it can be be accessible and out of the 
> way?  Every iteration of "OF" requires an OVER for the comparison, R@ 
> isn't really any harder and the ENDCASE still removes it.  In fact, 
> rather than have OF remove the selector with a DROP, it can be left on 
> the return stack until jumping to the ENDCASE where it is removed.  That 
> saves a bit of code.  It would be a change to the standard of course.
> 
> -- 
> 
> Rick C

I went through this, too, in 2013. As a result I did this:

http://turboforth.net/resources/case.html

CLF thread here: https://groups.google.com/forum/#!topic/comp.lang.forth/sXcSd_5F6bs%5B1-25%5D

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

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

Back to top | Article view | comp.lang.forth

csiph-web