Re: symbol tables and search tries

Vladimir Makarov <vmakarov@redhat.com>
31 Jan 2006 00:34:39 -0500

          From comp.compilers

Related articles
symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-28)
Re: symbol tables and search tries haberg@math.su.se (2006-01-28)
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-01-30)
Re: symbol tables and search tries haberg@math.su.se (2006-01-30)
Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-01-31)
Re: symbol tables and search tries RLake@oxfam.org.uk (2006-01-31)
Re: symbol tables and search tries vmakarov@redhat.com (Vladimir Makarov) (2006-01-31)
Re: symbol tables and search tries clint@0lsen.net (Clint Olsen) (2006-01-31)
Re: symbol tables and search tries haberg@math.su.se (2006-01-31)
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries find@my.address.elsewhere (Matthias Blume) (2006-01-31)
Re: symbol tables and search tries danwang74@gmail.com (Daniel C. Wang) (2006-01-31)
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-01-31)
[14 later articles]
| List of all articles for this month |

From: Vladimir Makarov <vmakarov@redhat.com>
Newsgroups: comp.compilers
Date: 31 Jan 2006 00:34:39 -0500
Organization: Red Hat, Inc.
References: 06-01-085 06-01-111 06-01-117
Keywords: symbols
Posted-Date: 31 Jan 2006 00:34:39 EST

Hans Aberg wrote:
> John Levine wrote:


> [I make my hash tables big enough that the chains are short, i.e.,
> design so that k>=N so it's O(1). Hash headers need only be one
> word pointers, so pick a number larger than the number of symbols
> you expect in a large program, say, 10,000, and use that. So it adds
> 40K to the size of the program, that's down in the noise these days.
> -John]


I am agree that hash tables are more suitable in practice than
balanced trees.


If you look at GCC, it uses extendable hash tables in many places.
The hashtables are very compact (one element takes only one pointer in
the table) because no chains are used. Also deletions of elements
from the hash table are permitted. The hashtable are rebuilt when
there are many collisions (after the rebuilding the size can be bigger
or smaller). Big number of collision might be because there are many
elements in the table or too many deletions were made.


So the hashtables in gcc are better practically in all respects than
balanced trees (speed and size). They permit deletion too as balanced
trees. Although the balance trees have one adavantage which is
possibility to traverse elements in some order (gcc hashtables permit
to do only unordered traversing easily).


As I know hashtables form gcc is used in many order compilers and
interpreters.


A standalone version of the hashtables can be found on
http://cocom.sf.net. Its description is on
http://cocom.sourceforge.net/ammunition-5.html


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.