特定な場合で仮想メソッドの呼び出しを高速化する方法
一昨日に考えたことです。
CRC16の計算に、こういうインターフェイスを設計した。
class ICrc16CCITTの実装はこのようです。
{
public:
virtual ~ICrc16() = 0 {}
virtual void ProcessBit(bool val) = 0;
virtual void ProcessByte(char val) = 0;
virtual void ProcessBlock(char* ptr, int len) = 0;
virtual short Get() = 0;
};
class CCrc16CCITT : public ICrc16問題はProcessBitとProcessByteは仮想メソッドで、このようなメソッドを呼び出すのはとても時間を掛かる:まず仮想メソッドテーブルで関数を探しなければならない。非仮想メソッドを呼び出すときこの段階は必要がない。
{
unsigned short _rem;
public:
CCrc16CCITT()
{
_rem = 0xffff;
}
~CCrc16CCITT()
{
}
void ProcessBit(bool val)
{
bool topBit = _rem >> 15;
_rem <<= 1;
if ( (topBit ^ val) == true )
_rem ^= 0x1021;
}
void ProcessByte(char val)
{
for (int i = 7; i >= 0; --i)
ProcessBit( (val & (1 << i)) != 0 );
}
void ProcessBlock(char* ptr, int len)
{
for(int i = 0; i < len; ++i)
ProcessByte(ptr[i]);
}
short Get()
{
return _rem;
}
};
VCコンパイラーはパラメータ/Ox 付けるとき、ProcessBitを呼び出すところのソースコードは以下のアセンブルを生成する。
mov eax, DWORD PTR [ebx]300MBファイルのCRC16を計算すれば、ProcessByte関数を314572800回呼び出す。そしてもっと厳しいのはProcessBitを2516582400回呼び出す。全部
mov eax, DWORD PTR [eax+4]
test ebp, esi
setne cl
movzx edx, cl
push edx
mov ecx, ebx
call eax
ror esi, 1
dec edi
jns SHORT $LL3@ProcessByt
mov eax, DWORD PTR [ebx]こうして仮想メソッドを呼び出す。時間を無駄に使った。
mov eax, DWORD PTR [eax+4]
......
call eax
よく考えたらそうしないとダメな原因は、例えば私はCCrazyCrcのクラスを書いて
class CCrazyCrc : public CCrc16CCITT {ならばCCrc16CCITTProcessByteの関数に呼び出すProcessBitはCCrc16CCITT::ProcessBitじゃなくCCrazyCrc::ProcessBitになった。でもCRCの計算についてこの可能性がないはず。コンパイラーは「CCrc16CCITT::ProcessByteに呼び出すProcessBitは決してCCrc16CCITT::ProcessBitだ」って事実を伝えばいい。
void ProcessBit(bool val) {...}
};
そしてCCrc16CCITTはこうなった。
class CCrc16CCITT : public ICrc16VCコンパイラは/Oxパラメータ付けば生成したコードに、CCrc16CCITT::ProcessBlockメソッドにもCCrc16CCITT::ProcessByteメソッドにもアセンブル言語の「call」はなくなった。
{
unsigned short _rem;
public:
CCrc16CCITT()
{
_rem = 0xffff;
}
~CCrc16CCITT()
{
}
void ProcessBit(bool val)
{
bool topBit = _rem >> 15;
_rem <<= 1;
if ( (topBit ^ val) == true )
_rem ^= 0x1021;
}
void ProcessByte(char val)
{
for (int i = 7; i >= 0; --i)
CCrc16CCITT::ProcessBit( (val & (1 << i)) != 0 );
}
void ProcessBlock(char* ptr, int len)
{
for(int i = 0; i < len; ++i)
CCrc16CCITT::ProcessByte(ptr[i]);
}
short Get()
{
return _rem;
}
};
136MBのファイルをCRCを計算して、
前者のコードは大体15.8秒かかる。後者大体8.8秒かかる。7秒節約した。