Data structures for symbol tables

In article <929@ima.ISC.COM>, beres@cadnetix.COM (Tim Beres) writes
some stuff to which the moderator appends:


> [It's hard to believe that storing a symbol table in a B-tree is worth the
> effort; B-trees make sense for disk files since looking at a page is
> relatively expensive, but for an in-core symbol table the O(1) lookup time
> of hashing should be better. It's also a lot easier to program. -John]


Depends on how large your symbol table is. It is easy to imagine
B-trees out performing hash tables if the b-tree nodes are near page
size. Remember, virtual memory is on a disk too. Given the variety
of computer architectures, hash functions, ways of handling hash
collisions, identifier usage patterns among languages, and programming
goals (i.e., how architecture specific it is possible to make the
implementation), I doubt if there is one right structure. Many of the
studies have been done on systems where page fetch delays aren't
charged to the process making them, making them suspect. Considering
the number of times a compiler gets used in comparison to the number
of times it gets written, the real question is: is the symbol table a
bottleneck worth speeding up? Probably the time would be better spent
creating structure editors that hand the compiler a pre-scanned pre-parsed
object to fiddle with as appropriate.


------ BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)
--

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