Maury Markowitz
-
Posts
222 -
Joined
-
Last visited
Content Type
Profiles
Forums
Blogs
Gallery
Events
Store
Status Updates posted by Maury Markowitz
-
Hey, I was looking through some old posts and I'd like to ask a follow-up question:
QuoteTurboBasic uses such a method. It keeps a table of 256 bytes that keeps the start addresses of the program lines. Of course there are more than 256 lines in many programs, so TurboBasic uses a quite simplistic "hash function" to derive the hash from the line number: Take the most significant byte of the line (a number between 0 and 127) times 2 defines the slot index.
Thus, if a program searches for line N, it is sufficient to compute floor(N / 256) * 2, to find the nearest line number below the line the program is looking for, and then perform a linear search from that line on. This means that the basic interpreter has to search through at most 255 lines to find the line - instead of performing the search from the start of the program.
I'm curious when this table is created and maintained? The values in it could theoretically change with every edit. I guess it could update it with every edit, as I suspect only the first so many slots are actually used in practice. But I don't think that's how they would do it.
Or perhaps it does this are program start/restart... but then you have the associated delay at startup and the need to flush it on edits.