[go-nuts] The necessity of garbage collection

[C K Kashyap]

Hi,

Could someone please point me to some data on situations where GC makes it convenient to deal with concurrency or perhaps an example scenario where not having a GC makes it more convoluted to deal with concurrency.

In my mind I was convinced about the need for GC but at a discussion with a colleague, a C++ fan,  I realized that I did not have concrete examples to illustrate the need for a GC. 

I'd appreciate the response very much.

Regards,

Kashyap

[tomwilde]

in contrast to manual memory management or other automatic memory management approaches?

[Dmitry Vyukov]

On Mon, Jun 17, 2013 at 5:32 PM, C K Kashyap <ckka...@gmail.com> wrote:
> Hi,
>
> Could someone please point me to some data on situations where GC makes it
> convenient to deal with concurrency or perhaps an example scenario where not
> having a GC makes it more convoluted to deal with concurrency.
> In my mind I was convinced about the need for GC but at a discussion with a
> colleague, a C++ fan, I realized that I did not have concrete examples to
> illustrate the need for a GC.

Simple concurrent copy-on-write publication:

var gm unsafe.Pointer

// publisher
m := *(*map[string]string)(atomic.Load(&gm))
m2 := make(map[string]string)
// fill m2 using m
atomic.Store(&gm, (unsafe.Pointer)(&m))

// readers
m := *(*map[string]string)(atomic.Load(&gm))
// use m

In C++ it would require std::mutex+std::shared_ptr, or atomic
operations on std::shared_ptr (I don't know what is the state of this
now, but previously it was either not supported or using mutex).

If you are using lots of this (e.g. mutating a tree using
partial-copy-on-write) overheads of std::shared_ptr becomes
prohibitive.

[tomwilde]

Hi Dmitry,

would you mind explaining that piece of code a little more in detail? I'm interested.

Thank you,

- Tom

[Dmitry Vyukov]

On Mon, Jun 17, 2013 at 7:26 PM, tomwilde <sedevel...@gmail.com> wrote:
> Hi Dmitry,
>
> would you mind explaining that piece of code a little more in detail? I'm
> interested.

Instead of protecting a map with RWMutex, you use copy-on-write; i.e.
a writers creates a new map and atomically publishes the pointer to
the new map; readers atomically load a pointer to the current version
of the map and use it. No other synchronization is required in
presence of GC, the old maps will be GCed when no longer in use.

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Ian Lance Taylor]

On Mon, Jun 17, 2013 at 8:26 AM, tomwilde <sedevel...@gmail.com> wrote:
>
> would you mind explaining that piece of code a little more in detail? I'm
> interested.

In English: one writer, multiple readers, where the number of readers
is not known to the program. This is handled easily by GC. In C++ it
requires using something like a std::shared_ptr, which makes all
reader access expensive. In other words, in scenarios where data is
shared among an unknown number of threads/goroutines, you pay a memory
access price somewhere. You can either pay it by adding locking to
every reader, or you can pay it in a garbage collector.

Also it's much much easier to write the garbage collector code correctly.

Ian

[Dmitry Vyukov]

On Mon, Jun 17, 2013 at 7:37 PM, minux <minu...@gmail.com> wrote:

> On Mon, Jun 17, 2013 at 9:43 PM, Dmitry Vyukov <dvy...@google.com> wrote:
>> Simple concurrent copy-on-write publication:
>>
>> var gm unsafe.Pointer
>>
>> // publisher
>> m := *(*map[string]string)(atomic.Load(&gm))
>> m2 := make(map[string]string)
>> // fill m2 using m
>> atomic.Store(&gm, (unsafe.Pointer)(&m))

> perhaps you meant m2?
> atomic.Store(&gm, (unsafe.Pointer)(&m2))

Yes, m2.

[minux]

On Mon, Jun 17, 2013 at 9:43 PM, Dmitry Vyukov <dvy...@google.com> wrote:

> Simple concurrent copy-on-write publication:
>
> var gm unsafe.Pointer
>
> // publisher
> m := *(*map[string]string)(atomic.Load(&gm))
> m2 := make(map[string]string)
> // fill m2 using m
> atomic.Store(&gm, (unsafe.Pointer)(&m))

perhaps you meant m2?
atomic.Store(&gm, (unsafe.Pointer)(&m2))
>

[Dmitry Vyukov]

On Mon, Jun 17, 2013 at 7:38 PM, Ian Lance Taylor <ia...@golang.org> wrote:
> On Mon, Jun 17, 2013 at 8:26 AM, tomwilde <sedevel...@gmail.com> wrote:
>>
>> would you mind explaining that piece of code a little more in detail? I'm
>> interested.
>
> In English: one writer, multiple readers, where the number of readers
> is not known to the program. This is handled easily by GC. In C++ it
> requires using something like a std::shared_ptr,

shared_ptr alone won't do. Amusingly it's not thread-safe. You can't
make a copy of shared_ptr in one thread and assign a new value to the
shared_ptr in another thread.

> which makes all
> reader access expensive. In other words, in scenarios where data is
> shared among an unknown number of threads/goroutines, you pay a memory
> access price somewhere. You can either pay it by adding locking to
> every reader, or you can pay it in a garbage collector.
>
> Also it's much much easier to write the garbage collector code correctly.

Note that if write a rare, the copy-on-write version incurs virtually
zero synchronization overhead to readers (single atomic load).

[Christoph Hack]

The copy-on-write idiom works by having a pointer gm to a big data structure. Whenever a thread T wants to change one or more attributes of the data structure, then process T copies the data structure, modifies the content and replaces the gm pointer atomically using a single CAS statement. Even if the modification of the attributes isn't atomic, the replacement of the gm pointer is. The whole algorithm is lock-free and other threads can still read from older versions of the data structure (assuming they have de-referenced the pointer before). Therefore, slow readers aren't a problem at all, but you might get many of those copies in your memory at a given time, if you have changed the data multiple times and other threads are still reading older snapshots of the data. Luckily, once a particular snapshot isn't used any more, the GC takes care of it automatically.

If you want to implement something like that in C++, you would either need to do some manual reference counting (which slows down every access to your data structure significantly), or you need to implement your own local GC.

-christoph

[Ian Lance Taylor]

On Mon, Jun 17, 2013 at 8:41 AM, Dmitry Vyukov <dvy...@google.com> wrote:
>
> shared_ptr alone won't do. Amusingly it's not thread-safe. You can't
> make a copy of shared_ptr in one thread and assign a new value to the
> shared_ptr in another thread.

Please don't tell me things like that, it just depresses me. This is
not how I want to start my week.

Ian

[C K Kashyap]

Thanks Dimitry et al ... I see the value here. Yes, I see the triviality of doing a COW that can take some error prone plumbing in a non-gc'd environment.

Thank you so much.

Regards,

Kashyap

[Dmitry Vyukov]

On Mon, Jun 17, 2013 at 8:12 PM, C K Kashyap <ckka...@gmail.com> wrote:
> Thanks Dimitry et al ... I see the value here. Yes, I see the triviality of
> doing a COW that can take some error prone plumbing in a non-gc'd
> environment.

It's not only about plumbing. Performance and scalability of this
algorithm is impossible to match even closely in C/C++ (unless you
roll your own GC).

[John Nagle]

On 6/17/2013 6:32 AM, C K Kashyap wrote:
> Could someone please point me to some data on situations where GC makes it
> convenient to deal with concurrency or perhaps an example scenario where
> not having a GC makes it more convoluted to deal with concurrency.
> In my mind I was convinced about the need for GC but at a discussion with a
> colleague, a C++ fan, I realized that I did not have concrete examples to
> illustrate the need for a GC.

The big advantage of garbage collection is that you don't have
to obsess on "who owns what". In a language with shared data between
concurrent activities, like Go, the language user doesn't have to
deal with determining who is the last to let go of a shared object.

Go generates garbage internally. When you create an
instance of an array, an instance object is created and passed
around. It can be passed to another concurrent activity, so
in general it can't be an on-stack object. Closures also generate
garbage internally. Somebody has to release that stuff.

There are three big questions in C/C++:
1. "How big is it?"
2. "Who deletes it?"
3. "Who locks it?"

#1 is responsible for the huge number of buffer overflow exploits
associated with C and C++ programs. C++ tries to paper over size
issues with collection classes, but the mold always seeps through
the wallpaper because system calls want raw pointers. Go always
checks subscripts, optimizing out some of the checks in inner
loops to get performance up. So Go automatically deals with #1.
No more buffer overflow exploits.

#2 is handled by garbage collection in Go, so the user doesn't
have to worry about it. C and C++ programming require obsessing
on who owns what, which is a pain. Trying to automate that
within C++ has not worked well. The C++ standards committee
struggled through three rounds of "auto_ptr" without making it
airtight.

#3 is the source of race conditions. Go is no better than
C and C++ at this. I've discussed that before, so I won't
repeat it here.

There are advantages to not having a GC. In hard real time
systems, the impact of a GC randomly firing off is unacceptable.
I'd like to see a hard compiled language which solves all three
of those problems above without garbage collection. Even
Erlang has a garbage collector.

John Nagle

[Dmitry Vyukov]

FYI: gcc/clang -fsanitize=address solve #1 and #2 for C/C++ as well.

#3 is the source of race conditions.  Go is no better than
C and C++ at this.  I've discussed that before, so I won't
repeat it here.

    There are advantages to not having a GC.  In hard real time
systems, the impact of a GC randomly firing off is unacceptable.
I'd like to see a hard compiled language which solves all three
of those problems above without garbage collection.  Even
Erlang has a garbage collector.

                        John Nagle

[Ziad Hatahet]

On Mon, Jun 17, 2013 at 11:56 AM, John Nagle <na...@animats.com> wrote:

I'd like to see a hard compiled language which solves all three

of those problems above without garbage collection.  Even
Erlang has a garbage collector.

                        John Nagle

Have you taken a look at Rust (rust-lang.org)? It has an optional garbage collector; therefore, unless absolutely needed, the preferred way is to allocate objects on the stack, or use linear types to avoid the use of GC. It also has immutability by default, and uses owned pointers + message passing to avoid race conditions.

--
Ziad

 

[Dave Cheney]

I think you are putting the cart before the horse. Rust is attempting to make their gc optional. This newly attempted experiment has only begun, so I think it is premature to draw such strong conclusions at this point. 

--

[Ziad Hatahet]

On Mon, Jun 17, 2013 at 2:49 PM, Dave Cheney <da...@cheney.net> wrote:

I think you are putting the cart before the horse. Rust is attempting to make their gc optional. This newly attempted experiment has only begun, so I think it is premature to draw such strong conclusions at this point. 

As far as I know, the GC has always been optional (are you thinking of D perhaps?). You can write an entire program without invoking the GC (which, at the present time, is denoted by the @ sigil). What they are experimenting with, is to remove the @ sigil, and pull the GC into the standard library.

Take a look at this, for instance, from almost a year ago: https://github.com/pcwalton/fempeg

From the README:

"It's designed to be a demo of the soft real-time capabilities and safety features of Rust.

FeMPEG performs no allocations (except in format strings in case of errors). All data is stored in constant memory or on the stack. This can be verified by the lack of ~ and @ sigils (signifying allocation) in the codebase."

--
Ziad

 

[Dave Cheney]

That is need what I was referring too. I am only a nascent Rust observer.  

[Michael Jones]

The simplest way to think of "when GC really, really helps" is cases where data structures are created and passed to other functions or threads. If there is one creator and one receiver, then control passes naturally with the return value. A creates and returns/sends to B. B is then responsible for deletion. When there are multiple B's, then either the data structure has to know (perfectly) when it can delete itself or the B's need to coordinate via some other mechanism. In a concurrent/threaded situation, you will have problems knowing when the last man standing is through with the data. Several people have explained this but the details are less significant than the general notion that, for example, the last thread using the data might have a problem and need to return abnormally and it must then discover every pointer that it's inherited responsibility for without fail. 

In the GC case, the mental model is that all allocations belong to the system's runtime library and threads just "borrow" them. Since the runtime comes to life before any user thread, and exists after all such threads have ended, the runtime is always in a position to determine data lifetimes correctly. This design also refactors all "when to delete" logic into a single, common place. That's good for correctness, for instrumentation, and makest possible to have the "best minds on it" and reuse that logic in every alloc/free in an arbitrarily complex concurrent system. That's the good. The bad is that a central GC system generally has to do detective work to discover data lifetime relationships that are already and easily known in the logic of the code. This makes it more expensive than doing it yourself, in those cases where you are able to do it yourself perfectly. Many broken C/C++ programs suggest that not all developers can in fact do this right in every case, especially in concurrent applications, as have been outlined here.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[Ziad Hatahet]

On Mon, Jun 17, 2013 at 9:24 PM, Michael Jones <m...@google.com> wrote:

Many broken C/C++ programs suggest that not all developers can in fact do this right in every case, especially in concurrent applications, as have been outlined here.

I agree with your reply overall. However, I think the situation should not be presented as a dichotomy of GC vs C and C++. The compiler can help with managing memory at compile time, by providing constraints or proofs for life times of objects. This is what Rust does do a certain degree; so you do not end up with dangling pointers, double-frees, race conditions, etc. All this can be proven at compile time, without the mess we have in C or C++. This kind of  provides you with the best of both worlds. I am curious to know if there are other languages that have a similar approach.

Furthermore, different implementations of GC are not equal. I presume you were primarily referring to the single global heap -- like Java, in your post. I am not a compiler expert, but I think another way about it is to have task-local GC, instead of a global heap. This would make it easier to parallelize, and reduce GC-pauses.

--
Ziad

[Michael Jones]

Agreed! Personally, I am a very big fan of "do everything possible at compile time" and again, for me, the idea of possible is very open ended. I'd be happy with compiles taking as long as necessary so that runtimes could be as short as possible.

[John Nagle]

On 6/17/2013 2:38 PM, Ziad Hatahet wrote:
> On Mon, Jun 17, 2013 at 11:56 AM, John Nagle <na...@animats.com> wrote:
>> I'd like to see a hard compiled language which solves all three
>> of those problems above without garbage collection. Even
>> Erlang has a garbage collector.

> Have you taken a look at Rust (rust-lang.org)? It has an optional garbage
> collector; therefore, unless absolutely needed, the preferred way is to
> allocate objects on the stack, or use linear types to avoid the use of GC.
> It also has immutability by default, and uses owned pointers + message
> passing to avoid race conditions.

There's a lot to be said for heavy use of immutable objects. If
something is immutable, it can be shared between concurrent activities
without locking. The only issue is getting rid of it when it's done,
for which garbage collection is very convenient.

Go has some immutability, but not a lot. Python has acquired
more over the years; originally, just strings and tuples were
immutable, but now there are "frozen dicts", "frozen sets", etc.
Python's concurrency benefits from this.

A problem with immutability is that somehow you have
to initialize the thing. In a language without constructors,
like Go, there's no "construction time" during which an object
is mutable. You can create a struct via structure initialization,
but for it to be "const", it must be a compile-time const. There's
no way to express "read-only" in Go. (Except for channels, which
are special.)

John Nagle

[Øyvind Teig]

I have tried to read myself up on COW (copy-on-write) http://en.wikipedia.org/wiki/Copy-on-write and on threads here, and in this thread. There must be a basic assumption here that I have failed to understand. Please help straighten this out:

1. After a thread A has modified on a copy and wants to update the original, oops.. some other thread B has also modified a copy and in fact suceeded in doing that. 
2. Provided this is not possible
1. there must be atomic copy-on-write-update (which would make the copy unnecessary)
2. ...
3. Provided this is prohibited
1. Is it so by programming pattern (don't like it: unsafe)
2. or by compiler (don't think it's possible)
3. ...
4. Provided this is not prohibited
1. If the original is kept before every copy-on-write it's easy to spot this that some other process has updated, since A has modified but copy of original is not equel to shared data (modified by some other thread)
2. Who decides which copy is the right? 
3. ...
5. If the shared object is immutable
1. Why is it not that for thread A?
2. Then what's the purpose of COW, if immuate for all after the original writer is out of context to modify it (CREW)
3. recursive argument: start at 1
4. ...
6. ...

In my head CREW Concurrent Read Exclusive Write means that if only ONE is allowed to write then all accesses (R/W) must be exclusive

Øyvind

[minux]

On Tue, Jun 18, 2013 at 3:58 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> I have tried to read myself up on COW (copy-on-write)
> http://en.wikipedia.org/wiki/Copy-on-write and on threads here, and in this
> thread. There must be a basic assumption here that I have failed to
> understand. Please help straighten this out:
> After a thread A has modified on a copy and wants to update the original,
> oops.. some other thread B has also modified a copy and in fact suceeded in
> doing that.

COW is suitable for cases where only the latest update is important and that
occasionally using a slightly stale value is not harmful.

btw, in linux kernel, this is called RCU, and people who want to see
the complexity
of COW without GC could look there.

[Paulo Pinto]

On 18 Jun, 07:53, Ziad Hatahet <hata...@gmail.com> wrote:
>  On Mon, Jun 17, 2013 at 9:24 PM, Michael Jones <m...@google.com> wrote:
>
> > Many broken C/C++ programs suggest that not all developers can in fact do
> > this right in every case, especially in concurrent applications, as have
> > been outlined here.
>
> I agree with your reply overall. However, I think the situation should not
> be presented as a dichotomy of GC vs C and C++. The compiler can help with
> managing memory at compile time, by providing constraints or proofs for
> life times of objects. This is what Rust does do a certain degree; so you
> do not end up with dangling pointers, double-frees, race conditions, etc.
> All this can be proven at compile time, without the mess we have in C or
> C++. This kind of  provides you with the best of both worlds. I am curious
> to know if there are other languages that have a similar approach.

Yes, ParaSail for example, although the language is still not done.

http://en.wikipedia.org/wiki/ParaSail_%28programming_language%29

>
> Furthermore, different implementations of GC are not equal. I presume you
> were primarily referring to the single global heap -- like Java, in your
> post. I am not a compiler expert, but I think another way about it is to
> have task-local GC, instead of a global heap. This would make it easier to
> parallelize, and reduce GC-pauses.

The success of Java in the enterprise helped making GC an accepted
technology.

However it also gave a bad name, because many without compiler
background associate
GC == Java, even though there are plenty to choose from. Although one
has to also say
most JVMs have very advanced GC implementations.

Having experienced the pleasure of using systems programming languages
with GC (Modula-3,
Oberon language family) back in the late 90's, I am still looking
forward to the day automatic memory
management becomes a reality on that level as well.

--
Paulo

[C K Kashyap]

As per Øyvind's point the original scheme of COW proposed has a subtle (not so subtle now that I think of it) bug. As in, chances of losing updates. This could perhaps be fixed with a "version" in the data structure? As in the publisher notes the version that it copied and just before updating it checks the version again and if it is bumped, then re-do the whole thing. kinda like transaction blocks.

I think even with this re-attempt logic in place, it's gonna be overall more simple than doing your own GC.

Regards,

Kashyap

[Dmitry Vyukov]

On Tue, Jun 18, 2013 at 11:58 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> I have tried to read myself up on COW (copy-on-write)
> http://en.wikipedia.org/wiki/Copy-on-write and on threads here, and in this
> thread. There must be a basic assumption here that I have failed to
> understand. Please help straighten this out:
>
> After a thread A has modified on a copy and wants to update the original,
> oops.. some other thread B has also modified a copy and in fact suceeded in
> doing that.

The copy is private to thread A, nobody else can modify it.
The copy becomes shared only after publication. At this point it also
become immutable.

> Provided this is not possible
>
> there must be atomic copy-on-write-update (which would make the copy
> unnecessary)

I do not understand.

> Provided this is prohibited
>
> Is it so by programming pattern (don't like it: unsafe)
> or by compiler (don't think it's possible)

I am lost here and below.

[Dmitry Vyukov]

On Tue, Jun 18, 2013 at 1:33 PM, C K Kashyap <ckka...@gmail.com> wrote:
> As per Øyvind's point the original scheme of COW proposed has a subtle (not
> so subtle now that I think of it) bug. As in, chances of losing updates.
> This could perhaps be fixed with a "version" in the data structure? As in
> the publisher notes the version that it copied and just before updating it
> checks the version again and if it is bumped, then re-do the whole thing.
> kinda like transaction blocks.
>
> I think even with this re-attempt logic in place, it's gonna be overall more
> simple than doing your own GC.

You either have 1 writer; or protect updates with a mutex; or use
plain CAS-loop on pointer value, no separate version is required, the
pointer value itself acts as unique version.

[Øyvind Teig]

kl. 11:36:38 UTC+2 tirsdag 18. juni 2013 skrev Dmitry Vyukov følgende:

On Tue, Jun 18, 2013 at 1:33 PM, C K Kashyap <ckka...@gmail.com> wrote:
> As per Øyvind's point the original scheme of COW proposed has a subtle (not
> so subtle now that I think of it) bug. As in, chances of losing updates.
> This could perhaps be fixed with a "version" in the data structure? As in
> the publisher notes the version that it copied and just before updating it
> checks the version again and if it is bumped, then re-do the whole thing.
> kinda like transaction blocks.
>
> I think even with this re-attempt logic in place, it's gonna be overall more
> simple than doing your own GC.

You either have 1 writer;

This is, I assume, one recipe as on how to use COW. The concept itself will not require one writer.

 

or protect updates with a mutex;

But then COW is not needed

 

or use
plain CAS-loop on pointer value,

CAS (Compare-and-swap)

 

no separate version is required, the
pointer value itself acts as unique version.

But for COW, the pointers to the shared data are constant: all users have pointers always pointing to the same shared data, located at the same address in its life time.

Øyvind 

 

[Dmitry Vyukov]

On Tue, Jun 18, 2013 at 2:46 PM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> kl. 11:36:38 UTC+2 tirsdag 18. juni 2013 skrev Dmitry Vyukov følgende:
>>
>> On Tue, Jun 18, 2013 at 1:33 PM, C K Kashyap <ckka...@gmail.com> wrote:
>> > As per Øyvind's point the original scheme of COW proposed has a subtle
>> > (not
>> > so subtle now that I think of it) bug. As in, chances of losing updates.
>> > This could perhaps be fixed with a "version" in the data structure? As
>> > in
>> > the publisher notes the version that it copied and just before updating
>> > it
>> > checks the version again and if it is bumped, then re-do the whole
>> > thing.
>> > kinda like transaction blocks.
>> >
>> > I think even with this re-attempt logic in place, it's gonna be overall
>> > more
>> > simple than doing your own GC.
>>
>> You either have 1 writer;
>
>
> This is, I assume, one recipe as on how to use COW. The concept itself will
> not require one writer.
>
>>
>> or protect updates with a mutex;
>
>
> But then COW is not needed

COW is for *readers*.

>> or use
>> plain CAS-loop on pointer value,
>
>
> CAS (Compare-and-swap)
>
>>
>> no separate version is required, the
>> pointer value itself acts as unique version.
>
>
> But for COW, the pointers to the shared data are constant: all users have
> pointers always pointing to the same shared data, located at the same
> address in its life time.

I am not sure what algorithm you are referring to.
In the algorithm I am referring to pointers are atomically updated to
point to newer version of the same object. E.g. a writer atomically
replaces part of a tree structure with a new version. New readers will
see this update and read the new tree state.

[Øyvind Teig]

I assume it's also with that algorithm legal and acceptable with conflicts. 

A reader could be in the middle of a read of an array (read "Dmitry"), then "atomically" (for the writer)

the reader gets its pointers updated (pointing to my name "Oyvind Teig").

The reader would quite fast get sour for "Dmitry Teig" when it has read the full name.

I certainly don't like what I see and hear and learn.

Go's concurrency is based on CSP: use channels whenever possible.

And if you think it's not possible because of something, think twice and third.

Only then...

Øyvind

[Dmitry Vyukov]

The writer must ensure that the atomic update transitions the data
structure from one consistent state to another consistent state.
If you need first and last name to be consistent, then you put them
into a struct and writer updates the pointer from one struct to
another struct. This way reader observes either old first and last
name or new first and last name.

[roger peppe]

By way of concrete illustration: http://play.golang.org/p/f850DWa2_C

I've used sync.RWMutex rather than atomically setting a pointer,
because I don't think there's any way to set a pointer atomically
without using unsafe. The point remains the same though:
once a client has read the data structure, it doesn't need to use
any locks to access it. A given version of the data will become
garbage and be collected when all clients have stopped using it.

[Ian Lance Taylor]

On Tue, Jun 18, 2013 at 12:58 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> After a thread A has modified on a copy and wants to update the original,
> oops.. some other thread B has also modified a copy and in fact suceeded in
> doing that.
> Provided this is not possible
>
> there must be atomic copy-on-write-update (which would make the copy
> unnecessary)
> ...
>
> Provided this is prohibited
>
> Is it so by programming pattern (don't like it: unsafe)
> or by compiler (don't think it's possible)

An example of a copy-on-write approach to a data structure is
std::string in current versions of the C++ library distributed with
GCC. The current version may be seen at

http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.h?view=markup
http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.tcc?view=markup

The essential steps are _M_leak and _M_mutate. The code keeps a
reference count to the string buffer. The reference count is
manipulated atomically. When a write operation is done, if there are
multiple references to the buffer, the buffer is first copied before
the write operation proceeds.

So for this case the answer to the above is both: the copy-on-write is
implemented by a programming pattern in std::string and enforced by
the compiler in uses of std::string.

Ian

[Øyvind Teig]

kl. 15:25:01 UTC+2 tirsdag 18. juni 2013 skrev Ian Lance Taylor følgende:

On Tue, Jun 18, 2013 at 12:58 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
>
> After a thread A has modified on a copy and wants to update the original,
> oops.. some other thread B has also modified a copy and in fact suceeded in
> doing that.
> Provided this is not possible
>
> there must be atomic copy-on-write-update (which would make the copy
> unnecessary)
> ...
>
> Provided this is prohibited
>
> Is it so by programming pattern (don't like it: unsafe)
> or by compiler (don't think it's possible)

An example of a copy-on-write approach to a data structure is
std::string in current versions of the C++ library distributed with
GCC.  The current version may be seen at

http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.h?view=markup
http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.tcc?view=markup

The essential steps are _M_leak and _M_mutate.  The code keeps a
reference count to the string buffer.  The reference count is
manipulated atomically.  When a write operation is done, if there are
multiple references to the buffer, the buffer is first copied before
the write operation proceeds.

Will it avoid "OIyavni nLdanTceei GTaylor" (our names merged)

I can only see M_is_shared used once, in push_back - one per char.

Or isn't that its purpose?

You write (I add):

The essential steps are _M_leak and _M_mutate.  The code keeps a 

reference count in the shared string buffer to the (shared?) string buffer.  The reference count in the shared string buffer is 

manipulated atomically.  When a write operation is done to the local string buffer, if there are 

multiple references to the buffer in the shared string buffer, the shared string buffer is first copied from the shared to the local string buffer before 

the write operation to the local string buffer proceeds.  

Puh, did that end up making sense, or did I obfuscate? Not so easy to read 3164 lines of code! Where should _M_leak and _M_mutate be inserted as headings?

Øyvind

[roger peppe]

On 18 June 2013 14:25, Ian Lance Taylor <ia...@golang.org> wrote:
> http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.h?view=markup
> http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.tcc?view=markup

wow.

[Ian Lance Taylor]

On Tue, Jun 18, 2013 at 7:04 AM, Øyvind Teig <oyvin...@teigfam.net> wrote:
> kl. 15:25:01 UTC+2 tirsdag 18. juni 2013 skrev Ian Lance Taylor følgende:
>>
>> An example of a copy-on-write approach to a data structure is
>> std::string in current versions of the C++ library distributed with
>> GCC. The current version may be seen at
>>
>>
>> http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.h?view=markup
>>
>> http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc%2B%2B-v3/include/bits/basic_string.tcc?view=markup
>>
>> The essential steps are _M_leak and _M_mutate. The code keeps a
>> reference count to the string buffer. The reference count is
>> manipulated atomically. When a write operation is done, if there are
>> multiple references to the buffer, the buffer is first copied before
>> the write operation proceeds.
>
>
> Will it avoid "OIyavni nLdanTceei GTaylor" (our names merged)

Yes, assuming the two strings are written in different threads.

> I can only see M_is_shared used once, in push_back - one per char.
> Or isn't that its purpose?

Look at the .tcc file also.

> You write (I add):
>
> The essential steps are _M_leak and _M_mutate. The code keeps a
> reference count in the shared string buffer to the (shared?) string buffer.
> The reference count in the shared string buffer is
> manipulated atomically. When a write operation is done to the local string
> buffer, if there are
> multiple references to the buffer in the shared string buffer, the shared
> string buffer is first copied from the shared to the local string buffer
> before
> the write operation to the local string buffer proceeds.
>
>
> Puh, did that end up making sense, or did I obfuscate? Not so easy to read
> 3164 lines of code! Where should _M_leak and _M_mutate be inserted as
> headings?

I'm not sure what you mean by headings. The base copy-on-write step
is probably in _M_mutate:
if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
// Allocate a new buffer and copy in the old one.

In other words, while a buffer is shared, it is never changed. Any
attempt to change it creates a new buffer and decrements the reference
count of the old one. When the reference count is 1, the buffer may
be modified in place. When the reference count is 0, the buffer is
freed (this last step is necessary in C++ because C++ does not have a
garbage collector).

Ian

[Ziad Hatahet]

On Tue, Jun 18, 2013 at 12:16 AM, John Nagle <na...@animats.com> wrote:

The only issue is getting rid of it when it's done,

for which garbage collection is very convenient.

Or, if they are allocated on the stack, or are managed by unique/owned pointers, then they get freed the moment they are out of scope, or have no owner. No need for a tracing gc.

 

   A problem with immutability is that somehow you have
to initialize the thing.

The way Rust gets around this is that it allows you to "freeze" and "thaw" types if you want to make them immutable or mutable, respectively; while still preserving guarantees that they will behave as expected. This means that the (im)mutability of a particular object is dependent on how the pointer to it is declared. This is proven statically for stack objects, and objects with unique pointers, and at runtime for GC-managed objects.

--

Ziad

[Ziad Hatahet]

On Tue, Jun 18, 2013 at 11:49 AM, Dmitry Vyukov <dvy...@google.com> wrote:

Stack allocated objects are freed when they are out of scope, it does

not mean that they are not used anymore. This is a common mistake in
C/C++.

C and C++ are unsafe languages, and allow what you mentioned. The newer languages we are discussing here do not have this problem.

 

Owned pointers can't practically collect cycles.

Owned pointers force one to use atomic reference counting and mutexes
for object lifetime management. Both things kill parallel performance.

I believe you are mixing up owned pointers in the way Rust implements them, with shared_ptr<> in how they are implemented in C++. Yes, the latter uses reference counting and mutexes. The former does not. Everything is proven statically at compile time, to ensure that at any given moment, an object has at most a single owner. Once it does not, it gets freed. As far as I know, this has zero runtime overhead. Once/if you need multiple owners, then you can use the GC.

--
Ziad

[Dmitry Vyukov]

On Tue, Jun 18, 2013 at 10:35 PM, Ziad Hatahet <hat...@gmail.com> wrote:
>>
>> The only issue is getting rid of it when it's done,
>> for which garbage collection is very convenient.
>
>
> Or, if they are allocated on the stack, or are managed by unique/owned
> pointers, then they get freed the moment they are out of scope, or have no
> owner. No need for a tracing gc.

Stack allocated objects are freed when they are out of scope, it does
not mean that they are not used anymore. This is a common mistake in
C/C++.

Owned pointers can't practically collect cycles.

Owned pointers force one to use atomic reference counting and mutexes
for object lifetime management. Both things kill parallel performance.

>> A problem with immutability is that somehow you have
>> to initialize the thing.
>
>
> The way Rust gets around this is that it allows you to "freeze" and "thaw"
> types if you want to make them immutable or mutable, respectively; while
> still preserving guarantees that they will behave as expected. This means
> that the (im)mutability of a particular object is dependent on how the
> pointer to it is declared. This is proven statically for stack objects, and
> objects with unique pointers, and at runtime for GC-managed objects.
>
>
> --
> Ziad
>
>

[John Nagle]

On 6/18/2013 6:25 AM, Ian Lance Taylor wrote:
> So for this case the answer to the above is both: the copy-on-write is
> implemented by a programming pattern in std::string and enforced by
> the compiler in uses of std::string.
> Ian

The trouble with that comes when you have to get a raw pointer
to the underlying data to use with some system call, DLL,
or C library. I refer to this as "the mold leaking
through the wallpaper". This is why auto_ptr runs into
so much trouble.

The same kinds of problems come up when a managed
environment like Go calls an un-managed environment
like C. One way to look at this is to consider
whether a reference is passed to a C function with
"keep" or "delete" privileges. If the function
doesn't have the right to keep the reference beyond
function return, it doesn't need "keep" privileges.
If it can't delete the referenced object, it doesn't
need "delete" privileges. A function which needs
neither can't mess up the memory management on the
managed side.

Functions which need "keep" or "delete" tend
to have to get deeply into the memory management
system of the managed side. It would be useful
in some languages if those concepts appeared explicitly
in the language, at least at the points where managed
and un-managed memory meet.

(For a reference counted language, this can be
a huge win. Something passed without "keep" or
"delete" privileges, into a language which checked
for that, need not have reference count updates.
Even where the language doesn't have those concepts
at the source level, it's something worth detecting
during compilation in reference counted languages.
I've suggested this for Python, but since Python
lets you look up variables by name at run time and
mess with them ("setattr()", etc.), even from
another thread, serious optimization is hopeless
without restricting some of the more outrageous
dynamic semantics of the language. Google people
who saw Unladen Swallow crash and burn will recognize
this problem.)

John Nagle

[John Nagle]

That sort of thing demonstrates how the C++ standards committee
went off into template la-la land. They tried to do far too much
with templates, resulting in messes like that. 3000 lines of template
to define strings.

John Nagle

[Dmitry Vyukov]

Ah, so this is kind of compiler-optimized GC, right?
Go does this in simple cases.
When pointers are passed via channels, it becomes more difficult, but
probably still possible.

[Paulo Pinto]

Yes.

On my humble opinion, this is the only way to have reference counting
with good
enough performance, as many needless increment/decrement operations
get removed
by the compiler.

That is also the approach taken by Objective-C with ARC and ParaSail.

--
Paulo

On Jun 19, 10:30 am, Dmitry Vyukov <dvyu...@google.com> wrote:

[John Nagle]

On 6/18/2013 1:09 PM, John Nagle wrote:
> On 6/18/2013 6:25 AM, Ian Lance Taylor wrote:
>> So for this case the answer to the above is both: the copy-on-write is
>> implemented by a programming pattern in std::string and enforced by
>> the compiler in uses of std::string.
>> Ian
>
> The trouble with that comes when you have to get a raw pointer
> to the underlying data to use with some system call, DLL,
> or C library. I refer to this as "the mold leaking
> through the wallpaper". This is why auto_ptr runs into
> so much trouble.

The day after I wrote that, I read this in the digest for
the Gazebo robot simulator:

> I get the following error :
>
> gazebo: /usr/include/boost/smart/ptr/shared/ptr.hpp:418: T*
> boost::shared_ptr<t>::operator->() const [with T = gazebo::physics::Entity]:
> Assertion `px != 0' failed.

That's the trouble with trying to implement reference counting
via templates. It almost works. Almost. When it doesn't,
someone is stuck debugging a huge system with a reference count
error.

Where Go is allowed to call C, keep the interface dumb.
The C side should not create or delete Go objects, or vice
versa.

John Nagle

[Ziad Hatahet]

The day after I wrote that, I read this in the digest for

    That's the trouble with trying to implement reference counting

via templates.  It almost works.  Almost.  When it doesn't,
someone is stuck debugging a huge system with a reference count
error.

Isn't the problem here because of either multithreading, or someone accessing the underlying pointers in a way they should not have in the first place? Why do you point out that it is a problem caused by templates (genuinely curious).

Thanks

--
Ziad