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

Groups > comp.lang.forth > #46623

Staged division

Show all headers | View raw

I am currently working on staged division, where you first compute a
(scaled) reciprocal, and later scaled-multiply that with a dividend to
get the quotient (usually applying the same divisor to many
dividends).  The current interface looks like this:

uprepare/ ( u1 -- ud )
up/ ( u2 ud -- u3 )
]u/ ( compilation: u1 -- ; run-time: u2 -- u3 )

I am wondering about the stack effect of UP/.  The current one is
convenient for implementing ]U/, but is cumbersome when the divisor is
computed at run-time (but is the alternative ( ud u2 -- u3 ) really
better?).

The problem becomes worse for the staged version of U/MOD (which
requires another stack item in the output of UPREPARE/MOD, for the
divisor), and for floored division we probably need another stack item
(for a correction bias).  

How to deal with all these stack items?

Data stack?  Requires cumbersome PICKs, but (some of) today's compilers are up
to the task.

Return stack? No standard way to get more than a double.

Locals?  No standard way to get all the cells with one local, usage
restrictions in the standard.

Memory? Inefficient with current compilers and in the foreseeable
future, and requires cumbersome allocation and deallocation.

Any ideas?

Anyway, here are first results, with UP/ implemented as:

: up/ ( u ud -- u2 )
    >r over um* nip 0 rot r> um* d+ nip ;

Benchmarks:

: benchmark
    0 100000000 0 ?do
        i [ 987654 ]u/ +
    loop . ;

: benchmark2
    0 100000000 0 ?do
        i 987654 / +
    loop . ;

32b     64b
vfxlin  gforth-fast
0.591   1.506 benchmark
0.539   2.437 benchmark2

Times in seconds user time on a Core i3-3227u (1.9GHz Ivy Bridge).

That's somewhat surprising.  I had expected Gforth to suffer more from
not being able to optimize the stack shuffling overhead in UP/ away,
and VFX to benefit from being able to do that, it being especially
good at dealing with constants, but it turns out differently.  Here's
the loop body in VFX:

benchmark             benchmark2
MOV  EDX, [ESP]       MOV  EDX, [ESP]    
PUSH 000001B2         MOV  ECX, 0096B43F 
MOV  ECX, DD8DFF61    MOV  EAX, EDX      
LEA  EBP, [EBP+-0C]   CDQ                
MOV  [EBP], EDX       IDIV ECX           
MOV  [EBP+04], EDX    ADD  EBX, EAX      
MOV  [EBP+08], EBX    ADD  [ESP], 01     
MOV  EBX, ECX         ADD  [ESP+04], 01  
MOV  EAX, EBX         JNO  080C0AC8      
MUL  [EBP]
POP  EBX
MOV  ECX, EDX
MOV  EAX, EBX
MUL  [EBP+04]
ADD  ECX, EAX
ADC  EDX, 00
ADD  EDX, [EBP+08]
ADD  [ESP], 01
ADD  [ESP+04], 01
MOV  EBX, EDX
LEA  EBP, [EBP+0C]
JNO  080C0A28

Ok, quite a few instructions more in benchmark, and a memory-carried
dependency (through [EBP+08], and on the critical path, too), but
given the slowness of IDIV, it's still surprising to me that
benchmark2 is faster.

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

Back to comp.lang.forth | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Staged division anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-11 11:55 +0000
  Re: Staged division Gary Bergstrom <forthprgrmr@gmail.com> - 2016-04-18 10:47 -0700
    Re: Staged division anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-04-24 17:22 +0000

csiph-web