2011-02-25 09:08:03 UTC

При написании crc32 калькулятора, а точнее при попытке оптимизации алгоритма расчета crc32, я столкнулся с интересным выводом, — вроде бы с виду более быстрый код, оказывается более медленным. Ещё один факт в копилку того, что нельзя делать выводы о производительности, основываясь на интуиции и не делая замеров — в 9 случаях из 10 вы окажетесь неправы.

Итак, имеем две реализации функции расчета crc32, первая:

void Crc32Update(Crc32Context* ctx, const void* data, uint32_t len)
{
    uint32_t i = 0;
    const uint8_t* block = data;

    while (i < len) {
        ctx->crc = ((ctx->crc >> 8) & 0x00FFFFFF) ^ crcTab[(ctx->crc ^ *block++) & 0xFF];
        ++i;
    }
}

И вторая.

void Crc32Update(Crc32Context* ctx, const void* data, long len)
{
    const uint8_t* block = data;

    while (--len >= 0) {
        ctx->crc = ((ctx->crc >> 8) & 0x00FFFFFF) ^ crcTab[(ctx->crc ^ *block++) & 0xFF];
    }
}

Вторая с виду кажется быстрее, — компактнее, нет лишней локальной переменной, но это только с виду. На самом деле, она медленнее процентов на 10 первой функции.

Посмотрим, что же сгенерировал компилятор для обеих функций, первой:

PUBLIC	_Crc32Update
; Function compile flags: /Ogtp
;	COMDAT _Crc32Update
_TEXT	SEGMENT
_Crc32Update PROC					; COMDAT
; _ctx$ = edx
; _data$ = edi
; _len$ = esi

; 70   :     uint32_t i = 0;

	xor	ecx, ecx

; 71   :     const uint8_t* block = data;
; 72   : 
; 73   :     while (i < len) {

	test	esi, esi
	je	SHORT $LN1@Crc32Updat
	push	ebx
$LL2@Crc32Updat:

; 74   :         ctx->crc = ((ctx->crc >> 8) & 0x00FFFFFF) ^ crcTab[(ctx->crc ^ *block++) & 0xFF];

	movzx	ebx, BYTE PTR [ecx+edi]
	mov	eax, DWORD PTR [edx]
	xor	ebx, eax
	and	ebx, 255				; 000000ffH
	shr	eax, 8
	xor	eax, DWORD PTR _crcTab[ebx*4]

; 75   :         ++i;

	inc	ecx
	mov	DWORD PTR [edx], eax
	cmp	ecx, esi
	jb	SHORT $LL2@Crc32Updat
	pop	ebx
$LN1@Crc32Updat:

; 76   :     }
; 77   : }

	ret	0
_Crc32Update ENDP
}

И второй:

PUBLIC	_Crc32Update
; Function compile flags: /Ogtp
;	COMDAT _Crc32Update
_TEXT	SEGMENT
_len$ = 8						; size = 4
_Crc32Update PROC					; COMDAT
; _ctx$ = edx
; _data$ = ecx

; 69   : {

	push	ebp
	mov	ebp, esp
	push	esi
	mov	esi, DWORD PTR _len$[ebp]

; 70   :     const uint8_t* block = data;
; 71   : 
; 72   :     while (--len >= 0) {

	dec	esi
	js	SHORT $LN1@Crc32Updat
	push	edi
	npad	5
$LL2@Crc32Updat:

; 73   :         ctx->crc = ((ctx->crc >> 8) & 0x00FFFFFF) ^ crcTab[(ctx->crc ^ *block++) & 0xFF];

	movzx	edi, BYTE PTR [ecx]
	mov	eax, DWORD PTR [edx]
	xor	edi, eax
	and	edi, 255				; 000000ffH
	shr	eax, 8
	xor	eax, DWORD PTR _crcTab[edi*4]
	inc	ecx
	dec	esi
	mov	DWORD PTR [edx], eax
	jns	SHORT $LL2@Crc32Updat
	pop	edi
$LN1@Crc32Updat:
	pop	esi

; 74   :     }
; 75   : }

	pop	ebp
	ret	0
_Crc32Update ENDP
}

Что же видно в результате сравнения:

1. Так как параметр модифицируется в коде, он вынужден выгрузить её из стека в регистр — несколько лишних команд. В первом же варианте, видя, что ничего не меняется и количество аргументов функции маленькое, он смог оптимизировать и засунуть параметр в регистр esi.
2. Дополнительно, перед каждым запуском цикла, есть уменьшение значения регистра, в который загружен этот параметр, чего нет в другом варианте.

В итоге, если функция вызывается миллионы или миллиарды раз, эти дополнительные инструкции, начинают вносить свой вклад в замедление.