Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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) |
| [18 later articles] |
| From: | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
| Newsgroups: | comp.compilers |
| Date: | 30 Jan 2006 01:58:29 -0500 |
| Organization: | Compilers Central |
| References: | 06-01-085 06-01-111 |
| Keywords: | symbols |
| Posted-Date: | 30 Jan 2006 01:58:29 EST |
(snip)
> [I don't understand what you're proposing. Balanced trees are O(log N)
> to search and require rebalancing whenever you insert something. Hash
> tables of the sort we usually use for compiler symbol tables are O(1)
> and balancing isn't an issue. -John]
Hash tables are O(1) until you have to resize them.
The IBM S/360 Fortran H compiler uses six balanced trees,
one for each possible symbol length.
In one manual IBM recommended distributing variable names
equally between one and six characters to speed compilation.
-- glen
[Well, yeah, but it's been a while since I've written a compiler that
had to run in a 128K byte machine. I understand why they wouldn't
have wanted to devote precious storage to a hash table in 1969, but
that was then. -John]
Return to the
comp.compilers page.
Search the
comp.compilers archives again.