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

Groups > comp.lang.forth > #32154

Re: Reduce dictionary lookups using LIT ?

Show all headers | View raw

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

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web