On Tuesday, 15 July 2014 at 21:57:30 UTC, H. S. Teoh via
Digitalmars-d wrote:
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
This is a rather interesting thought and boils down to the usual
conflict of machine logic not matching program / real world
logic. You mentioned a while ago that one of your teachers said
that programs were often overly complicated, bug and error prone,
because there was a mismatch of data structure and program logic
(which D's ranges try to fix). I find this way of thinking
interesting, because it shows that we are often impeded by the
attitude that we try to please the machine and adapt reality to
how the machine works, rather than trying to adapt the machine to
reality.*
The problem you described above is omnipresent. Objective-C has
autorelease, in plain C programs one has to be careful where and
when to free what, etc. I was wondering after reading your post,
whether it would be possible to have an automatic memory
management system that could help to create a 1-1-match, or if
even the compiler + language features could help to _easily_
achieve that. Maybe the copy approach mentioned earlier points
into that direction.
Anyway, I think you are on to something here. Maybe the solution
is not a hyper-super-waterproof GC algorithm (that will never be
achieved, I guess, in any language), but eliminating the need to
collect the garbage as much as possible.
* I've found that D gives me a lot of freedom in modelling
reality in a way the machine understands. But I've said that
already.
