MOVE and CMOVE speed (was: alternatives to `find`)

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	MOVE and CMOVE speed (was: alternatives to `find`)
Date	2015-11-04 09:52 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<2015Nov4.105206@mips.complang.tuwien.ac.at> (permalink)
References	(2 earlier) <1xpejdlw307sa.cfhipie69ann$.dlg@40tude.net> <1c9f4cc5-8086-4c29-9dd2-d9b997d406fc@googlegroups.com> <5637bbe8$0$23795$e4fe514c@news.xs4all.nl> <2015Nov3.123145@mips.complang.tuwien.ac.at> <56392305$0$23730$e4fe514c@news.xs4all.nl>

Show all headers | View raw

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>>Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>Did you realize that there is also a MOVE , that deals in address
>>>units?
>>>However it is intelligent, it handles overlaps. This one should
>>>the primitive, but the intelligence makes it less usefull as a
>>>primitive, because
>>>1. You get a check, unwanted overhead,
>
>>On the contrary, CMOVE is overspecified for most uses (and CMOVE>,
>>too), leading to overhead: Take the following microbenchmark:
>
>>create foo 20000 allot
>>: bench-move   10000000 0 do foo foo 1+     1000 move  loop ;
>>: bench-cmove  10000000 0 do foo foo 1+     1000 cmove loop ;
>>: bench-cmove2 10000000 0 do foo foo 1000 + 1000 cmove loop ;
>
>>The user times on a Core i7-4790K are as follows:
>
>> 0.196s bench-move
>>11.276s bench-cmove
>> 2.820s bench-cmove2
>
>>>2. intelligent, it can't be use for ERASE and FILL or implementing wheels.
>
>>It's inefficient to use CMOVE for FILL/ERASE:
>
>>: bench-fill   10000000 0 do foo 1000 1 fill loop ;
>>: bench-erase  10000000 0 do foo 1000 erase loop ;
>
>> 0.192s bench-fill
>> 0.204s bench-erase
>
>>I.e., about 56 times faster than using CMOVE for it as in BENCH-CMOVE.
>
>So if you use CMOVE for memory propagation it is slower than for
>non overlapping. Okay, but that is a useless conclusion. Two different
>functionalities have different timings.

You (want to?) miss the main point: MOVE is much faster for
non-overlap than CMOVE.  FILL is much faster for filling (and erasing)
than CMOVE.

>I can't believe you used the same buffer all the time, so this
>benchmark stays in the L1 cache, hardly realistic.

The L1 cache has a pretty good hit rate, and that includes uses of
MOVE, CMOVE, FILL and ERASE, most of which are not for huge memory
regions.

But sure, if you want numbers for L1, L2 miss, L3 hit, here they are
(larger array, same number of total byte accesses):

create foo 2000000 allot
: bench-move   10000 0 do foo foo 1+ 1000000 move loop ;
: bench-cmove  10000 0 do foo foo 1+ 1000000 cmove loop ;
: bench-cmove2 10000 0 do foo foo 1000000 + 1000000 cmove loop ;
: bench-fill   10000 0 do foo 1000000 1 fill loop ;
: bench-erase  10000 0 do foo 1000000 erase loop ;

 0.280s move
11.372s cmove (for filling)
 2.748s cmove2 (non-overlapping)
 0.296s fill
 0.296s erase                   

So the L3 access slows it down a little, but not that much.

Once more with main memory (same number of total byte accesses):

200000000 allocate throw constant foo
: bench-move   100 0 do foo foo 1+ 100000000 move loop ;
: bench-cmove  100 0 do foo foo 1+ 100000000 cmove loop ;
: bench-cmove2 100 0 do foo foo 100000000 + 100000000 cmove loop ;
: bench-cmove3 100 0 do foo 100000000 + foo 100000000 cmove loop ;
: bench-fill   100 0 do foo 100000000 1 fill loop ;
: bench-erase  100 0 do foo 100000000 erase loop ;

 0.900s move                    
11.388s cmove (for filling)     
 2.784s cmove2 (non-overlapping)
 0.912s fill                    
 0.924s erase                   

Again, even main memory access does not cost so much that it makes up
for the CMOVE overhead.  But the main memory overhead seems to be
absorbed in the CMOVE overhead (thanks to prefetching and store
buffering).

>This are the results for copying 1000 bytes with overlap, with
>move and cmove, and for 1,000,000 bytes, with fill
>---------------------------
>Left move, right cmove
>Doing 1000 bytes
>First has overlap
> 314 uS  309 uS
>  430 uS  442 uS
>  Fill
>   270 uS
>
>Second time: 1,000,000 bytes
> 1.954mS  3.186mS
>  2.060mS  1.574mS
>  Fill
>   1183 uS
>
>
>    688.784mS  2112.263mS  113.789mS
>-----------------------------
>
>The last is your benchmark, but I toned it down to 1M repetitions.
>Results for lina64 AMD(Vishera) 4 Ghz, MOVE CMOVE FILL coded
>in assembler using the REP mechanism of x86, one byte at a time.

So that would be 6.88s for bench-move, 21.12s for BENCH-CMOVE, and
1.13s for FILL accessing L1.  All slower than my corresponding numbers
(which may be due to the CPU or due to the software), but anyway, MOVE
comes out faster there, too.

Concerning your other measurements, it's strange that the 1M
non-overlapping MOVE is so much slower than the CMOVE, because apart
from the check it could do the same thing, and the check should not
take 0.5ms.  Maybe your MOVE uses the other direction from CMOVE for
these parameters, and that happens to be slower on that CPU; in that
case, change it such that the preferred direction of the CPU happens
more often.

Gforth implements MOVE using glibc's memmove(), CMOVE with an C-coded
loop (which gcc translates to a machine-code loop, not REP MOVSB), and
FILL (and ERASE) with glibc's memset().

>Nothing changes my mind.

That's a pity.

- 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 — Previous in thread | Find similar | Unroll thread

Thread

alternatives to `find` Marcos Cruz <use_the_contact_page@programandala.net> - 2015-10-21 20:09 +0000
  Re: alternatives to `find` anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-22 05:54 +0000
    Re: alternatives to `find` Marcos Cruz <use_the_contact_page@programandala.net> - 2015-10-22 15:37 +0000
      Re: alternatives to `find` Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-10-22 22:03 -0700
        Re: alternatives to `find` Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-10-22 22:14 -0700
          Re: alternatives to `find` hughaguilar96@gmail.com - 2015-10-23 01:28 -0700
          Re: alternatives to `find` Marcos Cruz <use_the_contact_page@programandala.net> - 2015-10-23 12:12 +0000
          Re: alternatives to `find` anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-26 11:39 +0000
            Re: alternatives to `find` Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-10-26 05:14 -0700
        Re: alternatives to `find` Marcos Cruz <use_the_contact_page@programandala.net> - 2015-10-23 12:30 +0000
          Re: alternatives to `find` Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-10-23 22:52 -0700
            Re: alternatives to `find` Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-10-23 23:14 -0700
            Re: alternatives to `find` Marcos Cruz <use_the_contact_page@programandala.net> - 2015-10-24 11:15 +0000
              Re: alternatives to `find` Coos Haak <chforth@hccnet.nl> - 2015-10-24 14:34 +0200
                Re: alternatives to `find` anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-24 14:45 +0000
                Re: alternatives to `find` Coos Haak <chforth@hccnet.nl> - 2015-10-24 17:23 +0200
            Preserving standard and common use names (Re: alternatives to `find`) Marcos Cruz <use_the_contact_page@programandala.net> - 2015-10-24 11:53 +0000
              Re: Preserving standard and common use names (Re: alternatives to `find`) Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-10-24 22:48 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) "Elizabeth D. Rather" <erather@forth.com> - 2015-10-24 21:05 -1000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-10-25 01:34 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) "Elizabeth D. Rather" <erather@forth.com> - 2015-10-24 22:45 -1000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-25 09:16 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) "Elizabeth D. Rather" <erather@forth.com> - 2015-10-25 08:46 -1000
                Re: Preserving standard and common use names (Re: alternatives to `find`) hughaguilar96@gmail.com - 2015-10-25 21:31 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-10-25 18:50 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) Mark Wills <markwills1970@gmail.com> - 2015-10-26 01:57 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) Paul Rubin <no.email@nospam.invalid> - 2015-10-26 02:07 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) Ron Aaron <rambamist@gmail.com> - 2015-10-26 11:14 +0200
                Re: Preserving standard and common use names (Re: alternatives to `find`) Mark Wills <markwills1970@gmail.com> - 2015-10-26 04:18 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) "Elizabeth D. Rather" <erather@forth.com> - 2015-10-26 09:22 -1000
                Re: Preserving standard and common use names (Re: alternatives to `find`) hughaguilar96@gmail.com - 2015-10-26 21:34 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-26 10:58 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Mark Wills <markwills1970@gmail.com> - 2015-10-26 05:59 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-10-26 14:58 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-27 17:09 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-28 12:50 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-28 15:56 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Paul Rubin <no.email@nospam.invalid> - 2015-10-28 10:31 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-10-28 19:26 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) Paul Rubin <no.email@nospam.invalid> - 2015-10-28 12:37 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-28 23:03 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Paul Rubin <no.email@nospam.invalid> - 2015-10-28 16:21 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-10-28 20:37 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-28 23:13 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-10-29 03:01 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-29 10:04 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-29 15:29 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Mark Wills <markwills1970@gmail.com> - 2015-10-30 04:17 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2015-10-30 11:36 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-31 15:25 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2015-10-31 20:34 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2015-10-30 20:51 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Mark Wills <markwills1970@gmail.com> - 2015-11-02 01:39 -0800
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-11-02 11:12 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2015-11-02 12:09 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Mark Wills <markwills1970@gmail.com> - 2015-11-02 05:09 -0800
                Re: Preserving standard and common use names (Re: alternatives to `find`) Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-11-02 06:23 -0800
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-11-02 14:39 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2015-11-20 16:20 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Mark Wills <markwills1970@gmail.com> - 2015-11-21 00:26 -0800
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-31 15:03 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-31 16:35 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-11-01 14:07 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-11-01 21:05 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-31 16:31 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-10-31 20:33 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) Bernd Paysan <bernd.paysan@gmx.de> - 2015-10-29 22:27 +0100
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-29 13:19 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-29 10:00 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-29 13:29 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-29 14:04 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-29 16:29 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-29 16:42 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-29 16:13 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) mhx@iae.nl - 2015-10-29 12:19 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-31 14:12 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) stephen@mpeforth.com (Stephen Pelc) - 2015-10-31 16:49 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) Paul Rubin <no.email@nospam.invalid> - 2015-10-31 10:33 -0700
                Re: Preserving standard and common use names (Re: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-11-01 14:14 +0000
                Re: Preserving standard and common use names (Re: alternatives to `find`) hughaguilar96@gmail.com - 2015-10-25 21:52 -0700
          Re: alternatives to `find` Albert van der Horst <albert@spenarnc.xs4all.nl> - 2015-10-30 12:30 +0000
      Re: alternatives to `find` anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-10-26 11:47 +0000
  Re: alternatives to `find` Chris Curl <ccurl609@gmail.com> - 2015-11-02 06:17 -0800
    Re: alternatives to `find` Mark Wills <markwills1970@gmail.com> - 2015-11-02 06:35 -0800
    Re: alternatives to `find` Coos Haak <chforth@hccnet.nl> - 2015-11-02 15:45 +0100
      Re: alternatives to `find` Chris Curl <ccurl609@gmail.com> - 2015-11-02 07:17 -0800
        Re: alternatives to `find` Albert van der Horst <albert@spenarnc.xs4all.nl> - 2015-11-02 19:39 +0000
          Re: alternatives to `find` Mark Wills <markwills1970@gmail.com> - 2015-11-02 12:19 -0800
          Re: alternatives to `find` anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-11-03 11:31 +0000
            Re: alternatives to `find` Albert van der Horst <albert@spenarnc.xs4all.nl> - 2015-11-03 21:11 +0000
              MOVE and CMOVE speed (was: alternatives to `find`) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-11-04 09:52 +0000

csiph-web