Ето в това видео от Going Native 2013 A. Alexandrescu разказва за някои от проблемите, които виртуалните функции в С++ създават. А именно : всеки обект държи по един (или повече) 64 битов (най-често) указател към виртуалната таблица, това измества разни неща от cache-а; винаги този указател седи в началото на обекта (а в началото е добре, да има неща които се ползват по-често. Това може да е указателят към виртуалната таблица, но може да е друго :)). Рядко в живота може човек да се докара до там, че да иска и това да забързв. Но се случва.
Идеята е да си напишем наша имплементация на виртуални функции, която да ползва не 64 битово число, ами 8 (така ще се ограничим по максимален брой виртуални функции в интерфейс или по максимален брой класове в йерархия, но 256 (2^8) често е повече от достатъчно).
Ето и примерна имплементация (с малко macro-та и нагласявки :)). На места е малко redundant; мисля че може да се постигне и по-приятен синтаксис.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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”, който ползваме като указател към виртуална таблица -> ако не се очаква виртуални методи да се викат често, навярно е по-добре да не е в началото на обекта.