skef@cmu-cs-spice.ARPA (Skef Wholey) (03/13/85)
From david@daisy.UUCP (David Schachter) Thu Mar 7 05:40:06 1985
My programs generally allocate tables of a few kilobytes and then
grow them as necessary. That is, I keep track of how many entries
in a given table are used and how many are available. When I
have to add another entry to a full table, I allocate a bigger
chunk of memory, copy the original to the new chunk, delete the
old chunk, and fix up my various pointers, indices, and maxima.
Sure, I do the same thing. I used the "several really huge tables" scenerio
instead of the "grow by allocating a new chunk, copying, and deallocating
the old chunk" in my original message to simplify the discussion. Growing
the tables dynamically is obviously the right thing to do. Note however,
that as you grow things, you may not be able to really free up the resources
associated with the old chunk. That is the whole problem. If you keep
growing one table larger and larger, you're going to leave a big hole in
your address space, which on something like Vax/Unix will cost you page
table space and backing store.
Software that allocates fixed-size tables has limits. Software
that checks for filled tables (or arrays or structures or
whatever) and handles such cases appropriately has fewer
limits. The size of the address space isn't an issue.
My point was that given an address space big enough for the task at hand,
sparseness becomes an issue. The combination of large and sparse may give
your applications a few more years of life in the market place.
A large address translation cache will help with any kind of paged virtual
address space. With a large enough translation cache, the implementation of
the page table data structures becomes pretty unimportant. Given fancy
things like copy-on-write pages, the above table growing task becomes even
more efficient. When I am actually writing code to do that sort of thing
under Accent, the copy operation is performed by copying page table entries,
more or less. The data in the tables needn't even be paged in to copy it.
--Skef
--
uucp: ...!seismo!cmu-cs-spice!skef
arpa: skef@CMU-CS-Spice