On Tue, Jul 15, 2014 at 09:11:23PM +0000, John Colvin via Digitalmars-d wrote: > On Tuesday, 15 July 2014 at 20:03:15 UTC, Chris wrote: > >On Monday, 14 July 2014 at 23:43:57 UTC, H. S. Teoh via Digitalmars-d > >wrote: [...] > >>http://bartoszmilewski.com/2013/09/19/edward-chands/ > >> > >> > > > >From the link above: > > > >"It’s a common but false belief that reference counting (using shared > >pointers in particular) is better than garbage collection. There is > >actual research* showing that the two approaches are just two sides > >of the same coin. You should realize that deleting a shared pointer > >may lead to an arbitrary long pause in program execution, with > >similar performance characteristics as a garbage sweep. It’s not only > >because every serious reference counting algorithm must be able to > >deal with cycles, but also because every time a reference count goes > >to zero on a piece of data a whole graph of pointers reachable from > >that object has to be traversed. A data structure built with shared > >pointers might take a long time to delete and, except for simple > >cases, you’ll never know which shared pointer will go out of scope > >last and trigger it." > > > >* http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf > > I've been wondering about this. Could the following argument be true? > > Situations where automatic memory management are necessary are, by > definition, the situations where one cannot easily reason about where > memory freeing can occur. Therefore, no automatic memory management > system can be considered practically predictable, unless you didn't* > need it in the first place. > > *strictly speaking
Sounds about right. Which is why you have advice like preallocating everything before a game level (i.e., eliminate the need for memory management during that level), or minimizing GC load by avoiding frequent allocations of small objects (i.e., reduce the amount work that needs to be done by the memory management system), keeping things on stack rather than heap if possible (maximize trivial instances of memory management and minimize non-trivial instances -- can also be viewed as: if you structure your program to correspond with the structure of your memory usage, then memory management has a 1-to-1 correspondence with the control structure of the program itself so it doesn't need to be done as a separate task). Hmm. Now that I come to think of it, it seems that the complexity of memory management arises due to structural mismatch between memory usage and program structure, that is, memory acquisition and release do not correspond 1-to-1 with the call structure of the program. If your program can be structured such that it matches your memory usage pattern exactly, then everything can be stack-allocated, and there is no need for sophisticated memory management schemes. It's when the lifetimes of your memory allocations differ from the lifetime of program units (i.e., functions), that extra work, in the form of memory management algorithms, is needed to compensate for the "impedance mismatch", so to speak. Which suggests the rather interesting idea that perhaps some innovative way of structuring the parts of your program such that each corresponds with the structure (and lifetime) of a particular piece of data, then it should minimize, or maybe completely eliminate, the need for complex memory management! (I have no idea if such a thing exists, though. But it's an interesting thought.) For example, if your code creates a string in one section of a function, which is subsequently consumed by the second section, then by the time the function exits the string is not needed anymore, so you could ostensibly just allocate it on the stack instead of the heap. It's when you need to return the string that things become complicated: because now there's a mismatch between the lifetime of your function and the lifetime of the string. So now you need some way of keeping track of the lifetime of the string, and dispose of it when it's no longer needed. But if your program can be structured such that the allocators of memory and the consumers of memory are always matched together 1-to-1, then you can always allocate only on the stack and no memory will need to persist past the function in which it is allocated. Not sure when such a structuring is possible, or whether it is at all possible to structure arbitrary programs this way, though. Definitely not possible in a stack-only paradigm, I think; but maybe possible (or we can go a little farther) with concurrent paradigms? T -- "A one-question geek test. If you get the joke, you're a geek: Seen on a California license plate on a VW Beetle: 'FEATURE'..." -- Joshua D. Wachs - Natural Intelligence, Inc.