Re: Lock-free reference counting

Juha Nieminen <nospam@xxxxxxxxxxxxxx> wrote:

I'm getting tired of your utter stupidity.

That's a shame. He's not the one that's being stupid on this point.

You know, for someone who complains about garbage collectors a lot, you
don't seem to have a particularly strong grasp on how they, or language
runtimes in general, work. I don't know how many programming languages
you actually know, but wide experience will serve you well.

The scope of the reference at the language level determines where that
reference stops pointing to the object.

False. Consider the C fragment

typedef struct { int splat; } thing;
typedef struct { int splot; } otherthing;

extern otherthing *make_otherthing(void);
extern void twiddle(thing *);

void foo(thing *t)
otherthing *o = make_otherthing();
t->splat = o->splot;

The scope of t is the entire function foo, agreed? Now let's look at
what GCC does to it.

.file "buf"
.p2align 4,,15
..globl foo
.type foo, @function
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $4, %esp
movl 8(%ebp), %ebx
call make_otherthing
movl (%eax), %eax
movl %eax, (%ebx)
movl %ebx, 8(%ebp)
addl $4, %esp
popl %ebx
popl %ebp
jmp twiddle
.size foo, .-foo
.ident "GCC: (Debian 4.3.2-1) 4.3.2"
.section .note.GNU-stack,"",@progbits

This is raw GCC output, for Intel x96. I've not molested it in any
way. (You can verify this if you like: I'm using Debian gcc 4.3.2-1; I
used the options gcc -O2 -xc -S -o-. My example source is frivolous,
but the generated code is totally real.

Here's the interesting part of the code again, this time with a
commentary. (Remember that GCC writes destinations on the right.)

pushl %ebp ; here we build a stack frame...
movl %esp, %ebp
pushl %ebx ; ebp is caller-saves and we want it
subl $4, %esp ; not quite sure why this is here
movl 8(%ebp), %ebx ; grab t from caller's arguments, put in ebx
call make_otherthing ; get o (left in eax)
movl (%eax), %eax ; fetch o->splot -- clobbers o in eax!
movl %eax, (%ebx) ; store in t->splat
movl %ebx, 8(%ebp) ; bizarre -- it's already there
addl $4, %esp ; undo pointless stack twiddle
popl %ebx ; restore caller's registers
popl %ebp
jmp twiddle ; and tailcall twiddle

The important point is that after the movl (%eax), %eax, the value of o
is lost forever! The reference's lifetime is considerably shorter than
the variable's scope.

It would be nice to say that the scope provides an upper bound on the
lifetime of the value, but even that's not true, bearing in mind that it
might persist as debris in a stack-allocated register variable for
longer than one might expect, simply because the compiler decided to
postpone cleaning it up.

The GC cannot collect the object as long as some reference is pointing
to it. The only way for it to collect it is if no reference is
pointing to it anymore.

This is true.

The scope of the reference at language determines how long the
reference lives.

And this is a repetition of the above false claim.

Of course a GC is completely oblivious to scope. It only cares about
whether a reference to the object exists or not.

And this is true again.

In other words, at some point the compiler determines that it's ok to
drop the reference, in other words, end its scope.

It might help if we explained that scope isn't really a concept about
variables at all. It's a concept about /names/ and /bindings/.

At any point in its processing of a source file, a compiler has an idea
of what various identifiers `mean': some will refer to types, some to
functions, others to variables. These meanings we call bindings.
Bindings are introduced by various language constructs. In C, variable
declarations are an obvious example; function parameters are another.
The region of the program for which a particular binding holds is called
its scope.

(I've omitted lots of stuff on dynamic binding, and mess to do with how
global bindings work in order to keep this description simple.
Apologies if I've missed anything important out. There's also a
distinction to be made between compile-time bindings and runtime
bindings, and I'm just not going there for now.)

It so happens that, in C, variables with automatic storage duration have
lifetime which is related to the scope of the corresponding binding.
This is not an accident: it's simple for programmers to deal with, and
easy for the compiler to arrange. But here it's important to see the
distinction. The connection between lifetime and scope is not absolute:
variables with static storage duration have lifetime which is very
different from the scope of their bindings, for example. Other
languages have different rules: in most function languages, including
Lisp and Scheme, have unlimited lifetimes for all variables, because
this is convenient (essential?) for programming with closures.

So, to repeat your claim:

In other words, at some point the compiler determines that it's ok to
drop the reference, in other words, end its scope.

You mean `end its lifetime'. But, as I showed with the explicit code
example, the compiler is free to (and will!) end the lifetime early if
nobody will care.

The GC looks if the reference exists, and the existence of the
reference is determined by its scope.

I hope you can now see why this is wrong.

Of course it has. The GC can *not* collect the object as long as
there's a reference pointing to it, and the lifetime of the reference is
determined by its scope.

You keep saying that. You keep being wrong.

No they weren't. In your example the scope of the garbage-collected
reference was shorter than in the equivalent C++ program. In your
artificial example you assume that the compiler drops the reference as
soon as it's not needed anymore, in other words, shortens its scope

You're still confused about scopes and lifetimes (not surprisingly
because I've not posted this article yet).

If the reference was reference-counted, than just the act of
shortening its scope would destroy the object immediately.

The difference is that ending the life of a reference-counted object is
nontrivial compared to simply overwriting a pointer, which is all that's
necessary in a garbage collected world.

-- [mdw]