> The enviroment overall is "tight" and you need to be
> very selective over memory and CPU use. As heard at
> last PalmSource, "In a way, we are back to the glory
> days of DOS coding before Windows 3.0 where you weren't
> enslaved by a Protected Mode Manager."
Heh heh... Protected mode, what's that?
More seriously, I'd like to get some folks opinions on the first statement
quoted above, regarding tight resources. Specifically, in how it applies to
dynamically sized containers (ie, STL-like containers such as vector or
list, or others for that matter).
I'll start with an example, taken from a problem I've been wrestling with
lately. Let's say I want a sorted list of Item, which contains a record
index into some db (2 bytes) and some flag data (2 bytes), for a total of 4
bytes. We need operations for access, insert in the middle, remove from the
middle, etc. The usual round of list-like operations.
Several ways to go about this:
A. Allocate a memory array of n_Items * sizeof(Item).
For efficieny, may allocate in chunks at a time.
Bennies: Easy, quick access via the array [] operator.
Easy bidirectional iteration.
Slaps: Insert must sometimes reallocate and copy whole array.
Everything above inserted item must be shifted up.
Everything above removed item must be shifted down.
Can waste space on unused items at end of array.
B. Use a singly linked list.
Item has 4-byte pointer to next Item.
Bennies: Efficient in that all memory allocated is used.
Easy forward iteration.
Efficient to insert/remove Items from middle.
Slaps: Pointer to next Item doubles size of Item
(for small Item's; other data may dwarf pointer)
No reverse iteration.
May fragment memory. ???
Loss of [] operation. May make resorting difficult.
C. Use some other structure (double-linked list, tree, etc).
Bennies: Fast and efficient (Maybe, maybe not?)
Slaps: Memory overhead can kill.
D. Use a matching Palm database. IE, a record in the
index database corresponds to a record in the "real"
database.
Bennies: Easy to implement (use Palm API).
Slaps: Now calling DB API calls twice as frequently. Can
kill performance. (I know, I did this.)
E. Other ideas? Bennies and slaps?
Other things to consider. Are we using pointers or handles? If pointers,
we might frag memory. If handles, we need to constantly lock/unlock. What
about storing database indices? While we need to worry about
insertion/deletion in our own structure, we also need to update the indices
if we insert/delete from the database. (On the assumption for delete's that
we move the record to the end of the database.)
I've been bashing my skull against the keyboard (especially letters 't' 'y'
and '7', I like them) pondering what I should do. (My app needs to index
all records in a database, keeping a sorted index and a few flags for each.
Currently, once I get over a few hundred, things start to crawl. Yet I can
go hogging up dynamic memory without fear of running out.)
I'm not looking for someone to solve my problem here. I presented my
problem just to show some of the issues that can crop up from this sort of
thing. I also don't want STL: while it's great for desktops, I think it's a
little bit too much for a Palm. (This is not an argument against C++
templates, which if used properly would be fine.)
Rather, just wanted to start a discussion on speed and memory issues when
dealing with dynamic containers. I'd appreciate hearing from others on your
comments to the above and/or what problems you've experienced in your own
coding.
---- --- -- -
Matthew D Moss
[EMAIL PROTECTED]
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palm.com/devzone/mailinglists.html
