Reference counting 
Author Message
 Reference counting

What does the expression "reference counting" mean?
Can somebody tell me?

Janos Blazi



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting

Quote:

>What does the expression "reference counting" mean?
>Can somebody tell me?

It's a garbage collection technique that works by having each object
maintain a count of the number of pointers that refer to it.  Every time a
pointer is created, the counter in the object it points to is increased.
Every time a pointer is deleted, this counter is decremented.  And when a
pointer is modified, the counter in the old object is decreased, while the
counter in the new object is increased.  Whenever a counter drops to 0, the
object has become garbage and may be collected; if the object contains any
pointers, they get deleted in the process, which will decrement the
counters in the objects they point to, and so on.

Reference is not usually used as the sole GC mechanism in a general system,
because it will never clean objects that are involved in circular reference
chains.  However, it can be used in applications that are known not to have
such chains or take care to deal with them appropriately.  Some programming
language implementations also use RC as the primary GC mechanism, but will
revert to a more effective GC mechanism when necessary (I think most
Smalltalk implementations are like this).

--

GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting
In article

Quote:

>What does the expression "reference counting" mean?
>Can somebody tell me?

Reference counting means keeping track of how many things
refer to a particular object/chunk of memory. If nothing
refers/has a pointer to the thing, then for practical purposes
it no longer exists and the space it takes can be reclaimed
(see garbage collection) for other objects. (Analogy to a disk
directory: if no file descriptor contains a reference to a particular
block on disk, that block is free for use.) The reference count is
usually stored with the object in question, and incremented or
decremented automatically by routines that handle references to
objects.

Reference counting is one way of managing memory allocation
but is not generally used in lisp in its (r.c.'s) most straightforward form.

paul        somewhat surprised by such a basic question



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting

Quote:

> What does the expression "reference counting" mean?
> Can somebody tell me?

      One day a student came to Moon and said, "I understand how to
      make a better garbage collector. We must keep a reference count
      of the pointers to each cons." Moon patiently told the student
      the following story:

           "One day a student came to Moon and said, `I understand how
           to make a better garbage collector . . . '"

Christopher



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting
In my native tongue Hungarian there is proverb: "There are no old jokes,
there are only old men. For a new born are all jokes new."

For ROBERT:
"Nincsenek rgi viccek, csak ?reg emberek vannak. Egy jszl?ttnek minden
vicc j."

Janos Blazi



Quote:
> In article


> >What does the expression "reference counting" mean?
> >Can somebody tell me?

> Reference counting means keeping track of how many things
> refer to a particular object/chunk of memory. If nothing
> refers/has a pointer to the thing, then for practical purposes
> it no longer exists and the space it takes can be reclaimed
> (see garbage collection) for other objects. (Analogy to a disk
> directory: if no file descriptor contains a reference to a particular
> block on disk, that block is free for use.) The reference count is
> usually stored with the object in question, and incremented or
> decremented automatically by routines that handle references to
> objects.

> Reference counting is one way of managing memory allocation
> but is not generally used in lisp in its (r.c.'s) most straightforward
form.

> paul        somewhat surprised by such a basic question



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting

Quote:

> language implementations also use RC as the primary GC mechanism, but will
> revert to a more effective GC mechanism when necessary (I think most
> Smalltalk implementations are like this).

I find this a little weird.  The recent research I've seen indicates that a good GC

is better than ref counting, particularly when there is a reasonable amount of
objects changing hands, and absolutely in a multithreaded environment.

dave



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting

Quote:


> > somewhat surprised by such a basic question

> In my native tongue Hungarian there is proverb: "There are no old
> jokes, there are only old men. For a new born are all jokes new."

You are missing the point. The fact that the answers to these "basic
questions" may be new and interesting revelations to you is not
surprising. What is surpising is that you seem to have the expectation
that more experienced people will continue to volunteer their precious
time answering such questions, when the person asking them obviously
has made zero effort trying to find answers on his own.

Joachim

--




Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting


Quote:
> Some programming
> language implementations also use RC as the primary GC mechanism, but will
> revert to a more effective GC mechanism when necessary (I think most
> Smalltalk implementations are like this).

This is incorrect.  There hasn't been a reference counting based Smalltalk
implementation since Ungar's generational GC papers came out.  Even most
non-Xerox implementations of that era already had real GC as their memory
collection technique.  And they did it for the same reasons Lisper's have
known for years - systems that generate large numbers of small, short-lived
objects do better with GC than RC.

And don't try to mention this misconception on comp.lang.smalltalk, either.
You'll be lucky if your asbestos suit doesn't get burnt up.  This statement
is as insulting to Smalltalkers as the "All Lisps are interpreted" statement
is to Lispers.

At this point, the only people still thinking RC is a good memory management
technique are the brain damage cases (usually from the C++ camps) who (a)
are so used to NO memory management that they think ANY kind of memory
management is a good idea and (b) can't understand that anything other than
heavyweight objects need to be allocated.

faa



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting

[snip]

Quote:
> Some programming
> language implementations also use RC as the primary GC mechanism, but will
> revert to a more effective GC mechanism when necessary (I think most
> Smalltalk implementations are like this).

Actually, I don't believe any extent or historical implementation of
Smalltalk used this dual schema, and while there were probably a few
experimental or prototype systems which used reference counting as the
primary mechanism, I don't *think* than any production system did. The
Blue Book describes reference counting as a possible gc technique, but
the state of the art in Smalltalk GC is, FWICT, at least as good as the
state of the art in Common Lisp and Scheme implementations. Squeak, for
example, has a very interesting generational gc where the strategy is to
gc a small young pool very frequently. The pool is small enough that
gcing even on modest hardware takes very little--and predictable--time.
Full gcs are exceeding rare. This permitted Squeak to, for example, do
realtime FM synthesis with 4 voices (or something like that :)), again,
on fairly old macs. I don't think I've *ever* had a spontaneous
perceivable GC pause while working in Squeak. On the contrary, I find
that many large apps written in MCL flash the little GC cursor at me
quite a bit (my latest nemisis in this regard is StarLogo), but that
seems to be a problem with those apps rather than an inherent defect of
MCL, as I had no such troubles with SK8.

Interestingly, there was just a thread on the Squeak list about *adding*
reference counting for certain kinds of objects. (And it would be a good
thing, I think, for objects in need of finalization, filestreams,
sockets, etc.)

VisualWorks has extensive tuning capabilities for it's gc, but I don't
*think* reference counting is one of them. IMHO, once you've got full
garbage collection, reference counting is silly *except* for those
objects for which a guaranteed freeing is a very good idea. And that's a
relatively small number of objects.

CPython and Perl, OTOH, do in fact use nothing but reference counting.

(I still bet that an often gced small pool is probably a better idea, in
the long run. I think python holds onto reference counting to simplify
integration with C modules.)

Cheers,
Bijan.



Sat, 20 Apr 2002 03:00:00 GMT  
 Reference counting
You are right, I have not tried to find books on the subject. To tell you
the truth I would not even know where to start. An would be a lot of work. I
am reading the news and every now and then I ask a question.

But anyway: Isn't is a free newsgroup? Can't I ask as many questions as I
want to? NOBODY MUST ANSWER MY QUESTIONS. IF YOU DO NOT WANT TO ASK, SIMPLY
SKIP THEM. ALSO YOU CAN MARK THEM AS READ.

But a lot of people answer. What is wrong with that? I learn a lot, other
newcomers may learn a lot and even the experts cac clarify their positions.
Look at the threads I created.

So I do not understand your lack of patience. My questions, however naive or
stupid  they are, cannot disturb you in any tangible way. Or do you mean
"somebody with your history should not have the right to ask any questions"?

Janos Blazi



Quote:


> > > somewhat surprised by such a basic question

> > In my native tongue Hungarian there is proverb: "There are no old
> > jokes, there are only old men. For a new born are all jokes new."

> You are missing the point. The fact that the answers to these "basic
> questions" may be new and interesting revelations to you is not
> surprising. What is surpising is that you seem to have the expectation
> that more experienced people will continue to volunteer their precious
> time answering such questions, when the person asking them obviously
> has made zero effort trying to find answers on his own.

> Joachim

> --





Sun, 21 Apr 2002 03:00:00 GMT  
 Reference counting
* Janos Blazi -> Joachim Achtzehnter
| So I do not understand your lack of patience.

  then you should make an effort to understand people's lack of patience
  with you, rather than telling them there's something wrong with them
  because you don't understand something.  thinking very carefully about
  this now may be the best spent time of the rest of your life, as it may
  dramatically change the way you interact with people you don't know.

#:Erik



Sun, 21 Apr 2002 03:00:00 GMT  
 Reference counting

Quote:

> You are right, I have not tried to find books on the subject. To
> tell you the truth I would not even know where to start.

Most people these days would probably do an online search to
start. General Web search engines can dig up a lot of useful links,
and there is always www.deja.com to search newsgroup archives.

Quote:
> An would be a lot of work.

That was my point. You expect OTHERS to do the work for you, while your
effort is limited to "asking a question now and then".

Quote:
> But anyway: Isn't is a free newsgroup? Can't I ask as many questions
> as I want to? NOBODY MUST ANSWER MY QUESTIONS. IF YOU DO NOT WANT TO
> ASK, SIMPLY SKIP THEM. ALSO YOU CAN MARK THEM AS READ.
> [more angry bla bla omitted]

Yes, you can certainly continue behaving the way you do. You again
missed the point. I was not trying to stop you from doing anything,
this would have been hopeless, anyway. I was merely trying to help you
understand what the other poster meant with his remark.

Joachim

--




Sun, 21 Apr 2002 03:00:00 GMT  
 Reference counting

Quote:

>Actually, I don't believe any extent or historical implementation of
>Smalltalk used this dual schema, and while there were probably a few
>experimental or prototype systems which used reference counting as the
>primary mechanism, I don't *think* than any production system did. The
>Blue Book describes reference counting as a possible gc technique, but
>the state of the art in Smalltalk GC is, FWICT, at least as good as the
>state of the art in Common Lisp and Scheme implementations.

What I know about Smalltalk implementations I learned from the book
"Smalltalk-80: Bits of History, Words of Advice", which is a collection of
papers about Smalltalk implementations and analyses thereof.  Reference
counting is mentioned frequently.

Admittedly, this book was published 15 years ago, and the papers were
written when modern GC techniques (e.g. generational GC) were still active
research projects, whereas the papers describe the actual, deployed ST-80
implementations.

--

GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.



Sun, 21 Apr 2002 03:00:00 GMT  
 Reference counting

Quote:

> CPython and Perl, OTOH, do in fact use nothing but reference counting.
> (I still bet that an often gced small pool is probably a better idea, in
> the long run. I think Python holds onto reference counting to simplify
> integration with C modules.)

ref counting presumably has the advantage that you don't have to move
objects, which is death (or a lot of work) for C integration.  I guess
you could use a noncompacting mark-sweep GC though?

It also seems to me that ref counting, unless you work very hard at
it, is really bad for performance on modern HW because it increases
memory traffic a lot (you have to keep incrementing/decrementing
references) and memory bandwidth is a huge bottleneck for any modern
machine.  Someone once told me that one of the reasons for the bad
performance of large C++ systems is that they all really do ref
counting (because they have to do *some* mem management, and they are
unwilling to use, say, the Boehm collector or maybe they just don't
know about it), and they typically do it naively, and this basically
doubles memory traffic or something.

Someone (Duane!) will now point out that this is all wrong and you can
do ref counting with no overhead...

--tim



Sun, 21 Apr 2002 03:00:00 GMT  
 Reference counting
ftp.cs.utexas.edu/pub/garbage/ holds papers on garbage collection
and dynamic memory allocation, including Paul Wilson's survey paper
"Uniprocessor garbage collection techniques":

    ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps
    ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps   (extended draft)

rthappe



Sun, 21 Apr 2002 03:00:00 GMT  
 
 [ 74 post ]  Go to page: [1] [2] [3] [4] [5]

 Relevant Pages 

1. reference counting vs. gargabe collection

2. reference counting vs. GC again

3. Cycles in Lazy evaluation (was: Reference counting GC)

4. Reference counting GC for ML/Haskell?

5. Reference count GC on cyclic structures

6. ruby-gtk reference counting

7. Reference count based Scheme

8. reference-counting gc?

9. Question about Finalization Control and reference counting

10. Reference counting on MultiProcessor machines

 

 
Powered by phpBB® Forum Software