Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #45184
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Forth dictionary implementation and performance |
| Date | 2016-01-29 17:42 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2016Jan29.184253@mips.complang.tuwien.ac.at> (permalink) |
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/
Back to comp.lang.forth | Previous | Next — Next in thread | Find similar | Unroll thread
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
csiph-web