neon
Да, llvm е доста добър във векторизацията на такива елементарни цикли. Проблемите са с многомерни масиви. Донякъде ми се иска да видя какви биха били резултатите със SVE(2) и SME, но вероятно ще ме домързи. Ако си спомням правилно, инструкциите на SVE няма да крашнат ако данните които четеш излязал от валидното адресно пространство и с разни хватки с предикати скоростта може би ще е бърза и без да се дава дължината на стринга.
#include <immintrin.h>
#include <cstdio>
int spcalc( const char *data ) {
long long idata32 = (long long)data & -32LL;
unsigned offset = (unsigned)(unsigned long long)data & 31, valid, zerof, sf, pf;
__m256i *ym_data = (__m256i*)idata32,
ym_s = _mm256_broadcastb_epi8( *(__m128i*)"s" ),
ym_p = _mm256_broadcastb_epi8( *(__m128i*)"p" ),
ym_z = _mm256_xor_si256( ym_s, ym_s ),
ym_c;
;
int res;
valid = -1 << offset;
ym_c = *ym_data++;
zerof = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_z ) );
valid &= zerof ^ (zerof - 1);
sf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_s ) );
pf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_p ) );
res = __builtin_popcount( sf & valid ) - __builtin_popcount( pf & valid );
zerof &= valid;
while( !zerof ) {
ym_c = *ym_data++;
zerof = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_z ) );
valid = zerof ^ ( zerof - 1 );
sf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_s ) );
pf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_p ) );
res += __builtin_popcount( sf & valid ) - __builtin_popcount( pf & valid );
}
return res;
}
int main() {
printf( "%i\n", spcalc( "eeeeesssssppppp" ) );
return 0;
}
Тва е за х64 с - mavx2. Не съм го мерил за скорост. Би трябвало да изрине всеки арм заради 256 битовите вектори и специфичните инструкции.
ПС: Взех домейн. Остава да напиша форум на С++ като съм по-свободен. Рабина там ще е позволен дивеч.
https://github.com/Azareal/cppforo
TIR Урсула село ерген чекии.
То точно това беше антипатърна от линка - че сега кода е платформо зависим а ако просто го напишеш да е удобен за векторизиране от компилатора обикновено той се справя по добре отколкото ръчно оптимизиран платформен, че и написан на асемблер код. То тук би помогнал един варнинг с който да заградиш някакъв код и да му кажеш да мрънка ако не успее да го векторизира.
А ако ти се пише форум дали ще е на Ц++ или на нещо друго няма кой знае какво значение. Зависи какви са ти целите - бързо писане, бърз фронд енд, бърз бак енд - или комбинация от всички - и според това вариантите са безброй. Лично за мен избора последните 15 години е сведен до две платформи - има ли какви да е рестрицкии то отивам към чисто Ц, за всички останали неща ползвам жаваскрипт/тайпскрипт и ноде. Целта ми е минимизиране на инвестиция в учене на поредната модна платформа или език или фреймворк докато мога да решавам проблемите по които работя с вече научените неща. Ноде-то го избрах като алтернатива на .нет, че там майкрософт осраха точно тази възвръщаемост на инвестицията - тамън им свикнеш на нещо и те го заменят с нещо ново - било то гуи или веб или дб.
Мисля, че ти е ясно, че това с 256 битовите вектори не е задължително да е по-бързо. Например Neoverse V1 има два SVE execution unit-a с 256 битови вектори, докато V2 е с четири юнита със 128 битови вектори. Като тествах (Graviton 3 vs. Grace-Hopper) скоростта беше сравнима (като се коригират различията в честотата).
Кода ми явно не е много добър. 20 GiB/s на 3700Х закотвен на 3.6 Ghz. А тия батки говорят за 87 GB/s. 3700Х има цял 256 битов изпълнител.
#include <immintrin.h>
#include <cstdio>
#include <ctime>
int spcalc( const char *data ) {
long long idata32 = (long long)data & -32LL;
unsigned offset = (unsigned)(unsigned long long)data & 31, valid, zerof, sf, pf;
__m256i *ym_data = (__m256i*)idata32,
ym_s = _mm256_broadcastb_epi8( *(__m128i*)"s" ),
ym_p = _mm256_broadcastb_epi8( *(__m128i*)"p" ),
ym_z = _mm256_xor_si256( ym_s, ym_s ),
ym_c;
;
int res;
valid = -1 << offset;
ym_c = *ym_data++;
zerof = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_z ) );
valid &= zerof ^ (zerof - 1);
sf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_s ) );
pf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_p ) );
res = __builtin_popcount( sf & valid ) - __builtin_popcount( pf & valid );
zerof &= valid;
while( !zerof ) {
ym_c = *ym_data++;
zerof = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_z ) );
valid = zerof ^ ( zerof - 1 );
sf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_s ) );
pf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_p ) );
res += __builtin_popcount( sf & valid ) - __builtin_popcount( pf & valid );
}
return res;
}
#define G4PCOUNT 1
int main() {
char data[0x10000];
unsigned i;
int r;
clock_t start, stop;
for( i = 0; i < 0x10000; i += 4 ) {
data[i + 0] = 'a';
data[i + 1] = 'p';
data[i + 2] = 's';
data[i + 3] = 'z';
}
data[0xFFFF] = 0;
start = clock();
for( i = 0; i < G4PCOUNT * 0x10000; i++ ) {
r = spcalc( data );
}
stop = clock();
printf( "%f GiB/s\n", (float)( G4PCOUNT * 4 ) / ( (float)( stop - start ) / CLOCKS_PER_SEC ) );
return 0;
}
Без информация за размера е тегаво иначе. Тия затва се скатават от проверката за край на низа.
Виж как го тестват от гитхъб репозиторито: https://github.com/lunacookies/n-times-faster
На личния ми лаптоп (MacBookAir с М2) ми дава
basic:
12 iters
3.062 ns/b
0.327 GB/s
table:
107 iters
0.357 ns/b
2.802 GB/s
table_length:
181 iters
0.211 ns/b
4.747 GB/s
table_8:
259 iters
0.149 ns/b
6.697 GB/s
table_16:
290 iters
0.133 ns/b
7.501 GB/s
neon:
905 iters
0.042 ns/b
23.704 GB/s
neon_less_reduce:
1396 iters
0.027 ns/b
37.092 GB/s
neon_lsb:
1447 iters
0.026 ns/b
38.439 GB/s
eqsub:
1884 iters
0.020 ns/b
50.875 GB/s
neon_eqsub:
844 iters
0.044 ns/b
22.813 GB/s
neon_eqsub_unroll:
1884 iters
0.019 ns/b
52.546 GB/s
neon_lsb_unroll:
3367 iters
0.011 ns/b
91.567 GB/s
lsb:
3390 iters
0.011 ns/b
92.157 GB/s
Тия хвърчат в небесата бе. Някои дори предполагат че винаги ще има само два вида знаци в буфера (p и s).
#include <immintrin.h>
#include <cstdio>
#include <ctime>
#include <vector>
#include <algorithm>
int spcalc( const char *data ) {
long long idata32 = (long long)data & -32LL;
unsigned offset = (unsigned)(unsigned long long)data & 31, valid, zerof, sf, pf;
const __m256i *ym_data = (const __m256i*)idata32;
__m256i ym_s = _mm256_broadcastb_epi8( *(__m128i*)"s" ),
ym_p = _mm256_broadcastb_epi8( *(__m128i*)"p" ),
ym_z = _mm256_xor_si256( ym_s, ym_s ),
ym_c
;
int res;
valid = -1 << offset;
ym_c = *ym_data++;
zerof = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_z ) );
valid &= zerof ^ (zerof - 1);
sf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_s ) );
pf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_p ) );
res = __builtin_popcount( sf & valid ) - __builtin_popcount( pf & valid );
zerof &= valid;
while( !zerof ) {
ym_c = *ym_data++;
zerof = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_z ) );
valid = zerof ^ ( zerof - 1 );
sf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_s ) );
pf = (unsigned)_mm256_movemask_epi8( _mm256_cmpeq_epi8( ym_c, ym_p ) );
res += __builtin_popcount( sf & valid ) - __builtin_popcount( pf & valid );
}
return res;
}
#define INPSIZE 1000000
#define MBS 128
int main() {
char data[INPSIZE + 1];
unsigned i, j, iters;
int r;
clock_t start, stop;
std::vector<double> durs;
double median;
for( i = 0; i < INPSIZE; i += 4 ) {
data[i + 0] = 'a';
data[i + 1] = 'p';
data[i + 2] = 's';
data[i + 3] = 'z';
}
data[INPSIZE] = 0;
start = clock();
for( i = 0; i < 100; i++ ) {
r = spcalc( data );
}
stop = clock();
iters = (unsigned)( ( CLOCKS_PER_SEC * 5 ) / ( ( stop - start ) / 100 ) / MBS );
for( i = 0; i < iters; i++ ) {
start = clock();
for( j = 0; j < MBS; j++ ) {
r = spcalc( data );
}
stop = clock();
durs.push_back( (double)( stop - start ) / MBS / CLOCKS_PER_SEC );
}
std::sort( durs.begin(), durs.end() );
median = durs[durs.size()/2];
printf( "iters <%u> %.3f ns/b %.3f GB/s\n", iters, ( median * 1000000000 ) / INPSIZE, (double)INPSIZE / 1000000000 / median );
return 0;
}
iters <868> 0.046 ns/b 21.780 GB/s
Да, повечето имплементации са напълно нереалистични.
eqsub e може би последната имплементация, която е донякъде реалистична. Проблемът е, че при NEON ако се опиташ да прочетеш вектор, който е извън адресното пространство, програмата ще крашне. Затова и единствения начин да се използват вектори е ако знаеш дължината на стринга. Не знам как е при avx2. Ако не ме домързи може да пробвам как е с SVE, но ще трябва да пускам Graviton3 instance-a си.
Между другото, двете ми mac mini пристигнаха та може да пробвам и със Streaming SVE като науча как да го използвам.
Но като цяло заниманието е безмислено защото задачата е безинтересна.
Тая задача е много сладка за х86 авх2 защото имаме инструкцията vpmovmskb, която взима най-старшият бит от всеки байт на умм регистъра и ги събира точно в 32 битов генерален регистър. В тази задача използвам този трик за да извлека резултата от сравнението с '\0', 's', и 'p', и да сведа решението до игра на 3 маски в генералните регистри. Мисля че няма еквивалент при неон. За SVE не знам. Но е доста приложима.
мисля че с тая задача на всички съвременни системи ще измерите единствено скороста на паметта в текущото и настроение, не настройка, а точно настроение, женско. оня ден колежката ми звъни за някви артефакти в някакъв рендер. наложи се да РАБОТЯ, нещо рядко напоследък. натраках някакво решение, нещата се оправиха, но за съжаление скоростта падна. измерих втори път за по-точно - паднала още повече, и то драстично, 3 пъти спрямо кота нула. ушите ми съвсем клепнаха, но ми хрумна да ревъртна и да пусна пак тест на кота нула - показа същата паднала скорост. оказа се че фикса изобщо не забавя (тъй като само смята, но не вдига трансфера на памет), просто съвременните системи са толкова магически че един и същи код се изпълнява в драстично различни времена само заради "разджуркването" на паметта, подчертавам говорим за код който всеки път се стартира като чисто нов процес при нулева заетост на процесора, не просто 3 пъти да тествам в една сесия. така че тия прости тестове без упоменати детайли за борба с ефектите на магията са смешни, меренето на бързодействие днес не е фасулска работа
кога ще ти уври главата вместо да постваш линкове, да вадиш тефтера и да водиш записки , като корейски полковник пред прасчо?
Не знам как е с Windows, но не съм забелязал Линукс да страда от "раздьуркане" на паметта. Ако под "скоростта на паметта" имаш предвид конфигурацията и размерите на кешовете, определено си прав при сравнение на различни системи. Тестовия стринг е толкова малък, че се кешира целия не само в L3, но в случая с процесора на Апъл дори и в L2 кеша.
За една и съща система в общи линии определя колко добре работи branch predictor-a и колко добър код генерира компилатора.
П.П. Първия ми наивен опит със SME снощи беше неуспешен. Даде ми Illegal instruction, вероятно компилатора генерира SVE инструкции без smstart/smstop.
Аз за това по принцип взимам минималното време, когато всичко е в кеша, един вид идеални обстоятелства. Примерно на 1000 повторения с едни и същи данни.
Всички пишем като се изказваш. За тва Евгени се разочарова толкова като не ти се сбъдна прогнозата.
ти ли си прасчо 
Пробвах и clang. Определено се справя по-добре от gcc.
eqsub iters <1767> 0.022 ns/b 45.278 GB/s
spcalc iters <801> 0.049 ns/b 20.559 GB/s
Edit: Но не и за моя вариант с тестване за нула.
Никога не съм обичал играта "Да напишем такъв код на C, че да получим нужният ни машинен код".
Много по-лесно е да си го напиша директно на асемблер. 
Но искрено се забавлявам да гледам такова шоу. Нещо като старите комедии с Лоурел и Харди.