Цена абстракции-4 (или все, что мама не рассказывала про C++)

Оказывается, за весь 2008й год не было ни одного поста про ценник абстракции. Это недопустимо, надо исправлять. Сегодня мы узнаем, как поиметь +30% в одну строчку, заменив if ( bool-flag ) на (int)bool-flag.

В коде случился такой паттерн: у объекта есть два указателя на разные куски в памяти, в зависимости от флажка надо выбирать либо по 1му, либо по 2му. (Для справки, это некая статическая часть данных, которая расшарена между несколькими копиями объектов, и динамическая часть, которая очень личная и которой объект владеет).

Написал return bDynamic ? m_pDynamic[iOffset] : m_pStatic[iOffset], слегка задумался. Поля m_pStatic и m_pDynamic в объекте лежат подряд. bool bDynamic хоть и занимает целый байт, принимает все равно значения 0 и 1. Догадается компилятор заменить это дело на (*(&m_pStatic+bDynamic))[iOffset], и выгоднее ли это?

Результаты MSVC 2005: да, выгоднее на 30%. Нет, не догадывается.

Результаты gcc 4.2.3: не уверен, что правильно понимаю ассемблерную нотацию, но похоже, догадывается сразу. Поэтому разницу померить не удается, результаты одинаковые.

Код бенчмарка под катом.

[code lang="cpp"]
// cl /O2 perftest.cpp
// shodan(at)shodan.ru

#include
#include
#include

#ifdef _WIN32
#include
#pragma comment(linker, "/defaultlib:winmm.lib")
typedef __int64 int64_t;
#else
#include
#define __forceinline inline
#endif

/// time since startup, in microseconds
int64_t sphMicroTimer()
{
#ifdef _WIN32
// Windows time query
static int64_t iStart = 0;
static int64_t iFreq = 0;

LARGE_INTEGER iLarge;
if ( !iFreq )
{
QueryPerformanceFrequency ( &iLarge ); iFreq = iLarge.QuadPart;
QueryPerformanceCounter ( &iLarge ); iStart = iLarge.QuadPart;
}

QueryPerformanceCounter ( &iLarge);
return ( iLarge.QuadPart-iStart )*1000000/iFreq;

#else
// UNIX time query
static int s_sec = -1, s_usec = -1;
struct timeval tv;

if ( s_sec == -1 )
{
gettimeofday ( &tv, NULL );
s_sec = tv.tv_sec;
s_usec = tv.tv_usec;
}

gettimeofday ( &tv, NULL );
return int64_t(tv.tv_sec-s_sec)*int64_t(1000000) + int64_t(tv.tv_usec-s_usec);
#endif // USE_WINDOWS
}

struct Locator
{
int m_iOffset;
bool m_bPart;
};

struct Foo
{
int * m_pParts[2];

__forceinline int Getter1 ( const Locator & l ) const
{
return l.m_bPart
? m_pParts[1][l.m_iOffset]
: m_pParts[0][l.m_iOffset];
}

__forceinline int Getter2 ( const Locator & l ) const
{
return m_pParts[l.m_bPart][l.m_iOffset];
}
};

__forceinline int Marker()
{
#ifdef _WIN32
__asm
{
or eax,eax
or ebx,ebx
or ecx,ecx
};
#else
asm("orl %eax,%eax");
asm("orl %ebx,%ebx");
asm("orl %ecx,%ecx");
#endif
return 0;
}

int main ()
{
#ifdef _WIN32
timeBeginPeriod ( 1 );
#endif

int dData1[] = { 1, 2, 3 };
int dData2[] = { 4, 5, 6 };

Locator l;
srand ( time(NULL) );
l.m_iOffset = rand() % 3;
l.m_bPart = rand() % 2;

volatile int NRUNS = 1000000;
volatile int NOBJECTS = 100;

Foo * f = new Foo [ NOBJECTS ];
for ( int i=0; i {
f[i].m_pParts[0] = dData1;
f[i].m_pParts[1] = dData2;
}

int64_t t1 = -sphMicroTimer();
int iSum1 = 0;
Marker();
for ( int i=0; i for ( int j=0; j iSum1 += f[j].Getter1 ( l );
Marker();
t1 += sphMicroTimer();

int64_t t2 = -sphMicroTimer();
int iSum2 = 0;
Marker();
for ( int i=0; i for ( int j=0; j iSum2 += f[j].Getter2 ( l );
Marker();
t2 += sphMicroTimer ();

#ifdef _WIN32
timeEndPeriod ( 1 );
#endif

printf ( "off=%d part=%d\n", l.m_iOffset, l.m_bPart );
printf ( "sum1=%d time1=%d\n", iSum1, t1 );
printf ( "sum2=%d time2=%d\n", iSum2, t2 );
}
[/code]

На моем десктопе собранный MSVC 2005 вариант выдает

[code lang="cpp"]
off=2 part=1
sum1=600000000 time1=133384
sum2=600000000 time2=102059
[/code]

  • kas

    в 2008 примерно также, глаз да глаз нужен, да

  • http://www.sdl.ru TSS

    В старенкой VS6 прирост 15% всего. По сгенеренному асму явно видно двойное обращение к памяти в m_pParts[][]
    Intel 9.1 выдает 25% (на /0x) /разница же между VC и ICC колоссальная – порядка 410-415% прироста/
    Интел, кстати, догадывается не вычислять адреса при каждом обращении в первом цикле и использует [edi+ecx*8+4] против [edi+ecx*8] для if().

  • http://www.leningrad.spb.ru/ shodan

    В смысле разника между icc /ox против cl /O2 в пять раз?!
    А конкретные цифры можно?

  • CreatorCray

    ICC 11.1.35 выдал следующий код (такой же выдал и ICC 10.1.21, только регистры выбрал другие)

    ;;; iSum1 += f[j].Getter1 ( l );
    test esi, esi
    je .B1.24
    .B1.23:
    mov edx, DWORD PTR [4+edi+ebx*8]
    mov edx, DWORD PTR [edx+ebp*4]
    jmp .B1.25
    .B1.24:
    mov edx, DWORD PTR [edi+ebx*8]
    mov edx, DWORD PTR [edx+ebp*4]
    .B1.25:

    VC7.1
    mov cl, BYTE PTR _l$[esp+84]
    test cl, cl
    je SHORT $L55749
    mov ecx, DWORD PTR [esi+eax*8+4]
    jmp SHORT $L55778
    $L55749:
    mov ecx, DWORD PTR [esi+eax*8]
    $L55778:
    mov ecx, DWORD PTR [ecx+edi*4]

    Выполнение:
    >ICCTest.exe
    off=2 part=0
    sum1=300000000 time1=153350
    sum2=300000000 time2=145983

    >VC71Test.exe
    off=1 part=1
    sum1=500000000 time1=192031
    sum2=500000000 time2=146246

  • kayru

    Вот еще на тему branchless select-ов статья: http://assemblyrequired.crashworks.org/tag/branchless/