Re: symbol tables and search tries

Matthias Blume <blume@tti-c.org>
3 Feb 2006 18:36:41 -0500

          From comp.compilers

Related articles
[14 earlier articles]
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-01-31)
Re: symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-31)
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-02-02)
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-02-02)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-02)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-02-03)
Re: symbol tables and search tries d148f3wg02@sneakemail.com (Karsten Nyblad) (2006-02-03)
Re: symbol tables and search tries henry@spsystems.net (2006-02-03)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-03)
Re: symbol tables and search tries haberg@math.su.se (2006-02-03)
Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-02-06)
Re: symbol tables and search tries Suif.liyuan@gmail.com (jjyynmb) (2006-02-24)
| List of all articles for this month |

From: Matthias Blume <blume@tti-c.org>
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:36:41 -0500
Organization: private
References: 06-01-085 06-01-111 06-01-112 06-01-127 06-02-008
Keywords: symbols, performance
Posted-Date: 03 Feb 2006 18:36:41 EST

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


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


If you double your hashtable when the load factor exceeds 1, then you
waste an expected number of buckets that is bounded by something very
close to the number of actual elements in the table. If you do not
double the size, then you have to use more chain links in each bucket.
In a typical implementation, the required number of extra pointers is
the same as the number of those wasted buckets. Thus, doubling the
number of buckets does not waste memory (in comparison with chaining).


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


Yes. But that is exactly what the "double the size on demand"
mechanism achieves.


I expect a binary tree implementation of the table to use _more_
memory than (or at best an equal amount as ) such a hashtable.


Matthias


Post a followup to this message

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