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

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

Reduce dictionary lookups using LIT ?

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

Contents

  Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-01 20:24 -0400
    Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-01 19:39 -1000
      Re: Reduce dictionary lookups using LIT ? bruce.mcfarling@gmail.com - 2014-07-02 10:30 -0700
        Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-02 08:53 -1000
        Re: Reduce dictionary lookups using LIT ? Mark Wills <markwills1970@gmail.com> - 2014-07-02 13:47 -0700
          Re: Reduce dictionary lookups using LIT ? BruceMcF <agila61@netscape.net> - 2014-07-02 19:45 -0700
            Re: Reduce dictionary lookups using LIT ? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-07-03 16:56 +0000
              Re: Reduce dictionary lookups using LIT ? bruce.mcfarling@gmail.com - 2014-07-03 10:34 -0700
    Re: Reduce dictionary lookups using LIT ? Mark Wills <markwills1970@gmail.com> - 2014-07-02 01:27 -0700
      Re: Reduce dictionary lookups using LIT ? Bernd Paysan <bernd.paysan@gmx.de> - 2014-07-02 17:11 +0200
        Re: Reduce dictionary lookups using LIT ? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-07-02 16:31 +0000
          Re: Reduce dictionary lookups using LIT ? Bernd Paysan <bernd.paysan@gmx.de> - 2014-07-02 20:32 +0200
        Re: Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-03 03:01 -0400
          Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-02 21:42 -1000
          Re: Reduce dictionary lookups using LIT ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-03 16:05 +0000
      Re: Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-03 03:00 -0400
    Re: Reduce dictionary lookups using LIT ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-02 09:35 +0000
      Re: Reduce dictionary lookups using LIT ? "Elizabeth D. Rather" <erather@forth.com> - 2014-07-02 06:51 -1000
    Re: Reduce dictionary lookups using LIT ? chitselb <chitselb@gmail.com> - 2014-07-02 14:30 -0700
      Re: Reduce dictionary lookups using LIT ? "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-03 03:51 -0400
    Re: Reduce dictionary lookups using LIT ? Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2014-07-03 02:41 -0700
      Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 11:44 +0100
        Re: Reduce dictionary lookups using LIT ? Stefan Mauerhofer <smauerhofer@androsoft.ch> - 2014-07-03 06:03 -0700
          Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 15:16 +0100
            Re: Reduce dictionary lookups using LIT ? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-07-03 16:31 +0000
              Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 19:58 +0100
                Re: Reduce dictionary lookups using LIT ? "Alex McDonald" <blog@rivadpm.com> - 2014-07-03 20:02 +0100

Page 1 of 2  [1] 2  Next page →

#32106 — Reduce dictionary lookups using LIT ?

Reduce dictionary lookups using LIT ? ...

I saw a quote from a Forth book which said LIT was also
useful to eliminate dictionary lookups of numbers when
loading and compiling a vocabulary.

So, instead of:

: ONE 1 ;  \ LIT compiled by innner interpreter

this would be used in a vocabulary:

: ONE LIT 1 ;  \ LIT explicitly used

Here, 1 is not searched for in the dictionary by the inner
interpreter when compiling ONE due to the use of LIT .

I'd like to use that syntax in my vocabulary, but I think
it creates some problems.  I already have a historically
based run-time LIT which works differently.

A new "high-level" LIT as used in ": ONE LIT 1 ;" would
need to be something like the following:

: LIT BL WORD NUMBER POSTPONE LITERAL ; IMMEDIATE

Except, LITERAL calls the original run-time LIT:

: LITERAL POSTPONE LIT , ; IMMEDIATE
: LIT R> DUP "cell_adjustment" >R @ ;

This creates a name conflict between the two LITs, since
my vocabulary would need to use both at the same time.

A common option in such naming conflict situations is to
rename the run-time, wrapping it in paren's, e.g.: (LIT) .
Except, I don't want to change the historical name of the
original run-time LIT .  It seems to be well accepted.

So, is there a common name for such a high-level LIT?
Or, was there a version of LIT that did both?
And, is this technique even used anymore?


Rod Pemberton

[toc] | [next] | [standalone]

#32113

On 7/1/14 2:24 PM, Rod Pemberton wrote:
>
> Reduce dictionary lookups using LIT ? ...
>
> I saw a quote from a Forth book which said LIT was also
> useful to eliminate dictionary lookups of numbers when
> loading and compiling a vocabulary.
>
> So, instead of:
>
> : ONE 1 ;  \ LIT compiled by innner interpreter
>
> this would be used in a vocabulary:
>
> : ONE LIT 1 ;  \ LIT explicitly used
>
> Here, 1 is not searched for in the dictionary by the inner
> interpreter when compiling ONE due to the use of LIT .
>
> I'd like to use that syntax in my vocabulary, but I think
> it creates some problems.  I already have a historically
> based run-time LIT which works differently.
>
> A new "high-level" LIT as used in ": ONE LIT 1 ;" would
> need to be something like the following:
>
> : LIT BL WORD NUMBER POSTPONE LITERAL ; IMMEDIATE
>
> Except, LITERAL calls the original run-time LIT:n
>
> : LITERAL POSTPONE LIT , ; IMMEDIATE
> : LIT R> DUP "cell_adjustment" >R @ ;
>
> This creates a name conflict between the two LITs, since
> my vocabulary would need to use both at the same time.
>
> A common option in such naming conflict situations is to
> rename the run-time, wrapping it in paren's, e.g.: (LIT) .
> Except, I don't want to change the historical name of the
> original run-time LIT .  It seems to be well accepted.
>
> So, is there a common name for such a high-level LIT?
> Or, was there a version of LIT that did both?
> And, is this technique even used anymore?

In my experience, and according to ANS Forth, the compile-time word is 
LITERAL, and there is no standard for naming the run-time executable. In 
many systems, for example, LITERAL may examine the number and decide 
among several run-time functions, depending on whether the number to be 
compiled is a single-cell, double, FP, etc.

Optimizing compilers, of course, will incorporate the literal in the 
code being compiled, and there is no "run-time word".

Avoiding the dictionary search is, of course, of more value in systems 
where compile times are long. If your entire system and application 
compiles in under a second, as is often the case in well-optimized 
Forths, the improvement would be negligible. It's often a better use of 
your time to improve the overall dictionary search times.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

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

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

#32127

On Wednesday, July 2, 2014 1:39:23 AM UTC-4, Elizabeth D. Rather wrote:

> On 7/1/14 2:24 PM, Rod Pemberton wrote:
>> : ONE 1 ;  \ LIT compiled by innner interpreter 
>> 
>> this would be used in a vocabulary:
 
>> : ONE LIT 1 ;  \ LIT explicitly used

But that doesn't avoid the dictionary search, because you have to search the dictionary for ``LIT''. If 1 is used enough so that it makes a difference, then it would seem better to do:

1 CONSTANT 1

... and then you don't have LIT or whatever the run-time may be called at all.

That is also better suited to put into a system-specific prelude, since its only an issue in very specific cases, and most of the time its not worth worrying about. If testing a script that doesn't use ANEW, I can say BYE to gforth, start it up again, and cursor up to the previous commands I gave to load the file and the file is compiled in well under half a minute total, so in that case the difference is imperceptible.

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

#32129

On 7/2/14 7:30 AM, bruce.mcfarling@gmail.com wrote:
> On Wednesday, July 2, 2014 1:39:23 AM UTC-4, Elizabeth D. Rather wrote:
>
>> On 7/1/14 2:24 PM, Rod Pemberton wrote:
>>> : ONE 1 ;  \ LIT compiled by innner interpreter
>>>
>>> this would be used in a vocabulary:
>
>>> : ONE LIT 1 ;  \ LIT explicitly used
>
> But that doesn't avoid the dictionary search, because you have to search the dictionary for ``LIT''. If 1 is used enough so that it makes a difference, then it would seem better to do:
>
> 1 CONSTANT 1
>
> ... and then you don't have LIT or whatever the run-time may be called at all.
>
> That is also better suited to put into a system-specific prelude, since its only an issue in very specific cases, and most of the time its not worth worrying about. If testing a script that doesn't use ANEW, I can say BYE to gforth, start it up again, and cursor up to the previous commands I gave to load the file and the file is compiled in well under half a minute total, so in that case the difference is imperceptible.
>

Defining commonly-used numbers as CONSTANTs is cheap and clean. In early 
days, Chuck experimented with which were most useful, ranging from 0, 1 
and 2 to 1-9. In speed tests, 0, 1, and 2 turned out to be the only ones 
worth defining. I think we kept those until going to optimizing compilers.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

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

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

#32132

You only have to search for lit once - during the compilation of ONE. After that all instances of 1 in the source are replaced with ONE and you get a quicker compile. That's where Rod is coming from. I don't believe he's confused. I just doubt that the benefit will be that high.

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

#32138

On Wednesday, July 2, 2014 4:47:34 PM UTC-4, Mark Wills wrote:
> You only have to search for lit once - during the compilation of ONE. After that all instances of 1 in the source are replaced with ONE and you get a quicker compile. That's where Rod is coming from. I don't believe he's confused. I just doubt that the benefit will be that high.

But you defined ``1 CONSTANT 1'' once, and then you have the same effect, and instead of the compiled code being "<doLIT><#1>" its "<1_CONSTANT>". Use "1" enough time in the code, it can easily pay back the space taken by the constant (which is the context I'm more familiar with).

From the hand-assembled compiled Forth I've seen, whether fig-Forth or Camel, the esteemed Ms. Rather's advice regarding those kind of constants seems right as far as the ones that may give some space saving in a minimalist system ... -1 0 1 and 2.

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

#32159

In article <d731ae1e-a8a9-4e6d-b41c-1e8157adc521@googlegroups.com>,
BruceMcF  <agila61@netscape.net> wrote:
>On Wednesday, July 2, 2014 4:47:34 PM UTC-4, Mark Wills wrote:
>> You only have to search for lit once - during the compilation of ONE.
>After that all instances of 1 in the source are replaced with ONE and
>you get a quicker compile. That's where Rod is coming from. I don't
>believe he's confused. I just doubt that the benefit will be that high.
>
>But you defined ``1 CONSTANT 1'' once, and then you have the same
>effect, and instead of the compiled code being "<doLIT><#1>" its
>"<1_CONSTANT>". Use "1" enough time in the code, it can easily pay back
>the space taken by the constant (which is the context I'm more familiar
>with).
>
>From the hand-assembled compiled Forth I've seen, whether fig-Forth or
>Camel, the esteemed Ms. Rather's advice regarding those kind of
>constants seems right as far as the ones that may give some space saving
>in a minimalist system ... -1 0 1 and 2.

The only reasonable reason I can think of nowadays is pedagogical.
I have a constant zero in yourforth.fas as a simple example of constants.
Then I use the word 0 in an example of threaded code, such that I
do not need to introduce LIT at such an early stage. Because it
increments the interpreter pointer and fetches stuff from there it
is to be explained after regular interpretation of threaded code.

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]

#32161

On Thursday, July 3, 2014 12:56:43 PM UTC-4, Albert van der Horst wrote:
> In article <d731ae1e-a8a9-4e6d-b41c-1e8157adc521@googlegroups.com>,
> BruceMcF  <agila61@netscape.net> wrote:
> >From the hand-assembled compiled Forth I've seen, whether fig-Forth or 
> >Camel, the esteemed Ms. Rather's advice regarding those kind of
> >constants seems right as far as the ones that may give some space saving
> >in a minimalist system ... -1 0 1 and 2.
>
> The only reasonable reason I can think of nowadays is pedagogical. 
> I have a constant zero in yourforth.fas as a simple example of constants.
> Then I use the word 0 in an example of threaded code, such that I
> do not need to introduce LIT at such an early stage. Because it
> increments the interpreter pointer and fetches stuff from there it
> is to be explained after regular interpretation of threaded code.

That's a reasonable reason, to be sure. In a desktop setting, its seems like its just an echo of earlier days, unless there's a pedagological purpose to be served. 

If you are in a context where you are crunching bytes, then a 16-byte Forth in a direct threaded implementation may have a 0 constant as:
   <pointer_to_next_word><1.b><#0.b><JMP_op><pointer_to_doCON><#0>

... 10 bytes in a flat 16 bit machine language, so between:
   <LIT><#0>
and
   <0_CONSTANT>

... it takes only five appearances of 0 in source to break even and saves two bytes from then on. You get the same benefit from any literal defined as a constant, but most other values that would appear frequently have some programming significance as a significant address or offset or mask which should be a named constant ... for appearances AS numbers, -1 0 and 1 would be net wins as a set to pretty much always include them in a byte-crunching setting. Maybe 2. And they hit break-even faster with an umbilical Forth, since the dictionary overhead is on the host, not on the target.

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

#32115

I'd suggest LIT: or AS-LIT or something. I prefer LIT:

: ONE ( -- 1 ) LIT: 1 ;

The following definition works in my system:

: LIT: ( "n" -- ) 
  BL WORD NUMBER ABORT" Not a legal number"
  COMPILE LIT , ; IMMEDIATE
  
Your system may use POSTPONE rather than COMPILE.

But... Is your system so slow that you need this? Rhetorical.
I'm sure it's not. I question the benefit this would bring...
Is this a bootstrapping thing? You're trying to minimise 
dictionary lookups while the system is compiling/bootstrapping
itself? I guess that makes sense.

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

#32118

Mark Wills wrote:
> But... Is your system so slow that you need this? Rhetorical.

It's a Rod Pemberton idea.  Assume it to be wrong in every way.  In this 
case, the lookup for names comes before the lookup for numbers, so if you 
find a name, you are done, the time for number conversion isn't necessary.  
However, if he has a linear search, and LIT (or maybe D# and H#, a they are 
used in some Forths to denote specific bases rather than having the base 
prefixes) is found pretty early, then there is a benefit.  However, as such  
word would be defined pretty early (needed all the time), it is unlikely 
that you gain something.

If you have lots of literals, a slow dictionary search, and your Forth words 
don't conflict with literals (they usually shouldn't, at least in decimal 
mode), you could turn the search around: First try to convert as literal, 
and if that fails, search.  This would give a benefit, as indentifying a 
number is pretty fast, and in the "many literals" case the search is 
completed when it's a literal.

With Gforth's development version, you can shuffle the recognizer stack to 
give it a try.  But Gforth has a fast dictionary lookup...

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#32122

In article <lp17eg$96b$1@online.de>, Bernd Paysan  <bernd.paysan@gmx.de> wrote:
>Mark Wills wrote:
>If you have lots of literals, a slow dictionary search, and your Forth words
>don't conflict with literals (they usually shouldn't, at least in decimal
>mode), you could turn the search around: First try to convert as literal,
>and if that fails, search.  This would give a benefit, as indentifying a
>number is pretty fast, and in the "many literals" case the search is
>completed when it's a literal.

As I pioneered that technique allow me a remark. The recognizers for
numbers and strings belong in the "minimum search order" aka the ONLY
wordlist. I think it is a great advantage that the system recognizers
that must emulate ISO are there, as it guarantees no surprises for the
unaware. On occasion for large files with many numbers I've
switched to a minimum search order (without Forth-wordlist).
I think it an advantage that once a recognizer triggers it is all or
nothing, either it is that kind of denotation, or it is an exception.
This means that it would balk on 2SWAP. It starts with 2, so it
must be a number, but it isn't, so there. 1]
This results in the discipline to make them easily recognizable:
 Unix 0x#### : good
 Intel ####H : bad

(Note that 0x178A is the same as `` H# 178A ''expect for that small thing:
the space. How would you like `` 178A H# '' with the rule, if parsing a word
leads to an exception, execute the word following in the input stream,
to maybe make things right.)

My prefixes just don't accommodate Intel Hex.
I don't want the misspelled DROH give an error like :
   R is not a hex number.

I don't object to user defined recognizers, but
IMO user defined recognizer must be were they are: in a user selected
position in the search order.

>
>With Gforth's development version, you can shuffle the recognizer stack to
>give it a try.  But Gforth has a fast dictionary lookup...

You know you needn't try that to know it doesn't make sense.

>
>--
>Bernd Paysan

Groetjes Albert

1] I do hate the name 2SWAP. Much better would be PSWAP (for pair).
-- 
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]

#32128

Albert van der Horst wrote:
> As I pioneered that technique allow me a remark. The recognizers for
> numbers and strings belong in the "minimum search order" aka the ONLY
> wordlist. I think it is a great advantage that the system recognizers
> that must emulate ISO are there, as it guarantees no surprises for the
> unaware. On occasion for large files with many numbers I've
> switched to a minimum search order (without Forth-wordlist).
> I think it an advantage that once a recognizer triggers it is all or
> nothing, either it is that kind of denotation, or it is an exception.
> This means that it would balk on 2SWAP. It starts with 2, so it
> must be a number, but it isn't, so there. 1]

Different recognizer implementations have different trade-offs; your prefix-
recognizers are all-or-nothing; Gforth's recognizer can check for the 
complete word.  Even 2SWAP is recognized:

get-recognizers >r swap r> set-recognizers   ok
.recs rec:num rec:word rec:float rec:string rec:to  ok
123 . 123  ok
1. 3. 2swap d. d. 1 3  ok
5 constant 3  ok
3 . 3  ok
get-recognizers >r swap r> set-recognizers   ok
.recs rec:word rec:num rec:float rec:string rec:to  ok
3 . 5  ok

> This results in the discipline to make them easily recognizable:
>  Unix 0x#### : good
>  Intel ####H : bad

Or ANS Floats: ####E## : Very bad...

> I don't object to user defined recognizers, but
> IMO user defined recognizer must be were they are: in a user selected
> position in the search order.

Yes.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#32142

On Wed, 02 Jul 2014 11:11:11 -0400, Bernd Paysan <bernd.paysan@gmx.de>  
wrote:
> Mark Wills wrote:

>> But... Is your system so slow that you need this? Rhetorical.
>
> It's a Rod Pemberton idea.  Assume it to be wrong in every way.

It came from a partial quote from a book in Google Books which
came up when I searched for LITERAL or LIT or something.  Of course,
it was probably from the 1980's and not that common a thing.
Another quote seems to indicate it was a Forth-83 thing.

> In this case, the lookup for names comes before the lookup for
> numbers, so if you find a name, you are done, the time for number
> conversion isn't necessary.  However, if he has a linear search,
> and LIT (or maybe D# and H#, a they are used in some Forths to
> denote specific bases rather than having the base prefixes) is
> found pretty early, then there is a benefit.  However, as such
> word would be defined pretty early (needed all the time), it is
> unlikely that you gain something.

The gain is likely neglible.  As "bruce.mcfarling" noted, the entire
dictionary is no longer searched it's entirety, but the dictionary
is still partially searched to find LIT.

> If you have lots of literals, a slow dictionary search, and your
> Forth words don't conflict with literals (they usually shouldn't,
> at least in decimal mode), you could turn the search around: First
> try to convert as literal, and if that fails, search.  This would
> give a benefit, as indentifying a number is pretty fast, and in
> the "many literals" case the search is completed when it's a literal.

In an optimized compiled Forth, I'd expect that attempting the number
conversion first to add a slight overhead per word that would be far
less than a partial dictionary search for LIT.

In a threaded-interpreted Forth, I'd expect the ITC or DTC number
conversion routine to take much longer, perhaps comparable to a
full dictionary search.  There is much looping and division.

> With Gforth's development version, you can shuffle the recognizer
> stack to give it a try.  But Gforth has a fast dictionary lookup ...

...

Rod Pemberton

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

#32144

On 7/2/14 9:01 PM, Rod Pemberton wrote:
> On Wed, 02 Jul 2014 11:11:11 -0400, Bernd Paysan <bernd.paysan@gmx.de>
> wrote:
>> Mark Wills wrote:
>
>>> But... Is your system so slow that you need this? Rhetorical.
>>
>> It's a Rod Pemberton idea.  Assume it to be wrong in every way.
>
> It came from a partial quote from a book in Google Books which
> came up when I searched for LITERAL or LIT or something.  Of course,
> it was probably from the 1980's and not that common a thing.
> Another quote seems to indicate it was a Forth-83 thing.

It's a very old FIG-ish thing.

>> In this case, the lookup for names comes before the lookup for
>> numbers, so if you find a name, you are done, the time for number
>> conversion isn't necessary.  However, if he has a linear search,
>> and LIT (or maybe D# and H#, a they are used in some Forths to
>> denote specific bases rather than having the base prefixes) is
>> found pretty early, then there is a benefit.  However, as such
>> word would be defined pretty early (needed all the time), it is
>> unlikely that you gain something.
>
> The gain is likely neglible.  As "bruce.mcfarling" noted, the entire
> dictionary is no longer searched it's entirety, but the dictionary
> is still partially searched to find LIT.

LITERAL (which is the standard name for the compile-time word) is 
usually one of the first words defined, and so one of the last found in 
a search that starts at the recent end of the dictionary. This is one of 
the reasons why the "saving" is negligible.

>> If you have lots of literals, a slow dictionary search, and your
>> Forth words don't conflict with literals (they usually shouldn't,
>> at least in decimal mode), you could turn the search around: First
>> try to convert as literal, and if that fails, search.  This would
>> give a benefit, as indentifying a number is pretty fast, and in
>> the "many literals" case the search is completed when it's a literal.
>
> In an optimized compiled Forth, I'd expect that attempting the number
> conversion first to add a slight overhead per word that would be far
> less than a partial dictionary search for LIT.

That's a very bad idea. Among other things, the standards all (afaik) 
specify that the dictionary search should come first. If you're in hex, 
for example, ACE will be converted as a number, which is unlikely to be 
what you want. And folks optimizing by defining

0 CONSTANT 0   1 CONSTANT 1   (etc.)

...as is often suggested, will be defeated. Other chaos may ensue.

Other than the single digits, it is (of course) highly advantageous to 
define constants used multiple times and give them meaningful names, to 
improve readability and maintainability. Whatever slight compile-time 
improvements they yield is an added bonus.

> In a threaded-interpreted Forth, I'd expect the ITC or DTC number
> conversion routine to take much longer, perhaps comparable to a
> full dictionary search.  There is much looping and division.

Not in any reasonably competently-written Forth. It should be quite 
fast, and (of course) will quit on the first character that isn't a 
digit. A dictionary search may involve thousands of words.

However, most folks improve their dictionary search times by dividing up 
the dictionary into multiple threads using strategies such as hashing 
the name to save search time. That kind of strategy is much more 
rewarding than fiddling with literals.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

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

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

#32154

"Rod Pemberton" <dont_use_email@xnothavet.cqm> writes:
>In an optimized compiled Forth, I'd expect that attempting the number
>conversion first to add a slight overhead per word that would be far
>less than a partial dictionary search for LIT.
>
>In a threaded-interpreted Forth, I'd expect the ITC or DTC number
>conversion routine to take much longer, perhaps comparable to a
>full dictionary search.  There is much looping and division.

Division is a slow hardware operation, so the difference between
native code and threaded code there is less than for most operations.

But you don't need division for converting a string into a number,
just multiplication.  As for the looping, you just need one iteration
per character, not that much looping.  In dictionary lookup, you have
to loop through the search order, loop through the hash computation,
and loop through the collisions.

Anyway, we can be sure by measuring things:

: num ( n -- )
    0 ?do
        0 0 s" 25" >number 2drop 2drop
    loop ;

: dict ( n -- )
    0 ?do
        s" lit" find-name drop
    loop ;

[b8:~/gforth:5609] time gforth-itc xxx.fs -e "10000000 num bye"
6.772u 0.008s 6.795r 99.78%
[b8:~/gforth:5610] time gforth-itc xxx.fs -e "10000000 dict bye"
6.756u 0.008s 6.775r 99.84%

Interesting.

[b8:~/gforth:5611] time gforth-fast xxx.fs -e "10000000 num bye"
2.052u 0.004s 2.065r 99.55%
[b8:~/gforth:5612] time gforth-fast xxx.fs -e "10000000 dict bye"
1.960u 0.000s 1.963r 99.83%

That's on an AMD E-450 (1.65GHz netbook CPU).

Also interesting:

: eval ( n -- )
    0 ?do
        s" 25" evaluate drop
    loop ;

[b8:~/gforth:5614] time gforth-fast xxx.fs -e "10000000 eval bye"
40.267u 0.004s 40.298r 99.93%

About half of that is per-EVALUATE overhead:

: eval10 ( n -- )
    0 ?do
        s" 25 25 25 25 25 25 25 25 25 25" evaluate 2drop 2drop 2drop 2drop 2drop
    loop ;

[b8:~/gforth:5615] time gforth-fast xxx.fs -e "1000000 eval10 bye"
21.589u 0.000s 21.606r 99.92%

But the other half is still quite a bit slower than a FIND followed by
a >NUMBER.  There are still some things to optimize in Gforth, and we
will work on that when it becomes important.

- 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 2014: http://www.euroforth.org/ef14/

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

#32141

On Wed, 02 Jul 2014 04:27:54 -0400, Mark Wills <markwills1970@gmail.com>  
wrote:

> I'd suggest LIT: or AS-LIT or something. I prefer LIT:
>
> : ONE ( -- 1 ) LIT: 1 ;

I found a post by Peter Sovietov in Russian which used # .
He coded one of the online Forth optimizers in Javascript.

I decided to go ahead and just rename LIT as (LIT) .  Apparently,
some Forth-83 systems did this so they could use LIT as above.
And, the updated online version of Leo Brodie's Starting Forth
uses (LITERAL) .  My own dictionary only used LIT twice, once in
LITERAL and once where it shouldn't be, but will be for a while,
until I can remove it, or change another definition.

> The following definition works in my system:
>
> : LIT: ( "n" -- )
>   BL WORD NUMBER ABORT" Not a legal number"
>   COMPILE LIT , ; IMMEDIATE

I don't have ABORT" and I don't recall if my ABORT is exposed,
i.e., in the dictionary, but, yes, the sample I posted works,
at least with COMPILE .

> Your system may use POSTPONE rather than COMPILE.

Yes, I use COMPILE and [COMPILE] even though I have POSTPONE .
It's clear to me as to which operation is being performed.
I only used POSTPONE in the sample because I didn't want
the conversation diversion on why I should use POSTPONE instead.

> But... Is your system so slow that you need this? Rhetorical.
> I'm sure it's not.

No, it's not.  The dictionary is compiled once.

> I question the benefit this would bring...

I was just thinking about if a dictionary or program became
excessively large, doing large searches through the ENTIRE
dictionary, just to NOT find something in the dictionary.
I.e., seemed like an easy change to short-circuit the logic.

> Is this a bootstrapping thing?

No.  My inner interpreter will (still) compile a run-time
LIT and number, if the word is not found in the dictionary.

> You're trying to minimise dictionary lookups [...]

I understood that to be the point of using LIT that way.

> [...] while the system is compiling/bootstrapping itself?

At 3.2Ghz (probably obsolete now...), it isn't really needed.


Rod Pemberton

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

#32116

"Rod Pemberton" <dont_use_email@xnothavet.cqm> writes:
>I saw a quote from a Forth book which said LIT was also
>useful to eliminate dictionary lookups of numbers when
>loading and compiling a vocabulary.
>
>So, instead of:
>
>: ONE 1 ;  \ LIT compiled by innner interpreter
>
>this would be used in a vocabulary:
>
>: ONE LIT 1 ;  \ LIT explicitly used
>
>Here, 1 is not searched for in the dictionary by the inner
>interpreter when compiling ONE due to the use of LIT .

But it does not reduce dictionary lookups, because you now have to
look up LIT.

We have such words for string literals (S"), but for integer and FP
numbers we let the text interpreter do the conversion if the
dictionary lookup fails.  While S" has been a headache (in connection
with ' and POSTPONE), no such problems were present when dealing with
integer or FP literals.  So a number of people have been thinking of
also putting string literals in the text interpreter, and that's now a
feature of the development version of Gforth and AFAIK has long been a
feature of Albert van der Horst's systems.

So I don't think that an integer literal parsing word is a good idea.

>I'd like to use that syntax in my vocabulary, but I think
>it creates some problems.  I already have a historically
>based run-time LIT which works differently.

Sure, the name LIT is widely used for the run-time routine of LITERAL
(e.g., in fig-Forth, and following from that, in Gforth).  So you
might want to use a different name for the parsing word, say INT.

>A new "high-level" LIT as used in ": ONE LIT 1 ;" would
>need to be something like the following:
>
>: LIT BL WORD NUMBER POSTPONE LITERAL ; IMMEDIATE
>
>Except, LITERAL calls the original run-time LIT:
>
>: LITERAL POSTPONE LIT , ; IMMEDIATE
>: LIT R> DUP "cell_adjustment" >R @ ;
>
>This creates a name conflict between the two LITs, since
>my vocabulary would need to use both at the same time.

Given that the traditional LIT is only an internal name, and programs
normally don't use it (they use LITERAL), you could live with the
parsing LIT shadowing the traditional LIT.  I still think it's a bad
idea, because it's confusing to have the same name for two different
words.

- 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 2014: http://www.euroforth.org/ef14/

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

#32123

On 7/1/14 11:35 PM, Anton Ertl wrote:
> Sure, the name LIT is widely used for the run-time routine of LITERAL
> (e.g., in fig-Forth, and following from that, in Gforth).  So you
> might want to use a different name for the parsing word, say INT.
>
>> >A new "high-level" LIT as used in ": ONE LIT 1 ;" would
>> >need to be something like the following:
>> >
>> >: LIT BL WORD NUMBER POSTPONE LITERAL ; IMMEDIATE
>> >
>> >Except, LITERAL calls the original run-time LIT:
>> >
>> >: LITERAL POSTPONE LIT , ; IMMEDIATE
>> >: LIT R> DUP "cell_adjustment" >R @ ;
>> >
>> >This creates a name conflict between the two LITs, since
>> >my vocabulary would need to use both at the same time.
> Given that the traditional LIT is only an internal name, and programs
> normally don't use it (they use LITERAL), you could live with the
> parsing LIT shadowing the traditional LIT.  I still think it's a bad
> idea, because it's confusing to have the same name for two different
> words.

Rod is confusing compile time with run time. As you note, LIT is a 
traditional name for the run-time code (except, as I noted, if you allow 
for multiple kinds of literals you may compile one of a set of 
run-times, such as LIT, DLIT, FLIT, etc. Surely that decision needs to 
be made at compile time, so LITERAL examines the specified number and 
picks accordingly. I entirely agree that it's confusing (as well as 
non-standard) to try to make LIT do both the comple-time & run-time chores.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

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

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

#32134

On Tuesday, July 1, 2014 8:24:36 PM UTC-4, Rod Pemberton wrote:
> Reduce dictionary lookups using LIT ? ...
> 

What I wound up doing was a Bloom filter.  Take each character of the forth word.  Is it a digit?  Add that digit + 1 to the sum.  Finally, take the sum modulo 64  (my filter has 64 bits) and index the bit.  Most words like DUP ROT SWAP will total 0.  Anything that's a number or has a number in it will be nonzero.  If the bit we are looking at in the Bloom filter is off, that token can not be in the dictionary, and FIND can be bypassed.

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

#32145

On Wed, 02 Jul 2014 17:30:03 -0400, chitselb <chitselb@gmail.com> wrote:
> On Tuesday, July 1, 2014 8:24:36 PM UTC-4, Rod Pemberton wrote:
>> Reduce dictionary lookups using LIT ? ...

> What I wound up doing was a Bloom filter.  Take each character of the  
> forth word.  Is it a digit?  Add that digit + 1 to the sum.  Finally,  
> take the sum modulo 64  (my filter has 64 bits) and index the bit.  Most  
> words like DUP ROT SWAP will total 0.  Anything that's a number or has a  
> number in it will be nonzero.  If the bit we are looking at in the Bloom  
> filter is off, that token can not be in the dictionary, and FIND can be  
> bypassed.

I recalled the name, but I had to look that up.

Really?  A Bloom filter?  Wow ...

I read the first paragraph on Wikipedia and immediately
knew it was to filter out inputs that would cause
unecessary collisions for hash functions.  Then, the
second paragraph said just that.

It appears you've mentioned this here in the past,
perhaps elsewhere ...  So, it's possible I'd read
Wikipedia on the topic previously.

Anyway, cool!

Couldn't you have just used an extensible perfect hash?

;-)


Do you think this is cool?

I have a 8-bit, brute-force, hash generator for strings
that gets about 120 non-collision values out of 256.
Yes, that's not quite 128 out of 256, but still almost
50%, on an *8-bit* value.  That's a near impossible
task by hand or random guess, as most hashes seem to
be designed.  (This is coded in C.)

The values for the hash function are produced via a
brute-force program.  It generates random values used
in the hash function.  The program runs the entire set
of strings through the hash function.  It identifies
the total collisions per string set and total collisions
per hash value.  It repeats this for numerous iterations.
Once the total collisions and collisions per hash value
are low enough for a given hash, it displays the values
used for the hash.

I've used it with a simple DOS style command interpreter.
It uses the names of various DOS commands.  The set I chose
to use has only one collision between two words, upper-
and lowercase of the same word.  IIRC, I originally used
it, or a variation, for hashes on a C language keyword set.

The algorithm is really simple: 128 random bytes, another
128 bytes with the same values.  This constitutes an ASCII
8-bit character lookup table that adds bit randomness to
the string.  I.e., it's a string conversion like upper- or
lower-case, but to randomized values.  These were determined
by brute-force for minimal collisions on the entire string
set.  The hash function itself is just the XOR of the hash,
starting with zero, with the random value from the character
translation table for each character plus a constant, for
each character in the string.  The constant is also
randomized.

I hadn't thought to try it with the Forth ANS core
or core extension names since I had no apparent need
of it in my Forth interpreter.  I don't have a list of
them as text.  Of course, the Forth wordset isn't fixed,
so it wouldn't be of use for additionally defined words.
I.e., the dataset is not fixed, but it would be useful
for the initial dictionary, or perhaps where the
dictionary is fixed, maybe an embedded environment.


Rod Pemberton

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web