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

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

alternatives to `find`

Started byMarcos Cruz <use_the_contact_page@programandala.net>
First post2015-10-21 20:09 +0000
Last post2015-11-04 09:52 +0000
Articles 11 on this page of 91 — 15 participants

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

Contents

  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

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

#42996

FromAlbert van der Horst <albert@spenarnc.xs4all.nl>
Date2015-10-30 12:30 +0000
Message-ID<563362f8$0$23799$e4fe514c@news.xs4all.nl>
In reply to#42768
Marcos Cruz <use_the_contact_page@programandala.net> writes:

>En/Je/On 2015-10-23, Raimond Dragomir <raimond.dragomir@gmail.com>
>escribió/skribis/wrote:

>> In my system I have SEARCH which returns the dictionary pointer (the
>> so called "name token"). Based on it and knowning the dictionary entry
>> structure, you can get all info about a word.

>So its stack effect is

>       ( ca len -- nt | 0 )

I have that as the dictionary search word used by the interpreter since
about 2001. I called it FOUND. And in 1993 (being involved in the design
of the transputer Forth, find it on my website), I felt the need for nt's.
I called them dea's (nt is not a good name, "dictionary entry address" suggest
what is the intention that all information of the word can be found
via this address) Furthermore a ca len is a stringconstant. So I get
FOUND   ( sc -- dea | null )

Glad you guys catch up ;-)

>That's the latest option I've implemented, after Gforth's `find-name`,
>So far it seems simpler and more versatile than previous alternatives I
>tried.

>> I also have SEARCHWORDLIST that searches in a wordlist given as a
>> parameter.

>       ( ca len wid -- nt | 0 )

>Is it?

That is also a good factor. Normally this is repeated over wordlists
so I don't throw away the stringconstant.
(FIND)   ( sc wid -- dea | null)

: SEARCHWORDLIST (FIND) NIP NIP ;


Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#42840

Fromanton@mips.complang.tuwien.ac.at (Anton Ertl)
Date2015-10-26 11:47 +0000
Message-ID<2015Oct26.124727@mips.complang.tuwien.ac.at>
In reply to#42759
Marcos Cruz <use_the_contact_page@programandala.net> writes:
>`find-name` is not in the standard, but is it used the same way by other
>widely known systems?

Maybe.  The issue is that even if it isn't, it's a good idea to use a
different name for different behaviour.

- 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/

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

#43110

FromChris Curl <ccurl609@gmail.com>
Date2015-11-02 06:17 -0800
Message-ID<a088b91f-dfd5-40c3-8172-764be3673421@googlegroups.com>
In reply to#42733
In my simple implementation, this would create an empty word in the dictionary.

: string, ( addr count -- ) DUP C, 0 DO DUP C@ C, 1+ LOOP DROP ;
: create-empty ( addr count -- ) HERE LAST , 0 C, 0 C, string, 0 c, (LAST) ! ;

At this point HERE is where the word's implementation begins, which has yet to be defined, so executing the word now would most likely result in an error, unless HERE already had valid code in it.

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

#43112

FromMark Wills <markwills1970@gmail.com>
Date2015-11-02 06:35 -0800
Message-ID<dd7d6f29-60bd-42f1-8eb5-6dfa96ecd8ac@googlegroups.com>
In reply to#43110
On Monday, 2 November 2015 14:17:59 UTC, Chris Curl  wrote:
> In my simple implementation, this would create an empty word in the dictionary.
> 
> : string, ( addr count -- ) DUP C, 0 DO DUP C@ C, 1+ LOOP DROP ;
> : create-empty ( addr count -- ) HERE LAST , 0 C, 0 C, string, 0 c, (LAST) ! ;
> 
> At this point HERE is where the word's implementation begins, which has yet to be defined, so executing the word now would most likely result in an error, unless HERE already had valid code in it.

Indeed. Nice clear code. My point of course being that issues such as
linking a word into the dictionary in the current wordlist etc are often
very specific to the system you are using, thus a standardised set of 
words to address this would be nice.

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

#43114

FromCoos Haak <chforth@hccnet.nl>
Date2015-11-02 15:45 +0100
Message-ID<1xpejdlw307sa.cfhipie69ann$.dlg@40tude.net>
In reply to#43110
Op Mon, 2 Nov 2015 06:17:57 -0800 (PST) schreef Chris Curl:

> In my simple implementation, this would create an empty word in the dictionary.
> 
>: string, ( addr count -- ) DUP C, 0 DO DUP C@ C, 1+ LOOP DROP ;
shorter:
: string, dup c, 0 ?do count c, loop drop ;
still shorter:
: string, dup c, here swap dup allot cmove ;

I use ?DO in case count of the string is zero. CMOVE knows this too.

groet Coos

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

#43117

FromChris Curl <ccurl609@gmail.com>
Date2015-11-02 07:17 -0800
Message-ID<1c9f4cc5-8086-4c29-9dd2-d9b997d406fc@googlegroups.com>
In reply to#43114
On Monday, November 2, 2015 at 9:46:21 AM UTC-5, Coos Haak wrote:
> Op Mon, 2 Nov 2015 06:17:57 -0800 (PST) schreef Chris Curl:
> 
> > In my simple implementation, this would create an empty word in the dictionary.
> > 
> >: string, ( addr count -- ) DUP C, 0 DO DUP C@ C, 1+ LOOP DROP ;
> shorter:
> : string, dup c, 0 ?do count c, loop drop ;
> still shorter:
> : string, dup c, here swap dup allot cmove ;
> 
> I use ?DO in case count of the string is zero. CMOVE knows this too.
> 
> groet Coos
Good point. Heh ... my system is currently so bare-bones that it doesn't have CMOVE yet. I was planning on putting a word in there for that type of behavior, but I would probably given it a different name this is more intuitive to me, something like copy.string. Now I'll name it CMOVE instead.

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

#43136

FromAlbert van der Horst <albert@spenarnc.xs4all.nl>
Date2015-11-02 19:39 +0000
Message-ID<5637bbe8$0$23795$e4fe514c@news.xs4all.nl>
In reply to#43117
Chris Curl <ccurl609@gmail.com> writes:

>On Monday, November 2, 2015 at 9:46:21 AM UTC-5, Coos Haak wrote:
>> Op Mon, 2 Nov 2015 06:17:57 -0800 (PST) schreef Chris Curl:
>>=20
>> > In my simple implementation, this would create an empty word in the dic=
>tionary.
>> >=20
>> >: string, ( addr count -- ) DUP C, 0 DO DUP C@ C, 1+ LOOP DROP ;
>> shorter:
>> : string, dup c, 0 ?do count c, loop drop ;
>> still shorter:
>> : string, dup c, here swap dup allot cmove ;
>>=20
>> I use ?DO in case count of the string is zero. CMOVE knows this too.
>>=20
>> groet Coos
>Good point. Heh ... my system is currently so bare-bones that it doesn't ha=
>ve CMOVE yet. I was planning on putting a word in there for that type of be=
>havior, but I would probably given it a different name this is more intuiti=
>ve to me, something like copy.string. Now I'll name it CMOVE instead.

There is something very embarassing about CMOVE. Such low level words
should handle address units not characters. To move N CELLS one
would have to write
   N CELLS 1 CHARS / CMOVE
to be portable. (The same of course for C! C@ etc. In fact they are a
byte store and byte fetch, and everybody gambles that a whole
character fits in there, in case they want to handle text. )

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,
2. intelligent, it can't be use for ERASE and FILL or implementing wheels.

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#43139

FromMark Wills <markwills1970@gmail.com>
Date2015-11-02 12:19 -0800
Message-ID<f5139fb9-1c7d-43bb-a01f-4981cccfc1d9@googlegroups.com>
In reply to#43136
My system has COPYW which copies words (16-bit cells). On my system is worth the cost of implementing because it is literally twice as fast.

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

#43170

Fromanton@mips.complang.tuwien.ac.at (Anton Ertl)
Date2015-11-03 11:31 +0000
Message-ID<2015Nov3.123145@mips.complang.tuwien.ac.at>
In reply to#43136
Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>There is something very embarassing about CMOVE. Such low level words
>should handle address units not characters. To move N CELLS one
>would have to write
>   N CELLS 1 CHARS / CMOVE
>to be portable. (The same of course for C! C@ etc. In fact they are a
>byte store and byte fetch, and everybody gambles that a whole
>character fits in there, in case they want to handle text. )

That will hopefully be fixed in the next years:
<http://www.forth200x.org/char-is-1.html>

>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.

- 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/

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

#43195

FromAlbert van der Horst <albert@spenarnc.xs4all.nl>
Date2015-11-03 21:11 +0000
Message-ID<56392305$0$23730$e4fe514c@news.xs4all.nl>
In reply to#43170
anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

>Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>There is something very embarassing about CMOVE. Such low level words
>>should handle address units not characters. To move N CELLS one
>>would have to write
>>   N CELLS 1 CHARS / CMOVE
>>to be portable. (The same of course for C! C@ etc. In fact they are a
>>byte store and byte fetch, and everybody gambles that a whole
>>character fits in there, in case they want to handle text. )

>That will hopefully be fixed in the next years:
><http://www.forth200x.org/char-is-1.html>

>>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.

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

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.

My conclusions:
    overlap costs but the different functionality may be worth it.
    fill coded directly is about 3 times faster versus CMOVE with overlap
    for large moves CMOVE is 20% faster compared to MOVE

Nothing changes my mind. I think MOVE is superfluous and CMOVE should
be called MOVE (or at least BMOVE).

>- anton

For reference:
-------------------------
WANT CASE-SENSITIVE     CASE-INSENSITIVE
WANT ELAPSED
WANT .FORMAT

\ Different areas w.r.t. cache
create foo 10,000,000 allot
create foo1 10,000,000 allot
create foo2 10,000,000 allot
create foo3 10,000,000 allot
create foo4 10,000,000 allot

"Left move, right cmove %n Doing 1000 bytes%n First has overlap%n" .FORMAT
MARK-TIME foo foo 1+     1000 move  ELAPSED .uS
MARK-TIME foo1 foo1 1+     1000 cmove  ELAPSED .uS
CR
MARK-TIME foo2 foo2 1000 +     1000 move  ELAPSED .uS
MARK-TIME foo3 foo3 1000 +     1000 cmove  ELAPSED .uS
"%n Fill %n" .FORMAT
MARK-TIME foo4 1,000 0 fill ELAPSED .uS
"%n %n Second time: 1,000,000 bytes%n" .FORMAT

MARK-TIME foo foo 1+     1,000,000 move  ELAPSED .mS
MARK-TIME foo1 foo1 1+     1,000,000 cmove  ELAPSED .mS
CR
MARK-TIME foo2 foo2 1,000,000 +     1,000,000 move  ELAPSED .mS
MARK-TIME foo3 foo3 1,000,000 +     1,000,000 cmove  ELAPSED .mS
"%n Fill %n" .FORMAT
MARK-TIME foo4 1,000,000 0 fill ELAPSED .uS

CR

-------------------------

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

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

Fromanton@mips.complang.tuwien.ac.at (Anton Ertl)
Date2015-11-04 09:52 +0000
SubjectMOVE and CMOVE speed (was: alternatives to `find`)
Message-ID<2015Nov4.105206@mips.complang.tuwien.ac.at>
In reply to#43195
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/

[toc] | [prev] | [standalone]

Page 5 of 5 — ← Prev page 1 2 3 4 [5]

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

csiph-web