Re: Lock-free reference counting

Chris M. Thomasson wrote:
"Jon Harrop" <jon@xxxxxxxxxxxxxxxxx> wrote in message
news:8radna-lq4jsgqnUnZ2dnUVZ8tDinZ2d@xxxxxxxxxxxxxxxxx
Stephen Howe <sjhoweATdialDOTpipexDOTcom> wrote:
You said, "Which are scattered across memory.". I am pointing out that
the counters are _NOT_ scattered in memory...

That is incorrect.

if the reference counters are instrusive, the reference counters are
adjacent in memory to the object they count.

The objects themselves are scattered across memory => the references in
them
are also scattered.

Why do you "seem" to assume that the objects are always scattered across
memory?

That is the null hypothesis.

As to your last statement, that is only true if the object is passed
by value, it is not true if passed by reference or as a pointer, the
reference counts are _NEVER_ bumped.

Reference counts only exist to get bumped and they are bumped under a
variety of different circumstances including many where the data in the
object itself is not touched.

Passing objects to functions and procedures are one case where the counts
do not have to be mutated. In fact, the only time I ever need to
explicitly mutate counters is right before I hand a pointer to an object
off to another thread, and when a thread is done with a "shared" object.

Counter bumps can theoretically be optimized away in a variety of specific
circumstances (e.g. pass by reference to a function on the current thread).
My point is that real compilers do not automate these optimizations. So
either ordinary reference counted smart pointers are slow or you optimize
by hand, in which case you cannot claim to be using automatic memory
management and would be better off adopting a more efficient solution
anyway.

Even swapping a pair of reference counted smart pointers in an array
incurs several memory accesses to locations that would otherwise have
been untouched.

You can swap two reference counted objects without mutating their counts.

In theory, yes. In practice, GCC compiles the following C++ into a program
that is ~2x slower than the equivalent OCaml and which spends 60% of its
time bumping counters unnecessarily:

#include <iostream>
#include <vector>
#include <algorithm>
#include <boost/shared_ptr.hpp>

using namespace std;
using namespace boost;

int cmp(shared_ptr<int> a, shared_ptr<int> b)
{
return *a < *b;
}

int main(int argc, char *argv[])
{
vector<shared_ptr<int> > a;
const int n = (argc > 1 ? atoi(argv[1]) : 1000000);
cout << n << endl;
for (int i=0; i<n; ++i)
{
shared_ptr<int> k(new int);
*k = n - i;
a.push_back(k);
}
sort(a.begin(), a.end(), cmp);
return 0;
}

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
.

Relevant Pages

  • Re: How java passes object references?
    ... to think of them as being a specific location in a larger block of memory ... Whether a language passes by reference or by value, ... is a pointer pointing at the memory block. ... So when allocating local memory for o, it would simply allocate a ...
    (comp.lang.java.programmer)
  • Re: Lock-free reference counting
    ... Incrementing and decrementing scattered memory locations is the ... main reason reference counting is so slow. ... large blocks of such adjustments per page, ... to contain any long-lived pointer loops, ...
    (comp.programming)
  • Re: in defense of GC (was Re: How come Ada isnt more popular?)
    ... You can still have memory leaks ... pointer that still refers to allocated memory, ... Instead one simply clears the reference to the root of entire complex ...
    (comp.lang.ada)
  • Reference vs Pointer redux
    ... the distinction between a reference and a pointer. ... I pass parameters to a function by reference when I need to have the ... it's actually the memory address of the variable that is passed. ... I know that a pointer is a type of variable in C++ that holds the ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Design of image & view classes?
    ... >>will now point to invalid memory. ... >>would be usefull to prevent unnecessary copying, ... > that returns a pointer to the memory - temporarily. ... reference to the original image. ...
    (comp.lang.cpp)