symbol tables and search tries

"Mr.E" <mr.waverlye@verizon.net>
28 Jan 2006 15:10:45 -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)
[20 later articles]
| List of all articles for this month |

From: "Mr.E" <mr.waverlye@verizon.net>
Newsgroups: comp.compilers
Date: 28 Jan 2006 15:10:45 -0500
Organization: http://groups.google.com
Keywords: symbols, performance
Posted-Date: 28 Jan 2006 15:10:45 EST

I done some homework and there is something that I dont understand. In
all the books I've read everyone recommends hashing for symbol tables
but I've read a number of articles the state that searching tries is
many times faster than hashing. I understand there can sometimes be a
sizeable amount of overhead in using tries but with the different
methods of trie algorithms it would seem there would be a lot of clamor
for trie usage in compilers. Are there reasons why tries arent
advocated?


Thanks,


W.
[You need to read better articles. For the strings you're likely to
find in a compiler symbol table, tries would be about the same speed,
maybe slower, and the code would probably be more complicated. Tries
win when the strings are long and don't all fit in main memory.
Moreover, any compiler where symbol lookups are a significant part of
the compile time has worse problems than which search algorithm it's
using. -John]



Post a followup to this message

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