VTable по поръчка

Ето в това видео от Going Native 2013 A. Alexandrescu разказва за някои от проблемите, които виртуалните функции в С++ създават. А именно : всеки обект държи по един (или повече) 64 битов (най-често) указател към виртуалната таблица, това измества разни неща от cache-а; винаги този указател седи в началото на обекта (а в началото е добре, да има неща които се ползват по-често. Това може да е указателят към виртуалната таблица, но може да е друго :)). Рядко в живота може човек да се докара до там, че да иска и това да забързв. Но се случва.

Идеята е да си напишем наша имплементация на виртуални функции, която да ползва не 64 битово число, ами 8 (така ще се ограничим по максимален брой виртуални функции в интерфейс или по максимален брой класове в йерархия, но 256 (2^8) често е повече от достатъчно).

Ето и примерна имплементация (с малко macro-та и нагласявки :)). На места е малко redundant; мисля че може да се постигне и по-приятен синтаксис.

//custom vtable that uses 8 bits for vtable ptr, in stead of 64 bits
//the vtable ptr is first in the mem layout, aways there and aways giving us that +1 cache miss
//this vtable implementation is slimmer in terms of memory and as fast as c++ vtable (this two facts = (probably) faster code)
//it is ugly, but that should not scares you
//there may be some (macro) redudancy, but this is just a PoC
//credits : a.alexandrescu, going native 2013.

#include <iostream>

//add some dummy defines for having semantic in some places
#define CLASS(X) X
#define INTERFACE(X) X
#define NAME(X) X
#define RETURN(X) X
#define PARAM0(X) X
#define PARAM1(X) X

//our virtual functions will be static functions with "this" as 1st argument
#define VIRTUAL static

//declare (virtual) interface method; syntax:
//VTABLE_METHODN_DEFINE(0, InterfaceName, MethodName, MethodReturnType, Param0Type, ..., ParamN-1Type)
//first int goes from 0 to n (every next method has idx the idx of the previous+1)
//*this should be used to declare the interface methods in the interface class*
#define VTABLE_METHOD0_DEFINE(IDX, CLASS, NAME, RETURNTYPE) \
                    RETURNTYPE NAME() {  typedef RETURNTYPE (*name_t)(CLASS&); return ((name_t)(vtbl[this->tag*CLASS_LAST + IDX]))(*this); }


#define VTABLE_METHOD1_DEFINE(IDX, CLASS, NAME, RETURNTYPE, PARAM0) \
                    RETURNTYPE NAME(PARAM0 p0) { typedef RETURNTYPE (*name_t)(CLASS&, PARAM0); return ((name_t)(vtbl[this->tag*CLASS_LAST + IDX]))(*this, p0); }

//fills in vtable; syntax:
///REGISTER_METHODN(TheMethodIdx, Interface, ClassThatImplementsTheInterface, MethodReturnType, Param0Type, ..., ParamN-1Type)
///*to be used in the "init" proc*
#define REGISTER_METHOD0(METHOD, BASE, DERIVE, RETURNTYPE, NAME) { RETURNTYPE (*ptr)(BASE&); ptr = DERIVE::NAME; BASE::vtbl[DERIVE::ID*CLASS_LAST + METHOD] = (BASE::FP)ptr; }
#define REGISTER_METHOD1(METHOD, BASE, DERIVE, RETURNTYPE, NAME, PARAM0) { RETURNTYPE (*ptr)(BASE&, PARAM0); ptr = DERIVE::NAME; BASE::vtbl[DERIVE::ID*CLASS_LAST + METHOD] = (BASE::FP)ptr; }

#define TAG(X) tag = X;

//every class hierarchy with all of its classes has separate enum
//we use this and the next enum to calculate the method position in the vtable
enum {
    CLASS_BASE = 0,
    CLASS_DERIVED,
    CLASS_DERIVED_2,
    CLASS_LAST=CLASS_DERIVED_2,//because of some funny ptr arithmetic
};
//lets give names to the method indexes
enum {
    METHOD_GET=0,
    METHOD_SET=1,
    METHOD_LAST,
};

//every base class has :
//1. tag - every hierarchy class writes its id there
//2. static vtable

//every hierarchy class has :
//1. static ID

//example of base class and 2 derived classes
class Base {
protected:
    //specifies the object type
    uint8_t tag;
public:
    //specifies the class type
    static const int ID = CLASS_BASE;
    //**
    //vtable
    typedef void (*FP)();
    static FP vtbl[(CLASS_LAST+1) * METHOD_LAST];
    //**
    Base() {
        //set the obj type
        TAG(ID);
    }
    
    //define the interface methods
    VTABLE_METHOD0_DEFINE( METHOD_GET,
                           INTERFACE(Base),
                           NAME(get),
                           RETURN(int)
                          );
    
    VTABLE_METHOD1_DEFINE( METHOD_SET,
                           INTERFACE(Base),
                           NAME(set),
                           RETURN(void),
                           PARAM0(int)
                          );
    
    //implement the interface methods
    VIRTUAL int get(Base& self) {
        throw std::bad_function_call();
    }
    
    VIRTUAL void set(Base& self, int) {
        throw std::bad_function_call();
    }
};

//

class Derived : public Base {
    int i;
public:
    static const int ID = CLASS_DERIVED;

    Derived() {
        TAG(ID);
    }
    
    VIRTUAL void set(Base& self, int j) {
        Derived& myself = static_cast<Derived&>(self);
        myself.i = j;
        std::cout << "set" << std::endl;
    }
    
    VIRTUAL int get(Base& self) {
        Derived& myself = static_cast<Derived&>(self);

        int res = myself.i;
        std::cout << "get " << res << std::endl;
        return res;
    }
};

//

class Derived2 : public Derived {
    float f;
public:
    static const int ID = CLASS_DERIVED_2;

    Derived2() {
        TAG(ID);
    }
    
    VIRTUAL void set(Base& self, int j) {
        Derived2& myself = static_cast<Derived2&>(self);

        myself.f = j * .42f;
        std::cout << "set" << std::endl;
    }
    
    VIRTUAL int get(Base& self) {
        Derived2& myself = static_cast<Derived2&>(self);
        float res = myself.f;
        std::cout << "get " << res << std::endl;
        return res;
    }
};


void init/*vtable*/() {
    //init the vtable for "Base" class
    REGISTER_METHOD1(METHOD_SET,
                     INTERFACE(Base),
                     CLASS(Base),
                     RETURN(void),
                     NAME(set),
                     PARAM0(int)
                     );
    REGISTER_METHOD0(METHOD_GET,
                     INTERFACE(Base),
                     CLASS(Base),
                     RETURN(int),
                     NAME(get)
                     );
    // ***
    //init the vtable for "Derived" class
    REGISTER_METHOD0(METHOD_GET,
                     INTERFACE(Base),
                     CLASS(Derived),
                     RETURN(int),
                     NAME(get)
                     );
    REGISTER_METHOD1(METHOD_SET,
                     INTERFACE(Base),
                     CLASS(Derived),
                     RETURN(void),
                     NAME(set),
                     PARAM0(int)
                     );
    // ***
    //init the vtable for "Derived2" class
    REGISTER_METHOD0(METHOD_GET,
                     INTERFACE(Base),
                     CLASS(Derived2),
                     RETURN(int),
                     NAME(get)
                     );
    REGISTER_METHOD1(METHOD_SET,
                     INTERFACE(Base),
                     CLASS(Derived2),
                     RETURN(void),
                     NAME(set),
                     PARAM0(int));
}

Base::FP Base::vtbl[(CLASS_LAST+1) * METHOD_LAST];

int main(int argc, const char* argv[]) {
    init();
    
    Base* der = new Derived2();
    
    der->set(196);
    der->get();
    
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

//custom vtable that uses 8 bits for vtable ptr, in stead of 64 bits

//the vtable ptr is first in the mem layout, aways there and aways giving us that +1 cache miss

//this vtable implementation is slimmer in terms of memory and as fast as c++ vtable (this two facts = (probably) faster code)

//it is ugly, but that should not scares you

//there may be some (macro) redudancy, but this is just a PoC

//credits : a.alexandrescu, going native 2013.

#include <iostream>

//add some dummy defines for having semantic in some places

#define CLASS(X) X

#define INTERFACE(X) X

#define NAME(X) X

#define RETURN(X) X

#define PARAM0(X) X

#define PARAM1(X) X

//our virtual functions will be static functions with "this" as 1st argument

#define VIRTUAL static

//declare (virtual) interface method; syntax:

//VTABLE_METHODN_DEFINE(0, InterfaceName, MethodName, MethodReturnType, Param0Type, ..., ParamN-1Type)

//first int goes from 0 to n (every next method has idx the idx of the previous+1)

//*this should be used to declare the interface methods in the interface class*

#define VTABLE_METHOD0_DEFINE(IDX, CLASS, NAME, RETURNTYPE) \

RETURNTYPE NAME() { typedef RETURNTYPE (*name_t)(CLASS&); return ((name_t)(vtbl[this->tag*CLASS_LAST + IDX]))(*this); }

#define VTABLE_METHOD1_DEFINE(IDX, CLASS, NAME, RETURNTYPE, PARAM0) \

RETURNTYPE NAME(PARAM0 p0) { typedef RETURNTYPE (*name_t)(CLASS&, PARAM0); return ((name_t)(vtbl[this->tag*CLASS_LAST + IDX]))(*this, p0); }

//fills in vtable; syntax:

///REGISTER_METHODN(TheMethodIdx, Interface, ClassThatImplementsTheInterface, MethodReturnType, Param0Type, ..., ParamN-1Type)

///*to be used in the "init" proc*

#define REGISTER_METHOD0(METHOD, BASE, DERIVE, RETURNTYPE, NAME) { RETURNTYPE (*ptr)(BASE&); ptr = DERIVE::NAME; BASE::vtbl[DERIVE::ID*CLASS_LAST + METHOD] = (BASE::FP)ptr; }

#define REGISTER_METHOD1(METHOD, BASE, DERIVE, RETURNTYPE, NAME, PARAM0) { RETURNTYPE (*ptr)(BASE&, PARAM0); ptr = DERIVE::NAME; BASE::vtbl[DERIVE::ID*CLASS_LAST + METHOD] = (BASE::FP)ptr; }

#define TAG(X) tag = X;

//every class hierarchy with all of its classes has separate enum

//we use this and the next enum to calculate the method position in the vtable

enum {

CLASS_BASE = 0,

CLASS_DERIVED,

CLASS_DERIVED_2,

CLASS_LAST=CLASS_DERIVED_2,//because of some funny ptr arithmetic

};

//lets give names to the method indexes

enum {

METHOD_GET=0,

METHOD_SET=1,

METHOD_LAST,

};

//every base class has :

//1. tag - every hierarchy class writes its id there

//2. static vtable

//every hierarchy class has :

//1. static ID

//example of base class and 2 derived classes

class Base {

protected:

//specifies the object type

uint8_t tag;

public:

//specifies the class type

static const int ID = CLASS_BASE;

//**

//vtable

typedef void (*FP)();

static FP vtbl[(CLASS_LAST+1) * METHOD_LAST];

//**

Base() {

//set the obj type

TAG(ID);

}

//define the interface methods

VTABLE_METHOD0_DEFINE( METHOD_GET,

INTERFACE(Base),

NAME(get),

RETURN(int)

);

VTABLE_METHOD1_DEFINE( METHOD_SET,

INTERFACE(Base),

NAME(set),

RETURN(void),

PARAM0(int)

);

//implement the interface methods

VIRTUAL int get(Base& self) {

throw std::bad_function_call();

}

VIRTUAL void set(Base& self, int) {

throw std::bad_function_call();

}

};

class Derived : public Base {

int i;

public:

static const int ID = CLASS_DERIVED;

Derived() {

TAG(ID);

}

VIRTUAL void set(Base& self, int j) {

Derived& myself = static_cast<Derived&>(self);

myself.i = j;

std::cout << "set" << std::endl;

}

VIRTUAL int get(Base& self) {

Derived& myself = static_cast<Derived&>(self);

int res = myself.i;

std::cout << "get " << res << std::endl;

return res;

}

};

class Derived2 : public Derived {

float f;

public:

static const int ID = CLASS_DERIVED_2;

Derived2() {

TAG(ID);

}

VIRTUAL void set(Base& self, int j) {

Derived2& myself = static_cast<Derived2&>(self);

myself.f = j * .42f;

std::cout << "set" << std::endl;

}

VIRTUAL int get(Base& self) {

Derived2& myself = static_cast<Derived2&>(self);

float res = myself.f;

std::cout << "get " << res << std::endl;

return res;

}

};

void init/*vtable*/() {

//init the vtable for "Base" class

REGISTER_METHOD1(METHOD_SET,

INTERFACE(Base),

CLASS(Base),

RETURN(void),

NAME(set),

PARAM0(int)

);

REGISTER_METHOD0(METHOD_GET,

INTERFACE(Base),

CLASS(Base),

RETURN(int),

NAME(get)

);

// ***

//init the vtable for "Derived" class

REGISTER_METHOD0(METHOD_GET,

INTERFACE(Base),

CLASS(Derived),

RETURN(int),

NAME(get)

);

REGISTER_METHOD1(METHOD_SET,

INTERFACE(Base),

CLASS(Derived),

RETURN(void),

NAME(set),

PARAM0(int)

);

// ***

//init the vtable for "Derived2" class

REGISTER_METHOD0(METHOD_GET,

INTERFACE(Base),

CLASS(Derived2),

RETURN(int),

NAME(get)

);

REGISTER_METHOD1(METHOD_SET,

INTERFACE(Base),

CLASS(Derived2),

RETURN(void),

NAME(set),

PARAM0(int));

}

Base::FP Base::vtbl[(CLASS_LAST+1) * METHOD_LAST];

int main(int argc, const char* argv[]) {

init();

Base* der = new Derived2();

der->set(196);

der->get();

return 0;

}

Не успях да събера мотивация да направя тестове за да видя има ли забързване, в кои случаи има и колко е то. Според Alexanderscu Facebook работи 4% по-бързо заради тази магия :).
Предимство е, че така можем и да изберем къде да поместим този “char”, който ползваме като указател към виртуална таблица -> ако не се очаква виртуални методи да се викат често, навярно е по-добре да не е в началото на обекта.

Stoyan

May 14, 2014

Hmm, this will break the alignment of all members after the table. It would make sense if you can squeeze some tiny members in the now 3 free bytes, otherwise the gains would be dubious.

Reply to Stoyan
savage309

May 14, 2014

А да, така е. Ако успееш да вместиш нещо – успееш. Ако не ще имаш същата скорост, но с доста тегав синтаксис.
Може и в базовият клас да има разни други данни, та още там да стане вместването и да си сигурен, че наследниците не трябва да мислят за това 🙂

Reply to savage309

savage309

Software developer Twitter @savage309

Published

May 14, 2014

savage309 in Computing and stuff | May 14, 2014

VTable по поръчка

savage309

Software developer Twitter @savage309

Published

May 14, 2014

Cancel Reply

Write a Comment