UNDROP an alternative to ?DUP 
Author Message
 UNDROP an alternative to ?DUP

Examples are hypothetical and used to demonstrate a technique
only .

The word ?DUP is often associated with a convention, such
as "if the name field contains a zero pointer, it is dummy."
In that case you don't want to try print the name :

There is a hidden branch in ?DUP. That translate to
pipe line stall in this time and age. Furthermore most people
find the indeterministic stack behaviour of ?DUP not elegant. 1)
I propose UNDROP . This just pushes a zero on the stack, or a
cell of garbage ( saving one or two nanoseconds).
UNDROP saves an extra ELSE branch without a hidden branch.

The above example then becomes :

It can go where ?DUP cannot:

\ Print a words name from its DICTIONARY_ENTRY_ADDRES.
\  Ignore dummy dea's.
: ID.
DUMMY_FLAG OVER >FFA CONTAINED-IN

The return stack allows a similar technique though:
: ID. DUP >R

1)
Elegance is for leopards, dancers, programmers.
Elegance stands for ease, efficiency, speed.

I hate to see this becoming a software patent, so Anton please
bear with me:
This article copyright Albert van der Horst DFW The Netherlands. It may be
freely distributed on terms that redistribution shall not be restricted.
Techniques and knowledge revealed here in are public domain, hence not
patentable. Acronyms STNT, MT e.a. are scientific terms not trademarks.
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
To suffer is the prerogative of the strong. The weak -- perish.



Mon, 15 Dec 2003 18:53:43 GMT  
 UNDROP an alternative to ?DUP



Quote:
> Examples are hypothetical and used to demonstrate a technique
> only .

> The word ?DUP is often associated with a convention, such
> as "if the name field contains a zero pointer, it is dummy."
> In that case you don't want to try print the name :

> There is a hidden branch in ?DUP. That translate to
> pipe line stall in this time and age. Furthermore most people
> find the indeterministic stack behaviour of ?DUP not elegant. 1)
> I propose UNDROP . This just pushes a zero on the stack, or a
> cell of garbage ( saving one or two nanoseconds).
> UNDROP saves an extra ELSE branch without a hidden branch.

> The above example then becomes :


    You don't need a new word to do this:


--

-GJC

-Abolish Public Schools.



Tue, 16 Dec 2003 09:02:43 GMT  
 UNDROP an alternative to ?DUP

Quote:


> > Examples are hypothetical and used to demonstrate a technique
> > only .
> > The word ?DUP is often associated with a convention, such
> > as "if the name field contains a zero pointer, it is dummy."
> > In that case you don't want to try print the name :

> > There is a hidden branch in ?DUP. That translate to
> > pipe line stall in this time and age. Furthermore most people
> > find the indeterministic stack behaviour of ?DUP not elegant. 1)
> > I propose UNDROP . This just pushes a zero on the stack, or a
> > cell of garbage ( saving one or two nanoseconds).
> > UNDROP saves an extra ELSE branch without a hidden branch.
> > The above example then becomes :

>     You don't need a new word to do this:


That's true, but suppose the last word in the phrase uses 3 stack items,
then you'd need to DUP something below that, and there's no guarantee it
will be this easy anywhere inside the phrase.  And you're adding a DUP
just so you can do DROP later, which could make the code harder to
follow.

UNDROP can (and should) come at the very end.  Since you don't care what
item it has, on *some* architectures it will be more efficient -- you
just bump the stack pointer without copying the data.  (But on systems
where the top stack item is in a register it won't make any difference,
you'll still copy the top item to the 'real' stack.)  

I think it's potentially almost as useful as ?DUP .  Since you can make
it do

: UNDROP DUP ;

any time you don't have it, it isn't a big problem for portability.



Tue, 16 Dec 2003 11:04:52 GMT  
 UNDROP an alternative to ?DUP

I used to use

IF ... 0 THEN DROP

The name UNDROP just says that the value is unused.
And a compiler may trace any use of that meaningless value.

So the real questions are,

1) do we need a name for a bogus value?

2) is UNDROP a good name for that?

When I saw the subject line, I thought
that it is about

: ?DUP DUP IF UNDROP THEN ;
and that UNDROP returns the consumed cell.
So probably the answer to the 2nd question is 'no'.



Tue, 16 Dec 2003 17:20:03 GMT  
 UNDROP an alternative to ?DUP


Quote:
>There is a hidden branch in ?DUP.

That's why Gforth provides ?DUP-IF and ?DUP-0=-IF.

As mlg notes, the name is unintuitive, because, from the name, I would
expect the sequence DROP UNDROP to be a noop.  DUMMY might be a better
name.

Quote:
>I hate to see this becoming a software patent, so Anton please
>bear with me:
>This article copyright Albert van der Horst DFW The Netherlands.

Does not really matter much, because only prior publication is
important for non-patentability, copyright is irrelevant.  It's
probably not yet resolved if a Usenet posting is considered as
publication in the patent sense.

- anton
--
M. Anton Ertl                    Some things have to be seen to be believed

http://www.complang.tuwien.ac.at/anton/home.html



Tue, 16 Dec 2003 20:10:27 GMT  
 UNDROP an alternative to ?DUP


Quote:
>: UNDROP DUP ;

Gforth without TOS caching (e.g., 0.4.0 on Intel processors):

: UNDROP DUP ;  ok
.s <0>  ok
undrop
:1
undrop
^^^^^^
Error: Invalid memory address

- anton
--
M. Anton Ertl                    Some things have to be seen to be believed

http://www.complang.tuwien.ac.at/anton/home.html



Tue, 16 Dec 2003 20:12:55 GMT  
 UNDROP an alternative to ?DUP

Quote:

> Does not really matter much, because only prior publication is
> important for non-patentability, copyright is irrelevant.  It's
> probably not yet resolved if a Usenet posting is considered as
> publication in the patent sense.

Should be. Anybody can read newsgroups, so the audience is broad and
unspecified. Also, with deja (now google) archiving newsgroups, anyone
can later find usenet postings. A usenet posting with X-archive: no
perhaps is not a publication ;-).

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/



Wed, 17 Dec 2003 03:27:09 GMT  
 UNDROP an alternative to ?DUP

Quote:

>> Does not really matter much, because only prior publication is
>> important for non-patentability, copyright is irrelevant.  It's
>> probably not yet resolved if a Usenet posting is considered as
>> publication in the patent sense.

>Should be. Anybody can read newsgroups, so the audience is broad and
>unspecified. Also, with deja (now google) archiving newsgroups, anyone
>can later find usenet postings. A usenet posting with X-archive: no
>perhaps is not a publication ;-).

>--
>Bernd Paysan
>"If you want it done right, you have to do it yourself"
>http://www.jwdt.com/~paysan/

As I have said, in H3sm...

hroot <==SYSCALLS zero xor x ushift 2pdrop true ->p ->link ->code ->r !  
s->p s->r setSize swap r->s r->p <-r r-1 rpcopy rdrop pup pswap p!  p->s


onbits over not -?r nip move maskbyte - min max literal ?positive

double  dshift  dup  drop  cells  bytes  bump  align  aint  and  address

                                         ^^^^ that's UNDROP

If you do bump interactively you get random interpreter junk. If you do it
in a thread    drop bump   is a no-op. There appears to be about a dozen
occurences of it in the H3sm interpreter.

:;grep -n bump m
349:#   bump            ( ---  old_pyte ) undrop. Only useful in threads.
350:ATOM_(bump,bump)
363:#   bytes           bump  1->Size  drop
372:#   cells           bump  sizeof(int)->Size  drop
992:    call zero_no_bump                       # SUSPECT
1934:zero_no_bump:
2993:call bump
3018:call bump
3040:call bump
3056:call bump
3335:call bump
3550:call bump
3558:call bump
3699:call bump
4484:call bump
4529:call bump

As I recall from my first UNDROP for Amiga JForth, you can't do
        UNDROP UNDROP
if you cache TOS. H3sm doesn't at this time. H3sm also doesn't have ?DUP.

Rick Hohensee



Tue, 16 Dec 2003 23:28:00 GMT  
 UNDROP an alternative to ?DUP

Quote:

> UNDROP can (and should) come at the very end.  Since you don't care what
> item it has, on *some* architectures it will be more efficient -- you
> just bump the stack pointer without copying the data.  (But on systems
> where the top stack item is in a register it won't make any difference,
> you'll still copy the top item to the 'real' stack.)

I don't care for the idea behind UNDROP if the context has
anything to do with a standard or ANS Forth. It is a good
example of a suggestion to move away from the Forth
virtual machine model to embrace the details of some
implementation using specific hardware architectural features.

The whole idea is that one has such an implementation
of Forth where bypassing the model of the virtual machine
and directly manipulating the stack pointer will give
you a couple of nanoseconds of savings on complex
machines that are subject to pipeline stalls.

The problem is that ANS doesn't specify a stack pointer,
because there many not be a stack pointer at all.  The
assumption that there is even a stack pointer in the
first place, and that monkeying with it directly
will give you a few nanoseconds because of avoiding
pipeline stalls or such is a very specific environmental
dependency.

That's fine for a MachineForth or ColorForth or any Forth
that is tuned for a specific machine, but it is
clearly not going along with the idea behind
something like ANS Forth.

(If ANS specifies a stack pointer, I missed it.
I am pretty sure that it can't.)

But if all you need is

Quote:
> : UNDROP DUP ;

That is standard, but it gives you no increase in speed,
and has a rather non-intuitive name that makes me scatch
my head and say, "UNDROP ? Does it just mean DUP ?"  
It adds one more unneeded word which will not make
things clearer, cleaner, faster or better in general.


Wed, 17 Dec 2003 00:04:26 GMT  
 UNDROP an alternative to ?DUP

Quote:

> As I recall from my first UNDROP for Amiga JForth, you can't do
> UNDROP UNDROP if you cache TOS.

Wyever not?  UNDROP's just  T PUSH  right?

Andrew.



Wed, 17 Dec 2003 00:13:31 GMT  
 UNDROP an alternative to ?DUP

Quote:


> > UNDROP can (and should) come at the very end.  Since you don't care
> > what item it has, on *some* architectures it will be more efficient
> > -- you just bump the stack pointer without copying the data.  (But
> > on systems where the top stack item is in a register it won't make
> > any difference, you'll still copy the top item to the 'real'
> > stack.)
> I don't care for the idea behind UNDROP if the context has
> anything to do with a standard or ANS Forth. It is a good
> example of a suggestion to move away from the Forth
> virtual machine model to embrace the details of some
> implementation using specific hardware architectural features.
> The whole idea is that one has such an implementation
> of Forth where bypassing the model of the virtual machine
> and directly manipulating the stack pointer will give
> you a couple of nanoseconds of savings on complex
> machines that are subject to pipeline stalls.

Well, but we've occasionally considered the problems with ?DUP which is
standard.  This is one way to avoid that.  Probably a better way would
be the special IF that works like ?DUP IF though, since ?DUP is hardly
ever used apart from IF .  Possibly it might have some use in recursion,
though.

So UNDROP doesn't look really good, I think it looks better than ?DUP
but there are probably other ways to avoid ?DUP that are better still.

Quote:
> But if all you need is
> > : UNDROP DUP ;
> That is standard, but it gives you no increase in speed,
> and has a rather non-intuitive name that makes me scatch
> my head and say, "UNDROP ? Does it just mean DUP ?"
> It adds one more unneeded word which will not make
> things clearer, cleaner, faster or better in general.

Yes.  And Anton pointed out that it doesn't always work, and so

: UNDROP 0 ;    or
: UNDROP TRUE ;

work better at (on some architectures) greater cost.  And it's still not
quite intuitive.  Oh well.



Wed, 17 Dec 2003 00:45:24 GMT  
 UNDROP an alternative to ?DUP

Quote:
> There is a hidden branch in ?DUP. That translate to
> pipe line stall in this time and age. Furthermore most people
> find the indeterministic stack behaviour of ?DUP not elegant. 1)
> I propose UNDROP . This just pushes a zero on the stack, or a
> cell of garbage ( saving one or two nanoseconds).
> UNDROP saves an extra ELSE branch without a hidden branch.

Let's try to measure that.

There are two ?DUPs in the simple_hash code I posted on behalf
of the shootout last week. Here's the modified approach:

\ Hash Table iterator data/functions
: ht_next ( 'ht -- 'node )
        0 LOCALS| sz ht |

                                    ht ht->iter_next !  EXIT  
                             ENDIF  ( "undrop" ) DROP

        BEGIN  

        WHILE  



                   ht ht->iter_next !  EXIT  
            ENDIF  ( "undrop" ) DROP
        REPEAT  
        0 ;

And here are the measurements:

HASH.frt
\ ( P54C 166 MHz )
\ FORTH> #80000 TO NUM MAIN
\ 13880 hashes, 8.267 seconds elapsed. ok ( ?DUP )
\ 13880 hashes, 8.139 seconds elapsed. ok ( UNDROP 1.6% faster )

\ ( Athlon 900 MHz )
\ FORTH> #80000 TO NUM MAIN
\ 13880 hashes, 0.507 seconds elapsed. ( ?DUP )
\ 13880 hashes, 0.504 seconds elapsed. ( UNDROP 0.5% faster )

HASH2.frt
\ ( P54C 166 MHz )
\ FORTH> main many
\ 1 9999 150 1499850 9.874 seconds elapsed. ( ?DUP )
\ 1 9999 150 1499850 9.706 seconds elapsed. ( UNDROP  1.73% faster )

\ ( Athlon 900 MHz )
\ FORTH> main many
\ 1 9999 150 1499850 1.752 seconds elapsed. ( ?DUP )
\ 1 9999 150 1499850 1.746 seconds elapsed. ( UNDROP 0.3% faster )

It seems roughly 1.7% runtime can be gained on ancient hardware,
next to zero time on more current chips.

-marcel



Wed, 17 Dec 2003 01:48:49 GMT  
 UNDROP an alternative to ?DUP

Quote:

> Well, but we've occasionally considered the problems with ?DUP which is
> standard.  This is one way to avoid that.  Probably a better way would
> be the special IF that works like ?DUP IF though, since ?DUP is hardly
> ever used apart from IF .  Possibly it might have some use in recursion,
> though.

> So UNDROP doesn't look really good, I think it looks better than ?DUP
> but there are probably other ways to avoid ?DUP that are better still.

I agree with you.  At the risk of setting some people off I will
add that I agree with Chuck that ?DUP should be avoided.  But
you can't avoid dealing with it at some level in ANS since it
has to be there in the first place.

Quote:
> > But if all you need is

> > > : UNDROP DUP ;

> > That is standard, but it gives you no increase in speed,
> > and has a rather non-intuitive name that makes me scatch
> > my head and say, "UNDROP ? Does it just mean DUP ?"
> > It adds one more unneeded word which will not make
> > things clearer, cleaner, faster or better in general.

> Yes.  And Anton pointed out that it doesn't always work, and so

> : UNDROP 0 ;    or
> : UNDROP TRUE ;

> work better at (on some architectures) greater cost.  And it's still not
> quite intuitive.  Oh well.

Quite right.  The idea is quite different that DUP.
I probably should have left out my comment on : UNDROP DUP ;


Wed, 17 Dec 2003 02:04:45 GMT  
 UNDROP an alternative to ?DUP

Quote:
> Examples are hypothetical and used to demonstrate a technique
> only .

> The word ?DUP is often associated with a convention, such
> as "if the name field contains a zero pointer, it is dummy."
> In that case you don't want to try print the name :

> There is a hidden branch in ?DUP. That translate to
> pipe line stall in this time and age. Furthermore most people
> find the indeterministic stack behaviour of ?DUP not elegant. 1)
> I propose UNDROP . This just pushes a zero on the stack, or a
> cell of garbage ( saving one or two nanoseconds).
> UNDROP saves an extra ELSE branch without a hidden branch.

A system that's capable of worrying about pipeline stalls is probably
generating in-line code that can optimize this phrase, so you don't have to
worry about it.

I don't see any need for a new word in any case.  Nobody forces you to use
?DUP.  If you prefer to push something for a later DROP to drop, just use 0 or
an extra DUP.

Cheers,
Elizabeth

--
================================================
Elizabeth D. Rather   (US & Canada)       800-55-FORTH
FORTH Inc.                                      +1 310-491-3356
5155 W. Rosecrans Ave. #1018  Fax: +1 310-978-9454
Hawthorne, CA 90250
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
================================================



Wed, 17 Dec 2003 02:07:17 GMT  
 UNDROP an alternative to ?DUP

Quote:


> > Does not really matter much, because only prior publication is
> > important for non-patentability, copyright is irrelevant.  It's
> > probably not yet resolved if a Usenet posting is considered as
> > publication in the patent sense.

> Should be. Anybody can read newsgroups, so the audience is broad and
> unspecified. Also, with deja (now google) archiving newsgroups, anyone
> can later find usenet postings. A usenet posting with X-archive: no

Off-topic: Are there other resources like deja/google? Google is
probably getting too powerful. What if some day they decide you have
to pay to browse their usenet archives?

As to the original thread, I also dislike the UNDROP name. Even {*filter*}
would be better... short and concise ;-)



Wed, 17 Dec 2003 03:53:47 GMT  
 
 [ 69 post ]  Go to page: [1] [2] [3] [4] [5]

 Relevant Pages 

1. Undrop-It v1.Obeta1

2. fun with undrop, the grossly mis-named H3sm-1.0

3. +R as a name for DUP >R

4. DUP >R

5. dup

6. Memory behavior of String#dup

7. dup, clone, and "deep copy"

8. self being altered even when .dup'ed

9. dup vs clone

10. 5 dup ($)

11. Resb and dup in NASM

12. Problem with DUP

 

 
Powered by phpBB® Forum Software