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] devnull> 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

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

clipka <ano### [at] anonymousorg> 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

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

clipka <ano### [at] anonymousorg> 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

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

clipka <ano### [at] anonymousorg> wrote:
> Then again, how would any other GC prevent this kind of thing happening?

  A GC keeps track of *all* the references that are pointing to an object,
including the 'this' pointer (or whatever the equivalent is in any given
language).

  You could avoid this problem in a reference-counted scenario by
incrementing the reference count in the beginning of the function and
decrementing it when exiting the function, but that's burdensome and
makes member functions less efficient (especially if they are supposed
to be fast).

-- 
                                                          - Warp

Post a reply to this message

Am 14.03.2012 18:09, schrieb Warp:
> clipka<ano### [at] anonymousorg>  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:
> [...]


Well, I wasn't actually considering approaches that would be 
prohibitively inefficient :-P

Post a reply to this message

Am 14.03.2012 18:16, schrieb Warp:
> clipka<ano### [at] anonymousorg>  wrote:
>> Then again, how would any other GC prevent this kind of thing happening?
>
>    A GC keeps track of *all* the references that are pointing to an object,
> including the 'this' pointer (or whatever the equivalent is in any given
> language).
>
>    You could avoid this problem in a reference-counted scenario by
> incrementing the reference count in the beginning of the function and
> decrementing it when exiting the function, but that's burdensome and
> makes member functions less efficient (especially if they are supposed
> to be fast).

But doesn't the "this-pointer tracking" in a reference-tracking GC 
approach incur approximately that very same penalty?

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> But doesn't the "this-pointer tracking" in a reference-tracking GC 
> approach incur approximately that very same penalty?

  Efficient GC algorithms are extremely complicated and I don't know in
detail how they work, but AFAIK they do not keep track of all references
all the time, but only periodically. That means that when a method is
called, it doesn't necessarily incur any penalty at all in terms of
memory management.

  (This means that objects are not destroyed immediately when the last
reference to them disappears. Only when the GC algorithm determines at
some point that no reference exists to an object, will it mark to be
eventually removed.)

-- 
                                                          - Warp

Post a reply to this message

Invisible escreveu:
> On 14/03/2012 04:53 AM, clipka wrote:
>> Am 13.03.2012 21:37, schrieb Orchid Win7 v1:
>>
>>> Wait - there are open-source Java libs now?
>>>
>>> (Last time I looked at Java, all anyone ever used it for was pointless
>>> Tic-Tac-Toe applets. Nobody ever wrote actual large applications with
>>> it, just small toy examples.)
>>
>> You've never heard of Java enterprise application servers, have you?
> 
> I've heard of them - but I have no idea what the hell they are. Last 
> time I checked, "enterprise" refers either to NCC-1701-D, a galaxy-class 
> starship of the United Federation of Planets, or to a piece of software 
> which is pointlessly over-engineered, over-complex, over-priced, and 
> sold by pushy over-paid salesmen in bad suits.

it's everywhere, Andrew.  Kinda like electricity: you just notice it 
when it goes down (and a huge call stack fills your browser).

-- 
a game sig: http://tinyurl.com/d3rxz9

Post a reply to this message

Invisible escreveu:
> Backwards compatibility is pretty evil, eh? ;-)

haskell still to get its own historic warts... :)

-- 
a game sig: http://tinyurl.com/d3rxz9

Post a reply to this message

On 14/03/2012 17:49, clipka wrote:
> Am 14.03.2012 18:09, schrieb Warp:
>> clipka<ano### [at] anonymousorg> 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:
>> [...]
>
>
> Well, I wasn't actually considering approaches that would be
> prohibitively inefficient :-P

That's actually how Haskell's GC works. :-P

(Or rather, it is if you select 1-space. The default is 2-space. In 
other words, it allocates twice as much RAM as it actually needs. When 
one half fills, it copies everything to the other half. More RAM, but 
less processor time...)

Post a reply to this message

On 14/03/2012 16:51, Warp wrote:
> Invisible<voi### [at] devnull>  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?

Usually the object's class tells you that. You already have a vtable or 
similar structure. (At least, you do in languages where /everything/ is 
dynamically bound by default.)

>    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?

Depends on the implementation.

Smalltalk does it by adding a layer of indirection. The address of every 
object in the system is held in a giant "object table". All objects are 
referred to be object IDs, which are merely indices into this table. To 
move an object, merely update its object table entry. (You can also 
store auxiliary information here - e.g., if you wanted to /lock/ the 
object while it's being moved.)

How Haskell does it is to copy each object from its old location to its 
new location, and then overwrite the old copy with a "hey, this is where 
I moved this object to" reference. The GC engine then uses that to 
update any references in other objects as it finds them.

>    You can't avoid bookkeeping when you are allocating blocks of variable
> size.

Sure. At a minimum, you need to know the size of those blocks. 
Realistically, you also need to know what they contain, or you can't 
follow pointers. You probably need to know a little other stuff too.

Most of this information is per-class rather than per-object, however.

Post a reply to this message

On 14/03/2012 19:47, nemesis wrote:
> Invisible escreveu:
>> Backwards compatibility is pretty evil, eh? ;-)
>
> haskell still to get its own historic warts... :)

Sadly, yes.

Although it /does/ have fewer than most languages. Then again, there's 
less of it to start with, so I guess it would do.

Post a reply to this message

On 14/03/2012 18:58, nemesis wrote:

> it's everywhere, Andrew. Kinda like electricity: you just notice it when
> it goes down (and a huge call stack fills your browser).

Do you want to know... what... it... is?

The Matrix is everywhere. It is all around us. Even here, in this very 
room. You can... feel it. When you walk across the street. When you go 
to church. When you pay your taxes.

(Wait, what were we talking about?)

Post a reply to this message

On 3/14/2012 2:26, Invisible wrote:
> pointlessly over-engineered,

The difference between enterprise software and other software is that 
enterprise software is capable of being managed centrally. You can configure 
it and maintain it and check its health while it's running, centrally, 
without being there.

Do you get paged when your web server goes down? Can you configure how much 
traffic has to dip before you get woken up at night? Can you get a list of 
the people who are allowed to see a particular page? Can you track down 
which ISP is at fault when the traffic to your site dips 20%? When serving 
pages is slow, can you tell which part of the system is causing it? A bad 
disk sector? A flakey network card?

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 8:03, Invisible wrote:
> Heh, really? Most languages I work with can allocate new objects in O(1)
> time and using O(1) memory for bookkeeping. I'm not used to dynamic
> allocation being anything to worry about.

Yeah, it's the *de*allocation that takes a while.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 9:24, clipka wrote:
> So far, so good. But how does the GC know how long each chunk of
> garbage-to-collect is?

It's using basically the same kind of information that's already in each 
object to point to a vtable. If the first word of each object points to a 
vtable, you stick the information once in the vtable about how big it is and 
where the pointers are.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 15:34, Orchid Win7 v1 wrote:
>  merely update its object table entry.

This is also important for the "becomes" operator.

In Smalltalk, if you have an array X of size 10 that you now want to be size 
20, you can do something essentialy like this:

y := a new array of size 20.
copy first ten elements of x into y.
x becomes y

That last statement swaps the variables x and y, so that all former 
references to x now point to y and vice versa. It's how smalltalk does the 
equivalent of std::vector without actually having a header object and a 
content object.

I've nver seen any other language do that.

> Most of this information is per-class rather than per-object, however.

And I suspect if your language is sufficiently strongly typed, you could 
figure out the classes of non-variant data without having to add information 
to the instances.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 2:55, Invisible wrote:
> to know whether the libraries eventually settled down and they stopped doing
> crap like this, or... ?

Both those are deprecated now."

> to make it easy for people to write code for your platform and only your
> platform. >:-D

I didn't say they had a generous reason for doing it. But it's exactly that 
reason for why 90% of OSS is either targetting programmers or sucks. Usually 
both. That which doesn't is paid for by a large company trying to displace 
proprietary software.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 8:52, Warp 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.

And your references have to be as big as your address space, approximately.

Smalltalk back in the 64K days used a 5-bit reference count. If you ever had 
more than 30 references, it just wouldn't get collected until the mark/sweep 
collector ran.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 10:10, clipka wrote:
> Then again, how would any other GC prevent this kind of thing happening?

Because real GC engines count references on the stack. The very fact that A 
is going to return to a member function of B is enough to keep it live.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 10:52, clipka wrote:
> But doesn't the "this-pointer tracking" in a reference-tracking GC approach
> incur approximately that very same penalty?

No, because it's not counting references. The efficiency of GC over RC is to 
a large extent the elimination of updating something every time you assign a 
pointer.  The GC runs, sees a reference to B on the stack, and avoids 
discarding B.  C++ programs don't have access to the stack per se, so they 
can't do that sort of thing.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/14/2012 8:37, Invisible wrote:
> Um... So how is the pro version actually different from VS Express?

Some of them include a bunch of stuff you don't need if you're only working 
by yourself, for example.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 15/03/2012 03:40 AM, Darren New wrote:
> On 3/14/2012 8:03, Invisible wrote:
>> Heh, really? Most languages I work with can allocate new objects in O(1)
>> time and using O(1) memory for bookkeeping. I'm not used to dynamic
>> allocation being anything to worry about.
>
> Yeah, it's the *de*allocation that takes a while.

...but not as long as figuring out /what/ to deallocate. ;-)

The other fun thing is that few people have built concurrent GC engines. 
At least with manual memory management, one thread doesn't usually block 
other threads from running.

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> The other fun thing is that few people have built concurrent GC engines. 
> At least with manual memory management, one thread doesn't usually block 
> other threads from running.

  A concurrent compacting GC sounds to me like a very hard problem.
If the GC moves objects around in RAM, it has to make sure that no code
is modifying the object while the GC is moving it. How does it achieve
that efficiently, I have no idea.

-- 
                                                          - Warp

Post a reply to this message

On 15/03/2012 02:42 PM, Warp wrote:

>    A concurrent compacting GC sounds to me like a very hard problem.

Everybody seems to think they know how it could be done... and yet, 
nobody has written the code that does it.

> If the GC moves objects around in RAM, it has to make sure that no code
> is modifying the object while the GC is moving it. How does it achieve
> that efficiently, I have no idea.

Well, Haskell currently does thinks like have a separate heap for each 
processor core. But that doesn't guarantee there are no pointers from 
one heap to another, so you still gotta be careful. What you would 
probably do is "mark" each object somehow, before you go about moving 
it. Trouble is, that adds the overhead of testing whether each object is 
marked every single time you want to access any object...

I'm sure it can be implemented somehow. The question is how complicated 
it would be, and how much overhead it would add.

Post a reply to this message

Am 15.03.2012 15:42, schrieb Warp:
> Invisible<voi### [at] devnull>  wrote:
>> The other fun thing is that few people have built concurrent GC engines.
>> At least with manual memory management, one thread doesn't usually block
>> other threads from running.
>
>    A concurrent compacting GC sounds to me like a very hard problem.
> If the GC moves objects around in RAM, it has to make sure that no code
> is modifying the object while the GC is moving it. How does it achieve
> that efficiently, I have no idea.

If the GC was part of the OS, maybe something could be done with page 
faulting.

Post a reply to this message

On 15/03/2012 04:14 PM, clipka wrote:

> If the GC was part of the OS, maybe something could be done with page
> faulting.

Indeed. Darren found a paper about this very idea a while back. Some 
guys patched the Linux kernel to do interesting stuff in this direction.

And of course, if GC was in the OS, then you wouldn't have this 
situation of "the GC engine for program X isn't actually using this RAM 
right now, but because it's reserved it from the OS, the GC engine for 
program Y can't use it"...

Post a reply to this message

On 3/15/2012 2:09, Invisible wrote:
> least with manual memory management, one thread doesn't usually block other
> threads from running.

You would be surprised at the number of implementations of malloc() and 
free() that assume you're single-threaded and require locks.

Also, in a language that supports threads in the first place (like Erlang), 
the heaps are per-thread, so that's OK.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/15/2012 9:20, Invisible wrote:
> And of course, if GC was in the OS, then you wouldn't have this situation of

You also wouldn't need finalizers.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/15/2012 7:42, Warp wrote:
>    A concurrent compacting GC sounds to me like a very hard problem.

Yes.

> If the GC moves objects around in RAM, it has to make sure that no code
> is modifying the object while the GC is moving it. How does it achieve
> that efficiently, I have no idea.

You wind up dividing the heap into multiple zones, based on whether you've 
scanned the object, compacted the object, or haven't looked at the object. 
If someone tries to write to an object you've scanned and assign it a 
pointer to an object you haven't scanned, then at that point you move the 
object from the unscanned to the scanned region.

If you set it up so writes cause page faults in that situation, you can get 
really good performance by just GCing one page worth of objects each time 
you hit that fault, which is the paper Andrew refers to.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 15/03/2012 11:17 PM, Darren New wrote:
> On 3/15/2012 9:20, Invisible wrote:
>> And of course, if GC was in the OS, then you wouldn't have this
>> situation of
>
> You also wouldn't need finalizers.

Yeah you would. The OS doesn't magically "know" that a specific object 
is holding a specific external resource.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> You would be surprised at the number of implementations of malloc() and 
> free() that assume you're single-threaded and require locks.

  Care to give an example (in a modern OS)? At least Gnu libc uses locking
malloc() and free() (and it's one of the reasons for their slowness).

  Quite many multithreaded programs would break if malloc() and free()
were not thread-safe.

-- 
                                                          - Warp

Post a reply to this message

On 3/16/2012 1:52, Invisible wrote:
> On 15/03/2012 11:17 PM, Darren New wrote:
>> On 3/15/2012 9:20, Invisible wrote:
>>> And of course, if GC was in the OS, then you wouldn't have this
>>> situation of
>>
>> You also wouldn't need finalizers.
>
> Yeah you would. The OS doesn't magically "know" that a specific object is
> holding a specific external resource.

If your OS is garbage-collected, it's not an "external" resource, now is it?

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

On 3/16/2012 4:41, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> You would be surprised at the number of implementations of malloc() and
>> free() that assume you're single-threaded and require locks.
>
>    Care to give an example (in a modern OS)? At least Gnu libc uses locking
> malloc() and free() (and it's one of the reasons for their slowness).

I think you just answered the question.

Maybe I phrased my statement wrong. Lots of implementations of malloc() and 
free() share a heap amongst multiple threads, so either need to lock 
internally or need to be used from a single-threaded system. And hence, they 
assume you're single threaded within the context of malloc/free because 
they've acquired a global lock.  I.e., yes, you get contention between 
threads with manual memory management.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> On 3/16/2012 1:52, Invisible wrote:
> > On 15/03/2012 11:17 PM, Darren New wrote:
> >> On 3/15/2012 9:20, Invisible wrote:
> >>> And of course, if GC was in the OS, then you wouldn't have this
> >>> situation of
> >>
> >> You also wouldn't need finalizers.
> >
> > Yeah you would. The OS doesn't magically "know" that a specific object is
> > holding a specific external resource.

> If your OS is garbage-collected, it's not an "external" resource, now is it?

  I think that the idea was that RAM is not the only resource that an
object could own, and having to manually free such resource is error-prone
and going back to the days of C programming.

-- 
                                                          - Warp

Post a reply to this message

On 3/16/2012 11:39, Warp wrote:
>    I think that the idea was that RAM is not the only resource that an
> object could own, and having to manually free such resource is error-prone
> and going back to the days of C programming.

Right. In a GCed operating system, why would you own anything other than 
GCed resources? You don't need file handles. You don't need IPC ports. You 
don't need window handles. Etc. Look at Smalltalk - nothing had finalizers, 
because it had its own OS. Or Hermes. Or Eros. (Eros and Hermes, for 
example, treats all your disk space as just one big virtual memory address 
space. There's no files. You just store data in your variables, and serve 
them over IPC ports.)

About the only thing you'd need is some way of closing a socket when the 
connection got GCed, in which case you could have a process that closes the 
socket when its local IPC connections all get closed, and you just talk 
through that process. That's basically how Erlang manages it.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Right. In a GCed operating system, why would you own anything other than 
> GCed resources?

  I think you are talking about system resources. A program may use other
resources than simply system resources. If objects are never finalized,
how exactly are you going to free those resources? Manually?

  Even then, sometimes even *memory* handling could require finalizers.
The quintessential example would be if you wanted to implement a
copy-on-write mechanism. In this case you need to "retain" and "release"
a reference counter each time an object takes hold of or drops a shared
block of memory. Without finalizers it becomes difficult.

  You could have manual "retains" and "release" calls, but then we are
back to square one, ie. manual memory management, which is laborious and
error-prone, and hard to make exception-safe.

-- 
                                                          - Warp

Post a reply to this message

On 3/16/2012 12:38, Warp wrote:
>    I think you are talking about system resources. A program may use other
> resources than simply system resources.

Like what?

> The quintessential example would be if you wanted to implement a
> copy-on-write mechanism.

That hasn't anything to do with finalizers. In advanced systems, that sort 
of stuff isn't something you write in the application code, either, any more 
than worrying about taking things out of the B-tree is something a SQL 
programmer worries about when deleting a row.

And yes, at IBM, when they were working in NIL (the precursor to Hermes), 
they ported a large and complex system from a single machine implementation 
to run on a distributed hot-failover cluster changing nothing but the 
compiler, just like you could with SQL code.

-- 
Darren New, San Diego CA, USA (PST)
   People tell me I am the counter-example.

Post a reply to this message