Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!pasteur!ucbvax!agate!violet.berkeley.edu!pete
From: pete@violet.berkeley.edu (Pete Goodeve)
Newsgroups: comp.sys.amiga
Subject: Re: IPC - Standard Message Blocks
Message-ID: <9131@agate.BERKELEY.EDU>
Date: 23 Apr 88 08:31:33 GMT
References: <5699@well.UUCP>
Sender: usenet@agate.BERKELEY.EDU
Reply-To: pete@violet.berkeley.edu.UUCP (Pete Goodeve)
Organization: University of California, Berkeley
Lines: 118
Summary: ain't necessarily so...


Oh oh! Looks like the blind men have their fingers on the elephant again...

In article <5699@well.UUCP> Stuart H. Ferguson writes:

> A Comparison of Different Standard Message Formats
>
> There have been a variety of proposals for a standard message structure
> which allows any number of blocks of data of any type.  The three I
> compare are nested chunks, entry list, and linked list of chunks. [...]

[He then goes on to show code for finding a particular "chunk type ID" with
each of the formats, and finds that a linked list is a little faster in
this situation than the IPCMessage format we've been suggesting.]

It's a little disheartening to see people totally ignore the last two
months of wide ranging discussion, and try to demonstrate a minor supposed
disadvantage of the format we've settled on (the "Entry" or "Item" array)
in one particular case.

What we've been trying to do over the past couple of months is come up with
a single format that covers all the situations we've been able to think of.
The Pete(r) IPCMessage format has evolved from this over a long series of
iterations.

There are quite a few reasons for choosing the compactness of a (variable
size) array over a linked list.  The main one is probably that your average
message WON'T have an arbitrary series of items, but rather one or two
fixed fields that the server program won't have to search for at all.  The
IDs serve two purposes in such a case: first as a validity check, and
also as a secondary selection mechanism for variant fields.  If a list is
more suitable in a particular case -- a list of file names, for example --
there is nothing to stop an item pointing to one.  Long, complex, messages
seem not in the spirit of IPC though: better to send a string of short and
to-the-point ones that can be handled quickly.

Another major reason is that the "control information" for an item, and the
data it points to, must in general be kept separate.  There's no guarantee
that there would be any space for a list node (or any of the control
information) at the head of a piece of data -- it might be embedded in
something else.  And we want to avoid copying, remember?

                           + + + + + + + +


Stuart also stacked the deck a little when he showed code for finding an
item in our structure:
        ....
>         for (i=0; i<mess->number_of_entries; i++) {
>                 ptr = mess->entry_array[i];
>                 if (ptr->ctype == ctype) return ptr;
>         }
        ....

Now I would do it more like this (using Stuart's -- not our -- notation):

    ....
    struct Entry *ptr;
    int i;
    for (i = mess->number of entries, ptr = mess->item_array; i--; ptr++)
         if (ptr->ctype == ctype) return ptr;
    ....

(remembering that the increment value of a pointer in C is equal to the
size of its type).  This involves a simple addition -- no array
computations -- which is just about as fast as address chain following.
Sure, there are probably a couple more machine cycles involved, and you do
need the counter as well, but, heck, you're talking such minor savings for
a function that will be insignificant compared to all the other things
you'll want to do with the contents of a message.

                           + + + + + + + +


>  [.....]    Changing either of the other two involves allocating new
> memory, copying old data to the new memory and de-allocating the old
> memory.  With a linked list, adding or removing nodes is as simple as
> swapping pointers.  [......]

Dunh hunh?  Changing the SIZE of a piece of data in ANY scheme will involve
allocating memory (and copying, if some of the old data is to be retained
in the new chunk).  Of course in the first scheme -- using a sequential
"IFF" type format -- any such change would mean regenerating the whole
thing, but both the Item and Linked-list approaches have almost exactly the
same overhead.

To make such a change to an entry in a list, you allocate memory for the
new node, copy over any of the old data needed and create the revised data,
modify two node pointers appropriately, and deallocate the old chunk.

To make such a change to an Item, you allocate memory for the new data
block, copy over any of the old data needed and create the revised data,
modify one pointer (in the "Entry" structure) appropriately, and deallocate
the old chunk.

Now, look at those carefully.  Which one wins?

And another minor, but relevant, point.  At some point the server is
(usually!) going to reply the message, and the client is going to want to
know what happened to the stuff it sent over.  If some of it was simply
snipped out of a linked list, it is just gone, with no record.  On the
other hand in our protocol an Item's pointer is set to NULL if its data is
removed (or taken over by the server).  (If it is simply altered, things
are different of course; we may want flags in the status word to indicate
such happenings.)

                           + + + + + + + +

Listen, I think linked lists are great, too.  I use them everywhere.  But
no one construct is right for everything.  I'll try to select the best one
for the job, taking ALL the relevant factors into account.  (I even
actually descended to using a "goto" today [...My GOD, How will I ever hold
my head up again...?].)

                                                    -- Pete --

BTW -- I'm moving my future postings on IPC over to the *official*
comp.sys.amiga.tech (cross-posting days are done!).  I hope everyone can
now join me there...?