Для включения в состав ядра Linux предложен набор патчей с оптимизированной реализацией функции memchr(), применяемой для поиска символа в массиве. В отличие от старого варианта, в котором применялось побайтовое сравнение, предложенная реализация построена с учётом полного использования 64- и 32-разрядных регистров CPU. Вместо байтов сравнение осуществляется с использованием машинных слов, что позволяет за раз сравнивать как минимум 4 байта...Подробнее: https://www.opennet.dev/opennews/art.shtml?num=57493
Я думал и так уже оптимизировали все что можно для 64бит
Оно и оптимизировано уже более 10 лет. Называется аппаратная предвыборка данных (prefetch). Почему заявивший "The optimized "memchr()" is nearly 4x faster than the original one for long strings" не знает, что на больших блоках узким местом является скорость чтения из памяти - это другой вопрос.
Вы немного ошибаетесь. Никакие prefetch и прочие не избавят числодробилку от побайтового перебора. Ну да, память надо прочитать и загнать в кэш, но никто не говорит, что ядро стало работать в 4 раза быстрее, просто -1 узкий момент.
А ещё я немного смотрю, чего оно там числодробит:nl = memchr(line, '\n', end - buffer);
Сразу видно человека не разбирающегося в теме
Когда-то давно сравнивал свою реализацию strlen (это почти memchr, только чуть другой)Побайтовый наивный алгоритм проиграл по скорости около 4 раз 8-байтовому. Еще написал не совсем правильный sse-алгоритм, он еще в 1.5-2 раза быстрее.
Это к разговору про скорость подсистемы памяти.
То есть не догадались посчитать теоретический предел чтения из памяти и сравнить с ним результаты измерений? Это к разговору об измерениях. Про год и тип процессора не спрашиваю, как и про использование команды prefetchnta.
>Называется аппаратная предвыборка данных (prefetch).А в Эльбрусах, Итаниках и прочих VLIW такой есть?
Попробуйте дочитать моё сообщение до конца - там вся суть. Что касается вопроса, если нет аппаратной предвыборки - можно обеспечить программную, как делали раньше на IA32. Для этого есть либо специальная команда, либо читают память с шагом равным размеру линейки кеша.
> Называется аппаратная предвыборка данных (prefetch).Интересно, а как предвыборка может изменить тот факт что телепать по 1 байту за раз вместо 4 означает в 4 раза больше инструкций на это самое? Инструкции все моментально чтоли выполняются, такты не занимают? Без предвыборки вы еще и память бонусом к этому дофигища подождете. И там упоминабтся строки до 512 байтов, чтоли. Это наверное не настолько ужасно?
> И там упоминабтся строки до 512 байтов, чтоли.Для недочитавших моё сообщение повторяю цитату автора "for long strings". Большая строка - это не 512 байт. В современных реалиях это, должно быть, гигабайты. Разницу скорости чтения из кеша и ОЗУ ищите сами. Чувак копировал пояснения из копии Агнер Фога или Генри Уоррена и не усёк этот нюанс, ему простительно. ;)
> Интересно, а как предвыборка может изменить тот факт что телепать по 1
> байту за раз вместо 4 означает в 4 раза больше инструкций
> на это самое? Инструкции все моментально чтоли выполняются, такты не занимают?А подготовительные операции мы не считаем, зачем это - вдруг разрушит нашу стройную гипотезу. И статистику по длине строк не собрали. Просто голословно посчитаем себя умнее автора существующей реализации через REP SCASB, но напишем про это не ему, а вот тут.
> REP SCASBНасколько помню, этот вариант проиграл варианту на (условных) переходах.
Продолжай теоретизировать.
>> REP SCASB
> Насколько помню, этот вариант проиграл варианту на (условных) переходах.Как бы не важно, кто и что там якобы помнит, когда вот код из реального мира:
#ifdef __HAVE_ARCH_MEMCHR
void *memchr(const void *cs, int c, size_t count)
{
int d0;
void *res;
if (!count)
return NULL;
asm volatile("repne\n\t"
"scasb\n\t"
"je 1f\n\t"
"movl $1,%0\n"
"1:\tdecl %0"
: "=D" (res), "=&c" (d0)
: "a" (c), "0" (cs), "1" (count)
: "memory");
return res;
}
EXPORT_SYMBOL(memchr);
#endif> Продолжай теоретизировать.
Гипотетически Аноним уделал разрабов ядра, а практически он сравнивает свой воображаемый мега-код с "ускорением в 4 раза", которое уже дважды отклонили, как нерабочее.
Это было сказано про мое сравнение реализаций strlen.
В ядре линукс мало кого интересует производительность, особенно мало используемых дублирующих функций.
Специально искал этот допотопный memscan?
> Это было сказано про мое сравнение реализаций strlen.Нет никакого сравнения: ни цифр, ни подробностей о железе.
> В ядре линукс мало кого интересует производительность, особенно мало используемых дублирующих
> функций.А на самом деле анонимный эксперт не осилил поискать __HAVE_ARCH_MEMCHR
> Специально искал этот допотопный memscan?
Да, специально искал и нашёл memchr. Тема же про memchr. ;)
> __HAVE_ARCH_MEMCHRпроизводительностью которого заинтересовались и предлагают варианты.
Пока нет никаких измерений производительности. С какой целью Вы упорно пишете чушь в ответ на мои сообщения? Вы ещё вчера хотели вернуться к своим баранам.
Может, он и там тупил, ну они его и того?
> Для недочитавших моё сообщение повторяю цитату автора "for long strings". Большая строка
> - это не 512 байт. В современных реалиях это, должно быть, гигабайты.Я что-то не уверен что ядро в принципе таким оперирует. Там длинное это наверное PATH_MAX какой-нибудь. Хоть я и не смотрел какой там наихучший случай конечно.
> Разницу скорости чтения из кеша и ОЗУ ищите сами.
Спасибо, Капитан Очевидность.
> А подготовительные операции мы не считаем, зачем это - вдруг разрушит нашу
> стройную гипотезу.Ну, э, подготовительные операции или нет, а по эн байтов за раз обычно эффективнее чем по одному.
> И статистику по длине строк не собрали. Просто голословно
> посчитаем себя умнее автора существующей реализации через REP SCASB,Ммм а как сие на ARM и RISCV?
> но напишем про это не ему, а вот тут.
Ага. Усомнившись в некоторых аспектах спича. И автор наверное все же не полный рак и побенчил свое добро? И что там реально будет лучше - ну я не настолько хорошо все варианты микроархитектур x86 знаю чтобы рассуждать чего в каком случае лучше и для кого из подвидов.
>> Для недочитавших моё сообщение повторяю цитату автора "for long strings". Большая строка
>> - это не 512 байт. В современных реалиях это, должно быть, гигабайты.
> Я что-то не уверен что ядро в принципе таким оперирует.Разумеется, не оперирует. Но автор написал long. Вспоминаем определение кеш-памяти - это маленькая быстрая память. Значит не попадает в кеш.
> Там длинное
> это наверное PATH_MAX какой-нибудь. Хоть я и не смотрел какой там
> наихучший случай конечно.Там ускоряют drivers/misc/lkdtm/heap.c
то есть вот это:if (memchr(val, 0xAB, 512) == NULL) {
pr_info("Memory appears initialized (%x, no earlier values)\n", *val);
} else {
pr_err("FAIL: Slab was not initialized\n");
pr_expected_config_param(CONFIG_INIT_ON_ALLOC_DEFAULT_ON, "init_on_alloc");
}...
if (memchr(val, 0xAB, PAGE_SIZE) == NULL) {
pr_info("Memory appears initialized (%x, no earlier values)\n", *val);
} else {
pr_err("FAIL: Slab was not initialized\n");
pr_expected_config_param(CONFIG_INIT_ON_ALLOC_DEFAULT_ON, "init_on_alloc");
}>> Разницу скорости чтения из кеша и ОЗУ ищите сами.
> Спасибо, Капитан Очевидность.
>> А подготовительные операции мы не считаем, зачем это - вдруг разрушит нашу
>> стройную гипотезу.
> Ну, э, подготовительные операции или нет, а по эн байтов за раз
> обычно эффективнее чем по одному.На одном байте особенно эффективно будет, ага.
Assembly/Compiler Coding Rule 5. (MH impact, MH generality) Selectively inline a function if
doing so decreases code size or if the function is small and the call site is frequently executed.Assembly/Compiler Coding Rule 8. (ML impact, ML generality) Favor inlining small functions that
contain branches with poor prediction rates. If a branch misprediction results in a RETURN being
prematurely predicted as taken, a performance penalty may be incurred.>> И статистику по длине строк не собрали. Просто голословно
>> посчитаем себя умнее автора существующей реализации через REP SCASB,
> Ммм а как сие на ARM и RISCV?$ grep -R "e __HAVE_ARCH_MEMCHR" *
arch/powerpc/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/s390/include/asm/string.h:#define __HAVE_ARCH_MEMCHR /* inline & arch function */
arch/arm/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/alpha/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/x86/include/asm/string_32.h:#define __HAVE_ARCH_MEMCHR
arch/arm64/include/asm/string.h:#define __HAVE_ARCH_MEMCHRuProf
arch/sh/include/asm/string_32.h:#define __HAVE_ARCH_MEMCHR>> но напишем про это не ему, а вот тут.
> Ага. Усомнившись в некоторых аспектах спича. И автор наверное все же не
> полный рак и побенчил свое добро? И что там реально будет
> лучше - ну я не настолько хорошо все варианты микроархитектур x86
> знаю чтобы рассуждать чего в каком случае лучше и для кого
> из подвидов.Как бы он это сделал? Вот реально, без синтетики. С тех пор как AMD CodeAnalyst превратился в uProf, не понятно, как симулировать исполнение и посмотреть что там сколько занимает в тактах.
Тут, курица или яйцо. Работает медленно -- ищем решение без поиска в лоб, не используем поиск в лоб -- нет оптимизации и работает медленно.Так микрооптимизации очень нужны, если они хорошо поддерживаются.
Наоборот всегда было главное единообразие чтобы обеспечить переносимость. Наоптимизировать под конкретное железо это к другим проприетарным производителям.
Обычно имеются в начичии и оптимизированные варианты для известных архитектур, и неоптимизированные для любых, если оптимизированного не нашлось.
Раздуто, а не оптимизированно
Было бы оптимизировано, то не получилось бы сделать раздуто. Было бы супермеганеподдерживаемораздуто.
В итоге получат, что толстое ядро тормозит сильнее, чем микроскопическое ускорение от поиска в строках.
Оно оптимизировано. Просто надо ещё мест, где можно очереднус спектр запустить по сторонним каналам. Обращение за пределы выделенной памяти и прочие плюшки.
> Вместо байтов сравнение осуществляется с использованием машинных слов, что позволяет за раз сравнивать как минимум 4 байта.Как в glibc 🤗
Там разве не sse и avx(512) с "до 64 байтами" за раз?
avx(512) в здравом уме в ядре использовать никто не будет, потому что на интелах оно имеет риск проложить производительность всей числодробилки, а не только одного ядра."Linus Torvalds: I hope Intel's AVX-512 'dies a painful death'"
Ядро поддерживает софт, работающий с AVX512, но это на жуткого любителя.
> avx(512) в здравом уме в ядре использовать никто не будетЭто монолит, нет смысла апеллировать к здравому смыслу.
Ну, бОльшая часть ядра до последнего времени таки здравому смыслу соответствовала.Последние веяния в виде иоурины, ёбпф и хруста - да, заставляют напрячься. Это то, что в монолит ну никак не вписывается, да.
Что за урина? Это uring чтоли так назвали? Оно может и брейнфак, но ОЧЕНЬ БЫСТРЫЙ брейнфак. И когда вы хотите всякие там 100Gig сеточки, сторажи типа оптана и проч - окей, но этот брейнфак быстрее обычных способов в разы! Поэтому с ним и канителятся.
спасибо за инфу! смысул этих инструкций и новых процев околонулевой. пожалуй , пока останусь ка на коре2дуо.
https://colfaxresearch.com/skl-avx512/
Английского не знаю. Судя по тексту "Я" сайт перевёл хорошо если не отлично.
А что правда не так с avx-512? Я то наоборот стараюсь использовать векторизацию, вот только железа, поддерживающего что-то выше SSE так и не опробовал (у меня максимум SSE-4.3). Так что тут я слегка профан, и был бы рад пофиксить ещё немного пробелов в знаниях.Что в нём не так - неоптимальная реализация работы с 512-битными векторами или бессмыссленность такого подхода из за неизбежных узких мест? Насколько я заметил, самая частая ошибка при векторизации - это разложить по вектору элементы некоей сложной обработки вместо того, а не сами группы (на уровне которых линейность таки прослеживается).
Когда контекст исполнения (поток) переключается, регистры процессора надо сохранять. Операция не мгновенная, требует место в ОЗУ и может марать кеш. Было 16 штук 32-х байтных регистров (256 бит), стало вдвое больше и в количестве, и по размеру. Помножьте 2К на 1000 потоков. Интел выиграла в каком-то тесте, а система в целом просела, да ещё и ядро надо допилить.
Не так в нём то, что оно превращает в кипятильник весь камень, и частоты падают на всём кипятильнике, а не на конкретном ядре.
(и это не так из эксплуатационного)
Ещё с ним не так то, что разные процы поддерживают разные несовместимые субсеты оного...
А так да, скорее всего оптимизации касаются как раз SSE(2) и AVX(2) - но честно скажу, не смотрел.
В принципе и даже на стандартных регистрах можно через поиск нуля после вычитания, но изврат тот ещё.
В принципе даже просто выровненный забор и 4-8 сравнений на стандартных регистрах должны дать хороший прирост, если там до этого оно побайтово делалось.
В ядре не используются команды фпу, ссе и авх
glibc используется?
Первый найденный случайный файлhttps://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
Найди отсутствие AVX
> Первый найденный случайный файл
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
> Найди отсутствие AVXНашёл баш-программиста ядра. Смотрим не Makefile, а первый найденный случайный код. Что бы это значило и зачем? ;)
kernel_fpu_begin();
crypto_aegis128_aesni_init(&state, ctx->key.bytes, req->iv);
crypto_aegis128_aesni_process_ad(&state, req->src, req->assoclen);
crypto_aegis128_aesni_process_crypt(&state, &walk, ops);
crypto_aegis128_aesni_final(&state, tag_xor, req->assoclen, cryptlen);kernel_fpu_end();
> Что бы это значило и зачем? ;)напечатай из ядра sin(M_PI/19)
> напечатай из ядра"В ядре не используются команды" печати.
открой для себя printkhttps://www.opennet.dev/man.shtml?topic=printk
" DESCRIPTION
Print a formatted message to the ..."
Вот, чёрт.
>> Что бы это значило и зачем? ;)
> напечатай из ядра sin(M_PI/19)Ну вывести 0.16459459028 как бы не проблема. Вопрос был к утверждавшим, что FPU можно и нужно.
The kernel's printf does not support %n. Floating point formats (%e, %f,
%g, %a) are also not recognized, for obvious reasons. Use of any
unsupported specifier or length qualifier results in a WARN and early
return from vsnprintf().
Еще как используются, всякие там хеш-функции и прочие подобные вещи в нескольких вариантах есть.
Посмотрите, _как_ оно во "всяких там" используется. Человек прав в принципе, но сформулировал некорректно. Не принято использовать. Криптопреобразования работают с данным достаточно больших объёмов и в специфичных случаях, потому имеет смысл озадачиться с сохранением контекста.
Специально скопирую сюда из /glibc/string/memchr.c
что бы люди могли почитать комментарии к коду и сделать выводы.
/* Search no more than N bytes of S for C. */
void *
MEMCHR (void const *s, int c_in, size_t n)
{
/* On 32-bit hardware, choosing longword to be a 32-bit unsigned
long instead of a 64-bit uintmax_t tends to give better
performance. On 64-bit hardware, unsigned long is generally 64
bits already. Change this typedef to experiment with
performance. */
typedef unsigned long int longword;const unsigned char *char_ptr;
const longword *longword_ptr;
longword repeated_one;
longword repeated_c;
unsigned char c;c = (unsigned char) c_in;
/* Handle the first few bytes by reading one byte at a time.
Do this until CHAR_PTR is aligned on a longword boundary. */
for (char_ptr = (const unsigned char *) s;
n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
--n, ++char_ptr)
if (*char_ptr == c)
return (void *) char_ptr;longword_ptr = (const longword *) char_ptr;
/* All these elucidatory comments refer to 4-byte longwords,
but the theory applies equally well to any size longwords. *//* Compute auxiliary longword values:
repeated_one is a value which has a 1 in every byte.
repeated_c has c in every byte. */
repeated_one = 0x01010101;
repeated_c = c | (c << 8);
repeated_c |= repeated_c << 16;
if (0xffffffffU < (longword) -1)
{
repeated_one |= repeated_one << 31 << 1;
repeated_c |= repeated_c << 31 << 1;
if (8 < sizeof (longword))
{
size_t i;for (i = 64; i < sizeof (longword) * 8; i *= 2)
{
repeated_one |= repeated_one << i;
repeated_c |= repeated_c << i;
}
}
}/* Instead of the traditional loop which tests each byte, we will test a
longword at a time. The tricky part is testing if *any of the four*
bytes in the longword in question are equal to c. We first use an xor
with repeated_c. This reduces the task to testing whether *any of the
four* bytes in longword1 is zero.We compute tmp =
((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
That is, we perform the following operations:
1. Subtract repeated_one.
2. & ~longword1.
3. & a mask consisting of 0x80 in every byte.
Consider what happens in each byte:
- If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
and step 3 transforms it into 0x80. A carry can also be propagated
to more significant bytes.
- If a byte of longword1 is nonzero, let its lowest 1 bit be at
position k (0 <= k <= 7); so the lowest k bits are 0. After step 1,
the byte ends in a single bit of value 0 and k bits of value 1.
After step 2, the result is just k bits of value 1: 2^k - 1. After
step 3, the result is 0. And no carry is produced.
So, if longword1 has only non-zero bytes, tmp is zero.
Whereas if longword1 has a zero byte, call j the position of the least
significant zero byte. Then the result has a zero at positions 0, ...,
j-1 and a 0x80 at position j. We cannot predict the result at the more
significant bytes (positions j+1..3), but it does not matter since we
already have a non-zero bit at position 8*j+7.So, the test whether any byte in longword1 is zero is equivalent to
testing whether tmp is nonzero. */while (n >= sizeof (longword))
{
longword longword1 = *longword_ptr ^ repeated_c;if ((((longword1 - repeated_one) & ~longword1)
& (repeated_one << 7)) != 0)
break;
longword_ptr++;
n -= sizeof (longword);
}char_ptr = (const unsigned char *) longword_ptr;
/* At this point, we know that either n < sizeof (longword), or one of the
sizeof (longword) bytes starting at char_ptr is == c. On little-endian
machines, we could determine the first such byte without any further
memory accesses, just by looking at the tmp result from the last loop
iteration. But this does not work on big-endian machines. Choose code
that works in both cases. */for (; n > 0; --n, ++char_ptr)
{
if (*char_ptr == c)
return (void *) char_ptr;
}return NULL;
}
Покажи ещё sysdeps/x86_64/multiarch/memrchr-evex.Shttps://sourceware.org/git?p=glibc.git;a=blob;f=sysdeps/x86_...
Суть вот где:/* Handle the first few bytes by reading one byte at a time.
Do this until CHAR_PTR is aligned on a longword boundary. */На этом основании предлагаемому в ядро "в четыре раза быстрее" влупили NAK.
Давай так. Напиши свой наивный побайтовый алгоритм memchr (можешь даже префетч присобачить). И сравни с glibc, который будет использовать оптимизированный под твой процессор. На данных до одного гигабайта, чтоб уж наверняка вылезти за пределы всех уровней кеша.
Ещё раз, для не уловивших суть: предлагаемое в ядро в общем случае НЕ РАБОТАЕТ, в отличие от реализации из glibc и остальных наивных.
Вернемся к нашим скачущим баранам. Тогда зачем в ветке про glibc ты приводишь код из glibc, и приводишь код не всех реализаций/оптимизаций?Про твое "замечание" про чтение начальных нескольких невыровненных байт. Как эта O(1) операция повлияет на скорость, особенно при очень больших N?
> Тогда зачем в ветке про glibc ты
> приводишь код из glibc,В ответ на заявление "Как в glibc 🤗" я показал, что оно - ложно.
> и приводишь код не всех реализаций/оптимизаций?
Затем, что я различаю "необходимое" и "достаточное".
> Про твое "замечание" про чтение начальных нескольких невыровненных байт. Как эта O(1)
> операция повлияет на скорость, особенно при очень больших N?Для тех, кто не понимает русский язык ("не работает"), не умеет ходить по ссылкам и не читает здесь сообщения, повторяю:
> I think you're missing the point. Loads at unaligned addresses may not
> be allowed by hardware using conventional load instructions or may be
> inefficient. Given that this memchr implementation is used as a fallback
> when no hardware-specific version is available, you should be
> conservative wrt. hardware capabilities and behavior. You should
> probably have a pre-alignment loop.Exactly!
The initial code is broken, NAK.> Вернемся к нашим скачущим баранам.
Возвращайтесь. Вы здесь задержались слишком.
"как в glibc", было сказано на счет "позволяет за раз сравнивать как минимум 4 байта".Во время тестирования strlen, я тоже чисто случайно ошибся и читал невыровненные слова. Так вот, этот ошибочный вариант работал чуть медленнее выровненного варианта, примерно также в 4 раза быстрее наивного побайтового.
> "как в glibc", было сказано на счет "позволяет за раз сравнивать как
> минимум 4 байта".Ещё раз: в данном случае оно не сравнивает, оно даже прочитать память не может, в отличие от glibc.
> Во время тестирования strlen, я тоже чисто случайно ошибся и читал невыровненные
> слова. Так вот, этот ошибочный вариант работал чуть медленнее выровненного варианта,
> примерно также в 4 раза быстрее наивного побайтового."У меня на виртуалке работает!" (ц)
> "У меня на виртуалке работает!" (ц)У тебя вообще ничего не работает, и ты сидишь на оффтопе и рассуждаешь, что должно быть на линуксе.
Пиши memchr, можешь даже с префетчем и выравниванием по байтам, потом сказки рассказывай, что и где не работает.
> Пиши memchr, можешь даже с префетчем и выравниванием по байтам, потом сказки
> рассказывай, что и где не работает.Дублирую цитаты:
I think you're missing the point. Loads at unaligned addresses may not
be allowed by hardware using conventional load instructions or may be
inefficient. Given that this memchr implementation is used as a fallback
when no hardware-specific version is available, you should be
conservative wrt. hardware capabilities and behavior. You should
probably have a pre-alignment loop.https://lkml.org/lkml/2022/7/11/1323
Exactly!
The initial code is broken, NAK.https://lkml.org/lkml/2022/7/11/1329
Аноним публично назвал двух уважаемых разработчиков Линукс сказочниками. Надеюсь, ему хватит сил набраться смелости и принести этим людям извинения. Или хотя бы назваться - я не могу всех подряд анонимов презирать.
>> "У меня на виртуалке работает!" (ц)
> У тебя вообще ничего не работает, и ты сидишь на оффтопе и
> рассуждаешь, что должно быть на линуксе.Кажется, я понял. Тут просто фанатика бомбануло, что я за него сорцы Линукса посмотрел, когда он не смог. Но это не оправдывает его хамство по отношению к другим.
Тем временем существует оптимизированный memchr_inv
> On 32-bit hardware, choosing longword to be a 32-bit unsigned
> long instead of a 64-bit uintmax_t tends to give better
> performance.ох уж эта сишка и ее проблемы с типами на разных архитектурах.
Хрустик как-то спасёт тебя от разного размера регистров в проце?
Кстати, может ли Rust защитить от реальной проблемы предлагаемого "ускорения" - невозможность чтения двойных слов по невыровненым адресам на некотором железе?
> Кстати, может ли Rust защитить от реальной проблемы предлагаемого "ускорения" - невозможность
> чтения двойных слов по невыровненым адресам на некотором железе?А вот не факт. Скорее всего исключение от железки поймает в тыкву и не факт что сможет нормально обработать. Во всяком случае, ловить переполнение стека без MMU оно не умеет, а с MMU его даже рак хоть на асме поймает.
Интересно, можно ли нарушение alignment requirements поймать на этапе трансляции. Люди то увидели. А автор даже не знал.
> Общий прирост производительности подсистем ядра при использовании оптимизированного варианта "memchr()" пока не оценивался, как не анализировалась и целесообразность замены реализации (в коде ядра вызов функции memchr() встречается 129 раз, в том числеСм. абсолютное и относительное улучшение — https://pashev.ru/nnt
Такого количества багов, костылей и рудиментов не было даже в ранней винде после перехода с мсдос
а что ты хотел, 31 год идёт ядру, его ещё причёсывают хотя бы хоть как-то
а что ты хотел, 1031 год идёт ядру, его ещё причёсывают хотя бы хоть как-тоP.S. где-то в далеком далеком интернете тысячу лет спустя
Ну да, в то время люди задавались вопросом "какие такие строки, как часто и зачем надо сравнивать в ядре".
Ты ещё исходники индусской 11 не видел.
Я нормальный линукс десктоп не видел... хотя бы на уровне XP
Ага, мы уже все видел тулчейн в исходниках XP, можешь не продолжать, вот где костыли так костыли.
Плохому линуксоиду виндоус мешает
ЛЮБОМУ линуксоиду виндоуз мешает)
А виндузоид не видел десктопа лучшего, чем XP.
Это классика, это знать надо
Да знаю - синдром утёнка.
Переходи на армянский алфавит! Как не хочешь? У тебя синдром утёнка!!!! (Логика тех, кто использует это словосочетание).
Это некрофилия а не классика
Тупой ты баран.
>Ты ещё исходники индусской 11 не виделКстати! Я, старый линуксовод (не помню XP, то есть перешёл до появления XP) недавно купил подержанный неттоп, а на нём обнаружилась 11-я винда. И, знаете ли, даже понравилось! Гламурненькая система. Только обновляется, сцуко, без спроса.
В поддержанных неттопах Windows 7 есть, 11-я в новых.>И, знаете ли, даже понравилось! Гламурненькая система.
Будь осторожен это начало признака деградации.
>Только обновляется, сцуко, без спроса.
Знаете ли вы, что Windows периодически делает скриншоты вашего Рабочего стола и отправляет их на непонятные сервера.
>>И, знаете ли, даже понравилось! Гламурненькая система.
>Будь осторожен это начало признака деградации.Это что-то со скрижалей фанатиков.
Тебе M$ тогда исходники показывал ранней Венды?
Уж лучше чем у этой студенческой подделкиJust for fun! Как говорится...
Ну так показывал или фантазёр?
На изучай сколько угодно хоть вин2000 хоть нт4magnet:?xt=urn:btih:66a26447f563c3dc2336de74ae37dc14d11dd8b9&dn=windows_nt_4_source_code.zip
magnet:?xt=urn:btih:82658c6baab65a855f804a534e55f64fbb2ec977&dn=Windows_2000_source_code.rar
Лютое не нужно.
> На изучай сколько угодно хоть вин2000 хоть нт4
> magnet:?xt=urn:btih:66a26447f563c3dc2336de74ae37dc14d11dd8b9&dn=windows_nt_4_source_code.zip
> magnet:?xt=urn:btih:82658c6baab65a855f804a534e55f64fbb2ec977&dn=Windows_2000_source_code.rarГораздо новее есть исходники, windows server 2003 :)
> Такого количества багов, костылей и рудиментов не было даже в ранней винде
> после перехода с мсдосЭто ты погорячился и просто не видел в Win3.x/9x их типа-кернелы - настолько раздристаное месиво что состояло из примерно трех не особо связанных между собой частей.
> Вместо байтов сравнение осуществляется с использованием машинных слов,
> что позволяет за раз сравнивать как минимум 4 байта.Очень интересно, и каким же образом это делается с учётом что ожидается некоторая универсальность для разных архитектур
Он ифдефов конечно же напихал. Но ничего хорошего в этом нет имхо.>> if defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64
Способ назван "сломаным"> I think you're missing the point. Loads at unaligned addresses may not
> be allowed by hardware using conventional load instructions or may be
> inefficient. Given that this memchr implementation is used as a fallback
> when no hardware-specific version is available, you should be
> conservative wrt. hardware capabilities and behavior. You should
> probably have a pre-alignment loop.Exactly!
The initial code is broken, NAK.P.S. At least you may look into strscpy() implementation to get a clue.
>Очень интересно, и каким же образом это делаетсяпараллельный аппаратный компоратор, хотя тут есть один момент для строк вида, abac, aaaa и т. д. если ишем a.
С помощью #ifdef ... #else ?
Осталось понять, что он там оптимизировал:$ grep -R "e __HAVE_ARCH_MEMCHR" *
arch/powerpc/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/s390/include/asm/string.h:#define __HAVE_ARCH_MEMCHR /* inline & arch function */
arch/arm/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/alpha/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/x86/include/asm/string_32.h:#define __HAVE_ARCH_MEMCHR
arch/arm64/include/asm/string.h:#define __HAVE_ARCH_MEMCHR
arch/sh/include/asm/string_32.h:#define __HAVE_ARCH_MEMCHR
> до 4 раз быстрееЭто же не реклама, зачем употребтять "до"? Тем более, что в оригинале написано "около" - "around ~4x".
> "around ~4x"Каков радиус этого эраунда?
Это не важно, главное что центр в районе 4х
> центр в районе 4хТочно-точно центр? Судя по цифрам из топика - это теоретический край.
> в больших строках новый вариант оказался быстрее старого примерно в 4 раза (например, для строк в 1000 символов)В 4 раза - что планируем получить...
> В ядре Linux размер обрабатываемых в memchr() строк достигает 512 байт. Прирост производительности для 512 байтовых строк, в ситуации, когда искомый символ находится в конце строки, составляет 20%.
Максимум 20% - мягко сказать, уже далеко не в 4 раза.
> Общий прирост производительности подсистем ядра при использовании оптимизированного варианта "memchr()" пока не оценивался
В реальности - 0.0X%, что даже постыдились показать.
> Максимум 20%С какого потолка взял?
> В реальности - 0.0X%, что даже постыдились показать.
Русским языком же написано "пока не оценивался", какие буквы ты не понял?
Эта тема обещает быть самой весёлой переписью экспертов. ;)If you fix the issue, kindly add following tag where applicable
Reported-by: kernel test robot <lkp@intel.com>All errors (new ones prefixed by >>):
>> lib/string.c:902:7: error: conflicting types for 'memchr'
void *memchr(const void *p, int c, unsigned long length)
^
include/linux/string.h:162:15: note: previous declaration is here
extern void * memchr(const void *,int,__kernel_size_t);
^
1 error generated.
> С какого потолка взял?Перечитай сабж внимательно.
Хоспадя. Сами в 2022 году писать не умеют, так хоть бы списывать учились. http://fastcode.sourceforge.net/
> ... так хоть бы списывать учились. http://fastcode.sourceforge.net/Эти тоже в Стэнфорде спионерили: © 1997-2005 Шон Эрон Андерсон https://graphics.stanford.edu/~seander/bithacks.html
А зачем в новой реализации исходная строка/указатель двигается?
Имя автора северокорейского засланца прочитай и всё поймешь
void *memchr(const void *p, int c, size_t length)
{
u64 mask, val;
const void *end = p + length;
c &= 0xff;while ((long ) p & (sizeof(long) - 1)) {
if (p >= end)
return NULL;
if (*(unsigned char *)p == c)
return (void *) p;
p++;
}
if (p <= end - 8) {
mask = c; /* <================= это нахуа? */
MEMCHR_MASK_GEN(mask);for (; p <= end - 8; p += 8) {
val = *(u64*)p ^ mask;
if ((val + 0xfefefefefefefeffull) & (~val & 0x8080808080808080ull))
break;
}
}for (; p < end; p++)
if (*(unsigned char *)p == c)
return (void *)p;return NULL;
}
Ну наверное для MEMCHR_MASK_GEN
Я уж испугался. Думал на расте переписали и уделали Си )
А я уж думал, что подобное давно оптимизировали. Интересно, а компиляторы хотя бы до такой наивной оптимизации доросли?if (strlen(s) == 5) --> if (strnlen(s, 6) == 5)
Это не сильно актуально при малых строках строках, а при огромных - выигрыш существенен. Тем не менее второй вариант кода - большая редкость.
> А я уж думал, что подобное давно оптимизировали.Давно оптимизировали. Предлагаемый код пока вообще не работает.
> Интересно, а компиляторы хотя
> бы до такой наивной оптимизации доросли?
> if (strlen(s) == 5) --> if (strnlen(s, 6) == 5)-Wno-stringop-overread
Warn for calls to string manipulation functions such as "memchr", or "strcpy" that are
determined to read past the end of the source sequence.
> -Wno-stringop-overread
> Warn for calls to string manipulation functions such as "memchr", or "strcpy" that are
> determined to read past the end of the source sequence.И как сие работает? Сдается мне, что эта опция совсем не для этого. Я имею ввиду, что часто нет необходимости вычислять всю длину строки, и при сравнении длины строки с N можно дальше N+1 байта не ходить, что очень даже полезно в случае, если строка очень большая.
Да, опция для другого. Задействованный механизм позволяет иногда оптимизировать чуть лучше:
$ cat test.c
#include <string.h>int test(const char* s)
{
return strlen(s) == 5;
}int main()
{
return test("12345");
}$ gcc -o test.s test.c -S -O2
$ cat test.stest:
subq $8, %rsp
call strlen@PLT
cmpq $5, %rax
sete %al
addq $8, %rsp
movzbl %al, %eax
retmain:
movl $1, %eax // strlen вообще не вызывается
ret
В асм листинге вырезал нерелевантный текст.То, что Вы предлагаете - это не наивная оптимизация. Подсчёт кол-ва символов в строке помещает всю строку в кеш. Если её длина больше 5 - может именно это программисту и надо?
Чуть лучше, только если строка - это константа. Что же касается строкиstrlen(s) == 5
То тут довольно очевидно что именно программисту нужно. По крайней мере когда результат выполнения strlen никуда не сохраняется.
Мне не очевидно, даже не знаю, когда такое может потребоваться и почему в реальной задаче нельзя проверить s[5].
> Мне не очевидно, даже не знаю, когда такое может потребоваться и почему
> в реальной задаче нельзя проверить s[5].Что если длина строки 2 а память, где хранится строка, перед этим была обнулена? А что если проверяемая длина лежит за границей выделенного блока памяти? Вы точно знаете как именно организованы строки в Си?
>> Мне не очевидно, даже не знаю, когда такое может потребоваться и почему
>> в реальной задаче нельзя проверить s[5].
> Что если длина строки 2 а память, где хранится строка, перед этим
> была обнулена?Вот поэтому и пишу "в реальной задаче". Могу придумать гипотетическую задачу, где надо как-то сгруппировать строки по длине. В таком случае эти нули окажутся проверены на предыдущих шагах.
> А что если проверяемая длина лежит за границей выделенного
> блока памяти?Это частный случай вышеуказанного. В том числе и если по виртуальному адресу нет физической памяти.
> Вы точно знаете как именно организованы строки в Си?
Как считает целесообразным для решения задачи программист, так и организует. Если часто нужна длина, она не вычисляется каждый раз, а хранится отдельно. На практике, если программа более-менее серьёзно работает с текстом, strlen оказывается в каких-то вспомогательных местах, если вообще есть.
Я спрашиваю про конкретную оптимизацию при использовании конкретной функции из стандартной библиотеки, вы же отвечаете непонятно на что, затем придумываете гипотетические задачи, в которых эта функция не используется вовсе. Если я вызываю strlen(s), то это означает, что мне неизвестна длина строки (внешние данные), а если я вызываю strnlen(s, 6), это означает что мне не нужна точная длина строки, я лишь хочу убедится, что ее длина больше 5.
> Я спрашиваю про конкретную оптимизацию при использовании конкретной функции из стандартной
> библиотеки, вы же отвечаете непонятно на что,А я увидел человека, кто не может сгенерировать ассемблерный листинг и изучить его.
> затем придумываете гипотетические задачи,
> в которых эта функция не используется вовсе.Потому что реальную задачу Вы не показали.
> Если я вызываю strlen(s),
> то это означает, что мне неизвестна длина строки (внешние данные), аВот именно. На практике для каждой такой строки определяется её длина. Если требуется эффективно находить строки длиной 5 - их длина оказывается уже посчитана при проверке входных данных.
> если я вызываю strnlen(s, 6), это означает что мне не нужна
> точная длина строки, я лишь хочу убедится, что ее длина больше
> 5.В №75 написано: if (strlen(s) == 5) --> if (strnlen(s, 6) == 5)
Изначально Вы искали строки длиной равной 5 и интересовались, способен ли транслятор заменить вызов стандартной функции на функцию, о которой он ничего не знает.
Вы, наверное, удивитесь, но:
1. в стандарте есть только strnlen_s (определена ли она по умолчанию - implementation defined);
2. исходники популярной программы GNU bash содержат файл bash/lib/sh/strnlen.c с реализацией strnlen.
> А я увидел человека, кто не может сгенерировать ассемблерный листинг и изучить
> его.А если человек сгенерировал, изучил, но вам не доложил, как вы его отличите от того, кто не смог? Так вот, если вашей функции test выше скормить программно заполненный массив символов, то в asm листинге таки будет виден вызов strlen. Сюрприз? Мне почему-то показалось, что доказывать это нет необходимости. Мне не нужен вызов strlen("12345"), ибо чтобы узнать результат этого вызова компьютер не нужен. Я спрашивал о strlen(s), где s - это переменная, а не константа, зашитая в коде. Но не напрягайтесь, сейчас мне ваш ответ не нужен, только не после демонстрации вами вашей логики.
>> А я увидел человека, кто не может сгенерировать ассемблерный листинг и изучить
>> его.
> А если человек сгенерировал, изучил, но вам не доложил, как вы его
> отличите от того, кто не смог?Очень просто - априори я верю человеку на слово. Если он пишет "Интересно, а компиляторы хотя бы до такой наивной оптимизации доросли?" - значит ему действительно интересно узнать.
> Так вот, если вашей функции
> test выше скормить программно заполненный массив символов, то в asm листинге
> таки будет виден вызов strlen. Сюрприз? Мне почему-то показалось, что доказывать
> это нет необходимости.Действительно, сюрприз. В том листинге, что я привёл, в test() есть вызов strlen. Но в main() нет вызова test(). Я полагал, что нет смысла объяснять очевидные вещи.
> Мне не нужен вызов strlen("12345"), ибо чтобы узнать
> результат этого вызова компьютер не нужен. Я спрашивал о strlen(s), где
> s - это переменная, а не константа, зашитая в коде. Но
> не напрягайтесь, сейчас мне ваш ответ не нужен, только не после
> демонстрации вами вашей логики.Я и не напрягаюсь. Спрашивающий настрочил 4 ответа, но затруднился показать реальный пример со (strlen(s) == 5) - значит он такое никогда не писал. А раз даже он не писал, то и оптимизировать нет смысла.
По мне, слишком редкая операция - сравнение длины строки с заранее известной константой, чтобы тратить ресурсы на оптимизацию.Если уж прям надо часто работать с длиной строки, то лучше использовать паскалевские-, с++- строки с длиной.
Сколько раз в секунду ядро линукса ищет символ в массиве? Чисто для понимания, насколько ускорится вся работа десктопа.
В файловых системах должна часто использоваться. Например, для поиска (отсутствия) слешей.
Теперь прикиньте длину среднего имени файла и затраты на подготовку его быстрой функции (допустим, он в итоге всё-таки напишет рабочий вариант).
> затраты на подготовку его быстрой функцииТеоретик, ты даже не знаешь какие затраты. Насколько затраты больше, чем побайтовое чтение (невыравненного начала)?
Конечно, не знаю. Пока есть два нерабочих варианта "быстрой функции", и один Анонимный эксперт, который замерял rep scasb для 1 байта на i80386, знать как бы и не о чем.
> rep scasb для 1 байта на i80386Теоретик, как раз на нем REP SCASB или другие стрковые инструкции с префиксом REP могут быть и быстрее, в отличии от суперскалярных процессоров с внеочередным исполнением команд.
Ну то есть цифр никаких так и нет, один трындёж.
> В файловых системах должна часто использоваться. Например, для поиска (отсутствия) слешей.Если бы анонимный эксперт отвечал за свои слова, то поиск в тексте ext4 выдал бы ему следующее из fs/ext4/ioctl.c
if (memchr_inv(head.fmh_reserved, 0, sizeof(head.fmh_reserved)) ||
memchr_inv(head.fmh_keys[0].fmr_reserved, 0,
sizeof(head.fmh_keys[0].fmr_reserved)) ||
memchr_inv(head.fmh_keys[1].fmr_reserved, 0,
sizeof(head.fmh_keys[1].fmr_reserved)))
return -EINVAL;
Спасибо, что отвечаешь за мои слова, а то было лень искать примеры.
Отвечаю. Вы, сударь, пустозвон:* memchr_inv - Find an unmatching character in an area of memory.
> memchr_invкстати, оптимизированный, не побайтовый
Логика в чем по твоему? Если каждое звено по отдельности не в носит существенного вклада в производительность всей системы, то оптимизировать ничего не нужно?
Это просто чувак захотел стать знаменитым. Там стоит почитать ответы. Он как бы исправил исходную ошибку (код вообще нерабочий изначально), вот новое:Have you had a chance to read how strscpy() is implemented? Do you understand why it's done that way?
> Это просто чувак захотел стать знаменитым. Там стоит почитать ответы. Он как
> бы исправил исходную ошибку (код вообще нерабочий изначально), вот новое:20 лет никто не замечал что код не работает. этим не рабочим кодом никто не пользовался. теперь им никто не будет пользоваться до 20% быстрее.
ну, ок.
Пишу же - там читайте ответы. Исходная - в смысле в предлагаемом "ускорении" была ошибка и оно не собиралось даже на каких-то архитектурах. Потом была вторая попытка. Его вежливо спросили, понимает ли он вообще, что пишет. Вроде бы автор уже скис.
>20 лет никто не замечал что код не работаетВся суть линукса в одной фразе
>>20 лет никто не замечал что код не работает
> Вся суть линукса в одной фразеВся суть анонимных экспертов. Код не видели, ничего не поняли, но уже что-то мнят.
Fedora 36.uname -a
Linux 5.18.10-200.fc36.x86_64 #1 SMP PREEMPT_DYNAMIC Thu Jul 7 17:21:38 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
Хмм. А что интенсивный поиск в больших строках в ядре делает?
Ну, если экзотический драйвер, понятно, можно в сам драйвер поместить недостающее.
Но, это не должна быть массовая функция.
Но, видимо кто то хочет 0нанизм с поиском и интенсивным копированием в ядро переместить.
Да, растишке такое и не снилось.
чот я не нашёл профита :)
# ./a.out
ARRAY SIZE: 1048576
LIB: 20754
NEW: 25628
#include <stdio.h>
#include <stdlib.h>
#include <linux/types.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <sys/time.h>#define A_SZ 1024*1024
unsigned char str[A_SZ] = { '\0' };
long long tv = 0;
unsigned long long _rdtsc()
{
union ts {
unsigned long long tx;
struct dword {
long tl, th;
} dw;
} t;asm("rdtsc\n":"=a"(t.dw.tl), "=d"(t.dw.th));
return t.tx;
}void gen_array()
{
int i, c;
srand(time(NULL));for (i = 0; i < A_SZ;) {
c = rand() % 255;
if (!isprint(c))
continue;
str[i] = c;
i++;
}
printf("ARRAY SIZE: %d\n", i);
}#define MEMCHR_MASK_GEN(mask) (mask *= 0x0101010101010101ULL)
void *new_memchr(const void *p, int c, size_t length)
{
__u64 mask, val;
const void *end = p + length;c &= 0xff;
/* write(1, "strchr\n", 7); */
while ((long)p & (sizeof(long) - 1)) {
if (p >= end)
return NULL;if (*(unsigned char *)p == c)
return (void *)p;p++;
}if (p <= end - 8) {
mask = c;
MEMCHR_MASK_GEN(mask);for (; p <= end - 8; p += 8) {
val = *(__u64 *) p ^ mask;
if ((val + 0xfefefefefefefeffull) & (~val & 0x8080808080808080ull))
break;
}
}for (; p < end; p++)
if (*(unsigned char *)p == c)
return (void *)p;return NULL;
}int main()
{
unsigned char ch;
char *ret = NULL;
int count = 0;gen_array();
/* glibc */
tv = _rdtsc();
for (ch = 0x20; ch < 0x7E; ch++)
ret = memchr(str, ch, A_SZ);
printf("LIB: %lld\n", _rdtsc() - tv);/* new */
tv = _rdtsc();
for (ch = 0x20; ch < 0x7E; ch++)
ret = new_memchr(str, ch, A_SZ);
printf("NEW: %lld\n", _rdtsc() - tv);return (0);
}
Что с чем сравниваешь?При чем тут ядро линукс?
> /* glibc */
Угадай с 3 раз, какая в glibc реализация memchr: побайтовая, пословная, sse, avx?
> Угадай с 3 раз, какая в glibc реализация memchr: побайтовая, пословная, sse,
> avx?Да пофиг, быстрее и всё.
Согласен, надо glibc запихать в ядро.
> Согласен, надо glibc запихать в ядро.)))
Не, просто поступил запрос на возможность впаять эту фичу в юзерспейс...
Чтоб не газифицировать лужи, быстрее бенч накидал.В жлибсе вот эта юзается https://www.felixcloutier.com/x86/pcmpistri.html
> Не, просто поступил запрос на возможность впаять эту фичу в юзерспейс...Облом, кто-то оказался шустрее.
В musl такая же пословная реализация memchr, вроде. Можешь сравнить.
> чот я не нашёл профита :)
> # ./a.out
> ARRAY SIZE: 1048576
> LIB: 20754
> NEW: 25628Если чего ещё не нашли - они там "ускоряют" drivers/misc/lkdtm/heap.c
то есть вот это:
if (memchr(val, 0xAB, 512) == NULL) {
pr_info("Memory appears initialized (%x, no earlier values)\n", *val);
} else {
pr_err("FAIL: Slab was not initialized\n");
pr_expected_config_param(CONFIG_INIT_ON_ALLOC_DEFAULT_ON, "init_on_alloc");
}...
if (memchr(val, 0xAB, PAGE_SIZE) == NULL) {
pr_info("Memory appears initialized (%x, no earlier values)\n", *val);
} else {
pr_err("FAIL: Slab was not initialized\n");
pr_expected_config_param(CONFIG_INIT_ON_ALLOC_DEFAULT_ON, "init_on_alloc");
}
> ... они там "ускоряют"printk выкинули бы, вот это был бы профит )))
Я вообще в шоке.))) А если партия даст миллиону китайцев задание отправить такие ускорения?
Я посмотрел код, непонятная магия сравнения байта со словом, если кто может, объясните плиз методу.
Вот тут почитай: https://graphics.stanford.edu/~seander/bithacks.html#ValueIn...
пункт "Determine if a word has a zero byte" и за ним "Determine if a word has a byte equal to n"
На русском есть книга Генри С. Уоррен мл. "Алгоритмические трюки для программистов", см главу "поиск в слове".