On Tue, 2 Mar 1999, Mike Pellegrino wrote:
> Once I start allocating out of a pool of database records, a number of
> things happen.
>
> The first is that I have multiple pools to manage because a database
> record can hold only <64K of data. To hold more than 64K of data, we
> need multiple records.
Yes, you'll need to chain the management data. A LRU technique of some
sort might help (to try and keep the working set most easily accessed), as
perhaps moving some overhead into the allocated blocks themselves.
> The second thing is that now I have to write a memory allocator (which
> is not bad if it's a fixed size allocator), take care of fragmentation
> of the "heap"/compaction, etc. While I could do this, it would be
> better to have the OS do it natively (using their APIs) because it's
> more efficient. And, they are doing it anyway via their database API.
I'd have to argue with this: everyone and their sibling has at one time
written their own allocation system on top of the OS, and it is a bog
standard technique. The overhead shouldn't be much significant beyond the
size of your own code. (Becaue most of the time user code will only be
triggering one of the allocators.) The timewise overhead should be
minimal, _assuming_ that the OS doesn't use virtual (paged or swapped)
allocation. Which it doesn't, which is where we came in.
> The third thing is that every write operation in the pool (compaction
> especially) involves DmWrite operations. While they are relatively
> fast, there would be a good number of them occurring on allocations and
> deletes. While initially cheaper in terms of time to perform than a
> DMNewRecord, as compaction occurs, that performance advantage
> dissipates.
That's why my first thought would be to keep the active pool data on the
heap, swapping inactive pool data out into storage, moving the MRU blocks
into the active pool area. Without trying it, I've no idea whether this
would be workable.
> The fourth item to note is that multiple heaps don't work very well (as
> Palm found out themselves in Palm OS 1.0/2.0). There can be issues
> where I want to allocate a large block, but none of my pools can handle
> it by itself. Collectively, they have enough space, but no single pool
> can hold the entire record (Rhodes describes this really well in Palm
> Programming, A Developers Guide). This means I either must fragment the
> allocated memory block over multiple pools, rearrange the pool memory
> across the different pools to find a good space, or disallow the
> allocation. All of this boils down to a lot of overhead (even more than
> DmNewRecord). Ultimately, the Palm OS 3.0 team didn't want to tackle
> this issue because they have a single heap to allocate from. I don't
> want to tackle this issue because the Palm people have already done that
> work for me ;-)
Actually, this one doesn't sound too difficult to solve, in a very rough
but probably sufficient manner (which seems to count for a lot, in
allocation systems): if allocations fail, due to heap fragmentation, swap
blocks out of their pools into storage, swapping out entire pools if
needed, until their is room. This assumes, of course, that blocks in
storage aren't in a pool, but are floating about loose or are in a single
heap-pool.
I must say that I am interested in exploring this virtual-memory idea. I
remember discussing the idea ages ago (with Ed Keyes, I expect), and it
seemed a fairly obvious thing to do, based on the use of handles (as
opposed to pointers) for heap storage. (But, since this is Ed, the idea
was of course to set up a hack that would provide virtual memory to all
running programs, using the standard handle calls. :-)
--
Kenneth Albanowski ([EMAIL PROTECTED], CIS: 70705,126)
