Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!glinda!smith
From: smith@glinda.ctron.com (Larry Smith)
Newsgroups: comp.lang.c++
Subject: Re: fragmentation of free store (Double indirection)
Message-ID: <1403@glinda.ctron.com>
Date: 5 Apr 91 18:13:00 GMT
References: <285@paradim.UUCP> <1986@godzilla.tcs.com> <1398@glinda.ctron.com> <12932@goofy.Apple.COM>
Organization: Cabletron Systems Inc.  Rochester, NH
Lines: 98

In article <12932@goofy.Apple.COM> russell@apple.com (Russell Williams) writes:
>Re double indirection to solve free store fragmentation:; the first level 
>of pointer is often called a Handle or master pointer:

Thanks, I knew that.

>In article <1398@glinda.ctron.com> smith@glinda.ctron.com (Larry Smith) 
>writes:
>> Sadly, few compilers use this mechanism to implement
>> pointers.  C, C++, Pascal, etc all implement pointers as bare addresses. 
> Of
>> course, you can implement the above scheme yourself in C, etc, but then 
>you'll
>> have to dereference twice whereever the pointer is used.  This is why 
>you'll
>> always see things like "WindowRecord^^.HorizSize" in Macintosh Pascal 
>code
>
>First, Apple's MPW C++ and Symantec's Think C for the Mac both implement 
>this.  In MPW C++, classes derived from HandleObject get automatic double 
>indirection.  This is even more attractive in C++ than Pascal because 
>p^^.field in Pascal becomes (*p)->field or (**p).field in C.

The *compilers* do no such thing.  If you have to type (*p)->field then
you are dereferencing the handle yourself.  My point is, it's of scant use
if you have to do it yourself, as the rest of your posting pointed out.
I believe the *compiler* should handle all the ugly details.  When I say:

char *foobar = strdup("The rain in Spain falls mainly in the plain");

I want foobar to have a *handle* to the string.  If the system needs to
compact memory, fine!  Let it do so, whenever it wants.  Later, I want to
be able to say:

printf("%s\n",foobar);

And have the compiler issue the correct double-indirection instructions.

Bottom line: *pointers* should be implemented as *handles*.


>There are several costs of such schemes:
>1. Overhead is added to every object reference.  One workaround is to 
>dereference once before periods of heavy use of the referenced data 
>structure and pass a pointer.  The structure must then be locked against 
>movement and unlocked later.  This is one of the more common Mac 
>programming errors (forgetting to lock a dereferenced Handle).

And, yes, I am quite well aware that this will entail a hit in performance.
I would eagerly sacrifice more performance than this scheme entails to be able
to have a runtime errors like: ERROR - ATTEMPT TO REFER TO PREVIOUSLY FREED
MEMORY rather than having the offending line go ahead and bonk some random
data structure thereby costing me days of debugging agony.  C++ does almost
everything on the heap, it frags like nobody's business and wild pointers can
tromp over data structures at will.  Memory get used but not allocated,
freed and used again, allocated and never freed - even freed but never
allocated.  I'll take a nice clean coredump with a stack trace to the offending
line over a whacked data structure and a program that limps along and THEN
coredumps and points to a perfectly innocent line that has nothing to do with
the problem.

>2. It is difficult to make multiple inheritance work.  MI involves passing 
>around pointers to the middle of an object.  MPW C++ disallows MI for 
>HandleObjects (how would you like pointers represented as a 
><handle>,<offset> pair?).

Implementation detail.  If all pointers *were* handles this would not be a
problem, and, yes, pointers *should* be <handles><version_num> (and <offset>
if appropriate to an implementation).

>3. It is difficult to allocate such objects on the stack.  Since you can 
>take the address of a stack object, you'd have to allocate a dummy handle 
>on the stack for each stack HandleObject to provide the extra level of 
>indirection in case it was needed.  MPW C++ disallows stack allocation of 
>HandleObjects.

Again, it's the *distinction* between pointers and handles that causes the
problem.  If pointers were *implemented* as handles none of that would be
visible to the programmer.

>In sum, double indirection is a useful tool but not a panacea.  Many Mac 
>programmers long for the free and easy (as it were) memory usage style of 
>a virtual, directly addressed heap, but the handle-based heap does allow 
>Mac programs to run in a much more constrained memory environment.

It is not a panacea (you spell good for a programmer) but it is *far* better
than what we are dealing with now.  As for the "free and easy" virtually
addressed heap - THAT'S WHAT I GOT NOW AND IT'S KILLING ME WITH BUGS!  (I
work on a SPARC). Fragged heaps are a pain in the butt no matter whether
your heap is virtual or not, very large address spaces merely delay the
inevitable day when the system has enough memory but not all in one spot,
and it does NOTHING to help find dangling or wild pointers.

>*** Disclaimer: I do not represent Apple's official position on anything ***
*** Disclaimer: I do not represent Cabletron's official position on anything ***

Larry Smith
smith@ctron.com