Случилось странное – я столкнулся с буквально классической задачей с собеседования в реальной жизни. Задача состоит в том, что необходимо найти первый не нулевой бит в массиве. Поиск должен происходить максимально быстро, скорость поиска желательно получить приближённую к линейной. Никаких правил по распределению единиц в массиве нет. Массив не велик и должен не вылезать за пределы одной кэш-линии.
Родились 3 варианта алгоритма, одна часть которого общая во всех случаях, вторая специфическая.
Общая часть сводится к поиску первого 32 разрядного слова с хотя бы одним не нулевым битом. Дальше, в найденном 32 разрядном слове ищем первый не нулевой бит. Я не знаю как можно оптимизировать первую часть алгоритма, так что ищу простым перебором.
Со второй частью вариантов куда больше. Первый приходящий в голову это последовательный перебор всех 32 битов по маске с одной установленной единицей, которая сдвигается на каждой из итераций. Вариант откровенно херовый, т.к. он будет по разному себя вести на разных машинных архитектурах (big/little -endian). Тем не менее, вариант для little-endian.
{
uint32_t block_mask = 0xFFFFFFFF;
uint32_t bit_mask = 0x80000000;
int i, j,
blocks_count = buff_len / sizeof(uint32_t),
bits_count = sizeof(uint32_t) * 8;
uint32_t *data = (uint32_t*)buffer;
for( i = 0; i < blocks_count; ++i )
{
if( data[i] & block_mask )
{
for( j = 0; j < bits_count; ++j )
{
if( data[i] & bit_mask )
break;
bit_mask = bit_mask >> 1;
}
break;
}
}
return i*buff_len+(sizeof(uint32_t)-(j/8+1))*8+(j%8);
}
Чуть подумав возникает небольшое упрощение: в найденном 32 разрядном слове, сначала, находим нужный байт, а уже в нем ищем бит. Этот вариант от архитектуры процессора не зависит и вобщем-то не плох, т.к. не требует никаких дополнительных затрат.
{
uint8_t bit_mask = 0x80;
int i, j, k,
blocks_count = buff_len / sizeof(uint32_t);
uint32_t *data = (uint32_t*)buffer;
char *sub_data;
for( i = 0; i < blocks_count; ++i )
{
if( data[i] & 0xFFFFFFFF )
{
sub_data = (char*)&data[i];
for( j = 0; j < sizeof(uint32_t); ++j )
{
if( sub_data[j] & 0xFF )
{
for( k = 0; k < 8; ++k )
{
if( sub_data[j] & bit_mask )
break;
bit_mask = bit_mask >> 1;
}
break;
}
}
break;
}
}
return i*buff_len + j*8 + k;
}
Более быстрым, но в то же время и вызывающим дополнительные расходы будет вариант с таблицами, указывающими на позицию первого не нулевого бита. Для начала вариант с таблицами на байт.
static int init_table()
{
int i, pos = 0;
uint8_t bit_mask = 0x80;
for( i = 0xFF; i >= 0; --i )
{
if( !(i & bit_mask) )
{
++pos;
bit_mask = bit_mask >> 1;
}
table[i] = pos;
}
}
int table_pos(char *buffer, size_t buff_len)
{
uint8_t bit_mask = 0x80;
int i, j, k,
blocks_count = buff_len / sizeof(uint32_t);
uint32_t *data = (uint32_t*)buffer;
char *sub_data;
for( i = 0; i < blocks_count; ++i )
{
if( data[i] & 0xFFFFFFFF )
{
sub_data = (char*)&data[i];
for( j = 0; j < sizeof(uint32_t); ++j )
{
if( sub_data[j] & 0xFF )
break;
}
break;
}
}
return i*buff_len + j*8 + table[sub_data[j]];
}
Подумалось, что скорость может возрасти, если построить таблицу не для байта, а для 16 битного слова.
static int init_big_table()
{
int i, pos = 0;
uint16_t bit_mask = 0x8000;
for( i = 0xFFFF; i >= 0; --i )
{
if( !(i & bit_mask) )
{
++pos;
bit_mask = bit_mask >> 1;
}
big_table[i] = pos;
}
}
int big_table_pos(char *buffer, size_t buff_len)
{
int i, j,
blocks_count = buff_len / sizeof(uint32_t);
uint32_t *data = (uint32_t*)buffer;
uint16_t *sub_data;
for( i = 0; i < blocks_count; ++i )
{
if( data[i] & 0xFFFFFFFF )
{
sub_data = (uint16_t*)&data[i];
for( j = 0; j < sizeof(uint16_t); ++j )
{
if( sub_data[j] & 0xFFFF )
break;
}
break;
}
}
return i*buff_len + j*16 + big_table[sub_data[j]];
}
Для 32 разрядных слов таблицы по вполне понятным причинам строить не стал.
А вот и замеры по скорости. Зависимость времени поиска от позиции ненулевого бита в 32 разрядном слове.
В целом, вариант с таблицей более быстрый, но требует предварительной инициализации, что не очень радует. Но с учетом ускорения поиска в 2 раза, на это можно пойти.
[Update] И еще один вариант, благодаря наводке Miroslav Rubanets.
{
uint32_t block_mask = 0xffffffff;
int i, j, blocks_count = buff_len / sizeof(uint32_t);
uint32_t *data = (uint32_t*)buffer;
for( i = 0; i < blocks_count; ++i )
{
if( data[i] & block_mask )
{
j = __builtin_clz( data[i] );
break;
}
}
return i*buff_len+(sizeof(uint32_t)-(j/8+1))*8+(j%8);
}
Как видно из обновленного графика (выше) вариант “сливает” таблицам, но все же куда лучше чем перебор со сдвигом.
это тест на низкоуровневого программиста. Тот кто пройдет знает что в процессоре есть команда кто не знает – будет писать таблички что не влазят в L1.
Для кроссплатформенности можно забить статический binary search, но во всех интересных процессорах команда есть.
Какая команда в процессоре есть?
на практике никто не вспоминает так как обертка над __builtin_clz/__builtin_ctz из gcc и _BitScanForward/_BitScanReverse из msvc решает эти вопросы. Там же и plain C пристраивается в конец. Механизм интринсиков он конечно зделан не для людей а для машин, но там где биты вместо байтов решают там и без них никак.
Не знал про такие функции, спасибо за наводку! Кстати, добавил с ней тоже вариант, таблицам проигрывает.
Можно еще сделать генерацию таблицы в компайлтайме. Как то так
Спасибо, так даже проще
Добрый день, сразу хочу сказать, что видел дату поста, знаю, что давно написано
Хотел спросить, почему для получения итогового индекса бита номер 32хбитового блока домножается на buff_len везде? он разве не на bits_count = sizeof(uint32_t) * CHAR_BITS должен домножаться?
И еще, почему не проверяется и не рассматривается случай, когда размерность массива не кратна sizeof(uint32_t)? В условиях это не оговорено же.
Деталей не помню, выглядит действительно как-то подозрительно, сейчас мне кажется что вместо i*buff_len должно быть что-то в духе i*size_of(uint32_t)*8. На сколько я понимаю, это как раз то, что ты написал. А приведенный вариант откровенная херота :???:
Размерность не проверяется, так как делалось для такого случая (там видоизмененный вариант), когда она гарантированно кратна 4.