multithreading.

[Chris Thomasson]

Chris Thomasson wrote:
[...]
Yes: the task rewrites expressions trees. There is a very similar C++
program here:

http://www.codecodex.com/wiki/index.php?title=Derivative
[...]

[...]

[...]
Alls I have to do is replace 'Var, Int, Plus and Times' with the VERY
simple cache outlined above and I know it will cut the number of
new/delete calls by a large margin. That about all I can do in C++. Is
that fair?

Also, I would need to create a special virtual function or id in the base
class which allows be to replace delete calls. Sketch:
___________________________________________________________________________
class Base {
public:
virtual ~Base() {};
virtual void CacheDelete() = 0;
virtual const Base *clone() = 0;
virtual const Base *d(const std::string &v) const = 0;
virtual std:stream &print(std:stream &o) const = 0;
};


#define INT_DEPTH() 10000


struct Int : public Base {
int n;
Int* m_next;

Int(int m) : n(m) {}
~Int() {}

void Ctor(int m) {
n = m;
}

static Int* g_head;
static int g_depth;

void CacheDelete() {
CachePush(this);
}

static Int* CachePop(int const m) {
Int* _this = g_head;
if (! _this) {
_this = new Int(m);
} else {
g_head = _this->m_next;
--g_depth;
_this->Ctor(m);
}
return _this;
}

static void CachePush(Int* const _this) {
if (g_depth < INT_DEPTH()) {
_this->m_next = g_head;
g_head = _this;
++g_depth;
} else {
delete _this;
}
}


const Base *clone() { return CachePop(n); }
const Base *d(const std::string &v) const { return CachePop(0); }
std:stream &print(std:stream &o) const { return o << n; }
};


Int* Int::g_head = NULL;
int Int::g_depth = 0;
___________________________________________________________________________



This is only the Int class, but you get my drift... I would replace delete
calls on the Base with Base->DELETE(). This would be simpler than an id.

 

[Dilip]

Jon Harrop wrote:

[...]

{
Bar bar()
f(bar);
g()
}

Reference counting will keep "bar" alive until its reference count happens
to be zeroed when it drops out of scope even though it is not reachable
during the call to "g()". Real garbage collectors can collect "bar" during
the call to "g" because it is no longer reachable.

The above is pretty much what you get from

using (Bar bar = new Bar()) {
f(bar);
g();
}

in GC environment. See

http://msdn2.microsoft.com/en-us/library/yh598w02(VS.80).aspx

So GCs can clearly collect sooner than reference counters.

You probably mean

using (Bar bar = new Bar()) {
f(bar);
}
g();

which is pretty much what you get from

{
Bar bar();
f(bar);
}
g();

;-)

I am not so sure. In the former example all the 'using' block does is
to call bar.Dispose() as a syntactic shortcut on reaching the closing
scope. That is useful only if Bar is encapsulating some kind of non-
memory resource like a file handle or a socket and that needs to be
closed as soon as f(bar) returns. The 'bar' object itself (after
f(bar) returns) is only _eligible_ for collection. Its memory will
_not_ be reclaimed until the GC actually runs (which won't happen
until there is a memory pressure in Gen 0 regions).

In the latter case, bar is destructed right after f(bar) returns which
is what I thought C++ meant by _deterministic_ destruction.

This is what James Kanze has been lamenting through out this thread.

Am I wrong?

 

[Alexander Terekhov]

Jon Harrop wrote:

[...]

{
Bar bar()
f(bar);
g()
}

Reference counting will keep "bar" alive until its reference count happens
to be zeroed when it drops out of scope even though it is not reachable
during the call to "g()". Real garbage collectors can collect "bar" during
the call to "g" because it is no longer reachable.

The above is pretty much what you get from

using (Bar bar = new Bar()) {
f(bar);
g();
}

in GC environment. See

http://msdn2.microsoft.com/en-us/library/yh598w02(VS.80).aspx

So GCs can clearly collect sooner than reference counters.

You probably mean

using (Bar bar = new Bar()) {
f(bar);
}
g();

which is pretty much what you get from

{
Bar bar();
f(bar);
}
g();

;-)

I am not so sure. In the former example all the 'using' block does is
to call bar.Dispose() as a syntactic shortcut on reaching the closing
scope. That is useful only if Bar is encapsulating some kind of non-
memory resource like a file handle or a socket and that needs to be
closed as soon as f(bar) returns. The 'bar' object itself (after

IOW, you want some observable behavior (other than memory reclamation,
see below) to take place precisely at scope exit.

f(bar) returns) is only _eligible_ for collection. Its memory will
_not_ be reclaimed until the GC actually runs (which won't happen
until there is a memory pressure in Gen 0 regions).

In the latter case, bar is destructed right after f(bar) returns which
is what I thought C++ meant by _deterministic_ destruction.

Think of the latter case with bar being a handle/wrapper for GC_MALLOC'd
memory (using Boehm collector or some such) containing a bunch of
something "like a file handle or a socket and that needs to be closed as
soon as f(bar) returns."

regards,
alexander.

 

[Dilip]

Jon Harrop wrote:
[...]
{
Bar bar()
f(bar);
g()
}
Reference counting will keep "bar" alive until its reference count happens
to be zeroed when it drops out of scope even though it is not reachable
during the call to "g()". Real garbage collectors can collect "bar" during
the call to "g" because it is no longer reachable.
The above is pretty much what you get from
using (Bar bar = new Bar()) {
f(bar);
g();
}
in GC environment. See
http://msdn2.microsoft.com/en-us/library/yh598w02(VS.80).aspx
So GCs can clearly collect sooner than reference counters.
You probably mean
using (Bar bar = new Bar()) {
f(bar);
}
g();
which is pretty much what you get from
{
Bar bar();
f(bar);
}
g();
;-)

I am not so sure. In the former example all the 'using' block does is
to call bar.Dispose() as a syntactic shortcut on reaching the closing
scope. That is useful only if Bar is encapsulating some kind of non-
memory resource like a file handle or a socket and that needs to be
closed as soon as f(bar) returns. The 'bar' object itself (after

IOW, you want some observable behavior (other than memory reclamation,
see below) to take place precisely at scope exit.

f(bar) returns) is only _eligible_ for collection. Its memory will
_not_ be reclaimed until the GC actually runs (which won't happen
until there is a memory pressure in Gen 0 regions).

In the latter case, bar is destructed right after f(bar) returns which
is what I thought C++ meant by _deterministic_ destruction.

Think of the latter case with bar being a handle/wrapper for GC_MALLOC'd
memory (using Boehm collector or some such) containing a bunch of
something "like a file handle or a socket and that needs to be closed as
soon as f(bar) returns."

I am still not getting it. In the former case, non-memory resources
are disposed of promptly at the end of scope. In the latter case, not
only are the non-memory resources disposed of, the destructor ensures
that the memory used by that object is also released. Isn't there a
difference?

 

[Alexander Terekhov]

Dilip wrote:
[...]

I am still not getting it. In the former case, non-memory resources
are disposed of promptly at the end of scope. In the latter case, not
only are the non-memory resources disposed of, the destructor ensures
that the memory used by that object is also released. Isn't there a
difference?

In the latter case, the destructor can basically do the same as
IDisposable.Dispose() in the former case and simply "offload" memory
release to some garbage collector like Boehm's one ("leaking" memory
garbage and relying on GC to collect it).

regards,
alexander.

 

[Dmitriy V'jukov]

That is irrelevant. Your argument in favor of reference counting was
completely fallacious.

You claimed was that reference counting is "more accurate than a traditional
GC could ever be". Consider:

{
Bar bar()
f(bar);
g()
}

Reference counting will keep "bar" alive until its reference count happens
to be zeroed when it drops out of scope even though it is not reachable
during the call to "g()". Real garbage collectors can collect "bar" during
the call to "g" because it is no longer reachable.

So GCs can clearly collect sooner than reference counters.

Can Real garbage collectors do this w/o help of compiler? I don't
think so...
With help of compiler reference-counting can easily collect 'bar'
precisely and promptly at the end of f().

You are mixing up GC with language, compiler and runtime.


Dmitriy V'jukov

 

[Dmitriy V'jukov]

Reference counts consume a lot more space.


Yes. For example, OCaml hides two bits inside each pointer totalling zero
overhead. In contrast, a reference counting system is likely to add a
machine word, bloating each and every value by 8 bytes unnecessarily on
modern hardware.

If you want as big overhead as possible then you can even add 1 MB per
each and every value. If you don't then you can use reference-counting
scheme w/o per object overhead.


Dmitriy V'jukov

 

[Dmitriy V'jukov]

Reference counts consume a lot more space.


Yes. For example, OCaml hides two bits inside each pointer totalling zero
overhead. In contrast, a reference counting system is likely to add a
machine word, bloating each and every value by 8 bytes unnecessarily on
modern hardware.

If you want as big overhead as possible then you can even add 1 MB per
each and every value. If you don't then you can use reference-counting
scheme w/o per object overhead.


Dmitriy V'jukov

 

[Dmitriy V'jukov]

Can Real garbage collectors do this w/o help of compiler? I don't
think so...
With help of compiler reference-counting can easily collect 'bar'
precisely and promptly at the end of f().

You are mixing up GC with language, compiler and runtime.


Dmitriy V'jukov

 

[Dilip]

No. I am saying that GC should not be able to collect the Bar object because
there is a live pointer/reference to it (e.g., the 'bar' variable).


A live pointer to an object means that its reachable and cannot be reaped by
the GC.

Chris, you can ram this point another million times and you'll get
back the same answer from Harrop -- that its "irrelevant".

When he says "GCs collect unreachable values" he will deliberately
fail to admit that unreachability of an object simply means that it is
__eligible__ for GC -- it does __not__ mean and will __never__ mean
that a GC will automatically happen and the object will be reaped then
and there. This is the essence of the non-determinism we always talk
about in the GC world. In this respect, GC is vastly different from
ref-counting where if the last reference drops the object is
__immediately__ destroyed. I have said this before -- COM has been
doing this for eons.

There is no sense wasting your breath on this.

 

[Dilip]

Excellent! You are now moving towards the correct way of looking at this.
You are basically saying that a GC should not be able to collect "bar"
because it is still in scope.

GC will not collect an object as long as there are live references to
it. Scope never had anything to do with it. Do you think the "using"
block in C# relies on scope?

You are correct that "bar" is in scope. However, GCs collect unreachable
values and scope has nothing to do with reachability.

... unreachable values are collected **only** when the GC is triggered
and you **never** know when that can happen. As a result the object
may be unreachable but its still hanging out there. This is the non-
determinism Chris has been trying to ram on you for the past, uh,
several million posts.

Scope is simply the

way we lay out source code. Reachability refers to whether or not global
roots (e.g. pointers on the stack or in registers) can follow a dependency
path through a snapshot of the heap at any given moment in time to reach a
given value. If there is no path from the roots to a given value then that
value is unreachable by definition. Note that this has absolutely nothing
to do with scope.

No one ever disputed any of this. In fact if you re-read (i.e if you
even bothered to read them in the first place) some of Jerry Coffin's
posts he says exactly this. Sounds like a straw-man to me.

It is precisely this discrepancy between scope and reachability that makes
reference counting keep values alive unnecessarily.

what do you mean?

{
ISomeType* obj = CoCreateInstance(....); // this api does the
AddRef
obj->DoSomethingWithThisObject();
obj->Release();
// do a lot of stuff here...
}

A properly written Release function will destroy obj right at that
point which is ref-counting done the COM way. are you saying obj is
kept alive until the end of the block? That might happen only if you
wrap ISomeType in some kind of smart pointer which will call Release
at the end of the block -- but I am not doing that here.

You are also correct that we can manually work around the problem of "bar"
being artificially kept alive during the call to "g()" by adding a new
nested scope. However, there are two problems with your solution:

1. This still isn't necessarily collecting "bar" as early as possible
because it may well become unreachable during the call to "f".

so what? being unreachable does not mean a GC will collect it right
away? in that sense its still being kept alive.

2. There still exists code (e.g. my example) where reference counting keeps
values alive unnecessarily.

How in the God's name can that be possible? Either you call an
explicit API that will decrement the ref-count or you wire up the dtor
in such a way that an end-of-scope takes care of such decrements. In
both cases, 0 means blow the object out of the water.

In fact, you can persue your idea further and try to always deallocate
values at the earliest opportunity. However, this culminates in a technique
called regioning that makes no use of reference counts and, consequently,
cannot be classified as a reference counting algorithm.

Regioning? Did you just pull that word out of your hat? Can you pass
me any links or papers mentioning such a concept?

 

[Gerhard Fiedler]

Yet real GCs do collect the value.

The difference seems to be what this article
<http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)> calls
the difference between "syntactic garbage" (no pointer anymore to an
object) and "semantic garbage" (pointers to an object may still exist, but
they won't be used anymore): "The reachability definition of "garbage" is
not optimal, insofar as the last time a program uses an object could be
long before that object falls out of the environment scope. A distinction
is sometimes drawn between syntactic garbage, those objects the program
cannot possibly reach, and semantic garbage, those objects the program will
in fact never again use."

From this article it seems that most GCs reclaim only syntactic garbage,
not semantic garbage. Are there any that really do this?

Gerhard

 

[George Peter Staplin]

Please show me a 100% accurate GC; good luck finding one. Well, let me help
you... A proxy GC can be accurate indeed. But, they are hardly traditional.
In fact they were invented on comp.programming.threads by Joe Seigh.

There are accurate GC. However, there are not many for C or C++. You
really need compiler support in C for a proper non-conservative GC.

It will only collect anything when the GC decides to run!! It does not run
all the time. If it did the performance would be so crappy that nobody would
every even think about using it. If you think this is comparable to a proxy
GC then your simply not getting it. Anyway, traditional GC is NOT about
performance, its about helping some programmers that do not know how, or
want, to manage their memory manually.

That is not true. There are GC that run all of the time. Dijkstra
wrote a concurrent collector many years ago, with a very clever coloring
algorithm designed to make objects move in stages, while preventing the
reuse of an object that is still in use.

I recommend that you read the book _Garbage Collection: Algorithms for
Automatic Dynamic Memory_. That book covers Dijkstra's work, and the
newer concurrent generational collectors used in languages like Java.

It's very difficult to make a GC work well in all situations and usage
patterns, though in practice that isn't usually a problem. The primary
language I work with uses reference-counted objects.

Reference counting introduces problems with circular references, and
thereby requires copying more data in some circumstances. On the other
hand reference counting tends to have more consistent runtime costs, so
it's sometimes preferable in realtime cases.

Knuth's TAOCP refers to a paper about a method for circular lists that
use reference counting, but I haven't thus far been able to find a copy
freely available online. I think it was used in a LISP or Scheme
implementation.

Thankfully, mark-and-sweep (from the 1950's IIRC) is not the end of the
research on GC.


George

 

[Dmitriy V'jukov]

That is irrelevant. Your argument in favor of reference counting was
completely fallacious.

You claimed was that reference counting is "more accurate than a traditional
GC could ever be". Consider:

{
Bar bar()
f(bar);
g()
}

Reference counting will keep "bar" alive until its reference count happens
to be zeroed when it drops out of scope even though it is not reachable
during the call to "g()". Real garbage collectors can collect "bar" during
the call to "g" because it is no longer reachable.

So GCs can clearly collect sooner than reference counters.

Can Real garbage collectors do this w/o help of compiler? I don't
think so.
With help of compiler reference-counting can promptly collect 'bar'
precisely at end of f().


Dmitriy V'jukov

 

[Jerry Coffin]

[ ... ]

Well, I think that Jerry is trying to deal with a troll who is used to
making false claims on purpose.

I realized from the beginning that the attempt was undoubtedly futile,
but I decided to make a dast-ditch attempt at educating each, using
what's I'd characterize as a Dogbert-style of "education through abuse."

In this case, however, it's obvious that neither Jon nor Razii is going
let even the most obvious facts get in the way of concluding whatever
they wish.

Trying to change the mind of somebody like Jon or Razii is clearly a
waste of time and effort. OTOH, if their posts receive no replies at
all, it's entirely possible that somebody else reading the thread (nor
or later) could conclude that they're providing reasonable and accurate
information.

It might seem that any intelligent person would see through such obvious
nonsense, but IME, that's not necessarily the case. Just for one
example, I examined the code behind one set of benchmarks a number of
years ago. Looking at it, I found things like this:

init0 = (int*)calloc(max_x,sizeof(int));
init1 = (int*)calloc(max_x,sizeof(int));
init2 = (int*)calloc(max_x,sizeof(int));
for (x=0; x<max_x; x++) {
init2[x] = 0;
init1[x] = 0;
init0[x] = 0;
}

To anybody who knows C or C++ at all, this code is clearly nonsense --
if you're going to zero the code immediately after allocation, there's
no reason to use calloc.

Back when I first looked at this, I spent some time looking at
benchmarks that purported to compare the speed of C and/or C++ with
Java. At least where source code was provided, the results were
uniformly dismal -- none of them seemed to even make a serious attempt
at accurate timing (e.g. most measured wall time instead of CPU time),
code that anybody would really write (see above) or much of anything
else.

I couldn't find a single benchmark that looked like it could produce a
result that meant anything. The results were fairly uniform, however,
and apparently based on that, some seemingly intelligent people seemed
to believe they meant something. Based on that I made a conscious
decision that when I saw similar nonsense, I'd at least attempt to
provide a little bit of factual information to counterbalance the
nonsense. As much as possible, I avoid it being a matter of taking my
word or theirs though -- I attempt to provide real evidence (e.g. links
to well-known papers by respected authors) so anybody who's really
interested can get started on real research.

I don't for a moment dream that mere facts are going to change the mind
of somebody like Razii or Jon Harrop. I do hope that there are a few
people in the world who might be a bit more open to reality, however.

 

[Jerry Coffin]

[ ... ]

So your performance claims are not based upon benchmark results.

This is the kind of post that makes it obvious you're just trolling, so
any further replies are pointless.

You conclusion would make sense if and only if the benchmark you cited
was the only one that existed or could exist. Since we both know that's
not the case, there is no logic to support your conclusion.

Your post reflects either a complete lack of honesty, or else a complete
failure to grasp even the most minimal requirements of logic.

 

[Jerry Coffin]

[ ... ]

From this article it seems that most GCs reclaim only syntactic garbage,
not semantic garbage. Are there any that really do this?

Yes and no. There's basically no such thing as a garbage collector (per
se) that does so.

At the same time, many of the same languages that are typically (or, in
some cases, mandatorily) implemented with garbage collection also often
include things like (again, optional or mandatory) tail recursion
elimination. That tail recursion elimination often makes more garbage
detectable.

For example, consider a stereotypical tail-recursive function, something
like:

f() {
X *x=new X;
// other stuff
if (something)
f();
}

Now, if you don't eliminate the tail recursion, each call to f results
in a new stack frame, so all the pointers to the X's remain on the
stack, and the garbage collector has to treat all of them as potentially
active. If the compiler eliminates the tail recursion, turning the code
into something on the general order of:

f() {
do {
X *x=new X;
// other stuff
} while (!something);
}

Now, instead of each invocation getting a new pointer, each time through
the loop, the pointer is overwritten with the address of the new object
that's allocated. That means there's no longer any pointer to the object
allocated in the previous iteration, so the garbage collector can now
detect that the object really is garbage, and therefore re-uses that
space.

Roughly similar optimizations can be applied in cases where (for
example) a function finishes by chaining to another function. Basically,
the compiler morphs the current stack frame into the stack frame for the
new function. In the process, pointers that aren't needed in the called
function typically get overwritten with new data. As a result, there are
no longer any pointers to whatever data was allocated in the stack frame
as it existed before the chaining took place. This, again, allows the
garbage collector to detect that whatever those pointers referred to are
now garbage.

 

[George Peter Staplin]

How do the mutators interact with the GC which "runs all the time"? Are you
taking about threads from a per-application GC thread pool running non-stop?
How much GC-to-thread introspection in going on? Any thread synchronization
between GC thread(s) and mutator threads?

This explains how Dijkstra's GC algorithm works (with a dedicated
"processor"):
http://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD492.html

There might also be a later writing about his work on that.

I think that Steele also wrote a variation on Dijkstra's algorithm. If
you have an ACM account you can probably access it.

Guy L. Steele, Jr., Multiprocessing Compactifying Garbage Collection,
Comm. ACM, Sep. 1975, vol. 18, No. 9, pp. 495-508.

The are proxy garbage collectors which can workout very well because they
can be made deterministic. Here is some more information on proxy gc:

http://groups.google.com/group/comp.programming.threads/msg/41f29efe33e7f124

http://groups.google.com/group/comp...=en&group=comp.programming.threads&q=proxy+gc

http://groups.google.com/group/comp.lang.c++/msg/e24a9459777ec430


RCU is also a proxy gc. The quiescent states at analogous to an application
thread releasing a reference to a proxy collector.

I'll read those. Thank you.


George

 

[Jerry Coffin]

[ ... ]

There are accurate GC. However, there are not many for C or C++. You
really need compiler support in C for a proper non-conservative GC.

Not disagreeing at all, but just to clarify: you really need compiler
support to have non-conservative GC in almost any language.

[ ... ]

That is not true. There are GC that run all of the time. Dijkstra
wrote a concurrent collector many years ago, with a very clever coloring
algorithm designed to make objects move in stages, while preventing the
reuse of an object that is still in use.

Most concurrent collectors don't run all the time though. While it's
possible to do so, it's almost always a lousy idea. In fact, one of the
major advantages of most implementations of GC over most implementations
of manual collection is specifically that they work lazily.

When/if you really try to collect garbage immediately after it's
generated, you end up doing a collection when there's very little
garbage. That's generally quite inefficient -- with a mark/sweep style
of collector, it means that your heap is generally fairly fragmented.
With a copying collector, it means most objects are still alive when you
do a collection -- and the time taken by a copying collector is (mostly)
proportional to the number of objects that remain alive when the
collection cycle runs.

As such, with any sort of copying-based collector, you generally want to
delay collection as long as possible, to give as many of the objects in
the current heap a chance to die before the collection takes place.

[ ... ]

Thankfully, mark-and-sweep (from the 1950's IIRC) is not the end of the
research on GC.

Far from it. In fact, it's pretty much just the beginning of GC
research.

Since this is being discussed in comp.lang.c++ (among other places) I
think it's worth adding out one other point though: most GC research is
conducted using languages (e.g. Lisp, Smalltalk, Self) where _all_ (or
at least almost all) variables live in the garbage collected memory
pool, and all that's ever created on the stack are references, pointers,
or whatever you prefer to call them, to the real objects.

This means a lot of GC research is only marginally applicable to a
language like C or C++. It's almost unimaginable that anybody (except,
perhaps, a recent Java expatriate) would write C++ code like:

int *i=new int;
for (i=0; i<whatever; ++i)
// ...

In C++ (and C, for that matter) such temporary objects are inevitably
created directly on the stack, NOT dynamically allocated. This means
that most objects that are created on the heap are likely to be
relatively long-lived. That, in turn, means that other forms of
collection (including reference counting) are generally likely to be FAR
more competitive with things like copying collectors in C++ than would
appear to be the case in most GC research.

 

[Jerry Coffin]

[ ... ]

How do the mutators interact with the GC which "runs all the time"? Are you
taking about threads from a per-application GC thread pool running non-stop?
How much GC-to-thread introspection in going on? Any thread synchronization
between GC thread(s) and mutator threads?

Most concurrent garbage collectors require some sort of either read
barriers or write barriers. As such, they're really only somewhat
concurrent -- they don't (necessarily) require that you stop the world,
but they may stop certain parts of the world. In fact, some go so far as
to call them "mostly concurrent" instead of truly "concurrent." E.g.
see:

http://research.sun.com/techrep/2000/smli_tr-2000-88.pdf

Dijkstra's algorithm is typically implemented using read barriers. These
are (horrendously) inefficient without direct hardware support (that's
not present in typically mainstream hardware).

If you want to look at concurrent GC in more detail, you might want to
look at what claims to be _the_ Garbage Collection Bibliography:

http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbibH.html