- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
#include <stdio.h>
#include <string.h>
#include <inttypes.h>
void swap(uint8_t *x, uint8_t *y)
{
uint8_t tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
// эту хуйню тоже можно нагенерировать
uint64_t cmp_bits(uint8_t a[restrict 9])
{
return
((uint64_t)(a[0] < a[1]) << 0) |
((uint64_t)(a[0] < a[2]) << 1) |
((uint64_t)(a[0] < a[3]) << 2) |
((uint64_t)(a[0] < a[4]) << 3) |
((uint64_t)(a[0] < a[5]) << 4) |
((uint64_t)(a[0] < a[6]) << 5) |
((uint64_t)(a[0] < a[7]) << 6) |
((uint64_t)(a[0] < a[8]) << 7) |
((uint64_t)(a[1] < a[2]) << 8) |
((uint64_t)(a[1] < a[3]) << 9) |
((uint64_t)(a[1] < a[4]) << 10) |
((uint64_t)(a[1] < a[5]) << 11) |
((uint64_t)(a[1] < a[6]) << 12) |
((uint64_t)(a[1] < a[7]) << 13) |
((uint64_t)(a[1] < a[8]) << 14) |
((uint64_t)(a[2] < a[3]) << 15) |
((uint64_t)(a[2] < a[4]) << 16) |
((uint64_t)(a[2] < a[5]) << 17) |
((uint64_t)(a[2] < a[6]) << 18) |
((uint64_t)(a[2] < a[7]) << 19) |
((uint64_t)(a[2] < a[8]) << 20) |
((uint64_t)(a[3] < a[4]) << 21) |
((uint64_t)(a[3] < a[5]) << 22) |
((uint64_t)(a[3] < a[6]) << 23) |
((uint64_t)(a[3] < a[7]) << 24) |
((uint64_t)(a[3] < a[8]) << 25) |
((uint64_t)(a[4] < a[5]) << 26) |
((uint64_t)(a[4] < a[6]) << 27) |
((uint64_t)(a[4] < a[7]) << 28) |
((uint64_t)(a[4] < a[8]) << 29) |
((uint64_t)(a[5] < a[6]) << 30) |
((uint64_t)(a[5] < a[7]) << 31) |
((uint64_t)(a[5] < a[8]) << 32) |
((uint64_t)(a[6] < a[7]) << 33) |
((uint64_t)(a[6] < a[8]) << 34) |
((uint64_t)(a[7] < a[8]) << 35);
}
void printshit(uint8_t a[restrict 9])
{
size_t i = 0;
while(*a != 4)
{
a++;
i++;
}
printf("arr[%" PRIu64 "] = %zu\n", cmp_bits(a), i);
}
void permute(char *a, size_t l, size_t r)
{
size_t i;
if (l == r)
printshit(a);
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i));
}
}
}
int main()
{
uint8_t a[] = {0,1,2,3,4,5,6,7,8};
size_t n = 9;
permute(a, 0, n-1);
return 0;
}
Ну и еще такое говно можно как-нибудь аппаратно реализовать
Какая универсальность )))
Борманд в прошлом треде уже показал pshufb.
В принципе если компилятор достаточно умён он шаффлы
Превратит в MMX/SSE инструкции.
Но обычно они сливают этот шанс если что-то посложнее тупого копирования (((
Надо будет попробовать расширить тот говнопример на произвольные размеры и шаффлы.
Походу интринсиками ебашить -- пока единственный способ.
Почему же?
Интринсиками непортабельно.
А вот препроцессором имитировать PSHUFB чтобы мракос развернулся в мувы int8_t внутри структуры, тогда код будет портабельный.
На умном компиляторе быстрый, на глупом — медленный, со сдвигами и битовыми масками.
Это если он не охуеет от количества операций... Должен же быть какой-то порог в пределах которого он мёржит операции в одну.
8 — MMX
16 — SSE
32 — AVX-2
В примере выше, он легко понимает что копирования 16 элементов это сдвиг.
Как будет вдохновение попробую сделать тасующий регистр на препроцесоре.
Ну вот, всё работает:
https://godbolt.org/z/KsPq5soo9
Осталось шуффлы напилить.
Да, на массивах и векторах-структурах шланг городит дичь.
А вот недавняя версия gcc 12.1 структуры векторизует хорошо, а массивы просто отлично.
>Походу интринсиками ебашить -- пока единственный способ.
Я по заветам Царя переделал на массивы: выхлоп стал ГОРАЗДО чище.
https://godbolt.org/z/478cY9jP7
GCC 11.3 и младше конечно так хорошо не умели, так что налицо прогресс.
Правда первое перемешивание он догадался через pshuflw
А последующие почему-то через джва pshufb.
https://gcc.gnu.org/gcc-12/changes.html
Vectorization is enabled at -O2 which is now equivalent to the original -O2 -ftree-vectorize -fvect-cost-model=very-cheap. Note that default vectorizer cost model has been changed which used to behave as -fvect-cost-model=cheap were specified.
Интересно что даже с этими флагами прошлые версии GCC не могут нормально векторизовать код.
Интринсики — непортабельное, трудночитаемое говно.
А через массивы, у меня и на арме хороший векторный выхлоп получился
Видимо оно внутри решает что шаффлить батами лучше. Что мы видим и по SSE выхлопу: гцц и тут юзает pshufb
Вдохной массив отсортирован или нет?
Но говнище редкостное.
Не проще ли будет за O(N*log N) его отсортировать и просто взять средний элемент?
Зацени сдвиговый регистр: https://govnokod.ru/28289
Находим индексы медианы для всех возможных перестановок хуйни, чтоб сделать таблицу соответствия, и потом можно сделать 36 сравнений, по результатам этих сравнений через эту таблицу можно найти, по какому индексу тут медиана
36 сравнений это (N*N-N)/2=(9*9-9)/2.
То есть O(N²)
> для быстрого нахождения медианы
Это так же "быстро", как осортировать массив наиболее тупым способом: питузком.
А асимптотические оценки имеют смысл только на очень больших размерах
Тратить O(n^2) по площади кристалла на компараторы тоже не айс.
Хотя, возможно, в какой-то обработке сигналов может пригодиться такая сортировка по 4-8 элементов на каждый такт. Что-нибудь в духе поиска медианы в небольшом окне.
Привет. Посоветуйте актуальный FPGA для начала. Например по книжке вирта Проект Оберон пройти.
У меня была de0 nano. Камень там неплохой, но вот по периферии она совсем голая. Можно ещё у марсохода посмотреть, вроде неплохие платы делали если ещё живы.
Ну и морально готовься к ёбле с жуткой, уёбищной проприетарщиной. С опенсурсом в этой области всё совсем плохо, хотя есть прогресс в том же Yosys.
Плюс многие IP Core (модули) закрытые и\или платные. Но с этим ситуация гораздо лучше, опенсурсных модулей и проектов куча.
Кроме верилога ещё обычно бывает VHDL. Ну и схемы в гуйне можно порисовать если хочется по-старинке.
Бля, я думал это область, в которой вообще по дефолту всё опенсурсное. Пиздец...
А нахуя это всё тогда? Чисто экспериментировать с архитектурой? Делать медленный процессор, для которого js буде ассемблером? Я хочу fpga чтобы гарантировать, что у меня в стеке нет аппаратных закладок, и для этого желаю контролировать всё начиная от кристалла. И получаю в итоге проприетарный программатор. Мда...
Сделать быструю аппаратную реализацию какого-то алгоритма.
Возможность не меняя железо перепрограммировать его в другой алгоритм.
ASIC'и на чём-то надо прототипировать. Ну и какие-нибудь реалтаймовые задачки, с которыми проц тупо не справится.
З.Ы. Если хочешь опенсурса -- кроме i386/amd64 вообще сложно какое-то актуальное железо найти. Это будут или какие-нибудь слабые микроконтроллеры или говно мамонта, на которое вендору уже насрать.
Опенсурсный программатор, к слову несложно найти или даже написать. Там достаточно высрать битстрим из файла в какой-нибудь jtag-over-usb.
Проприетарщина таится именно в синтезе этого битстрима из твоих исходников. Ну и причина довольно прозаичная -- чем больше кишков кристалла вендор опубликует, тем быстрее его идею склонируют другие. А без знаний о кишках чипа синтез невозможен, увы. Разве что для низкочастотных схем.
fixed
Не проще взять qsort?
https://godbolt.org/z/8frGY1GG1
Выхлоп после препроцессора:
Нет blendps и shuffle.
Хотя шаффлы вынесенные в отдельные функции нормально превращаются в SSE-инструкции.
И компилятор не догадывается что его равноценно можно использовать для целых.
В оригинале https://govnokod.ru/24496#comment452141 чтобы обойти это дерьмо кастят в флоаты: _mm_castsi128_ps, а потом обратно в целый __m128i.
Наверное blend нетрудно реализовать через битовые маски чтобы сгенерить семейство инструкции pand.
А бленд вручную лепить из and и or -- это же медленнее будет...
З.Ы. А если версию SSE поднять, там не завезли для интов аналог?
Да. Плюс оно даже через and/or не понимает.
> З.Ы. А если версию SSE поднять, там не завезли для интов аналог?
Я вчера перепробовал все вореции с этим struct union.
SSE4 — максимальная. От 4.2 пользы нет. А дальше AVX и VEX префиксы.
Практически тоже самое, только с трехоперандными командами (меньше мувов).
Меня спасла царская структура данных массив.
С ней векторизуется хорошо. Но только на последнем гцц.
https://govnokod.ru/28309#comment782800
https://godbolt.org/z/478cY9jP7