gross@umiami.ir.miami.edu (Mondo) (01/23/91)
Okay folks, here's yer big chance to solve a silly little argument for
three of us novice Mac programmers.
If you want to create a linked list, do you have to:
a) Use a handle to the head node only and use pointers
for the rest of the list (Problem we see: the Memory
Manager will compact the heap and make all those ptrs invalid.)
or
b) Use linked handles for every node in the list.
Please help us. Thanks.
--
Jason Gross Comp Sci Ugrad University of Miami Class of '91 (?)
===========================================================================
Hey, wanna save the world? | Got sumtin' to say? gross@umiami.bitnet
Nuke a Godless, Communist, | Pick and choose! gross@umiami.ir.miami.edu
gay whale for Christ. | gross@miavax.ir.miami.edu
- Anonymous | jgross@umbio.med.miami.edu
===========================================================================
The University of Miami has a lovely fountain. rg2c+@andrew.cmu.edu (Robert Nelson Gasch) (01/24/91)
On 23-Jan-91 in Linked Lists: Handles or Po.. user Mondo@umiami.ir.miami.ed writes: >Okay folks, here's yer big chance to solve a silly little argument for >three of us novice Mac programmers. > >If you want to create a linked list, do you have to: > > a) Use a handle to the head node only and use pointers > for the rest of the list (Problem we see: the Memory > Manager will compact the heap and make all those ptrs invalid.) > > or > > b) Use linked handles for every node in the list. > >Please help us. Thanks. I'm no expert on the subject, but here's my response: I'm not sure what the problem is. I Started programming in C a year ago and translated my linked list routines from Pascal without any problems. They use pointers only, no handles. If there's an issue of Mac programming I'm missing, please alert me, but I don't see any reason why a linked list should have to use handles. Even the head you can just malloc() and free(), so I see nothing that would require the use of handles. --Rob
rcbaab@rw8.urc.tue.nl (Annard Brouwer) (01/24/91)
rg2c+@andrew.cmu.edu (Robert Nelson Gasch) writes: >user Mondo@umiami.ir.miami.ed writes: >>If you want to create a linked list, do you have to: >> a) Use a handle to the head node only and use pointers >> for the rest of the list (Problem we see: the Memory >> Manager will compact the heap and make all those ptrs invalid.) >> or >> ... >I'm no expert on the subject, but here's my response: >I'm not sure what the problem is. I Started programming in C a year ago >and translated my linked list routines from Pascal without any problems. >They use pointers only, no handles. If there's an issue of Mac programming >I'm missing, please alert me, but I don't see any reason why a linked list >should have to use handles. Even the head you can just malloc() and free(), >so I see nothing that would require the use of handles. It's quite simple, depending on the size of your linked list the speedup you get by using handles is significant, plus the memory manager can move smaller clumps of memory around which might help you when memory is getting tight. It's not that difficult to do but please do not use calls like MoveHHi() and HLock() and HUnlock(). They have given me lot's of problems and so I don't use them anymore... Good luck! Annard. -- | Annard Brouwer Bitnet : rcgbbaab@heitue51 | Dreef 74 UUCP : rcbaab@urc.tue.nl | NL-5504 LD Veldhoven packet-radio : pe1koo@pi8mid | The Netherlands [44.137.28.6]
d88-jwa@aswad.nada.kth.se (Jon W{tte) (01/24/91)
In article <1991Jan23.002212.7648@umiami.ir.miami.edu> gross@umiami.ir.miami.edu (Mondo) writes: >Okay folks, here's yer big chance to solve a silly little argument for >three of us novice Mac programmers. > a) Use a handle to the head node only and use pointers > for the rest of the list (Problem we see: the Memory > Manager will compact the heap and make all those ptrs invalid.) You could allocate with NewPtr. The problem is that this fragments the heap and is SLOOOOW due to a memory mgr bug in the IIfx and ci. > b) Use linked handles for every node in the list. Yup ! Or, if the list is "small", a handle containing all the elements, that you just resize... Jon W{tte, Stockholm, Sweden, h+@nada.kth.se :: This article is fake. If you take it for real, the _REAL_ :: Jon W{tte will sue you for slander. So there ! Nyah ! :-)
d88-jwa@aswad.nada.kth.se (Jon W{tte) (01/24/91)
In article <.664719435@rw8.urc.tue.nl> rcbaab@urc.tue.nl writes: >>I'm no expert on the subject, but here's my response: >It's not that difficult to do but please do not use calls like MoveHHi() and >HLock() and HUnlock(). They have given me lot's of problems and so I don't >use them anymore... Remind me not to use your programs... If you use a dereferenced handle (like, pass it to the ToolBox) you'll have to lock it. If you lock a handle, it's nice to do it at the top of the heap. Thus: char state ; state = HGetState ( handle ) ; MoveHHi ( handle ) ; HLock ( handle ) ; DoSomething ( * handle ) ; HSetState ( handle , state ) ; This is the recommended way of doing it. h+ Jon W{tte, Stockholm, Sweden, h+@nada.kth.se :: This article is fake. If you take it for real, the _REAL_ :: Jon W{tte will sue you for slander. So there ! Nyah ! :-)
mneerach@iiic.ethz.ch (Matthias Ulrich Neeracher) (01/25/91)
In article <1991Jan24.145729.12853@nada.kth.se>, d88-jwa@aswad.nada.kth.se (Jon W{tte) writes: > If you use a dereferenced handle (like, pass it to the ToolBox) > you'll have to lock it. Absolutely. > If you lock a handle, it's nice to do it > at the top of the heap. Only if you are going to lock it for a certain time and across many memory allocating calls. MoveHHi() certainly doesn't influence the *correctness* of your program, but indiscriminate use can hurt *performance* terribly. Matthias ----- Matthias Neeracher mneerach@iiic.ethz.ch "These days, though, you have to be pretty technical before you can even aspire to crudeness." -- William Gibson, _Johnny Mnemonic_
ml27192@uxa.cso.uiuc.edu (lanett mark) (01/25/91)
gross@umiami.ir.miami.edu (Mondo) writes: >Okay folks, here's yer big chance to solve a silly little argument for >three of us novice Mac programmers. >If you want to create a linked list, do you have to: > a) Use a handle to the head node only and use pointers > for the rest of the list (Problem we see: the Memory > Manager will compact the heap and make all those ptrs invalid.) If you use pointers and allocate structures with new then they are "locked" and will not be moved by the memory manager. Handles are for your memory conveniece only. Mark Lanett
keith@Apple.COM (Keith Rollin) (01/25/91)
In article <1991Jan24.145729.12853@nada.kth.se> d88-jwa@aswad.nada.kth.se (Jon W{tte) writes: >In article <.664719435@rw8.urc.tue.nl> rcbaab@urc.tue.nl writes: > >If you use a dereferenced handle (like, pass it to the ToolBox) >you'll have to lock it. If you lock a handle, it's nice to do it >at the top of the heap. Thus: > > char state ; > > state = HGetState ( handle ) ; > MoveHHi ( handle ) ; > HLock ( handle ) ; > DoSomething ( * handle ) ; > HSetState ( handle , state ) ; > >This is the recommended way of doing it. For elaborate cases, where the stuff between HLock and HSetState can be quite lengthy or allocate non-relocatable blocks, I'd agree. But for small cases, doing the MoveHHi is not worth it. MoveHHi is an expensive call in terms of time, so you don't want to call it blindly. MacApp includes a procedure called LockHandleHigh that does all of the setup for you. In MacApp 3.0, which will return the old state for you, the above would look like this: state = LockHandleHigh(handle); DoSomething(*handle); HSetState(handle, state); -- ------------------------------------------------------------------------------ Keith Rollin --- Apple Computer, Inc. --- Developer Technical Support INTERNET: keith@apple.com UUCP: {decwrl, hoptoad, nsc, sun, amdahl}!apple!keith "Argue for your Apple, and sure enough, it's yours" - Keith Rollin, Contusions
hawley@adobe.COM (Steve Hawley) (01/26/91)
In article <.664719435@rw8.urc.tue.nl> rcbaab@urc.tue.nl writes: >It's not that difficult to do but please do not use calls like MoveHHi() and >HLock() and HUnlock(). They have given me lot's of problems and so I don't >use them anymore... Ooh - bad advice. This means that you have to double dereference the handle to your data structure every time you use it in conjunction with a Toolbox call that may move memory. That is going to slow you down a whole lot. See, the cool thing about linked lists is that the data in the links can be accessed relatively quickly on most processors because of offset addressing modes. This means that something like register thing *p; p->foo = 0; will compile to something like: clr.w xx(a2) /* where xx is the offset of foo */ or, if you don't get the register: move.l p,a0 clr.w xx(a0) if you have register thing **p; (**p).foo = 0; you'll get this: move.l (a2),a0 clr.w xx(a0) So, best case, you're still going to be as bad as the WORST case for simple pointers. So ideally, you'd want to do this: register thing *p; thing **h; p = *h; p->foo = 0; /* etc etc */ So this gets you the best of both worlds: moveable memory and fast access. Being an intrepid programmer, you decide that you do the following: typedef struct thing { short count, frobnotz, fibblebean; struct thing **next; } thing *thingptr, **thinghandle; thinghandle MakeThingList() { thinghandle h, head; register thingptr p; Boolean notdone = false; head = h = (thinghandle)Newhandle((long)sizeof(thing)); p = *h; p->count = -1; /* signal the head */ while (notdone) { p->frobnotz = FinkNottle(); p->fibblebean = FeldWrent(); notdone = AmIdone(); if (notdone) { p->next = (thinghandle)NewHandle((long)sizeof(thing)); h = p->next; p = *h; /* Here's the trouble. At this point, p is a stale pointer. * h could have moved during NewHandle(), so p may or may not * actually point to a valid data structure. This is an * easy mistake to make, and may go undetected FOR A LONG * TIME. * This can be solved by: * 1) Keeping h locked until we're done with the handle. * 2) HLocking h before any call that may move memory, and * unlocking it later * 3) reassigning p after every call that may move memory */ } } return(head); } Solution 1 has a trade-off: it is possible that your handle is causing heap fragmentation that prevents an allocation from happening. In other words, there may be a situation where there is enough memory to complete a task, but it is inaccessible because your handle is in the way. The good news about this method is that is the least prone to human error of the three, and probably the most efficient in terms of cycles. Solution 2 and 3 will work, but are tedious and prone to much more insidious problems. Suppose you're not responsible for maintaining FinkNottle(), and your boss goes to the person who is and says, "Gee, FinkNottle() is really slow. Since you can't speed it up, why not put up a window that has a picture of a guy tapping his foot." Oh no! That means that FinkNottle() may move memory as well. What if FinkNottle() itself doen't move memory, but the function Nitfol() that gets called by WinkleBlat() that gets called by FeldSpar() that gets called by FinkNottle() does. You see the problem. Program defensively. Steve Hawley hawley@adobe.com -- "Did you know that a cow was *MURDERED* to make that jacket?" "Yes. I didn't think there were any witnesses, so I guess I'll have to kill you too." -Jake Johansen
n67786@lehtori.tut.fi (Nieminen Tero) (01/27/91)
In article <1991Jan24.203150.24546@ux1.cso.uiuc.edu> ml27192@uxa.cso.uiuc.edu (lanett mark) writes: gross@umiami.ir.miami.edu (Mondo) writes: >Okay folks, here's yer big chance to solve a silly little argument for >three of us novice Mac programmers. >If you want to create a linked list, do you have to: > a) Use a handle to the head node only and use pointers > for the rest of the list (Problem we see: the Memory > Manager will compact the heap and make all those ptrs invalid.) If you use pointers and allocate structures with new then they are "locked" and will not be moved by the memory manager. Handles are for your memory conveniece only. Indeed pointers cannot be moved during program execution an thus they will stay valid all the time. But handles are not only for convinience only! It's wise to remember how jealous the system is when it comes to allocating a pointer. To minimize further heap fragmentation the system pursues all possible means to get the pointer allocated as low in the heap as possible. This also means compacting the memory so that handles are moved upwards to make room for the pointer. And there lies the speed penalty. If you opt for using handles the allocating process is significantly faster and there is less risk of fragmented heap. I remember testing pointer vs. handle allocation speed some time ago and a difference of order 5 to 10 were common. The test allocated several thousand variable size blocks and in case of the handles even locked them at place and dereferenced the handle. Still handles proved to be 5 times faster than pointers. Now that may or may not be significan in your program, but I'd advice making tests before deciding if in doubt. Mark Lanett -- Tero Nieminen Tampere University of Technology n67786@cc.tut.fi Tampere, Finland, Europe
stay@ohs.uucp (Steve Taylor) (01/27/91)
In article <Mbbb8a_00Uh_I4wpkg@andrew.cmu.edu>, rg2c+@andrew.cmu.edu (Robert Nelson Gasch) writes: > I'm no expert on the subject, but here's my response: > I'm not sure what the problem is. I Started programming in C a year ago > and translated my linked list routines from Pascal without any problems. > They use pointers only, no handles. If there's an issue of Mac programming > I'm missing, please alert me, but I don't see any reason why a linked list > should have to use handles. Even the head you can just malloc() and free(), > so I see nothing that would require the use of handles. > > --Rob The quick answer (and I'm sure you'll have many) is that handles *aren't* required. However, pointers compact and fragment the heap. See Scott Knaster's book "How To Write Macintosh Software" and IM II p36. While we're on the subject, how does the world look on this idea: typedef struct { int id; int score; ... } OneUnit; typedef OneUnit UnitList[1]; typedef UnitList **UnitLHandle; ... UnitLHandle aHandle; aHandle = NewHandle(initialSize); Using the amazing flexibility of C, we can access the array (**aHandle)[] at any point we want, [e.g. (**aHandle)[8].id = 1234] and it's completely dynamic, because we can always SetHandleSize(aHandle, newsize); From my experience, these are the advantages: All the advantages of arrays (greatly improved access speed, (which is no small advantage when you're going through an entire list for one element) access to qsort(), fewer stray pointers, no "following" pointers for finding and deleting elements, etc.) Saved space (4 bytes for every "next" field in a linked list, 8 bytes for every "next" and "prev" in a doubly-linked list) Dynamic to whatever extent we want. Disadvantages: It can be a very large block to have lying around in memory, relocateable or not. moves and deletes are (naturally) relatively slow, but BlockMove works nicely and (in my case) most of the time the user is looking, not changing or deleting. (Yes, this WAS supposed to be the disadvantage section.) So, what do you all think? Should I be cowering in a corner? ------------------------------------------------------------------------------- Life is the dress-rehearsal for Hell. Steven H. Taylor ohs!stay@iconsys.icon.com trACE(tm) Development
rcbaab@rwa.urc.tue.nl (Annard Brouwer) (01/28/91)
d88-jwa@aswad.nada.kth.se (Jon W{tte) writes: >In article <.664719435@rw8.urc.tue.nl> rcbaab@urc.tue.nl writes: >>It's not that difficult to do but please do not use calls like MoveHHi() and >>HLock() and HUnlock(). They have given me lot's of problems and so I don't >>use them anymore... >Remind me not to use your programs... Sure thing, I'll mention it in my about box :-)) >If you use a dereferenced handle (like, pass it to the ToolBox) >you'll have to lock it. If you lock a handle, it's nice to do it >at the top of the heap. Thus: > ... >This is the recommended way of doing it. I'd rather use something like: var BigBlah:HandleType; procedure test; var blah: HandleType; begin blah:=BigBlah; "now I can do whatever I like with whatever toolbox call I would like to use..." BigBlah:=blah; end; Ready, and I don't have to use those ^*&%$@##$ calls like MoveHHi etcx etc... This is also a recommended way of doing it! Good luck. Annard -- | Annard Brouwer Bitnet : rcgbbaab@heitue51 | Dreef 74 UUCP : rcbaab@urc.tue.nl | NL-5504 LD Veldhoven packet-radio : pe1koo@pi8mid | The Netherlands [44.137.28.6]
cfry@jove.cs.pdx.edu (Chall Fry) (01/28/91)
In article <1991Jan23.002212.7648@umiami.ir.miami.edu> gross@umiami.ir.miami.edu (Mondo) writes: If you want to create a linked list, do you have to: a) Use a handle to the head node only and use pointers for the rest of the list (Problem we see: the Memory Manager will compact the heap and make all those ptrs invalid.) or b) Use linked handles for every node in the list. (** Naming conventions for this post **) struct link { some_type data; link * or ** next; } * or ** head, * or ** p; So far there's been all sorts of good advice in this thread. No one yet, however, has advocated my personal favorite memory allocation algorithm: char *ptr = Random () * Random (); /* Look Ma, no handles! */ (I'd include *lots* of smilies, but I can't draw to save my life) Really, I can think of four decent data structures for managing a linklist on the Mac. Your choice a) seems to be flawed, at least in your wording. Having a handle to the head node and pointers for the body of the list seems pretty pointless. Either you mean for head to point to a handle sized to one link only, which makes the head relocatable but the rest of the list will be created with NewPtr, and a bunch of small nonrelocatable blocks being created and deleted all the time is the sort of thing that turns heaps into abysmal messes. BTW, if you're using malloc () to allocate your pointers, you're using NewPtr (Think C, alloc.c). In this case, having the head relocatable does very little to improve heap usage. The other interpretation is that you want head to be a handle large enough to hold the entire list, and use your own memory management scheme to add and delete links using space within the handle. This will work, but if you use pointers in your link.next fields, you can't ever move the block around, and again, you might as well make it a pointer to begin with as make it a handle and keep it locked all the time. The other choice you mention, using handles for every link, would be good for a list without many links, or if you were making a list of structures which were already handles (region and Picture handles come to mind). However, though I haven't run any tests, I'd think the Memory Manager might get bogged down if it had compact a large (5-10 thousand?) number of small blocks very often. Allocating a large block of memory with NewPtr and subletting using your own routines really isn't a bad method, particularly if your use SetPtrSize in your allocation function to grow and shrink your memory block as your list grows and shrinks (Don't use on every call.) However, if you allocated p as a large relocatable NewHandle block, and made your link.next fields integer offsets into p, you could get some of both worlds. I believe the 68030 at least has an addressing mode which allows double indirection with displacement in one instruction. (Memory Indirect [pre][post]indexed mode--will Think and MPW generate this mode?) Or, you can lock the handle and derefence it, which should execute searches pretty fast. Either way, your handle can be unlocked when not in use, and heap compaction won't require any pointer updating. It'll pack efficiently (everything's relocatable), and quickly (there's only one block). Only real problem is that you need your own link allocation code (and it can't call malloc or NewPtr). Not that I still don't prefer my Random () method, for the sheer adventure of it. --Chall Fry cfry@jove.cs.pdx.edu "Chall, 'nifty' I can deal with, but 'goshums' is just too much." -Anastasia
d88-jwa@dront.nada.kth.se (Jon W{tte) (01/29/91)
In article <rcbaab.665051952@rwa.urc.tue.nl> rcbaab@urc.tue.nl writes: >I'd rather use something like: >var BigBlah:HandleType; >procedure test; >var blah: HandleType; Shouldn't this be blah:Type ? > blah:=BigBlah; > BigBlah:=blah; And here, blah := BigBlah^^ ; BigBlah^^ := blah ; >This is also a recommended way of doing it! Not your way, certainly... h+ Jon W{tte, Stockholm, Sweden, h+@nada.kth.se :: This article is fake. If you take it for real, the _REAL_ :: Jon W{tte will sue you for slander. So there ! Nyah ! :-)
mneerach@iiic.ethz.ch (Matthias Ulrich Neeracher) (01/29/91)
In article <rcbaab.665051952@rwa.urc.tue.nl>, rcbaab@rwa.urc.tue.nl (Annard Brouwer) writes: > I'd rather use something like: > var BigBlah:HandleType; > > procedure test; > var blah: HandleType; > > begin > blah:=BigBlah; But then you can leave out the copy altogether. It won't change anything. > "now I can do whatever I like with whatever toolbox call I would like > to use..." > BigBlah:=blah; > end; Matthias ----- Matthias Neeracher mneerach@iiic.ethz.ch "These days, though, you have to be pretty technical before you can even aspire to crudeness." -- William Gibson, _Johnny Mnemonic_
resnick@cogsci.uiuc.edu (Pete Resnick) (01/29/91)
rcbaab@rwa.urc.tue.nl (Annard Brouwer) writes:
[ jibberish about the virtues of *not* using HLock, HUnlock, or MoveHHi...]
Annard, I don't know what you are trying to do, but you have totally
missed the point.
If you are really using a Handle (you refer to a HandleType in your
psuedo-code), it *must* be locked for some of the toolbox routines.
If you are implying that your's is always locked, or that your are
declaring a record or structure of some sort to hold the handle info,
or are allocating pointers instead of handles in the heap, you are
being a memory hog and causing fragmentation. Anyway way you go, you
are doing this improperly for all except the smallest programs.
It sounds like you got all in a huff for someone telling you that
you were wrong, when you were in fact either wrong or just plain
not understanding the original question.
I hope the new programmers who were looking for answers to questions
about memory allocation do not listen to this information. It is
just misguided.
pr
--
Pete Resnick (...so what is a mojo, and why would one be rising?)
Graduate assistant - Philosophy Department, Gregory Hall, UIUC
System manager - Cognitive Science Group, Beckman Institute, UIUC
Internet/ARPAnet/EDUnet : resnick@cogsci.uiuc.edu
BITNET (if no other way) : FREE0285@UIUCVMDJim.Spencer@p510.f22.n282.z1.mmug.edgar.mn.org (Jim Spencer) (01/30/91)
Annard Brouwer writes in a message to All AB> procedure test; AB> var blah: HandleType; AB> begin AB> blah:=BigBlah; AB> "now I can do whatever I like with whatever AB> toolbox call I would like to use..." AB> BigBlah:=blah; AB> end; AB> Ready, and I don't have to use those ^*&%$@##$ calls like MoveHHi AB> etcx etc... This is also a recommended way of doing it! I must be missing something: how does this in anyway help you in locking down your handles or in moving them high before you do so? Yea, you've created a variable in high global memory to hold the handle but that in turn is going to reference a master pointer (hopefully at the bottom of the Application heap because you've used sufficient calls to MoreMasters) which will actually point to your relocatable block which will be wherever the Memory Manager created it. If you don't move it high (the block, NOT the handle) you will create islands when you lock it. And if you don't lock it and the memory manager moves it when you do your toolbox call that can move memory (keeping in mind that the Memory manager controls it, NOT YOU, unless you lock it) your BigBlah will be exactly that: Blah. Crash and burn time folks. Can you say "dangling pointer?" -- Jim Spencer - via The Minnesota Macintosh Users Group UUCP-Fido Gateway UUCP: ...uunet!tcnet!kksys!edgar!mmug!22.510!Jim.Spencer INET: Jim.Spencer@p510.f22.n282.z1.mmug.edgar.mn.org