Re: symbol tables and search tries

Matthias Blume wrote:


> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:


>>(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 cost of an insertion or an access of a hash table element is O(1)
> amortized, taking the occasional need for resizing into account.
> (This assumes that the resizing policy is chosen appropriately.
> Example: Double the size when the load factor exceeds some fixed
> threshold.)


Assuming you can afford the extra memory, yes.


Note that O() notation assumes the large N limit, though most
compilers operate with more reasonable N.


The question, then, is with the available memory and expected size
which is the best choice? IBM chose a balanced tree for Fortran H.


The PL/I (F) compiler will move the symbol table to disk if it
runs out of memory. That might affect the choice, too.


Memory wasn't always as cheap as it is today.


-- glen
[Indeed, but does anyone see it getting more expensive? The Fortran compiler
on the IBM 1130 was about a dozen passes loaded from disk, and I sure hope
nobody suggests that as a way to build new comilers. -John]

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