Re: Rules and hypotheticals: continuations versus callbacks

[Matthijs van Duin]

On Wed, Mar 19, 2003 at 10:38:54AM +0100, Leopold Toetsch wrote:
I would propose, estimate the ops you need and test it :)
I haven't completed testing yet, however it's becoming clear to me that 
this is likely to be a pointless effort

There are so many variables that can affect performance here that the 
results I may find in these tests are unlikely to have any relation to 
the performance of rules in practice.

1. making continuations affects the performance of *other* code (COW)
2. the "let" operation is missing and all attempts to fake it are silly
3. to really test it, I'd need to make subrules full subroutines, but then 
  the performance difference will probably disappear in the overhead of all 
  other stuff.  To test I'd need large, realistic patterns; and I'm 
  certainly not in the mood to write PIR for them manually.

And it appears that on my machine continuations and garbage collection have
a quarrel, which also makes testing problematic.
I guess the only way to find out is to implement both systems and compare 
them using a large test set of realistic grammars.  Or ofcourse just 
implement it using continuations (system #1), since the speed difference 
probably isn't gonna be huge anyway.

Here is my test program for continuation and the results on my machine:

# "aaab" ~~ / ^ [ a | a* ] ab <fail> /

        set I5, 1000
        sweepoff        # or bus error
        collectoff      # or segmentation fault
        
begin:
        set S0, "aaab"
        set I0, 0
        new P0, .Continuation
        set_addr I1, second
        set P0, I1
        rx_literal S0, I0, "a", backtrack
        branch third
second:
        new P0, .Continuation
        set_addr I1, fail
        set P0, I1
deeper:
        rx_literal S0, I0, "a", third
        save P0         # normally hypothesize
        new P0, .Continuation
        set_addr I1, unwind
        set P0, I1
        branch deeper
unwind:
        dec I0          # normally de-hypothesize
        restore P0      # normally de-hypothesize
third:
        rx_literal S0, I0, "ab", backtrack
        sub I0, 2       # normally de-hypothesize
backtrack:
        invoke
fail:
        dec I5
        if I5, begin
        end


                  OPERATION PROFILE                 

 CODE   OP FULL NAME         CALLS  TOTAL TIME    AVG TIME
 -----  ------------       -------  ----------  ----------
     0  end                      1    0.000029    0.000029
    40  set_addr_i_ic         5000    0.024928    0.000005
    46  set_i_ic              1001    0.010573    0.000011
    60  set_s_sc              1000    0.005717    0.000006
    66  set_p_i               5000    0.016201    0.000003
   213  if_i_ic               1000    0.002848    0.000003
   274  dec_i                 4000    0.011390    0.000003
   370  sub_i_ic              1000    0.004227    0.000004
   675  save_p                3000    0.192309    0.000064
   682  restore_p             3000    0.246457    0.000082
   719  branch_ic             4000    0.012216    0.000003
   770  sweepoff                 1    0.000014    0.000014
   772  collectoff               1    0.000003    0.000003
   786  new_p_ic              5000    0.179403    0.000036
   819  invoke                5000    0.026285    0.000005
   962  rx_literal_s_i_sc_ic 10000    0.054260    0.000005
 -----  ------------       -------  ----------  ----------
    16                       48004    0.786861    0.000016
iBook; PPC G3; 700 Mhz

--
Matthijs van Duin  --  May the Forth be with you!