Back to General and Gameplay Programming

[C++] My reference-counting implementation

General and Gameplay Programming Programming

Started by Decrius January 09, 2009 06:19 AM

27 comments, last by visitor 15 years, 3 months ago

Decrius

100

Author

January 09, 2009 06:19 AM

Not so long ago I was advised to use boost::shared_ptr and not my own implementation. Using well tested libraries makes you're project more stable and I quite liked the idea how it makes sure unused data is deleted. I did some quick not very reliable test runs (as reliable as I can get) to see what the difference was between boost::shared_ptr, my old reference counting system I made half a year back (which syntax I dislike, since it requires you to use lose(), instead of delete) and just plain old new and delete without keeping track of anything. I'm a performance freak, so these were the measurements: if not keeping track is 100%, then boost was 233% and my method was 113%. The higher above 100%, the slower compared to tracking nothing at all. So, I created a new project and tried to make a reference counting implementation with more ease of use. I wanted it to use new and delete (not gain and lose, neither only new like for boost), be easy to add to any class, be transparent to the user and have very little overhead. I think I got the concept done, need to see what I'll throw if allocation goes awry, and the variables are non-descriptive. This is how it works, the reference counting system (NOTE: adding backslash after each row makes it all appear on one row with this syntax highlighter, so you'll have to add backslashes at all ends of the rows except the last):

#define REFERENCE_COUNTING(T)
    unsigned int reference_count;
public:
    static void *operator new (size_t size) throw (const char *)
    {
        void *p = malloc(size);
        if (!p)
        {
            throw "allocation failure";
        }
        T *b = (T *) p;
        b->reference_count = 0;
        return p;
    }
    
    static void operator delete (void *p)
    {
        if (p)
        {
            T *b = (T *) p;
            if (!b->lose())
            {
                free(p);
            }
        }
    }
    
    void gain()
    {
        reference_count++;
    }

private:
    bool lose()
    {
        if (!reference_count)
        {
            return false;
        }
        reference_count--;
        return true;
    }

public:
    unsigned int count()
    {
        return reference_count;
    }
private:

How it's implemented:

class B
{
    REFERENCE_COUNTING(B)

public:
    B()
    {
        std::cout << "B();\n";
    }

    ~B()
    {
        std::cout << "~B();\n";
    }
};

How it's used:

// normal syntax works, reference counting is entirely transparent
B *b = new B;
delete b;

// how it could work in a library
B *b = new B; // developer using a library allocates the class of the library

library_use(b); // send pointer to library

delete b; // 'delete' instance, won't be deleted since it's still in the library

library_shutdown();

// inside the library
library_use(B *b)
{
    b->gain();
    this->b = b; // library holds the pointer somehow
}

library_shutdown()
{
    if (b)
    {
        delete b;
        b = NULL;
    }
}

What do you think of this way of approaching a reference counting mechanism? It might be not how 'real' reference counting works...I mean, it won't _automatically_ delete the pointer, but this is the way I wanted to make this. Also, from the measurements I did, this came out to be _FASTER_ then plain new and delete. I guess something is wrong here, it took this way 87% of the time it takes without reference counting. This is the measurement code:

#include <iostream>
#include <windows.h>
#include <boost/shared_ptr.hpp>

//#include <mmgr/mmgr.cpp>

double GetSystemTime();

///////////////////////////////////////////////////////////

class A
{
public:
    A()
    {
    }

    ~A()
    {
    }
};

class B
{
    REFERENCE_COUNTING(B)

public:
    B()
    {
    }

    ~B()
    {
    }
};

typedef boost::shared_ptr<A> A_Ptr;

///////////////////////////////////////////////////////////

int main()
{
    double time;

    // boost
    time = GetSystemTime();
    for (unsigned int i = 0; i < 10000; i++)
    {
        A_Ptr a(new A);
    }
    std::cout << (GetSystemTime() - time) << '\n';

    // my method
    time = GetSystemTime();
    for (unsigned int i = 0; i < 10000; i++)
    {
        B *a = new B;
        delete a;
    }
    std::cout << (GetSystemTime() - time) << '\n';

    // normal allocation
    time = GetSystemTime();
    for (unsigned int i = 0; i < 10000; i++)
    {
        A *a = new A;
        delete a;
    }
    std::cout << (GetSystemTime() - time) << '\n';

    std::cout << '\n';
    /* and again */

    // boost
    time = GetSystemTime();
    for (unsigned int i = 0; i < 10000; i++)
    {
        A_Ptr a(new A);
    }
    std::cout << (GetSystemTime() - time) << '\n';

    // my method
    time = GetSystemTime();
    for (unsigned int i = 0; i < 10000; i++)
    {
        B *a = new B;
        delete a;
    }
    std::cout << (GetSystemTime() - time) << '\n';

    // normal allocation
    time = GetSystemTime();
    for (unsigned int i = 0; i < 10000; i++)
    {
        A *a = new A;
        delete a;
    }
    std::cout << (GetSystemTime() - time) << '\n';

    return 0;
}

///////////////////////////////////////////////////////////

double GetSystemTime()
{
    static LARGE_INTEGER Frequency;
    static BOOL UseHighPerformanceTimer = QueryPerformanceFrequency(&Frequency);

    if (UseHighPerformanceTimer)
    {
        LARGE_INTEGER CurrentTime;
        QueryPerformanceCounter(&CurrentTime);

        return static_cast<double>(CurrentTime.QuadPart) / Frequency.QuadPart;
    }
    else
    {
        return GetTickCount() * 0.001;
    }
}

///////////////////////////////////////////////////////////

Thanks for any comments. [Edited by - Decrius on January 9, 2009 7:26:57 AM]

[size="2"]SignatureShuffle: [size="2"]Random signature images on fora

dmail

116

January 09, 2009 06:36 AM

Quote:
What do you think of this way of approaching a reference counting mechanism?

I do not like it:
It is intrusive on the class which it is tracking.
Relies on C style casts which could result in bad casts when an offset is required in a hierarchy.
new function - should this not be a static function and should it also not throw an exception which is derived from bad_alloc?
delete - shouldn't this also be static? if so what happens(when static) and a null pointer is deleted which is valid.
If reference count is one and you call delete then you decrement the variable and do not free!
What happens when it is used in a hierarchy? does each level get a different variable reference_count which is not synchronised.

Decrius

100

Author

January 09, 2009 06:59 AM

Quote:Original post by dmail
Quote:
What do you think of this way of approaching a reference counting mechanism?

I do not like it:
It is intrusive on the class which it is tracking.
Relies on C style casts which could result in bad casts when an offset is required in a hierarchy.
new function - should this not be a static function and should it also not throw an exception which is derived from bad_alloc?
delete - shouldn't this also be static? if so what happens(when static) and a null pointer is deleted which is valid.
If reference count is one and you call delete then you decrement the variable and do not free!
What happens when it is used in a hierarchy? does each level get a different variable reference_count which is not synchronised.

What do you mean intrusive? And what's the problem with C casts?

And no, reference count always starts at zero...zero means 'one class is using it'. If no class is using it, the object doesn't exist, so why not using the zero? Perhaps I should call it other_references_counter.

And it should only be used in the base class, I myself don't need it for any derived class only.

And thanks, added static stuff and NULL checking.

[size="2"]SignatureShuffle: [size="2"]Random signature images on fora

Codeka

1,239

January 09, 2009 07:13 AM

Quote:Original post by Decrius
What do you mean intrusive? And what's the problem with C casts?

It's intrusive because you need to modify the class you're reference counting. boost::shared_ptr works with any class, not just ones you "own".

The problem with C-style casts is that it's not always clear what kind of cast you're doing. Is it's static_cast<>? reinterpret_cast<>? etc? A C++ class is more explicit in that respect.

Quote:Original post by Decrius
And no, reference count always starts at zero...zero means 'one class is using it'. If no class is using it, the object doesn't exist, so why not using the zero? Perhaps I should call it other_references_counter.

That's a non-standard meaning for the reference count. I've never heard of a reference counting implementation where "0" means "1 reference". It still works, obviously, but if another programmer comes along and sees your work, they're going to be confused for a while until they figure out the non-standard implementation.

War Worlds • Journal

Decrius

100

Author

January 09, 2009 07:25 AM

Quote:Original post by Codeka
It's intrusive because you need to modify the class you're reference counting. boost::shared_ptr works with any class, not just ones you "own".

Yes true. That isn't much of a feature-let-down for me, but it does mean it won't work for everything. The way this implementation works is that it needs to be IN a class, and doesn't CONTAIN the object. So it needs to be in a struct / class, while boost takes anything, true.

Quote:Original post by Codeka
The problem with C-style casts is that it's not always clear what kind of cast you're doing. Is it's static_cast<>? reinterpret_cast<>? etc? A C++ class is more explicit in that respect.

Is it used to make code more clear, or make it safer as well?

Quote:Original post by Codeka
That's a non-standard meaning for the reference count. I've never heard of a reference counting implementation where "0" means "1 reference". It still works, obviously, but if another programmer comes along and sees your work, they're going to be confused for a while until they figure out the non-standard implementation.

I get what you mean, but it didn't sound logical to me to not use the zero. All counters start at zero for computers...might change it to start at one, just for code clearness.

[size="2"]SignatureShuffle: [size="2"]Random signature images on fora

ToohrVyk

1,596

January 09, 2009 07:26 AM

Quote:Original post by Decrius
What do you think of this way of approaching a reference counting mechanism? It might be not how 'real' reference counting works...I mean, it won't _automatically_ delete the pointer, but this is the way I wanted to make this.

It doesn't work, and I can't really think of a way of making it work. Every delete calls the destructor: you can't use the object once you delete it, regardless of whether you deallocated the memory or not, and you certainly can't delete it a second time.

Try to add a complex object member (say, an std::string) to your object and you'll see what I mean.

Blog — Facebook

phresnel

953

January 09, 2009 07:41 AM

Just glimpsed over it:

0) Code C++, not C/C++

You are using #define macros, which should be avoided in c++ except for very rare cases. Most of what those macros where used for in C can now be done better with inheritance and templates.

1) Security

You are assuming that an implementing class puts your macro inside public visibilty. It could be that the macro hence exposes protected and private members of the implementing class (and users of intellisense will use what they see in the intellisense-popup (not microsoft specific)).

2) Fight the optimiser

Your benchmark is bogus:

    // my method    time = GetSystemTime();    for (unsigned int i = 0; i < 10000; i++)    {        B *a = new B; // << alloc        delete a;     // << dealloc    }    std::cout << (GetSystemTime() - time) << '\n';

Compilers are perfectly allowed to remove the whole loop, as it has no side effects, except the constructor or destructor do something that affects a bigger scope then the loop. It is generally quite hard to write benchmarks. A good start is to make the constructor somehow dependent on unpredictable data (for example user input), and to ensure the output is dependent on the processed input (enforce that the measured data participates in all stages of the IPO model).

3) Unreliable results

Point 3) is really an addendum to point 2). I see you have calls to std::cout<< in B::B() and B::~B(). While this would be a 99% guarantee that your loop will not be optimized away, it is not a good idea to read/write from/to standard i/o:

output buffering occurs, and every now and then (e.g. every 8192 chars) it will be flushed, which takes up processing time and makes measurement more or less unreliable
you interface with the operating system, which is always a (with respect to time) unpredictable process

4) Compare to boost::intrusive_ptr

You are comparing to boost::shared_ptr what really should be compared to boost::intrusive_ptr.

Appendix A)

Hint: If you are on Linux, you can get more reliable benchmark results by starting your benchmark as the only user process, by passing init=<path-to-your-benchmark> as an argument to the kernel (actually, if you're benchmark is stable (i.e. without std::cout or similar in the measure loop), you can get results that only vary in fractions of percents from run to run).

Appendix B)

For serious measurements, always check what your compiler spits out, i.e. have a look at the assembly, e.g. to make sure certain optimisations do not influence the results.

[C++] My reference-counting implementation

0) Code C++, not C/C++

1) Security

2) Fight the optimiser

3) Unreliable results

4) Compare to boost::intrusive_ptr

Appendix A)

Appendix B)

Further Reading on Optimisation

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

[C++] My reference-counting implementation

0) Code C++, not C/C++

1) Security

2) Fight the optimiser

3) Unreliable results

4) Compare to boost::intrusive_ptr

Appendix A)

Appendix B)

Further Reading on Optimisation

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines