Path: utzoo!utgpu!water!watmath!clyde!ima!johnl
From: webber@athos.rutgers.edu
Newsgroups: comp.compilers
Subject: Data structures for symbol tables
Message-ID: <930@ima.ISC.COM>
Date: 28 Mar 88 02:06:15 GMT
References: <911@ima.ISC.COM> <914@ima.ISC.COM> <917@ima.ISC.COM> <929@ima.ISC.COM>
Sender: johnl@ima.ISC.COM
Reply-To: webber@athos.rutgers.edu
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 24
Approved: compilers@ima.UUCP

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)
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request