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

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

Forth dictionary implementation and performance

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

Contents

  Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-29 17:42 +0000
    Re: Forth dictionary implementation and performance Paul Rubin <no.email@nospam.invalid> - 2016-01-29 16:20 -0800
      Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-30 13:54 +0000
        Re: Forth dictionary implementation and performance Paul Rubin <no.email@nospam.invalid> - 2016-01-31 11:57 -0800
          Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-01 06:47 +0000
            Re: Forth dictionary implementation and performance Paul Rubin <no.email@nospam.invalid> - 2016-02-01 00:47 -0800
              Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-01 11:13 +0000
    Re: Forth dictionary implementation and performance Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-30 01:57 +0100
      Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-30 17:18 +0000
        Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-30 17:51 +0000
    Re: Forth dictionary implementation and performance Paul Rubin <no.email@nospam.invalid> - 2016-01-29 18:01 -0800
      Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-30 13:59 +0000
        Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-30 17:38 +0000
          Re: Forth dictionary implementation and performance Paul Rubin <no.email@nospam.invalid> - 2016-01-31 12:05 -0800
            Re: Forth dictionary implementation and performance Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-01 03:01 +0000
            Re: Forth dictionary implementation and performance anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-01 06:17 +0000
              Re: Forth dictionary implementation and performance "Elizabeth D. Rather" <erather@forth.com> - 2016-01-31 21:27 -1000
    Re: Forth dictionary implementation and performance hughaguilar96@gmail.com - 2016-01-30 15:42 -0800

#45184 — Forth dictionary implementation and performance

In my course on efficient programs the task I gave to the students
this year was to optimize a very simplified implementation of the
Forth dictionary and text interpretation; the simplification was that
the input was simplified, and the found words were not compiled, but
just used for computing a checksum (so one would notice when one makes
a mistake).

The reference program was given in C, and can be found on
<https://www.complang.tuwien.ac.at/anton/lvas/effizienz-aufgabe15/#vorgabe>.
It implements each word list as a linked list, and searches all
wordlists on the search order until a match is found.

The input is a simplified form of running the Gforth cross compiler on
the Gforth kernel (without extra white space and text skipped by
comments).  I consider that a fairly big chunk of Forth code (cross.fs
has 4261 lines, and kernel/*.fs has 6948 lines).  Interestingly, when
flattened into one file and simplified, the result was not that big,
taking only 110KB.

The reference program took 165M cycles or 0.06s on a Xeon E3-1220.  So
one might say, that, for Forth programs of this size, the linked list
is good enough on desktop hardware.  Looking closer at the performance
is enlightening, though:

      164587102  cycles                   #      0.000 M/sec
       80381803  instructions             #      0.488 IPC  
         518240  branch-misses            #      0.000 M/sec
       21370347  L1-dcache-load-misses    #      0.000 M/sec
       45603137  L1-dcache-loads          #      0.000 M/sec

As you can see, the program has relatively low instructions per cycle
(IPC), and that probably mostly comes from the large number of L1 load
misses: almost every second load is an L1 miss.  That's because the
Forth wordlist does not fit into the L1 cache, and since we often walk
through much or all of it, the linked-list approach thrashes the
cache.

By using a hash table, this problem can be much reduced, and the
students saw big speedups and even bigger reductions in L1 cache
misses from hashing.

Other optimizations that the students performed were

1) Searching the same wordlist only once, even if it appears multiple
times in the search order.

2) Reorganizing the dictionary such that you first do the name lookup,
and each name has a list of wordlists in which it is defined (and the
associated xts, or, in this case, a serial number for computing the
checksum).

3) For each wordlist in the search order, store it's position in the
search order.  Then you can just go through the wordlists a name is
defined in once, and remember which wordlist (and xt/serial no) has
the earliest position.  This means that for each word you have to go
through the list of wordlists of the word only once, instead of going
through it once for every entry in the search order.

Hashing bought a huge speedup, the others some more, with 3) buying
relatively little, apparently because the lookup of the right wordlist
for a name does not cost that much, so optimizing that has little
potential.

The best effort by the students took 2.3M cycles.  Unfortunately they
did not put their work online, but if you are interested in the
efforts of those few who did, you can look at
<https://www.complang.tuwien.ac.at/anton/lvas/effizienz-abgaben/2015w/>.

- 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] | [next] | [standalone]

#45187

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> The reference program was given in C, and can be found on
> <https://www.complang.tuwien.ac.at/anton/lvas/effizienz-aufgabe15/#vorgabe>.

I'm puzzled by this program: it opens the file in read-only mode, but
then mmaps the file descriptor with PROT_READ|PROT_WRITE and modifies
one of the mapped-in pages.  I thought the mmap call wasn't supposed to
allow PROT_WRITE unless the file was open for writing, but I see that
it's working anyway.

As a secondary style issue, I'd use uint64_t instead of unsigned long
for the hash and related values.  I was thinking of trying the program
on an ARM so I'll have to fix that.

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

#45198

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> The reference program was given in C, and can be found on
>> <https://www.complang.tuwien.ac.at/anton/lvas/effizienz-aufgabe15/#vorgabe>.
>
>I'm puzzled by this program: it opens the file in read-only mode, but
>then mmaps the file descriptor with PROT_READ|PROT_WRITE and modifies
>one of the mapped-in pages.  I thought the mmap call wasn't supposed to
>allow PROT_WRITE unless the file was open for writing, but I see that
>it's working anyway.

Note MAP_PRIVATE; from the documentation: "Updates to the mapping are
not visible to other processes mapping the same file, and are not
carried through to the underlying file."  So even if the file was
opened R/W, the result would be the same.  Or, in other words, mmap()
is used here as (a hopefully more efficient variant of) read().

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

#45219

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> Note MAP_PRIVATE; from the documentation: "Updates to the mapping are
> not visible to other processes mapping the same file, and are not
> carried through to the underlying file." 

Hmm, I remember noticing that, but it didn't seem to displace the part
saying opening the file for read/write was required for PROT_WRITE.  I
asked on #linux IRC and someone there said it was undefined behaviour
under POSIX, so I'd be scared to deploy it in anything serious, but
anyway it seems to work for the example.

> in other words, mmap() is used here as (a hopefully more efficient
> variant of) read().

Yes, that part made sense.  Though reading the file in a single read()
call might conceivably be faster than mmap'ing the file and taking
multiple page faults while traversing it.  I think the next thing after
that is to use AIO to know which pages are available at a given time.
For such a small file I doubt any of this makes any difference, though.

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

#45226

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> Note MAP_PRIVATE; from the documentation: "Updates to the mapping are
>> not visible to other processes mapping the same file, and are not
>> carried through to the underlying file." 
>
>Hmm, I remember noticing that, but it didn't seem to displace the part
>saying opening the file for read/write was required for PROT_WRITE.  I
>asked on #linux IRC and someone there said it was undefined behaviour
>under POSIX, so I'd be scared to deploy it in anything serious, but
>anyway it seems to work for the example.

Better check yourself when people make such claims.  Like all lawyers,
standards lawyers prefer to give you the advice that something is not
allowed rather than erring on the other side, especially when they
give their advice for free.

Anyway, here's from the latest POSIX
<http://pubs.opengroup.org/onlinepubs/9699919799/functions/mmap.html>:

|If PROT_WRITE is specified, the application shall ensure that it has
|opened the file descriptor fildes with write permission unless
|MAP_PRIVATE is specified in the flags parameter as described below.

>> in other words, mmap() is used here as (a hopefully more efficient
>> variant of) read().
>
>Yes, that part made sense.  Though reading the file in a single read()
>call might conceivably be faster than mmap'ing the file and taking
>multiple page faults while traversing it.

My expectation is that read first causes the disk contents to be
loaded into kernel buffers, and then copies the data to user space,
while mmap() maps the OS buffers into user space without copying
(except the copy-on-write when I write to it).

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

#45229

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> <http://pubs.opengroup.org/onlinepubs/9699919799/functions/mmap.html>:
> |If PROT_WRITE is specified, the application shall ensure that it has
> |opened the file descriptor fildes with write permission unless
> |MAP_PRIVATE is specified in the flags parameter as described below.

Ah, ok, that clears things up nicely, thanks.

> My expectation is that read first causes the disk contents to be
> loaded into kernel buffers, and then copies the data to user space,
> while mmap() maps the OS buffers into user space without copying
> (except the copy-on-write when I write to it).

That's possible, though read() might be optimized in the case that the
user buffer is page aligned.  The copying might still be slower than the
extra context switches and potentially extra disk operations.

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

#45232

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> My expectation is that read first causes the disk contents to be
>> loaded into kernel buffers, and then copies the data to user space,
>> while mmap() maps the OS buffers into user space without copying
>> (except the copy-on-write when I write to it).
>
>That's possible, though read() might be optimized in the case that the
>user buffer is page aligned.

What kind of optimization do you have in mind?

>The copying might still be slower than the
>extra context switches and potentially extra disk operations.

It's also possible to optimize mmap() to avoid context switches in
many by mapping the buffers that are already in memory and contain the
file data when mmap() is called into the user space eagerly instead of
demand-paging these pages into user space.  I have no idea if that is
done, however.

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

#45188

Anton Ertl wrote:

> The best effort by the students took 2.3M cycles.  Unfortunately they
> did not put their work online, but if you are interested in the
> efforts of those few who did, you can look at
> <https://www.complang.tuwien.ac.at/anton/lvas/effizienz-abgaben/2015w/>.

How fast is Gforth on that benchmark by simply doing a FIND on all words 
encountered, and then only checksums the results?

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

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

#45204

Bernd Paysan <bernd.paysan@gmx.de> writes:
>Anton Ertl wrote:
>
>> The best effort by the students took 2.3M cycles.  Unfortunately they
>> did not put their work online, but if you are interested in the
>> efforts of those few who did, you can look at
>> <https://www.complang.tuwien.ac.at/anton/lvas/effizienz-abgaben/2015w/>.
>
>How fast is Gforth on that benchmark by simply doing a FIND on all words 
>encountered, and then only checksums the results?

I have now written a Forth version of ep15.c that processes the same
input format (and produces the same result on a 64-bit machine):
<https://www.complang.tuwien.ac.at/anton/lvas/effizienz-aufgabe15/ep15.fs>

It takes 180M cycles with gforth-fast on the reference machine, 36M of
which are consumed when just starting gforth-fast (so essentially 144M
for the actual program).  Here are the detailed results:

      179883538  cycles                   #      0.000 M/sec
      157894542  instructions             #      0.878 IPC  
        3568630  branch-misses            #      0.000 M/sec
        1269773  L1-dcache-load-misses    #      0.000 M/sec
       53807814  L1-dcache-loads          #      0.000 M/sec

How much of that is due to FIND-NAME?  If I first define FIND-NAME as

: find-name 2drop 0 ;

I get


      149942202  cycles                   #      0.000 M/sec
      139562133  instructions             #      0.931 IPC  
        2626759  branch-misses            #      0.000 M/sec
         839842  L1-dcache-load-misses    #      0.000 M/sec
       47026545  L1-dcache-loads          #      0.000 M/sec

If I replace it with 

: find-name 2drop [ s" #wordlists" find-name ]l ;

I get

      154854243  cycles                   #      0.000 M/sec
      143084355  instructions             #      0.924 IPC  
        2775349  branch-misses            #      0.000 M/sec
         884432  L1-dcache-load-misses    #      0.000 M/sec
       48098345  L1-dcache-loads          #      0.000 M/sec

I.e., 25-30M cycles spent in FIND-NAME.  So there is quite a bit of
potential for improvement there, but given that the other overheads
are so large, it's probably better to spend the effort elsewhere
first.

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

#45206

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>It takes 180M cycles with gforth-fast on the reference machine, 36M of
>which are consumed when just starting gforth-fast (so essentially 144M
>for the actual program).  Here are the detailed results:
>
>      179883538  cycles                   #      0.000 M/sec
>      157894542  instructions             #      0.878 IPC  
>        3568630  branch-misses            #      0.000 M/sec
>        1269773  L1-dcache-load-misses    #      0.000 M/sec
>       53807814  L1-dcache-loads          #      0.000 M/sec
>
>How much of that is due to FIND-NAME?  If I first define FIND-NAME as
>
>: find-name 2drop 0 ;
>
>I get
>
>
>      149942202  cycles                   #      0.000 M/sec
>      139562133  instructions             #      0.931 IPC  
>        2626759  branch-misses            #      0.000 M/sec
>         839842  L1-dcache-load-misses    #      0.000 M/sec
>       47026545  L1-dcache-loads          #      0.000 M/sec
>
>If I replace it with 
>
>: find-name 2drop [ s" #wordlists" find-name ]l ;
>
>I get
>
>      154854243  cycles                   #      0.000 M/sec
>      143084355  instructions             #      0.924 IPC  
>        2775349  branch-misses            #      0.000 M/sec
>         884432  L1-dcache-load-misses    #      0.000 M/sec
>       48098345  L1-dcache-loads          #      0.000 M/sec
>
>I.e., 25-30M cycles spent in FIND-NAME.  So there is quite a bit of
>potential for improvement there, but given that the other overheads
>are so large, it's probably better to spend the effort elsewhere
>first.

Ok, looking at it again, dynamic native code generation is disabled in
the engine built on that machine (I now remember that gcc-4.4 was one
of the particularly bad versions).  Running on the Haswell with
gcc-4.9.2, I see

 56837722      cycles:u                 
135146121      instructions:u            #    2.38  insns per cycle        
   266092      branch-misses:u                                             
   553092      L1-dcache-load-misses     #    1.57% of all L1-dcache hits  
 35236800      L1-dcache-loads                                         

With : find-name 2drop 0 ;

 50547534      cycles:u                 
122063613      instructions:u            #    2.41  insns per cycle        
   239118      branch-misses:u                                             
   459065      L1-dcache-load-misses     #    1.44% of all L1-dcache hits  
 31907684      L1-dcache-loads                                         

With : find-name 2drop [ s" #wordlists" find-name ]l ;

 51313405      cycles:u                 
122069990      instructions:u            #    2.38  insns per cycle        
   241427      branch-misses:u                                             
   476163      L1-dcache-load-misses     #    1.49% of all L1-dcache hits  
 31896977      L1-dcache-loads                                         

So the FIND-NAME overhead is 5-6M instructions.  Still quite a bit
more than the best the students got (and their result include all the
other things as well), but significantly better than it appeared at
first.  But again, other overheads dominate here, and probably even
more so for real text interpretation.

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

#45189

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> The reference program took 165M cycles or 0.06s on a Xeon E3-1220....
>       164587102  cycles                   #      0.000 M/sec
>        80381803  instructions             #      0.488 IPC  
>        518240  branch-misses            #      0.000 M/sec
>      21370347  L1-dcache-load-misses    #      0.000 M/sec
>      45603137  L1-dcache-loads          #      0.000 M/sec

On an i7-3770, gcc 4.7.2, perf 3.2.17, I get:

         120962754 cycles:u                  #    0.000 GHz
          99843302 instructions:u            #    0.83  insns per cycle
            658537 branch-misses:u
   <not supported> L1-dcache-load-misses
   <not supported> L1-dcache-loads
       0.043837722 seconds time elapsed

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

#45199

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> The reference program took 165M cycles or 0.06s on a Xeon E3-1220....
>>       164587102  cycles                   #      0.000 M/sec
>>        80381803  instructions             #      0.488 IPC  
>>        518240  branch-misses            #      0.000 M/sec
>>      21370347  L1-dcache-load-misses    #      0.000 M/sec
>>      45603137  L1-dcache-loads          #      0.000 M/sec
>
>On an i7-3770, gcc 4.7.2, perf 3.2.17, I get:
>
>         120962754 cycles:u                  #    0.000 GHz
>          99843302 instructions:u            #    0.83  insns per cycle
>            658537 branch-misses:u

More instructions, more branch misses, less cycles.  My guess is that
gcc-4.7.2 does something more efficient for the memcmp than the rep
that gcc 4.4.5 uses on the reference machine.  That's one of the
things the students found: memcmp() is slower on the reference machine
than alternatives (it's really perverse that many groups replaced it
with strncmp() and got a speedup).

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

#45205

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Paul Rubin <no.email@nospam.invalid> writes:
>>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> The reference program took 165M cycles or 0.06s on a Xeon E3-1220....
>>>       164587102  cycles                   #      0.000 M/sec
>>>        80381803  instructions             #      0.488 IPC  
>>>        518240  branch-misses            #      0.000 M/sec
>>>      21370347  L1-dcache-load-misses    #      0.000 M/sec
>>>      45603137  L1-dcache-loads          #      0.000 M/sec
>>
>>On an i7-3770, gcc 4.7.2, perf 3.2.17, I get:
>>
>>         120962754 cycles:u                  #    0.000 GHz
>>          99843302 instructions:u            #    0.83  insns per cycle
>>            658537 branch-misses:u
>
>More instructions, more branch misses, less cycles.  My guess is that
>gcc-4.7.2 does something more efficient for the memcmp than the rep

"rep cmpsb" meant here.

>that gcc 4.4.5 uses on the reference machine.  That's one of the
>things the students found: memcmp() is slower on the reference machine
>than alternatives (it's really perverse that many groups replaced it
>with strncmp() and got a speedup).

To check this, I ran the gcc-4.4.5-generated binary on a Core i7-4790K
(Haswell) instead of the Sandy-Bridge-based Xeon, and got the
following results:

157170042      cycles:u                 
 80383211      instructions:u            #    0.51  insns per cycle        
   517709      branch-misses:u                                             
 10158800      L1-dcache-load-misses     #   31.29% of all L1-dcache hits  
 32471601      L1-dcache-loads                                         

Compiling it with gcc-4.9.2 produced:

114623017      cycles:u                 
 99904228      instructions:u            #    0.87  insns per cycle        
   646886      branch-misses:u                                             
  9831540      L1-dcache-load-misses     #   28.06% of all L1-dcache hits  
 35036262      L1-dcache-loads                                         

Running this binary on the Xeon produced:

      120441184  cycles                   #      0.000 M/sec
      102888367  instructions             #      0.854 IPC  
         613337  branch-misses            #      0.000 M/sec
       18871467  L1-dcache-load-misses    #      0.000 M/sec
       39592359  L1-dcache-loads          #      0.000 M/sec

(apparently there is also a difference in the dynamically linked
libraries between these systems that results in the difference of
executed instructions).

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

#45220

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>gcc-4.7.2 does something more efficient for the memcmp than the rep
>>[cmpsb] that gcc 4.4.5 uses on the reference machine.

Wow, I'm surprised gcc as recently as 4.4.5 used rep cmpsb since I think
those rep instructions have been considered slow holdovers from the 8086
era for quite a long time.

> Compiling it with gcc-4.9.2 produced:
>  99904228      instructions:u            #    0.87  insns per cycle        

Ok, the difference was mostly the compiler.  I guess this test was
memcmp intensive but it's still interesting to see such a big
difference.

> (apparently there is also a difference in the dynamically linked
> libraries between these systems that results in the difference of
> executed instructions).

I tried compiling with --whole-program and got just a tiny speedup.

I have to ask, historically, did Forth in the minicomputer era really
use this linked list representation?  With a 1000 word vocabulary and
maybe 1 mhz memory cycle, that's a significant amount of time just doing
those lookups in a sizeable user program (10k tokens at 0.3 msec each is
3 seconds right there).  I guess the representation lets FORGET work
where hashing didn't, but did it matter?  I also remember something
about using multiple lists, then called "threads".

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

#45221

Paul Rubin <no.email@nospam.invalid> writes:

>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>gcc-4.7.2 does something more efficient for the memcmp than the rep
>>>[cmpsb] that gcc 4.4.5 uses on the reference machine.

>Wow, I'm surprised gcc as recently as 4.4.5 used rep cmpsb since I think
>those rep instructions have been considered slow holdovers from the 8086
>era for quite a long time.

>> Compiling it with gcc-4.9.2 produced:
>>  99904228      instructions:u            #    0.87  insns per cycle

>Ok, the difference was mostly the compiler.  I guess this test was
>memcmp intensive but it's still interesting to see such a big
>difference.

>> (apparently there is also a difference in the dynamically linked
>> libraries between these systems that results in the difference of
>> executed instructions).

>I tried compiling with --whole-program and got just a tiny speedup.

>I have to ask, historically, did Forth in the minicomputer era really
>use this linked list representation?  With a 1000 word vocabulary and
>maybe 1 mhz memory cycle, that's a significant amount of time just doing
>those lookups in a sizeable user program (10k tokens at 0.3 msec each is
>3 seconds right there).  I guess the representation lets FORGET work
>where hashing didn't, but did it matter?  I also remember something
>about using multiple lists, then called "threads".

I have a port of ciforth for a 6809 2 Mhz vintage sbc (see the site of
the Dutch Fig). Despite a single linked vocabulary and brutally
straightforward headers (same as in lina) the speed of compilation was
bearable. For this board there was also MAISforth (with Frans van de
Markt and Albert Nijhof of noforth fame as main contributors) This
Forth had some attention to speed and several "threads". It is quite
snappy. FORGETting/MARKERing on MAISForth (as in noforth) is of the
essential.

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]

#45225

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>gcc-4.7.2 does something more efficient for the memcmp than the rep
>>>[cmpsb] that gcc 4.4.5 uses on the reference machine.
>
>Wow, I'm surprised gcc as recently as 4.4.5 used rep cmpsb since I think
>those rep instructions have been considered slow holdovers from the 8086
>era for quite a long time.

gcc 4.9.2 compiles memset(...,0,64) into REP STOSQ, which is much
slower than 8 mov instructions.

>> (apparently there is also a difference in the dynamically linked
>> libraries between these systems that results in the difference of
>> executed instructions).
>
>I tried compiling with --whole-program and got just a tiny speedup.

I did not mean the overhead of the dynamic call, but that the called
function does different things on, e.g. libc-2.19 (on the Haswell box)
and libc-2.11.3 (on the reference machine).

>I have to ask, historically, did Forth in the minicomputer era really
>use this linked list representation?  With a 1000 word vocabulary and
>maybe 1 mhz memory cycle, that's a significant amount of time just doing
>those lookups in a sizeable user program (10k tokens at 0.3 msec each is
>3 seconds right there).

Yes, this was used; read the fig-Forth sources.  And 10k words is
probably upwards of 100 screens, and loading that much from floppy
disk takes more then 3 seconds, in particular since you would have to
change the disk if it holds only 85KB as the early ones did.  Even
earlier paper tape was used IIRC, and that was even slower.

>I guess the representation lets FORGET work
>where hashing didn't, but did it matter?  I also remember something
>about using multiple lists, then called "threads".

Hashing with external chaining works fine with FORGET.  And yes, it
does matter if you have only a few KB, so you cannot just load the
changed code on top of the old one, and reloading the whole thing
takes much longer than FORGETing and loading the code starting from
the changed screen.  I have not used FORGET or MARKER except for
testing purposes since the 1990s, but there are still a lot of people
who use FORGET, resulting in it being not destandardized in
Forth-2012.

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

#45227

On 1/31/16 8:17 PM, Anton Ertl wrote:
> Paul Rubin <no.email@nospam.invalid> writes:
...
>> I have to ask, historically, did Forth in the minicomputer era really
>> use this linked list representation?  With a 1000 word vocabulary and
>> maybe 1 mhz memory cycle, that's a significant amount of time just doing
>> those lookups in a sizeable user program (10k tokens at 0.3 msec each is
>> 3 seconds right there).
>
> Yes, this was used; read the fig-Forth sources.  And 10k words is
> probably upwards of 100 screens, and loading that much from floppy
> disk takes more then 3 seconds, in particular since you would have to
> change the disk if it holds only 85KB as the early ones did.  Even
> earlier paper tape was used IIRC, and that was even slower.

figForth was a very simple system whose objective was to be simple to 
implement. As a consequence, it was pretty inefficient. Professional 
systems were a lot faster, using a multi-threaded linked list and other 
optimization techniques.

>> I guess the representation lets FORGET work
>> where hashing didn't, but did it matter?  I also remember something
>> about using multiple lists, then called "threads".
>
> Hashing with external chaining works fine with FORGET.  And yes, it
> does matter if you have only a few KB, so you cannot just load the
> changed code on top of the old one, and reloading the whole thing
> takes much longer than FORGETing and loading the code starting from
> the changed screen.  I have not used FORGET or MARKER except for
> testing purposes since the 1990s, but there are still a lot of people
> who use FORGET, resulting in it being not destandardized in
> Forth-2012.

Many of our customers in these days had extremely complex applications 
loaded on top of miniFORTH, microFORTH, or early polyFORTH. The standard 
system, when launched, had a FORGET boundary such that the application 
could be reloaded easily and quickly, without re-launching the entire 
system. But, yes, this was pretty obsolete by the 90's.

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]

#45210

On Friday, January 29, 2016 at 11:22:53 AM UTC-7, Anton Ertl wrote:
> So
> one might say, that, for Forth programs of this size, the linked list
> is good enough on desktop hardware.  
> ...
> the 
> Forth wordlist does not fit into the L1 cache, and since we often walk 
> through much or all of it, the linked-list approach thrashes the 
> cache. 
> 
> By using a hash table, this problem can be much reduced

If you have unlimited memory, such as on a modern desktop computer, then a hash-table is going to be fast. Just make the table big enough that it never has to be rebuilt.

My symtab always takes less memory than a hash-table however (assuming that the hash-table is rebuilt when it is 1/2 full). The problem with cache-thrashing in a linked list is not going to happen. All of the nodes near the root are going to be in the data-cache so there won't be any cache-thrashing from one lookup to the next unless you are looking up uncommon words that are near the leaves. The difference is that symtab grows smoothly, whereas the hash-table grows in spurts with a lot of time taken to rebuild it --- so, if you are rebuilding often, the hash-table is inefficient --- quite a lot of cache-thrashing in a rebuild!

If you have a very limited amount of memory however, then a linked-list is the best solution because neither my symtab or your hash-table will fit in memory otherwise --- this is why Charles Moore used a linked-list in 1974.

My symtab was discussed here:
https://groups.google.com/forum/#!searchin/comp.lang.forth/symtab/comp.lang.forth/w3tHPsTaZvE/oOv9w1kmlfkJ

This is my calculation for memory usage:
On Wednesday, December 2, 2009 at 3:21:46 PM UTC-7, Hugh Aguilar wrote:
> On Dec 1, 2:59 am, Bernd Paysan <bernd.pay...@gmx.de> wrote:
> > You also miss some other points entirely: A tree has an overhead of 3 cells
> > per node (pointer to left/right/leaf).  A chained hash has an overhead of 2
> > cells per node (leaf+chain).  So if the hash is 2/3 filled, it takes as much
> > space as the tree.  A hash that's growing by a factor 2 per growth iteration
> > is filled about 2/3 on average.  Result: Size overhead is about the same.
> 
> You calculation doesn't make sense to me. For one thing, I don't know
> what a "leaf" is. If this refers to the pointer to the key string,
> then it can be ignored. The string can be placed in-line with the rest
> of the node's data. Also, whether you use a pointer or not, has
> nothing to do with the data structure, hash table or symtab, that you
> are working with.
> 
> My own calculation is that a hash table uses the same amount of memory
> as a symtab when the hash table is 1/2 full. This calculation helps
> the argument for hash tables because hash tables are a lot more
> efficient (fewer collisions) when 1/2 full rather than 2/3 full. Your
> calculation of 2/3 not only didn't make sense, but it hurt your
> argument anyway. According to the wikipedia article
> (http://en.wikipedia.org/wiki/Hash_table), the load factor should not
> exceed .7 because the cost of the collisions becomes excessive. A load
> factor of .67 (2/3) is pretty close to .7. I've never implemented a
> hash table, so I don't have any personal experience with this. AFAIK
> however, almost everybody resizes the hash table when the load factor
> passes the 1/2 threshold.
> 
> My calculation works like this: The memory consumed per node in a hash
> table is equal to N+N/L, with N being the number of nodes and L being
> the load factor. I am assuming the use of a linked list for collision
> resolution. Because of this, each node contains a forward link pointer
> to the next node in the linked list, or NIL if there are no more nodes
> in the linked list. This gives us N words of memory (one word per
> node). The load factor L is the fraction of the table that contains
> pointers to linked lists, and 1-L is the fraction of the table that
> contains NIL pointers. N/L is the size of the table given N nodes
> (assuming no collisions at all). I add N to N/L to obtain the total
> amount of memory used per node. If L is 1/2, then N+N/L is 3. My
> symtab also takes 3 words per node (left, rite and count), so a load
> factor of 1/2 is where hash tables equal symtabs in memory overhead.
> This, coincidentally, is also the load factor where most people resize
> their hash tables. When the load factor is < 1/2, the hash table uses
> more memory per node than a symtab does. When the load factor reaches
> the 1/2 threshold, the hash table is resized. The result is that the
> hash table *always* uses more memory per node than a symtab does. If
> you resize the hash table by doubling its memory usage, the hash
> table's load factor becomes 1/4. Now the hash table uses 5 words
> (1+1/.25) per node. This is 167% of symtab's 3 words per node, which
> is pretty bad.
> 
> My calculation above assumes that there are no collisions at all. This
> isn't realistic. Even in a sparsely populated hash table you are
> likely to have a few collisions. When the number of nodes is around
> 1/2 the hash table size however, there aren't too many collisions and
> it is reasonable to assume that there aren't any collisions. As the
> number of nodes increases to 2/3 or more, there are a lot more
> collisions and my equation becomes increasingly inaccurate. This is
> nothing to worry about because, as I said, it is typical to resize the
> hash table at 1/2 anyway.

[toc] | [prev] | [standalone]

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

csiph-web