shf@well.UUCP (Stuart H. Ferguson) (04/27/88)
Article 18883 of comp.sys.amiga: In some other article, Pete Goodeve exclaims: > Oh oh! Looks like the blind men have their fingers on the elephant again... ... > 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. I may have inadvertantly stepped on some sensitive toes as well. I'm not "totally ignoring" recent discussions -- if I did that, I wouldn't have said *anything* about the Pete/Peter message format. Quite the contrary, the process of demonstrating a "minor supposed disadvantage" is known, at least where I come from, as "Design Review." My intention was not to berate or belittle the design, but was rather to see how well it stands up to close examination. Pete does go on to defend the message format well in light of my complaints. > 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. Good starting place. > 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. The variable sized array does have the advantage of random access. That's not the olny way to get positionally defined fields, but its a resaonable one. It doesn't make sense, however, to use IDs on fixed fields as a "validity check." Either the user put the right data in the right place or not and requiring that he set the ID values correctly buys you nothing. I don't know why Pete should say it's "better" to send multiple short messages than one long, more complex one, however. I also don't know why he should say that an "average" message won't have an arbitrary series of items. These seem like a tradeoffs best decided by the user of the IPC system, not by the definition of the standard. > 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? There's also nothing preventing a node in a linked list from containing pointers to data memory. A linked list node can be any length and can therefore contain pointers as well as other data. An Entry item on the other hand is always just one pointer. If you wanted to store five bytes of data as an Entry, you would have to separately allocate five bytes for the data and point an Entry at it. To do the same thing with a linked list, you could allocate the node structure (comperable to an Entry structure) plus five bytes in the same structure and link this node into the list. Now which is more compact? ---- Pete showed the code I gave for finding an entry and compares it with how he would do it. > 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. You're right. In many respects, including the function I used as example, the two methods are really not that different in terms of efficiency and hassle for the programmer. I'll pick better examples this time. >> [.....] 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). ... >both the Item and Linked-list approaches have almost exactly the >same overhead. Here Pete has completely missed the main point of my previous article. Arrays and linked lists do NOT have the same overhead when it comes to changing them -- arrays can be MUCH HARDER to change than linked lists. Picture if you will an Entry array with 100 elements. Now suppose you want to _ADD_ one more Entry. You will need to allocate an array with 101 elements, copy the first 100 elements from the old array into the new one and deallocate the old array. What you end up with is a new array exactly like the old one except that the new one has space for the new Entry you wanted to add. Now you can attach your new Entry. Now picture a linked list with 100 nodes. To add something to this structure, you allocate ONE new node and link it in. > Now, look at those carefully. Which one wins? My point exactly. > 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. ... [You can tell when an Entry item has been removed but not a list node] > ... (If it is simply altered, things > are different of course; we may want flags in the status word to indicate > such happenings.) You'd probably want flags in the status word to indicate when data was taken over too, since you would want it more explicit than the implied "if the pointer's null, I took it" idea. This works fine for a server taking data FROM a client, but what about when the server returns data TO the client? Since Entry arrays are so hard to EXTEND, does the server need to use another mechanism to get arbitrary ammounts of data back to the client? Why the asymmetry? >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. There are advantages and limitations to both approaches, and I can see why the array concept is appealing. I like the idea of being able to mix fixed field data and ID tagged data together in the same construct (you can mix them using a linked list too, but somehow it's not as obvious). I'm harping on what I see to be limitations in the approach simply so they don't become a headache in the future. >(I even >actually descended to using a "goto" today [...My GOD, How will I ever hold >my head up again...?].) > -- Pete -- Well, I guess that's it on your credibility ... ;-) -- Stuart Ferguson (shf@well.UUCP) Action by HAVOC (shf@Solar.Stanford.EDU)
pete@violet.berkeley.edu (Pete Goodeve) (04/28/88)
In article <5819@well.UUCP> Stuart Ferguson writes: > In some other article, Pete Goodeve exclaims: > > Oh oh! Looks like the blind men have their fingers on the elephant again... > ... > > 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. > > I may have inadvertantly stepped on some sensitive toes as well. I'm > not "totally ignoring" recent discussions -- if I did that, I wouldn't > have said *anything* about the Pete/Peter message format. Quite the > contrary, the process of demonstrating a "minor supposed disadvantage" > is known, at least where I come from, as "Design Review." My intention > was not to berate or belittle the design, but was rather to see how well > it stands up to close examination. Point taken. Sorry if I was getting shirty, but I'm beginning to feel that I'm spending a lot of time going round in circles on this subject, and I just felt (and still feel) that the List option is not appropriate in this case. Anyhow, back to the review... > > 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 > [.....] It doesn't make sense, however, to use IDs on fixed > fields as a "validity check." Either the user put the right data in the > right place or not and requiring that he set the ID values correctly > buys you nothing. Yes, but he might have made a mistake, and the point of the InterPeterMessage is that the server can detect this and reject the Item (or more probably the whole message) without any disasters happening. If it doesn't check, it could happily cause a crash by using or writing inappropriate data. Also note my point about variant fields; for example a given message might always have two fields -- the first of fixed ID, say 'CMND', pointing to an action request string perhaps, and the second pointing to data which could be one of several types (background bitmap or brush, maybe); the server can detect from the ID itself how it is expected to apply the command to the data. > > I don't know why Pete should say it's "better" to send multiple short > messages than one long, more complex one, however. I also don't know > why he should say that an "average" message won't have an arbitrary > series of items. These seem like a tradeoffs best decided by the user > of the IPC system, not by the definition of the standard. I guess this is just where my fingers are on the elephant...(:-)) It just seems to me that if a client has to string a lot of distinct items together for service, they are likely to have been generated separately, and it might as well send each as a separate message to the server, which can handle and reply them in turn. As a concrete example, think of a set of file names that a client wants a server to process. Sure it could send all the names in one message, but why not be modular and send one message for each file? Then the client would know when the server had finished with each one because it would get the reply. As you say, it's a local decision in the final analysis, but if we're to avoid Babel we ought at least to have "preferred" protocols. > > There's also nothing preventing a node in a linked list from containing > pointers to data memory. A linked list node can be any length and can > therefore contain pointers as well as other data. An Entry item on the > other hand is always just one pointer. If you wanted to store five > bytes of data as an Entry, you would have to separately allocate five > bytes for the data and point an Entry at it. To do the same thing with > a linked list, you could allocate the node structure (comperable to an > Entry structure) plus five bytes in the same structure and link this > node into the list. Now which is more compact? But isn't this once again the Royal Road to Chaos? One of the design goals (!) of the IPCMessage was that an "ignorant" server could for instance pass most items down a network, and would know which ones it couldn't, without needing any idea of the contents. If a list node can contain "anything" we come bang up against my main objection to AREXX -- that its pointers can also contain "anything", so every process has to know "everything". What's a poor dumb server to do? > > > >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). ... > >both the Item and Linked-list approaches have almost exactly the > >same overhead. > > Here Pete has completely missed the main point of my previous article. > Arrays and linked lists do NOT have the same overhead when it comes to > changing them -- arrays can be MUCH HARDER to change than linked lists. [Stuart then compares changing the number of items in a 100 element array with a 100 element list.] I think maybe once again the disagreement arises from basic assumptions. I'm making the major assumption that the message block structure itself will not -- let's make that "MUST not" -- be changed in any significant way between original transmission and reply. In particular, the NUMBER of items won't change, so we have no problem of insertion in a linear sequence. The data may be changed, but in the message itself only item pointers and flags will be altered by the server. The client must include in the original message any item fields it expects back from the server. Yes this is a Restriction On Freedom, but that's really another way of saying "Standard", and I don't think that it will preclude anything we might want to do. As I say, if a particular situation really DOES NEED a list, just define a 'LIST' item ID, and hang one on; you might have problems trying to send it down a network, and an Ignorant Server would probably have to reject it, but... [Query to Peter: would the ii_Size be zero for a 'LIST'?! I think so.] > > You'd probably want flags in the status word to indicate when data was > taken over too, since you would want it more explicit than the implied > "if the pointer's null, I took it" idea. Funny. Peter made the same point in another posting, and I incorporated, quite independently, just such a flag in my latest (not yet posted) version of the IPCMessage definition. Must be important! (:-)) > > This works fine for a server taking data FROM a client, but what about > when the server returns data TO the client? Since Entry arrays are so > hard to EXTEND, does the server need to use another mechanism to get > arbitrary ammounts of data back to the client? Why the asymmetry? See the paragraphs above. I consider the client as REQUESTING stuff from the server, so it should know what it wants beforehand. If the server IS going to "volunteer" a lot of information, the client can always give it a port of its own to send all its goodies to (thus removing the asymmetry). > [.....] I'm harping on what I see to be limitations in the approach > simply so they don't become a headache in the future. Yes, you're right. That sort of criticism is needed. It's just that by now I've fairly well satisfied myself (and some others, I hope!) that we have a concept that we can try out. I am now doing so. That's undoubtedly where we'll REALLY start finding the snags. I'll keep you posted. > >(I even actually descended to using a "goto" today [...My GOD, How will I ever hold > >my head up again...?].) > > Well, I guess that's it on your credibility ... ;-) I knew it... I KNEW IT...!! -- Pete --