[C/C++] перетасовка бит в целом числе

Писать тесты, сравнивать производительность.

Если число бит известно на этапе компиляции, то о чем вообще речь? Просто сгенерируй формулу.

Известно не число бит, а число нулей к-е между ними вставляются. В смысле сгенерируй формулу? Исходные числа то разные и определяются в рантайме.

Если кол-во и положение нулей не меняется, то между входными и выходными числами всегда будет прослеживаться зависимость. Прогони через алгоритм необходимое число значений и вырази зависимость формулой.

Наверное через битовые поля будет быстрее, чем сдвиги, если нулей мало. Если нулей много, то сдвиги должны быть быстрее. Полагаю так...

а число нулей к-е между ними вставляются

ну и? раз число вложится в 64 бита, то вариантов немного - выпиши их руками

Уф... исходный пост кто нить читал? Формула пишется влет через битовые операции (вар. 1), но работает долго.

То что Вы предлагаете вообще индукцией называется, нафига она нужна? Если Вы про зависимость числа конечных значений от исходных, дык они равны, преобразование взаимно однозначное.

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

const int Z = ...; // число нулей 
int R; // длина исходного числа
int x; // исходное число
long offset = x&1; // результат
for( int i=1; i<R; i++ ) offset |= ( x&(1<<i) ) << i*Z;

Тогда я не понял задачу. Если тебе нужно просто проредить битовую строку неизвестной длины, то:

uint64_t spread_bits(uint64_t in)
{
   uint64_t out = 0;

   out |= (in & 1) << N;
   out |= (in & 2) << (2*N);
   out |= (in & 4) << (3*N);
   /* и т.д. */
   return out;
}

заодно оформить функцию как шаблон от N

заодно оформить функцию как шаблон от N

Ну, например... хотя я подозреваю, что тут можно порезвиться на уровне ассемблера: использовать несколько регистров и/или частей регистра на amd64, чтобы достичь максимального параллелизма.

Это долго работает. Там где это планируется использовать, борьба за отдельные такты идет...

Я думал про какие то варианты, скажем умножение и потом xor (гипотетически так можно неск битов сразу обработать), но вдруг есть какие то хитрые операции о которых я не знаю?

Это долго работает

Что «это» - твой цикл или моя гипотетическая реализация из фиксированного числа команд?

борьба за отдельные такты идет...

Тогда вручную распределяй операции по регистрам, так, чтобы они выполнялись в параллель. Но это всё равно писать кодогенератор.

вдруг есть какие то хитрые операции о которых я не знаю?

Я таких трюков не знаю, но можешь посмотреть здесь: http://graphics.stanford.edu/~seander/bithacks.html

Что «это» - твой цикл или моя гипотетическая реализация из фиксированного числа команд?

И то и то вообще то;-)

Я таких трюков не знаю, но можешь посмотреть здесь

Спасибо!

а может какое-нибудь аппаратное решение замутить? Схема примитивной должна быть, тут главное, как её на нужной скорости к компу прицепить )

У нас опыта создания аппаратных решений нет. Кроме того, я не очень представляю, как это аппаратное решение можно прикрутить непосредственно к кристаллу проца/GPU.

Какая таргет платформа?

Что «это» - твой цикл или моя гипотетическая реализация из фиксированного числа команд?

И то и то вообще то;-)

Тогда я бы попробовал переписать на асме. Что-то дамп сгенерированного gcc кода какой-то неубедительный.

ну не знаю, теоретически можно какой-нибудь фейковый модуль памяти сделать, в который по любому адресу можно записать исходное число, а читаться будет разреженное. Только надо как-то так сделать, чтобы ОС не пыталась его использовать по назначению

Какая таргет платформа?

x86_64

теоретически можно какой-нибудь фейковый модуль памяти сделать

Модуль RAM? O_o

я же говорю, фейковый. Хранить он будет только 64 бита, а прикидываться будет например 1Гб (для совместимости, чтоб комп запустился), читать и писать в них можно по любому адресу, выделенному для этого модуля

Тогда я бы попробовал переписать на асме. Что-то дамп сгенерированного gcc кода какой-то неубедительный.

По ссылке вроде есть некая реализация чего то похожего в частном случае, с массивом - число обрабатывается побайтно. Наверное это оптимальный вариант, надо будет тока аккуратно сделать...

Памяти??? Наск понимаю, нам тогда нужен модуль кэша верхнего уровня;-) Возьметесь пропатчить кристаллы процов нашего кластера?

я же говорю, фейковый.

Что фейковый, понятно. Я думал, ты ошибся насчет «модуля RAM». Но, если ты имел в виду именно RAM, ты сказал такую чушь...

а что не так? )

вроде есть некая реализация чего то похожего в частном случае, с массивом - число обрабатывается побайтно.

с lookup table? ИМХО, твою задачу можно сделать целиком на регистрах.

Про кэш тебе уже сказали... и ты правда предлагаешь модуль, висящий на шине памяти?

ну теоретически, насколько знаю, x86 архитектура позволяет объявить некоторые участки физического адресного пространства некэшируемыми, например, область видеопамяти. Так что можно выключить кэширование для этого модуля.

А вообще, пусть ТС озвучит требуюемую минимальную производительность, в битах в секунду. Вдруг и через PCI-E сойдет тогда подключение ))

с lookup table? ИМХО, твою задачу можно сделать целиком на регистрах.

Да. Асма я вообще не знаю, но у нас навроде есть знающие товарищи. Правда это ж придется под каждый проц свою реализацию писать... сомнительное удовольствие, и как там с конвейром то будет? Вообще то в этой задачи крутится еще много математики, векторизованной, специально все пишется так что бы оно конвееризовывалось хорошо, и когда конвейр слетает это фигово...

Пока наверное сделаю тупо таблицу на весь диапазон, для 2^10 это всего 8К, зато дает макс гибкость. Там поглядим...

А вообще, пусть ТС озвучит требуюемую минимальную производительность, в битах в секунду.

Очень условно одно преобразование на 10 тактов одного ядра проца.

это ж придется под каждый проц свою реализацию писать...

Не думаю. Просто обобщенная amd64-реализация, думаю, вполне подойдет.

и как там с конвейром то будет?

Там нужно не конвейер использовать, а суперскалярность. Все строки моей функции, в принцие, могут выполняться в параллель, если пишут значения каждая в свой регистр. В конце результат or'иться.

о в этой задачи крутится еще много математики [...] когда конвейр слетает это фигово...

Замена задачи на процессоре происходит раз в миллисекунды, дай ТНБ. Так что за конвейер я бы точно не беспокоился.

x86 архитектура позволяет объявить некоторые участки физического адресного пространства некэшируемыми, например, область видеопамяти

Мде. Ты хоть какое-то отношение к разработке устройств имеешь? Даже если ты сделаешь модуль, который пригоден для навешивания в шину памяти, он займет слот. И для его использования придется делать патч к ядру.

Очень условно одно преобразование на 10 тактов одного ядра проца.

Очень условно считаем, пусть тактовая частота процессора 3ГГц, получаем 3*10^8 преобразований в секунду по 64 бита = 19.2Гбит/с, что укладывается в характеристики PCIe x12 :)

Еще вопрос, числа нужно преобразовывать сразу по мере их возникновения или можно обрабатывать блоками?

И для его использования придется делать патч к ядру.

ну да, придется. А что?

И для его использования придется делать патч к ядру.

ну да, придется. А что?

Кэша нет - нормально, ХЗ как разрабатывать - тнормально, слот занимает - нормально, требует для использования нестандартное ядро - тоже нормально. Ты явно не понимаешь, о чем говоришь.

ну так ТС хочет странного, а обычные процессоры под такие задачи не заточены :) Какая задача, такое и решение :)

Я уже предложил PCI-e вместо шины памяти, если задача позволяет обрабатывать числа блоками относительно крупного размера

когда счет уже на такты идет, только ассемблер :) давно сталкивался с подобной задачей, но только под 8 битный микроконтроллер. Написал набор макросов, вроде:

#define bit_copy(src_bit, dest_reg, dest_bit) \
__asm__ __volatile__(                         \
"bst __tmp_reg__,%0"     "\n\t"               \
"bld %1,%2"              "\n\t"               \
:                                             \
:"I"(source_bit),"r"(dest_reg),"I"(dest_bit)  \
)

Не рекомендую увлекаться табличными методами. При кажущейся сложности O(1), их производительность на деле сильно зависит от состония кеша. Я бы порекомендовал как раз реализовать первый «долгий» способ, только производить эти действия не в цикле, а написать кодогенератор, разворачивающий такой цикл на этапе компиляции. Думаю, нужно стремиться к чему-то вроде (да приведенного примера b3 b2 b1 b0 -> b3 0 0 b2 0 0 b1 0 0 b0):

#define POS0 0
#define POS1 3
#define POS2 6
#define POS3 9

uint64_t transform(uint64_t in)
{
  uint64_t out = 0;
  out |= (in << POS0) & (1 << POS0);
  out |= (in << POS1) & (1 << POS1);
  out |= (in << POS2) & (1 << POS2);
  out |= (in << POS3) & (1 << POS3);
  return out;
}

Анализ вывода gcc -S -O2 показывает, что компилятор очень неплохо это оптимизирует.

В общем-то ты занимаешься преждевременной оптимизацией. Сначала замерь производительность такого решения «в лоб», а потом уже начинай оптимизировать.

А какая там латентность то у PCI-е?;-)

Странно, что ПЛИСку никто не предложил.

Странно, что ПЛИСку никто не предложил.

Совершенно очевидно, что PCIe-модуль будет на ПЛИС %)

Я бы порекомендовал как раз реализовать первый «долгий» способ, только производить эти действия не в цикле, а написать кодогенератор, разворачивающий такой цикл на этапе компиляции.

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

uint64_t transform1(uint64_t in){
  uint64_t out = in&1;
  out |= (in & 1) << 3;
  out |= (in & 2) << 6;
  out |= (in & 4) << 9;
  out |= (in & 8) << 12;
  out |= (in & 16) << 15;
  out |= (in & 32) << 18;
  out |= (in & 64) << 21;
  out |= (in & 128) << 24;
  return out;
}

uint64_t transform2(uint64_t in){
  uint64_t out = in&1;
  for( int i=1; i<8; i++ ) out |= ( in&(1<<i) )<<(3*i);
  return out;
}

g++ -S -O3:

_Z10transform1m:
.LFB12:
	.cfi_startproc
	.cfi_personality 0x3,__gxx_personality_v0
	movq	%rdi, %rcx
	movq	%rdi, %rdx
	andl	$1, %ecx
	andl	$2, %edx
	leaq	0(,%rcx,8), %rax
	salq	$6, %rdx
	orq	%rdx, %rax
	movq	%rdi, %rdx
	andl	$4, %edx
	orq	%rcx, %rax
	salq	$9, %rdx
	orq	%rdx, %rax
	movq	%rdi, %rdx
	andl	$8, %edx
	salq	$12, %rdx
	orq	%rdx, %rax
	movq	%rdi, %rdx
	andl	$16, %edx
	salq	$15, %rdx
	orq	%rdx, %rax
	movq	%rdi, %rdx
	andl	$32, %edx
	salq	$18, %rdx
	orq	%rdx, %rax
	movq	%rdi, %rdx
	andl	$128, %edi
	andl	$64, %edx
	salq	$24, %rdi
	salq	$21, %rdx
	orq	%rdx, %rax
	orq	%rdi, %rax
	ret
	.cfi_endproc

_Z10transform2m:
.LFB13:
	.cfi_startproc
	.cfi_personality 0x3,__gxx_personality_v0
	movq	%rdi, %rdx
	movq	%rdi, %rax
	movq	%rdi, %rcx
	andl	$2, %edx
	andl	$4, %eax
	andl	$1, %ecx
	salq	$6, %rax
	salq	$3, %rdx
	orq	%rax, %rdx
	movq	%rdi, %rax
	andl	$8, %eax
	orq	%rcx, %rdx
	salq	$9, %rax
	orq	%rax, %rdx
	movq	%rdi, %rax
	andl	$16, %eax
	salq	$12, %rax
	orq	%rax, %rdx
	movq	%rdi, %rax
	andl	$32, %eax
	salq	$15, %rax
	orq	%rax, %rdx
	movq	%rdi, %rax
	andl	$64, %eax
	salq	$18, %rax
	orq	%rax, %rdx
	movq	%rdi, %rax
	andl	$128, %eax
	salq	$21, %rax
	orq	%rdx, %rax
	ret
	.cfi_endproc

Фраза про преждевременную оптимизацию улыбнула (я ее сам регулярно произношу, так вот сейчас не тот случай). А тот код, что предложили Вы, делает не то что нужно;-)

Да, надо будет наверное потрясти специалистов по ассемблеру.

Шаблонную магию применить нельзя?

out |= (in & 1) << 3;

Заметь, что у red_eyed_penguin другие операции:

out |= (in << POS0) & (1 << POS0);

А нахрена?

Дык они же делают не то что нужно, он все время берет первый бит? И наск я этот вопрос изучал, -O3 всегда раскручивает короткие циклы с известным пределом.

Шаблонную магию применить нельзя?

По сравнению с теми же дефайнами ИМНО ничего не даст.

А нахрена?

Вообще то это реализация произвольного доступа к локально-рекурсивному массиву.

Дык они же делают не то что нужно, он все время берет первый бит?

ну там константы должны быть разные, да.