 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 14.03.2012 17:07, schrieb Invisible:
>>> You seem to suggest that there's 16 bytes of overhead /per object/. I'm
>>> saying I'm used to there being a fixed number of bytes of overhead,
>>> regardless of the number of objects. That's O(N) vs O(1).
>>
>> That's obviously impossible. The only way to achieve that would be
>> to allocate an array of objects (by value).
>>
>> If you allocate individual objects, the allocator has to know where they
>> are and if those memory blocks are free or not. At least if the allocator
>> ever wants to reuse freed memory blocks.
>
> If you're using garbage collection, it's quite possible - and, indeed,
> usual. Each time the GC collects the garbage, it also defragments the
> free space. You therefore need only store a pointer to the next free
> byte of memory. To allocate, just increment this pointer by the size of
> the block allocated. Allocation is now O(1) in time and space.
So far, so good. But how does the GC know how long each chunk of
garbage-to-collect is?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> If you're using garbage collection, it's quite possible - and, indeed,
>> usual. Each time the GC collects the garbage, it also defragments the
>> free space. You therefore need only store a pointer to the next free
>> byte of memory. To allocate, just increment this pointer by the size of
>> the block allocated. Allocation is now O(1) in time and space.
>
> So far, so good. But how does the GC know how long each chunk of
> garbage-to-collect is?
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. It also usually
needs access to each thread's stack, to see what local variables are
pointing to objects. And so on and so forth. There's a /reason/ why it's
usually hard-coded into the language run-time system rather than being
an add-on library.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 14.03.2012 17:29, schrieb Invisible:
>>> If you're using garbage collection, it's quite possible - and, indeed,
>>> usual. Each time the GC collects the garbage, it also defragments the
>>> free space. You therefore need only store a pointer to the next free
>>> byte of memory. To allocate, just increment this pointer by the size of
>>> the block allocated. Allocation is now O(1) in time and space.
>>
>> So far, so good. But how does the GC know how long each chunk of
>> garbage-to-collect is?
>
> 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. It also usually
> needs access to each thread's stack, to see what local variables are
> pointing to objects. And so on and so forth. There's a /reason/ why it's
> usually hard-coded into the language run-time system rather than being
> an add-on library.
You didn't quite /exactly/ answer my question :-P
My point here being that without any per-object memory overhead in
addition to the raw data, you can't do any dynamic memory management at
all. Whether that overhead is accounted for in the language run-time or
an added library is quite irrelevant in that respect.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> So far, so good. But how does the GC know how long each chunk of
>>> garbage-to-collect is?
>>
>> 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. It also usually
>> needs access to each thread's stack, to see what local variables are
>> pointing to objects. And so on and so forth. There's a /reason/ why it's
>> usually hard-coded into the language run-time system rather than being
>> an add-on library.
>
> You didn't quite /exactly/ answer my question :-P
>
> My point here being that without any per-object memory overhead in
> addition to the raw data, you can't do any dynamic memory management at
> all. Whether that overhead is accounted for in the language run-time or
> an added library is quite irrelevant in that respect.
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...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
clipka <ano### [at] anonymousorg> wrote:
> Am 14.03.2012 16:52, schrieb Warp:
> > clipka<ano### [at] anonymousorg> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
