Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #19163
| From | mhx@iae.nl (Marcel Hendrix) |
|---|---|
| Subject | Re: structure and interpretation of computer programs exercsie 1.3 in forth |
| Newsgroups | comp.lang.forth |
| Message-ID | <95779109028434@frunobulax.edu> (permalink) |
| Date | 2013-01-26 12:58 +0200 |
| References | <fb00c93f-5324-45ac-a612-5a65dd8e02fd@xm8g2000pbc.googlegroups.com> |
| Organization | Wanadoo |
Hugh Aguilar <hughaguilar96@yahoo.com> wrote Re: structure and interpretation of computer programs exercsie 1.3 in forth
[..]
> Here is a version of MINMAX in traditional assembly language:
>
> minmax: ; a b -- min max
> mov edx, [ebp]
> cmp edx, ebx
> mov ecx, edx
> cmovg edx, ebx
> cmovg ebx, ecx
> mov [ebp], edx
> next
>
> This is only 6 instructions, rather than 7, and it has only 2 memory
> accesses, rather than 3 --- so it should be slightly more efficient
> than what VFX generated --- but VFX was still pretty impressive.
>
> I haven't tested this, because I haven't yet figured out how the
> assembler works in VFX. I just wrote this in traditional assembly
> format. I'm assuming that EBP is the parameter stack pointer and EBX
> is the top value of the stack --- afaik, that is how VFX is
> implemented.
>
> Your method would be written like this:
>
> minmax: ; a b -- min max
> cmp [ebp], ebx
> jg swap
> next
>
> swap: ; a b -- b a
> xchg [ebp], ebx
> next
>
> It is shorter not longer on the x86. It is also slower not faster
> (because of the jump, which the branch-predictor will get wrong 50% of
> the time).
This problem is a lot more interesting than I initially thought.
My impression was that Intel continuously benchmarks generated code
and tweaks their CPU's so that simple stupid practices always win,
no matter what hardware needs to be added. My hypothesis was
that the branching code might be faster than the conditional moves.
Apparently, it doesn't work like that.
A rough benchmark of the two snippets seems to back up my initial
hypothesis:
FORTH> bench
branchless minmax : 0.271 seconds elapsed.
branching minmax2 : 0.123 seconds elapsed.
branching minmax3 : 0.123 seconds elapsed.
However, this is when the looped minmax2/3 always see the same two values
to compare and can perfectly predict which branch will be taken.
For the second benchmark I used a random generator to provide the
values to be compared, en the results are radically different:
FORTH> bench2
overhead : 0.719 seconds elapsed.
branchless minmax : 0.731 seconds elapsed.
branching minmax2 : 1.265 seconds elapsed.
branching minmax3 : 1.182 seconds elapsed.
The overhead of all three versions is 719 ms. Now the branchless
minmax needs almost zero time (12 ms) compared to minmax2 and minmax3
(546 ms). The branchless minmax is slightly larger, but with respect
to runtime there is no comparison -- it is 45 times faster at least.
There is another weird thing here: the exchange instruction does
not matter in bench, but leads to slighter slower code in bench2.
It is probably more important to notice that even in the case
where one operand is memory based, xchg is not slow at all.
-marcel
--
NEEDS -assemble
ANEW -minmax
CODE minmax \ a b -- min max
[rsp] -> rax mov,
[rsp cell +] -> rdx mov,
rax -> rdx cmp,
rdx -> rcx mov,
rax -> rdx cmovg,
rcx -> rax cmovg,
rdx -> [rsp cell +] mov,
rax -> [rsp] mov,
rbx jmp,
END-CODE
CODE minmax2 \ a b -- min max
rax pop,
rax -> [rsp] cmp,
>, IF, rax -> [rsp] xchg,
ENDIF, rax push,
rbx jmp,
END-CODE
CODE minmax3 \ a b -- min max
rax pop,
rcx pop,
rax -> rcx cmp,
>, IF, rax -> rcx xchg,
ENDIF, rcx push,
rax push,
rbx jmp,
END-CODE
#100000000 VALUE #times
1 2 DVALUE vals
: bench TIMER-RESET #times 0 ?DO LOOP MS? LOCAL preset
CR ." branchless minmax : " preset TIMER-PRESET vals #times 0 ?DO minmax LOOP 2drop .ELAPSED
CR ." branching minmax2 : " preset TIMER-PRESET vals #times 0 ?DO minmax2 LOOP 2drop .ELAPSED
CR ." branching minmax3 : " preset TIMER-PRESET vals #times 0 ?DO minmax3 LOOP 2drop .ELAPSED ;
: bench2
CR ." overhead : " TIMER-RESET #times 0 ?DO random random 2drop LOOP .ELAPSED
CR ." branchless minmax : " TIMER-RESET #times 0 ?DO random random minmax 2drop LOOP .ELAPSED
CR ." branching minmax2 : " TIMER-RESET #times 0 ?DO random random minmax2 2drop LOOP .ELAPSED
CR ." branching minmax3 : " TIMER-RESET #times 0 ?DO random random minmax3 2drop LOOP .ELAPSED ;
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 04:22 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-11 05:47 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:12 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:18 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:20 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:19 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:38 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:51 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 07:10 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 07:58 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth rickman <gnuarm@gmail.com> - 2013-01-14 10:01 -0500
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:25 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:28 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:33 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:37 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:56 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 08:03 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 08:06 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 12:27 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 17:32 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-13 23:21 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-13 23:41 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-13 23:43 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-14 00:02 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-14 22:43 +1300
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-14 02:41 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-01-14 11:13 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-01-14 11:16 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth mhx@iae.nl (Marcel Hendrix) - 2013-01-14 21:27 +0200
Re: structure and interpretation of computer programs exercsie 1.3 in forth Howerd <howerdo@yahoo.co.uk> - 2013-01-14 03:34 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-14 12:53 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-17 17:31 +1300
Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-21 19:35 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-14 02:55 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth rickman <gnuarm@gmail.com> - 2013-01-14 10:14 -0500
Re: structure and interpretation of computer programs exercsie 1.3 in forth Bernd Paysan <bernd.paysan@gmx.de> - 2013-01-14 20:04 +0100
Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-21 19:57 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-21 23:19 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-24 18:58 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-25 15:46 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Pablo Hugo Reda <pabloreda@gmail.com> - 2013-01-25 19:09 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-26 01:12 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth mhx@iae.nl (Marcel Hendrix) - 2013-01-26 12:58 +0200
Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-26 04:42 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-01-26 14:35 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:38 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 12:36 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 17:33 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-14 22:46 +1300
Re: structure and interpretation of computer programs exercsie 1.3 in forth rickman <gnuarm@gmail.com> - 2013-01-14 10:20 -0500
Re: structure and interpretation of computer programs exercsie 1.3 in forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-01-14 10:41 -0600
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-17 17:34 +1300
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:48 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:49 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-21 23:55 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Ed" <invalid@nospam.com> - 2013-01-18 12:50 +1100
Re: structure and interpretation of computer programs exercsie 1.3 in forth Bernd Paysan <bernd.paysan@gmx.de> - 2013-01-18 23:31 +0100
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Ed" <invalid@nospam.com> - 2013-01-20 12:42 +1100
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <markrobertwills@yahoo.co.uk> - 2013-01-20 01:24 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-20 15:51 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-21 22:14 +1300
Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-21 19:14 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth "A. K." <akk@nospam.org> - 2013-01-20 11:13 +0100
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-20 02:45 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-21 17:14 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-23 01:52 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-01-23 04:25 -0600
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-23 15:20 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-23 09:29 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-23 17:40 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-23 22:03 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-24 22:13 +1300
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-24 02:57 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-26 13:49 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-26 12:40 -1000
Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-26 23:20 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth mhx@iae.nl (Marcel Hendrix) - 2013-01-27 09:52 +0200
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2013-01-23 23:05 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-21 17:05 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth "A. K." <akk@nospam.org> - 2013-01-21 19:28 +0100
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-22 17:43 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2013-01-22 19:12 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth stephenXXX@mpeforth.com (Stephen Pelc) - 2013-01-21 12:13 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-21 17:28 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-22 18:06 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth Bernd Paysan <bernd.paysan@gmx.de> - 2013-01-22 19:30 +0100
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 23:06 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-22 02:20 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-22 03:36 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-22 06:51 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth marko <marko@marko.marko> - 2013-01-24 22:14 +1100
Re: structure and interpretation of computer programs exercsie 1.3 in forth the_gavino_himself <visphatesjava@gmail.com> - 2013-01-27 20:39 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth marko <marko@marko.marko> - 2013-02-01 22:07 +1100
Re: structure and interpretation of computer programs exercsie 1.3 in forth marko <marko@marko.marko> - 2013-02-01 22:53 +1100
Re: structure and interpretation of computer programs exercsie 1.3 in forth the_gavino_himself <visphatesjava@gmail.com> - 2013-02-08 19:50 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Elizabeth D Rather <erather@forth.com> - 2013-02-08 19:22 -1000
Re: structure and interpretation of computer programs exercsie 1.3 in forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-01-11 11:44 -0600
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 12:34 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:18 -0800
Re:structure and interpretation of computer programs exercsie 1.3 in forth Hans Bezemer <the.beez.speaks@gmail.com> - 2013-01-14 00:13 +0100
Re: structure and interpretation of computer programs exercsie 1.3 in forth Doug Hoffman <glidedog@gmail.com> - 2013-01-13 19:12 -0500
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 18:26 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-01-14 08:29 +0000
Re: structure and interpretation of computer programs exercsie 1.3 in forth Hans Bezemer <the.beez.speaks@gmail.com> - 2013-01-14 23:52 +0100
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 18:31 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-13 23:19 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:46 -0800
Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-21 23:40 -0800
csiph-web