Полуночные открытия
Писал я как-то генерацию чисел с m установленными битами через рекурсию и в цикле:
Первая работает быстрее второй раза в три для
, как и положено.
— Красиво ты ненулевые биты считаешь, — сказал
shuffle_c.
— Банальный трюк, — хмыкнул я и переставил ++c внутрь цикла. И время выполнения gen2(28, 14) вдруг возросло с 9.2 секунд до 11.2. Я воскликнул:
— Нипаняяятна! — и принялся разбираться.
Тело цикла:
Тело цикла:
Компилятор вынужден был, придерживаясь семантики оператора запятая, поместить инкремент (inc ecx) после вычисления побитовой конъюнкции, из-за чего не смог воспользоваться ее результатом сразу же в условном переходе, для чего ему пришлось добавить лишнюю операцию — test eax, eax.
Этот случай, на мой взгляд, отлично иллюстрирует две простые истины.
Истина №1. Писать на ассемблере эффективнее компилятора практически невозможно.
Истина №2. Но язык ассемблера надо знать, чтобы не допускать глупостей в высокоуровневом коде.
В этом посте есть одно пасхальное яйцо для самых внимательных. Чтобы его найти, не обязательно знать программирование.
template<void (*func)(int)>
void gen(int n, int m, int cn = 0, int cm = 0, int vec = 0)
{
if (cn == n) func(vec);
else {
if (n - cn > m - cm) gen<func>(n, m, cn + 1, cm, vec * 2);
if (cm < m) gen<func>(n, m, cn + 1, cm + 1, vec * 2 + 1);
}
}
template<void (*func)(int)>
void gen2(int n, int m)
{
for (int i = 0, len = (1 << n); i < len; ++i) {
int c = 0;
for (int u = i; u; u &= (u - 1)) ++c;
if (c == m) func(i);
}
}
void gen(int n, int m, int cn = 0, int cm = 0, int vec = 0)
{
if (cn == n) func(vec);
else {
if (n - cn > m - cm) gen<func>(n, m, cn + 1, cm, vec * 2);
if (cm < m) gen<func>(n, m, cn + 1, cm + 1, vec * 2 + 1);
}
}
template<void (*func)(int)>
void gen2(int n, int m)
{
for (int i = 0, len = (1 << n); i < len; ++i) {
int c = 0;
for (int u = i; u; u &= (u - 1)) ++c;
if (c == m) func(i);
}
}
Первая работает быстрее второй раза в три для
— Красиво ты ненулевые биты считаешь, — сказал
shuffle_c.— Банальный трюк, — хмыкнул я и переставил ++c внутрь цикла. И время выполнения gen2(28, 14) вдруг возросло с 9.2 секунд до 11.2. Я воскликнул:
— Нипаняяятна! — и принялся разбираться.
for (int u = i; u; u &= (u - 1)) ++c;
Тело цикла:
.text:004012F8 lea edi, [eax-1]
.text:004012FB inc ecx
.text:004012FC and eax, edi
.text:004012FE jnz short loc_4012F8
.text:004012FB inc ecx
.text:004012FC and eax, edi
.text:004012FE jnz short loc_4012F8
for (int u = i; u; u &= (u - 1), ++c);
Тело цикла:
.text:004012F8 lea edi, [eax-1]
.text:004012FB and eax, edi
.text:004012FD inc ecx
.text:004012FE test eax, eax
.text:00401300 jnz short loc_4012F8
.text:004012FB and eax, edi
.text:004012FD inc ecx
.text:004012FE test eax, eax
.text:00401300 jnz short loc_4012F8
Компилятор вынужден был, придерживаясь семантики оператора запятая, поместить инкремент (inc ecx) после вычисления побитовой конъюнкции, из-за чего не смог воспользоваться ее результатом сразу же в условном переходе, для чего ему пришлось добавить лишнюю операцию — test eax, eax.
Этот случай, на мой взгляд, отлично иллюстрирует две простые истины.
Истина №1. Писать на ассемблере эффективнее компилятора практически невозможно.
Истина №2. Но язык ассемблера надо знать, чтобы не допускать глупостей в высокоуровневом коде.
В этом посте есть одно пасхальное яйцо для самых внимательных. Чтобы его найти, не обязательно знать программирование.
