[C++] Reference counting en multiple inheritance

[MisterData]

Al een tijdje gebruik ik zelfgeschreven reference counting pointers. De relevante stukjes code daarvan heb ik hieronder geplakt. Zodra ik een object alloceer roep ik een speciale functie aan; die maakt een Resource-object, stopt daar de pointer in en geeft een ref<T> terug (die een Resource<T>* bevat). Op die manier kan ik ook weak-references maken (maar die zijn in dit verhaal niet echt van belang).

Het probleem begint echter als ik ga casten: als ik een class A heb die afstamt van B dan kan ik (zie code onder) gewoon ref<B>(a) doen (met a een ref<A>). Zoals je ziet wordt dan nog wel gecheckt of dat uberhaupt wel mag (dynamic_cast) maar vervolgens wordt de Resource<A>* domweg als Resource<B>* gebruikt. Dat dat niet netjes is weet ik ook wel, maar het werkt zo prima (waarschijnlijk omdat dynamic_cast<B*>(a) == a toevallig) en het heeft ook voordelen: de ref hoeft niet te weten wat het type van het originele object was en de ref blijft zo groot als een pointer (die dingen worden overal gebruikt dus moeten klein blijven).

Echter, bij multiple inheritance gaat dit goed fout. Ik zoek dus een manier om deze reference-counted pointers daarvoor geschikt te maken, zonder de ref<T>'s groter te maken of de reference count in het object zélf op te slaan (dan kan ik weer heel lastig weak references maken...). Een oplossing die ik zelf al had bedacht is om in Resource een Object* op te slaan (alle objecten stammen daarvan af) en in ref<T>::operator-> altijd een dynamic_cast<T>(_res->object) te doen. Ik vermoed alleen dat dat érg traag gaat zijn...

C++:

template< typename T > class Resource {
    friend class ref<T>;

    public:
        Resource(T*) {...}
        ~Resource() {...}
        inline void AddReference() {...}
        inline void DeleteReference() {...}

    protected:
        T* _object;
        long _rc;
        long _weakrc;
};

template<typename T> class ref {
    friend class Resource<T>;

    public:
        inline ref(intern::Resource<T>* rx=0) {...}
        inline ref(const ref<T>& org) {...}
        
        template<typename RT> inline ref(const ref<RT>& org) {  
            if(org._res==0) {
                _res = 0;
            }
            else {
                T* rt = dynamic_cast<T*>(org._res->_object);                
                if(rt==0) throw BadCastException();

                // Dit is natuurlijk smerig... maar het werkt tot op zekere hoogte
                // Merk op dat org._res een Resource<RT>* is....

                _res = reinterpret_cast<Resource<T>* >(org._res);
                if(_res!=0) {
                    _res->AddReference();
                }
            }
        }

        inline ~ref() {...}

        inline T* operator->() {
            if(_res->_object==0) throw NullPointerException();
            return _res->_object; // Omdat _res een Resource<T>* is, is _res->_object hier een T*
        }

    private:
        Resource<T>* _res;
};

[ Voor 0% gewijzigd door MisterData op 28-12-2007 14:09 . Reden: _data en _object zijn hetzelfde ]

[Soultaker]

Ten eerste: klopt het dat waar je refereert aan _res->_data je eigenlijk _res->_object bedoelt? (Er is namelijk geen _data member in Resource voor zover ik kan zien.)

Verder weet ik geen oplossing die even efficient is in alle gevallen, maar ik kan wel iets bedenken dat even goed werkt voor de huidige gevallen (single inheritance) en slechts marginaal slechter voor andere gevallen (vanwege de pointer adjustment). Dat is je ref class zo te definiëren dat 'ie met zowel het type van de originele pointer als met dat van de parent resource geparametriseerd wordt:

C++:

// Intention: ref<T,RT> is instantiatable only if T is a subclass of RT
template<class T, class RT> class ref {
    Resource<RT> *_res;

public:
    template<typename X> inline ref(const ref<X, RT> &org) {
        T *obj = dynamic_cast<T*>(org._res->_object);
        if (!obj) throw ...;
        _res = org._res;
    }

    inline T* operator->() {
        return (T*)(_res->_object);
    }
}

(Code is niet getest en er mist van alles; is alleen om het idee duidelijk te maken.)

Het idee hiervan is dus dat de resource ten alle tijden hetzelfde type behoudt, ook al heb je verschillende ref objects met verschillende types die ernaar verwijzen. De controle op geldigheid van de conversie wordt met dynamic_cast gedaan, maar die kan at compile time al uitgevoerd worden (wat wel zo efficient is) en het enige verschil is dat je nu de cast uitvoert in operator->(). In de meeste gevallen is de code die daarvoor gegenereerd wordt exact hetzelfde als nu, maar in het specifieke geval dat RT bijvoorbeeld niet de eerste maar de tweede base class van T is, moet er iets bij de pointer opgeteld worden. Dat is ook de situatie die nu fout gaat.

Als je die pointer adjustment wil voorkomen zou je, apart een pointer naar het Resource object en de gecaste pointer moeten bijhouden, maar zoals je zelf al zegt is dat waarschijnlijk niet wenselijk omdat je ref objecten dan twee keer zo groot worden. Mijn natte-vinger-analyse zegt ook dat de overhead van die pointer adjustment in de praktijk verwaarloosbaar is.

[ Voor 34% gewijzigd door Soultaker op 28-12-2007 14:05 ]

[MisterData]

Soultaker schreef op vrijdag 28 december 2007 @ 13:59:
Ten eerste: klopt het dat waar je refereert aan _res->_data je eigenlijk _res->_object bedoelt? (Er is namelijk geen _data member in Resource voor zover ik kan zien.)

Klopt, ik heb de code iets versimpeld, en daarbij per ongeluk _object en _data door elkaar gebruikt.

Verder weet ik geen oplossing die even efficient is in alle gevallen, maar ik kan wel iets bedenken dat even goed werkt voor de huidige gevallen (single inheritance) en slechts marginaal slechter voor andere gevallen (vanwege de pointer adjustment). Dat is je ref class zo te definiëren dat 'ie met zowel het type van de originele pointer als met dat van de parent resource geparametriseerd wordt:

C++:

template<class T, class RT> class ref {
    Resource<RT> *_res;

    template<typename X> inline ref(const ref<X, RT> &org) {
        T *obj = dynamic_cast<T*>(org._res->_object);
        if (!obj) throw ...;
        _res = org._res;
    }

    inline T* operator->() {
        return (T*)(_res->_object);
    }
}

Zoiets had ik ook bedacht, maar het punt is dat ik ook functies heb die een ref<T> als parameter willen. Als ik (op jouw manier) die functies een ref<T,RT> laat accepteren, dan moeten die functies allemaal template<typename RT> worden, wat natuurlijk niet helemaal de bedoeling is... het maakt die functies namelijk helemaal niet uit wat nou de originele RT was, als ze maar de methodes en members van T kunnen bereiken...

[Soultaker]

Dat is waar natuurlijk.

Ik weet niet hoe groot de overhead van dynamic_cast<> is in de praktijk, maar je zou ook het hele casten at runtime kunnen doen. (Sowieso moet een object een vtable hebben om te kunnen dynamic casten, toch?)

C++:

class Resource {
    void *_obj;
public:
    Resource(void *obj) : _obj(obj) { };
};

template<class T> class ref {
    Resource *res;
    // ..
    inline T* operator->() {
        return dynamic_cast<T*>(obj);
    }
};

Nadeel is dan dat je in principe de hele tijd dynamic casts uitvoert...

In z'n algemeenheid lijkt het me dat omdat de ref class twee types moet kennen om te kunnen casten (type van de base class en van de derived class), je ofwel die types aan de template parameters moet toevoegen (dat was mijn eerste suggestie) ofwel je gebruikt de base class informatie die je vanwege RTTI al hebt (aangezien je ook kunt dynamic_casten), maar dat zal dan altijd een runtime check zijn.

[ Voor 26% gewijzigd door Soultaker op 28-12-2007 14:36 ]

[.oisyn]

Ik zou het sowieso laten om de dynamic_cast automatisch te doen, dat gebeurt in de rest van C++ ook niet. Als je dat wilt, maak dan een dynamic_ref_cast template functie die een willekeurig type naar een willekeurig ander type kan casten middels een dynamic_cast (wat mogelijk een null ref teruggeeft als het niet lukt)

Wellicht dat je wilt kijken naar het design van boost::shared_ptr? (of die ook gewoon direct gebruiken, ben je meteen voorbereid op de toekomst aangezien het al in TR1 zit)

[MisterData]

.oisyn schreef op vrijdag 28 december 2007 @ 14:30:
Ik zou het sowieso laten om de dynamic_cast automatisch te doen, dat gebeurt in de rest van C++ ook niet. Als je dat wilt, maak dan een dynamic_ref_cast template functie die een willekeurig type naar een willekeurig ander type kan casten middels een dynamic_cast (wat mogelijk een null ref teruggeeft als het niet lukt)

Ik kan die constructor natuurlijk explicit maken...

Wellicht dat je wilt kijken naar het design van boost::shared_ptr? (of die ook gewoon direct gebruiken, ben je meteen voorbereid op de toekomst aangezien het al in TR1 zit)

Ik heb de broncode daarvan even snel doorgekeken, en waar het op neerkomt is dat shared_ptr een T* en een 'shared counter' bevat (waarschijnlijk een of andere unsigned int*):

C++:

    T * px;                     // contained pointer
    boost::detail::shared_count pn;    // reference counter

shared_ptr is dus twee keer zo groot als een pointer. Ik denk dat ik het ook maar zo ga doen dan

[.oisyn]

Die shared counter zal waarschijnlijk 2 counters bevatten: een strong en een weak counter. Wat je nu ook al hebt dus. Waarschijnlijk bevat het zelfs ook nog een pointer, anders zitten ze bij std::weak_ptr continu te checken of de strong count ongelijk is aan 0. Dat een shared_ptr zelf ook nog een pointer heeft is een beetje redundant maar waarschijnlijk om performance-redenen, omdat je anders een dubbele indirectie hebt (en dus meer kans op (dubbele) cache misses). Dat is idd iets om zelf ook te overwegen.

Maar wat data layout betreft zit je dus wel op gelijke voet met boost. Ik zou vooral eens goed kijken naar hoe zij omgaan met pointers naar gerelateerde typen en casts e.d.. Ook hebben ze bijvoorbeeld een shared_from_this class, waarvan je moet overerven om in je class implementatie een shared_ptr naar je this te krijgen (waarschijnlijk door de shared_count met je class te agregeren om te voorkomen dat er een nieuwe shared_count wordt gealloceerd elke keer als je van een rauwe pointer een shared_ptr maakt)

[ Voor 4% gewijzigd door .oisyn op 28-12-2007 15:49 ]

[MisterData]

.oisyn schreef op vrijdag 28 december 2007 @ 15:47:
Maar wat data layout betreft zit je dus wel op gelijke voet met boost. Ik zou vooral eens goed kijken naar hoe zij omgaan met pointers naar gerelateerde typen en casts e.d.. Ook hebben ze bijvoorbeeld een shared_from_this class, waarvan je moet overerven om in je class implementatie een shared_ptr naar je this te krijgen

Zoiets heb ik al eerder met jullie hulp weten op te lossen (zie \[C++] reference counting en this pointer)