![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
> The GC engine needs to know quite a bit about the objects it's scanning
> - how big they are, where their pointer fields are, etc.
Exactly how does the GC engine know how large a block of allocated
memory is? Where is this information stored? (You could get close to
this if all objects that the program ever allocated were forced to be
all of the same size. Of course that's unfeasible.)
Also, if objects are transparently movable in memory without breaking
the references pointing to them, that means that in addition to the
reference the actual raw memory address of the object has to also be
stored somewhere. Where is this information stored?
You can't avoid bookkeeping when you are allocating blocks of variable
size.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> Am 14.03.2012 16:52, schrieb Warp:
> > clipka<ano### [at] anonymous org> wrote:
> >> While this is true, it is not a problem specific to reference counting,
> >> but one that is inherent in /any/ attempt at automatic object lifetime
> >> management.
> >
> > It's not a problem for a garbage collector.
> Last time I heard, reference counting /is/ a garbage collection mechanism.
I think you know what I mean.
> > And btw, cyclic references are not the only problematic situation with
> > reference counting. There are cases where objects may be deleted too early,
> > while there's still code using them.
> I can't think of any reason why that could possibly happen, provided
> that the reference counting is implemented in a thread-safe manner.
Module A has a reference-counting smart pointer pointing to an object B.
A member function of that object B calls a function of module A. Said
function of A drops the reference to object B. Since it was the only
reference pointing to it, the object B gets deleted. When the function
in A ends, the execution returns to the member function of B, which now
operates on a deleted object. Undefined behavior ensues.
Yes, that *can* happen.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Am 14.03.2012 17:33, schrieb Kevin Wampler:
> On 3/14/2012 9:14 AM, clipka wrote:
>>> And btw, cyclic references are not the only problematic situation with
>>> reference counting. There are cases where objects may be deleted too
>>> early,
>>> while there's still code using them.
>>
>> I can't think of any reason why that could possibly happen, provided
>> that the reference counting is implemented in a thread-safe manner.
>
> Imagine you've implemented a tree where each node is an object which has
> a "delete" method that removes the node from the tree. If you're not
> careful the node could end up removing all references-counted pointers
> to itself (since "this" isn't reference counted) and be reclaimed while
> still running its own delete method.
It is a problem only as long as you tie object destruction to reclaiming
of memory.
If the memory management is designed to /first/ call the destructor of
the "payload object", and only /afterwards/ decrement the reference
counter and release memory, then I don't see anything you'd have to fear
from this scenario.
Problems may arise of course if you try to implement the reference
counter management functionality in the "payload object" itself. Don't
do that - tie the ref counter management to a dedicated pointer type.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Am 14.03.2012 17:44, schrieb Invisible:
> OK. Well typically each object has some overhead that tells you which
> class it belongs to. Typically the GC engine is going to go off that
> information, so you're arguably not adding any additional cost there.
> Typically each object just gets one pointer wider.
>
> Whether a static allocator can match that or not is open to debate. In
> particular, I'd imagine a static allocator might have O(N) cost per
> /free block/, whereas a typical GC implementation doesn't need to track
> free blocks at all...
If a GC implementation doesn't track free blocks, how is it ever going
to re-allocate them to anything?
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Am 14.03.2012 17:57, schrieb Warp:
>>> And btw, cyclic references are not the only problematic situation with
>>> reference counting. There are cases where objects may be deleted too early,
>>> while there's still code using them.
>
>> I can't think of any reason why that could possibly happen, provided
>> that the reference counting is implemented in a thread-safe manner.
>
> Module A has a reference-counting smart pointer pointing to an object B.
>
> A member function of that object B calls a function of module A. Said
> function of A drops the reference to object B. Since it was the only
> reference pointing to it, the object B gets deleted. When the function
> in A ends, the execution returns to the member function of B, which now
> operates on a deleted object. Undefined behavior ensues.
>
> Yes, that *can* happen.
Hm... you do have a point there.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 3/14/2012 9:58 AM, clipka wrote:
> It is a problem only as long as you tie object destruction to reclaiming
> of memory.
I think I probably just explained it poorly, the example I was imagining
was pretty much identical to what Warp pointed out.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> If a GC implementation doesn't track free blocks, how is it ever going
> to re-allocate them to anything?
A naive implementation of that would be:
- Resolve the location of all used objects by looking for references
to those objects in the program data.
- The size of the objects can be resolved from the reference type and/or
a virtual table pointed by the objects themselves.
- Sort the addresses of the objects.
- Compact all the objects by moving them towards the beginning of the
heap so that no free space is left between them.
- Update the "free memory starts from here" pointer to the end of the
last object relocated this way.
(Of course an actual GC is much, much more complicated than that in
order to make it actually efficient.)
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Am 14.03.2012 18:07, schrieb clipka:
> Am 14.03.2012 17:57, schrieb Warp:
>
>>>> And btw, cyclic references are not the only problematic situation with
>>>> reference counting. There are cases where objects may be deleted too
>>>> early,
>>>> while there's still code using them.
>>
>>> I can't think of any reason why that could possibly happen, provided
>>> that the reference counting is implemented in a thread-safe manner.
>>
>> Module A has a reference-counting smart pointer pointing to an object B.
>>
>> A member function of that object B calls a function of module A. Said
>> function of A drops the reference to object B. Since it was the only
>> reference pointing to it, the object B gets deleted. When the function
>> in A ends, the execution returns to the member function of B, which now
>> operates on a deleted object. Undefined behavior ensues.
>>
>> Yes, that *can* happen.
>
> Hm... you do have a point there.
Then again, how would any other GC prevent this kind of thing happening?
As soon as A drops the reference to B, the latter isn't referenced
anymore, so if at this moment the GC happens to kick in you're still in
for trouble. Except that now your error is even more sporadic in nature
and therefore even more difficult to hunt down.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> > Module A has a reference-counting smart pointer pointing to an object B.
> >
> > A member function of that object B calls a function of module A. Said
> > function of A drops the reference to object B. Since it was the only
> > reference pointing to it, the object B gets deleted. When the function
> > in A ends, the execution returns to the member function of B, which now
> > operates on a deleted object. Undefined behavior ensues.
> >
> > Yes, that *can* happen.
> Hm... you do have a point there.
I learned it the hard way. Yes, it happened to me in an actual project,
and I didn't know of this problem before that.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 3/14/2012 10:12 AM, Warp wrote:
> I learned it the hard way. Yes, it happened to me in an actual project,
> and I didn't know of this problem before that.
Heh, me too. It was quite a perplexing error at first.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |