The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]



"Для ядра Linux предложена реализация функции memchr, работающая до 4 раз быстрее"
Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Изначальное сообщение [ Отслеживать ]

"Для ядра Linux предложена реализация функции memchr, работающая до 4 раз быстрее"  +/
Сообщение от opennews (??), 12-Июл-22, 09:26 
Для включения в состав ядра Linux предложен набор патчей с оптимизированной реализацией функции memchr(), применяемой для поиска символа в массиве. В отличие от старого варианта, в котором применялось побайтовое сравнение, предложенная реализация построена с учётом полного использования 64- и 32-разрядных регистров CPU. Вместо байтов сравнение осуществляется с использованием машинных слов, что позволяет за раз сравнивать как минимум 4 байта...

Подробнее: https://www.opennet.ru/opennews/art.shtml?num=57493

Ответить | Правка | Cообщить модератору

Оглавление

Сообщения [Сортировка по времени | RSS]


1. "Для ядра Linux предложена реализация функции memchr, работаю..."  +6 +/
Сообщение от Аноним (1), 12-Июл-22, 09:26 
Я думал и так уже оптимизировали все что можно для 64бит
Ответить | Правка | Наверх | Cообщить модератору

8. "Для ядра Linux предложена реализация функции memchr, работаю..."  –7 +/
Сообщение от n00by (ok), 12-Июл-22, 10:06 
Оно и оптимизировано уже более 10 лет. Называется аппаратная предвыборка данных (prefetch). Почему заявивший "The optimized "memchr()" is nearly 4x faster than the original one for long strings" не знает, что на больших блоках узким местом является скорость чтения из памяти - это другой вопрос.
Ответить | Правка | Наверх | Cообщить модератору

10. "Для ядра Linux предложена реализация функции memchr, работаю..."  +6 +/
Сообщение от _hide_ (ok), 12-Июл-22, 10:11 
Вы немного ошибаетесь. Никакие prefetch и прочие не избавят числодробилку от побайтового перебора. Ну да, память надо прочитать и загнать в кэш, но никто не говорит, что ядро стало работать в 4 раза быстрее, просто -1 узкий момент.
Ответить | Правка | Наверх | Cообщить модератору

14. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от n00by (ok), 12-Июл-22, 10:24 
А ещё я немного смотрю, чего оно там числодробит:

        nl = memchr(line, '\n', end - buffer);

Ответить | Правка | Наверх | Cообщить модератору

158. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (158), 16-Июл-22, 02:09 
Сразу видно человека не разбирающегося в теме
Ответить | Правка | К родителю #10 | Наверх | Cообщить модератору

29. "Для ядра Linux предложена реализация функции memchr, работаю..."  +2 +/
Сообщение от Аноним (-), 12-Июл-22, 12:51 
Когда-то давно сравнивал свою реализацию strlen (это почти memchr, только чуть другой)

Побайтовый наивный алгоритм проиграл по скорости около 4 раз 8-байтовому. Еще написал не совсем правильный sse-алгоритм, он еще в 1.5-2 раза быстрее.

Это к разговору про скорость подсистемы памяти.

Ответить | Правка | К родителю #8 | Наверх | Cообщить модератору

35. "Для ядра Linux предложена реализация функции memchr, работаю..."  –2 +/
Сообщение от n00by (ok), 12-Июл-22, 13:13 
То есть не догадались посчитать теоретический предел чтения из памяти и сравнить с ним результаты измерений? Это к разговору об измерениях. Про год и тип процессора не спрашиваю, как и про использование команды prefetchnta.
Ответить | Правка | Наверх | Cообщить модератору

48. "Для ядра Linux предложена реализация функции memchr, работаю..."  –3 +/
Сообщение от Аноним (48), 12-Июл-22, 14:34 
>Называется аппаратная предвыборка данных (prefetch).

А в Эльбрусах, Итаниках и прочих VLIW такой есть?

Ответить | Правка | К родителю #8 | Наверх | Cообщить модератору

54. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от n00by (ok), 12-Июл-22, 14:49 
Попробуйте дочитать моё сообщение до конца - там вся суть. Что касается вопроса, если нет аппаратной предвыборки - можно обеспечить программную, как делали раньше на IA32. Для этого есть либо специальная команда, либо читают память с шагом равным размеру линейки кеша.

Ответить | Правка | Наверх | Cообщить модератору

89. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 03:25 
> Называется аппаратная предвыборка данных (prefetch).

Интересно, а как предвыборка может изменить тот факт что телепать по 1 байту за раз вместо 4 означает в 4 раза больше инструкций на это самое? Инструкции все моментально чтоли выполняются, такты не занимают? Без предвыборки вы еще и память бонусом к этому дофигища подождете. И там упоминабтся строки до 512 байтов, чтоли. Это наверное не настолько ужасно?

Ответить | Правка | К родителю #8 | Наверх | Cообщить модератору

92. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 13-Июл-22, 09:16 
> И там упоминабтся строки до 512 байтов, чтоли.

Для недочитавших моё сообщение повторяю цитату автора "for long strings". Большая строка - это не 512 байт. В современных реалиях это, должно быть, гигабайты. Разницу скорости чтения из кеша и ОЗУ ищите сами. Чувак копировал пояснения из копии Агнер Фога или Генри Уоррена и не усёк этот нюанс, ему простительно. ;)

> Интересно, а как предвыборка может изменить тот факт что телепать по 1
> байту за раз вместо 4 означает в 4 раза больше инструкций
> на это самое? Инструкции все моментально чтоли выполняются, такты не занимают?

А подготовительные операции мы не считаем, зачем это - вдруг разрушит нашу стройную гипотезу. И статистику по длине строк не собрали. Просто голословно посчитаем себя умнее автора существующей реализации через REP SCASB, но напишем про это не ему, а вот тут.

Ответить | Правка | Наверх | Cообщить модератору

105. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 11:19 
> REP SCASB

Насколько помню, этот вариант проиграл варианту на (условных) переходах.

Продолжай теоретизировать.

Ответить | Правка | Наверх | Cообщить модератору

106. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 11:30 
>> 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 раза", которое уже дважды отклонили, как нерабочее.

Ответить | Правка | Наверх | Cообщить модератору

108. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 11:49 
Это было сказано про мое сравнение реализаций strlen.
В ядре линукс мало кого интересует производительность, особенно мало используемых дублирующих функций.
Специально искал этот допотопный memscan?
Ответить | Правка | Наверх | Cообщить модератору

113. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 12:06 
> Это было сказано про мое сравнение реализаций strlen.

Нет никакого сравнения: ни цифр, ни подробностей о железе.

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

А на самом деле анонимный эксперт не осилил поискать __HAVE_ARCH_MEMCHR

> Специально искал этот допотопный memscan?

Да, специально искал и нашёл memchr. Тема же про memchr. ;)

Ответить | Правка | Наверх | Cообщить модератору

115. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 12:17 
> __HAVE_ARCH_MEMCHR

производительностью которого заинтересовались и предлагают варианты.

Ответить | Правка | Наверх | Cообщить модератору

127. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 13:49 
Пока нет никаких измерений производительности. С какой целью Вы упорно пишете чушь в ответ на мои сообщения? Вы ещё вчера хотели вернуться к своим баранам.
Ответить | Правка | Наверх | Cообщить модератору

144. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от ммнюмнюмус (?), 13-Июл-22, 22:46 
Может, он и там тупил, ну они его и того?
Ответить | Правка | Наверх | Cообщить модератору

132. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 16:15 
> Для недочитавших моё сообщение повторяю цитату автора "for long strings". Большая строка
> - это не 512 байт. В современных реалиях это, должно быть, гигабайты.

Я что-то не уверен что ядро в принципе таким оперирует. Там длинное это наверное PATH_MAX какой-нибудь. Хоть я и не смотрел какой там наихучший случай конечно.

> Разницу скорости чтения из кеша и ОЗУ ищите сами.

Спасибо, Капитан Очевидность.

> А подготовительные операции мы не считаем, зачем это - вдруг разрушит нашу
> стройную гипотезу.

Ну, э, подготовительные операции или нет, а по эн байтов за раз обычно эффективнее чем по одному.

> И статистику по длине строк не собрали. Просто голословно
> посчитаем себя умнее автора существующей реализации через REP SCASB,

Ммм а как сие на ARM и RISCV?

> но напишем про это не ему, а вот тут.

Ага. Усомнившись в некоторых аспектах спича. И автор наверное все же не полный рак и побенчил свое добро? И что там реально будет лучше - ну я не настолько хорошо все варианты микроархитектур x86 знаю чтобы рассуждать чего в каком случае лучше и для кого из подвидов.

Ответить | Правка | К родителю #92 | Наверх | Cообщить модератору

139. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 20:05 
>> Для недочитавших моё сообщение повторяю цитату автора "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, не понятно, как симулировать исполнение и посмотреть что там сколько занимает в тактах.

Ответить | Правка | Наверх | Cообщить модератору

9. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от _hide_ (ok), 12-Июл-22, 10:08 
Тут, курица или яйцо. Работает медленно -- ищем решение без поиска в лоб, не используем поиск в лоб -- нет оптимизации и работает медленно.

Так микрооптимизации очень нужны, если они хорошо поддерживаются.

Ответить | Правка | К родителю #1 | Наверх | Cообщить модератору

12. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (12), 12-Июл-22, 10:12 
Наоборот всегда было главное единообразие чтобы обеспечить переносимость. Наоптимизировать под конкретное железо это к другим проприетарным производителям.  
Ответить | Правка | К родителю #1 | Наверх | Cообщить модератору

45. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (45), 12-Июл-22, 14:17 
Обычно имеются в начичии и оптимизированные варианты для известных архитектур, и неоптимизированные для любых, если оптимизированного не нашлось.
Ответить | Правка | Наверх | Cообщить модератору

17. "Для ядра Linux предложена реализация функции memchr, работаю..."  +2 +/
Сообщение от Ананас (?), 12-Июл-22, 10:54 
Раздуто, а не оптимизированно
Ответить | Правка | К родителю #1 | Наверх | Cообщить модератору

19. "Для ядра Linux предложена реализация функции memchr, работаю..."  +2 +/
Сообщение от Аноним (12), 12-Июл-22, 10:55 
Было бы оптимизировано, то не получилось бы сделать раздуто. Было бы супермеганеподдерживаемораздуто.  
Ответить | Правка | Наверх | Cообщить модератору

42. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (42), 12-Июл-22, 13:46 
В итоге получат, что толстое ядро тормозит сильнее, чем микроскопическое ускорение от поиска в строках.
Ответить | Правка | К родителю #17 | Наверх | Cообщить модератору

79. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (79), 12-Июл-22, 20:54 
Оно оптимизировано. Просто надо ещё мест, где можно очереднус спектр запустить по сторонним каналам. Обращение за пределы выделенной памяти и прочие плюшки.
Ответить | Правка | К родителю #1 | Наверх | Cообщить модератору

2. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pashev.ru (?), 12-Июл-22, 09:29 
> Вместо байтов сравнение осуществляется с использованием машинных слов, что позволяет за раз сравнивать как минимум 4 байта.

Как в glibc 🤗

Ответить | Правка | Наверх | Cообщить модератору

4. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 12-Июл-22, 09:39 
Там разве не sse и avx(512) с "до 64 байтами" за раз?
Ответить | Правка | Наверх | Cообщить модератору

28. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Онаним (?), 12-Июл-22, 12:50 
avx(512) в здравом уме в ядре использовать никто не будет, потому что на интелах оно имеет риск проложить производительность всей числодробилки, а не только одного ядра.

"Linus Torvalds: I hope Intel's AVX-512 'dies a painful death'"

Ядро поддерживает софт, работающий с AVX512, но это на жуткого любителя.

Ответить | Правка | Наверх | Cообщить модератору

33. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 12-Июл-22, 12:59 
> avx(512) в здравом уме в ядре использовать никто не будет

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

Ответить | Правка | Наверх | Cообщить модератору

69. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Онаним (?), 12-Июл-22, 19:11 
Ну, бОльшая часть ядра до последнего времени таки здравому смыслу соответствовала.

Последние веяния в виде иоурины, ёбпф и хруста - да, заставляют напрячься. Это то, что в монолит ну никак не вписывается, да.

Ответить | Правка | Наверх | Cообщить модератору

90. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 03:28 
Что за урина? Это uring чтоли так назвали? Оно может и брейнфак, но ОЧЕНЬ БЫСТРЫЙ брейнфак. И когда вы хотите всякие там 100Gig сеточки, сторажи типа оптана и проч - окей, но этот брейнфак быстрее обычных способов в разы! Поэтому с ним и канителятся.
Ответить | Правка | Наверх | Cообщить модератору

73. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от иисус господь евреев (?), 12-Июл-22, 19:34 
спасибо за инфу! смысул этих инструкций и новых процев околонулевой. пожалуй , пока останусь ка на коре2дуо.
Ответить | Правка | К родителю #28 | Наверх | Cообщить модератору

135. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (135), 13-Июл-22, 16:32 
https://colfaxresearch.com/skl-avx512/
Ответить | Правка | Наверх | Cообщить модератору

136. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (135), 13-Июл-22, 16:33 
Английского не знаю. Судя по тексту "Я" сайт перевёл хорошо если не отлично.
Ответить | Правка | Наверх | Cообщить модератору

147. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от ммнюмнюмус (?), 14-Июл-22, 15:17 
А что правда не так с avx-512? Я то наоборот стараюсь использовать векторизацию, вот только железа, поддерживающего что-то выше SSE так и не опробовал (у меня максимум SSE-4.3). Так что тут я слегка профан, и был бы рад пофиксить ещё немного пробелов в знаниях.

Что в нём не так - неоптимальная реализация работы с 512-битными векторами или бессмыссленность такого подхода из за неизбежных узких мест? Насколько я заметил, самая частая ошибка при векторизации - это разложить по вектору элементы некоей сложной обработки вместо того, а не сами группы (на уровне которых линейность таки прослеживается).

Ответить | Правка | К родителю #28 | Наверх | Cообщить модератору

148. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 14-Июл-22, 17:18 
Когда контекст исполнения (поток) переключается, регистры процессора надо сохранять. Операция не мгновенная, требует место в ОЗУ и может марать кеш. Было 16 штук 32-х байтных регистров (256 бит), стало вдвое больше и в количестве, и по размеру. Помножьте 2К на 1000 потоков. Интел выиграла в каком-то тесте, а система в целом просела, да ещё и ядро надо допилить.
Ответить | Правка | Наверх | Cообщить модератору

156. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Онаним (?), 15-Июл-22, 22:11 
Не так в нём то, что оно превращает в кипятильник весь камень, и частоты падают на всём кипятильнике, а не на конкретном ядре.
Ответить | Правка | К родителю #147 | Наверх | Cообщить модератору

157. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Онаним (?), 15-Июл-22, 22:11 
(и это не так из эксплуатационного)
Ещё с ним не так то, что разные процы поддерживают разные несовместимые субсеты оного...
Ответить | Правка | К родителю #147 | Наверх | Cообщить модератору

30. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Онаним (?), 12-Июл-22, 12:51 
А так да, скорее всего оптимизации касаются как раз SSE(2) и AVX(2) - но честно скажу, не смотрел.
Ответить | Правка | К родителю #4 | Наверх | Cообщить модератору

31. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Онаним (?), 12-Июл-22, 12:52 
В принципе и даже на стандартных регистрах можно через поиск нуля после вычитания, но изврат тот ещё.
Ответить | Правка | Наверх | Cообщить модератору

32. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Онаним (?), 12-Июл-22, 12:54 
В принципе даже просто выровненный забор и 4-8 сравнений на стандартных регистрах должны дать хороший прирост, если там до этого оно побайтово делалось.
Ответить | Правка | Наверх | Cообщить модератору

70. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от с22 (?), 12-Июл-22, 19:30 
В ядре не используются команды фпу, ссе и авх
Ответить | Правка | К родителю #4 | Наверх | Cообщить модератору

72. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (-), 12-Июл-22, 19:32 
glibc используется?
Ответить | Правка | Наверх | Cообщить модератору

74. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (-), 12-Июл-22, 19:43 
Первый найденный случайный файл

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

Найди отсутствие AVX

Ответить | Правка | К родителю #70 | Наверх | Cообщить модератору

93. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 09:33 
> Первый найденный случайный файл
> 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();

Ответить | Правка | Наверх | Cообщить модератору

102. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 13-Июл-22, 10:39 
> Что бы это значило и зачем? ;)

напечатай из ядра sin(M_PI/19)

Ответить | Правка | Наверх | Cообщить модератору

104. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 11:08 
> напечатай из ядра

"В ядре не используются команды" печати.

Ответить | Правка | Наверх | Cообщить модератору

120. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 13-Июл-22, 12:53 
открой для себя printk

https://www.opennet.ru/man.shtml?topic=printk

" DESCRIPTION

Print a formatted message to the ..."

Ответить | Правка | Наверх | Cообщить модератору

122. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (122), 13-Июл-22, 12:59 
Вот, чёрт.
Ответить | Правка | Наверх | Cообщить модератору

125. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 13:45 
>> Что бы это значило и зачем? ;)
> напечатай из ядра 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().

Ответить | Правка | К родителю #102 | Наверх | Cообщить модератору

82. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от 67332 (?), 12-Июл-22, 21:43 
Еще как используются, всякие там хеш-функции и прочие подобные вещи в нескольких вариантах есть.
Ответить | Правка | К родителю #70 | Наверх | Cообщить модератору

94. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 09:40 
Посмотрите, _как_ оно во "всяких там" используется. Человек прав в принципе, но сформулировал некорректно. Не принято использовать. Криптопреобразования работают с данным достаточно больших объёмов и в специфичных случаях, потому имеет смысл озадачиться с сохранением контекста.
Ответить | Правка | Наверх | Cообщить модератору

22. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от n00by (ok), 12-Июл-22, 11:22 
Специально скопирую сюда из /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;
}


Ответить | Правка | К родителю #2 | Наверх | Cообщить модератору

26. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 12-Июл-22, 12:25 
Покажи ещё sysdeps/x86_64/multiarch/memrchr-evex.S

https://sourceware.org/git?p=glibc.git;a=blob;f=sysdeps/x86_...

Ответить | Правка | Наверх | Cообщить модератору

36. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 12-Июл-22, 13:15 
Суть вот где:

  /* Handle the first few bytes by reading one byte at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */

На этом основании предлагаемому в ядро "в четыре раза быстрее" влупили NAK.

Ответить | Правка | Наверх | Cообщить модератору

38. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (-), 12-Июл-22, 13:35 
Давай так. Напиши свой наивный побайтовый алгоритм memchr (можешь даже префетч присобачить). И сравни с glibc, который будет использовать оптимизированный под твой процессор. На данных до одного гигабайта, чтоб уж наверняка вылезти за пределы всех уровней кеша.
Ответить | Правка | Наверх | Cообщить модератору

55. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 12-Июл-22, 14:51 
Ещё раз, для не уловивших суть: предлагаемое в ядро в общем случае НЕ РАБОТАЕТ, в отличие от реализации из glibc и остальных наивных.
Ответить | Правка | Наверх | Cообщить модератору

58. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 12-Июл-22, 16:38 
Вернемся к нашим скачущим баранам. Тогда зачем в ветке про glibc ты приводишь код из glibc, и приводишь код не всех реализаций/оптимизаций?

Про твое "замечание" про чтение начальных нескольких невыровненных байт. Как эта O(1) операция повлияет на скорость, особенно при очень больших N?

Ответить | Правка | Наверх | Cообщить модератору

60. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 12-Июл-22, 17:13 
> Тогда зачем в ветке про 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.

> Вернемся к нашим скачущим баранам.

Возвращайтесь. Вы здесь задержались слишком.

Ответить | Правка | Наверх | Cообщить модератору

62. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 12-Июл-22, 17:32 
"как в glibc", было сказано на счет "позволяет за раз сравнивать как минимум 4 байта".

Во время тестирования strlen, я тоже чисто случайно ошибся и читал невыровненные слова. Так вот, этот ошибочный вариант работал чуть медленнее выровненного варианта, примерно также в 4 раза быстрее наивного побайтового.

Ответить | Правка | Наверх | Cообщить модератору

96. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 09:44 
> "как в glibc", было сказано на счет "позволяет за раз сравнивать как
> минимум 4 байта".

Ещё раз: в данном случае оно не сравнивает, оно даже прочитать память не может, в отличие от glibc.

> Во время тестирования strlen, я тоже чисто случайно ошибся и читал невыровненные
> слова. Так вот, этот ошибочный вариант работал чуть медленнее выровненного варианта,
> примерно также в 4 раза быстрее наивного побайтового.

"У меня на виртуалке работает!" (ц)

Ответить | Правка | Наверх | Cообщить модератору

101. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 10:37 
> "У меня на виртуалке работает!" (ц)

У тебя вообще ничего не работает, и ты сидишь на оффтопе и рассуждаешь, что должно быть на линуксе.

Пиши memchr, можешь даже с префетчем и выравниванием по байтам, потом сказки рассказывай, что и где не работает.

Ответить | Правка | Наверх | Cообщить модератору

128. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 14:01 
> Пиши 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

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

>> "У меня на виртуалке работает!" (ц)
> У тебя вообще ничего не работает, и ты сидишь на оффтопе и
> рассуждаешь, что должно быть на линуксе.

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

Ответить | Правка | Наверх | Cообщить модератору

129. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 14:07 
Тем временем существует оптимизированный memchr_inv
Ответить | Правка | Наверх | Cообщить модератору

81. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от achtosluchilos (ok), 12-Июл-22, 21:26 
>  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.

ох уж эта сишка и ее проблемы с типами на разных архитектурах.

Ответить | Правка | К родителю #22 | Наверх | Cообщить модератору

95. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Онаним (?), 13-Июл-22, 09:42 
Хрустик как-то спасёт тебя от разного размера регистров в проце?
Ответить | Правка | Наверх | Cообщить модератору

97. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 13-Июл-22, 09:51 
Кстати, может ли Rust защитить от реальной проблемы предлагаемого "ускорения" - невозможность чтения двойных слов по невыровненым адресам на некотором железе?
Ответить | Правка | К родителю #81 | Наверх | Cообщить модератору

133. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Аноним (-), 13-Июл-22, 16:20 
> Кстати, может ли Rust защитить от реальной проблемы предлагаемого "ускорения" - невозможность
> чтения двойных слов по невыровненым адресам на некотором железе?

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

Ответить | Правка | Наверх | Cообщить модератору

137. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 19:20 
Интересно, можно ли нарушение alignment requirements поймать на этапе трансляции. Люди то увидели. А автор даже не знал.
Ответить | Правка | Наверх | Cообщить модератору

3. Скрыто модератором  –3 +/
Сообщение от pashev.ru (?), 12-Июл-22, 09:31 
Ответить | Правка | Наверх | Cообщить модератору

5. "Для ядра Linux предложена реализация функции memchr, работаю..."  –19 +/
Сообщение от Аноним (5), 12-Июл-22, 09:39 
Такого количества багов, костылей и рудиментов не было даже в ранней винде после перехода с мсдос
Ответить | Правка | Наверх | Cообщить модератору

6. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Анонимemail (6), 12-Июл-22, 10:05 
а что ты хотел, 31 год идёт ядру, его ещё причёсывают хотя бы хоть как-то
Ответить | Правка | Наверх | Cообщить модератору

51. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (5), 12-Июл-22, 14:41 
а что ты хотел, 1031 год идёт ядру, его ещё причёсывают хотя бы хоть как-то

P.S. где-то в далеком далеком интернете тысячу лет спустя

Ответить | Правка | Наверх | Cообщить модератору

11. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 12-Июл-22, 10:12 
Ну да, в то время люди задавались вопросом "какие такие строки, как часто и зачем надо сравнивать в ядре".
Ответить | Правка | К родителю #5 | Наверх | Cообщить модератору

13. "Для ядра Linux предложена реализация функции memchr, работаю..."  +3 +/
Сообщение от КО (?), 12-Июл-22, 10:14 
Ты ещё исходники индусской 11 не видел.
Ответить | Правка | К родителю #5 | Наверх | Cообщить модератору

24. "Для ядра Linux предложена реализация функции memchr, работаю..."  –11 +/
Сообщение от Аноним (5), 12-Июл-22, 12:08 
Я нормальный линукс десктоп не видел... хотя бы на уровне XP
Ответить | Правка | Наверх | Cообщить модератору

25. "Для ядра Linux предложена реализация функции memchr, работаю..."  +3 +/
Сообщение от commiethebeastie (ok), 12-Июл-22, 12:13 
Ага, мы уже все видел тулчейн в исходниках XP, можешь не продолжать, вот где костыли так костыли.
Ответить | Правка | Наверх | Cообщить модератору

27. "Для ядра Linux предложена реализация функции memchr, работаю..."  +2 +/
Сообщение от Аноним (5), 12-Июл-22, 12:47 
Плохому линуксоиду виндоус мешает
Ответить | Правка | Наверх | Cообщить модератору

34. "Для ядра Linux предложена реализация функции memchr, работаю..."  +5 +/
Сообщение от Анонимemail (6), 12-Июл-22, 13:00 
ЛЮБОМУ линуксоиду виндоуз мешает)
Ответить | Правка | Наверх | Cообщить модератору

44. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (45), 12-Июл-22, 14:12 
А виндузоид не видел десктопа лучшего, чем XP.
Ответить | Правка | К родителю #27 | Наверх | Cообщить модератору

49. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (5), 12-Июл-22, 14:36 
Это классика, это знать надо
Ответить | Правка | Наверх | Cообщить модератору

53. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (45), 12-Июл-22, 14:46 
Да знаю - синдром утёнка.
Ответить | Правка | Наверх | Cообщить модератору

84. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Тот_Самый_Анонимус (?), 12-Июл-22, 22:24 
Переходи на армянский алфавит! Как не хочешь? У тебя синдром утёнка!!!! (Логика тех, кто использует это словосочетание).
Ответить | Правка | Наверх | Cообщить модератору

159. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Конь Антон (?), 16-Июл-22, 06:08 
Это некрофилия а не классика
Тупой ты баран.
Ответить | Правка | К родителю #49 | Наверх | Cообщить модератору

59. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Аноним (59), 12-Июл-22, 16:47 
>Ты ещё исходники индусской 11 не видел

Кстати! Я, старый линуксовод (не помню XP, то есть перешёл до появления XP) недавно купил подержанный неттоп, а на нём обнаружилась 11-я винда. И, знаете ли, даже понравилось! Гламурненькая система. Только обновляется, сцуко, без спроса.

Ответить | Правка | К родителю #13 | Наверх | Cообщить модератору

65. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (-), 12-Июл-22, 18:36 
В поддержанных неттопах Windows 7 есть, 11-я в новых.

>И, знаете ли, даже понравилось! Гламурненькая система.

Будь осторожен это начало признака деградации.

>Только обновляется, сцуко, без спроса.

Знаете ли вы, что Windows периодически делает скриншоты вашего Рабочего стола и отправляет их на непонятные сервера.

Ответить | Правка | Наверх | Cообщить модератору

85. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Тот_Самый_Анонимус (?), 12-Июл-22, 22:25 
>>И, знаете ли, даже понравилось! Гламурненькая система.
>Будь осторожен это начало признака деградации.

Это что-то со скрижалей фанатиков.

Ответить | Правка | Наверх | Cообщить модератору

46. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (45), 12-Июл-22, 14:26 
Тебе M$ тогда исходники показывал ранней Венды?
Ответить | Правка | К родителю #5 | Наверх | Cообщить модератору

50. "Для ядра Linux предложена реализация функции memchr, работаю..."  –3 +/
Сообщение от Аноним (5), 12-Июл-22, 14:38 
Уж лучше чем у этой студенческой подделки

Just for fun! Как говорится...

Ответить | Правка | Наверх | Cообщить модератору

52. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (45), 12-Июл-22, 14:43 
Ну так показывал или фантазёр?
Ответить | Правка | Наверх | Cообщить модератору

63. "Для ядра Linux предложена реализация функции memchr, работаю..."  +3 +/
Сообщение от Аноним (63), 12-Июл-22, 17:32 
На изучай сколько угодно хоть вин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

Ответить | Правка | К родителю #46 | Наверх | Cообщить модератору

66. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Аноним (-), 12-Июл-22, 18:37 
Лютое не нужно.
Ответить | Правка | Наверх | Cообщить модератору

118. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от commiethebeastie (ok), 13-Июл-22, 12:39 
> На изучай сколько угодно хоть вин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 :)

Ответить | Правка | К родителю #63 | Наверх | Cообщить модератору

134. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 16:22 
> Такого количества багов, костылей и рудиментов не было даже в ранней винде
> после перехода с мсдос

Это ты погорячился и просто не видел в Win3.x/9x их типа-кернелы - настолько раздристаное месиво что состояло из примерно трех не особо связанных между собой частей.

Ответить | Правка | К родителю #5 | Наверх | Cообщить модератору

16. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Бывалый смузихлёб (?), 12-Июл-22, 10:43 
> Вместо байтов сравнение осуществляется с использованием машинных слов,
> что позволяет за раз сравнивать как минимум 4 байта.

Очень интересно, и каким же образом это делается с учётом что ожидается некоторая универсальность для разных архитектур

Ответить | Правка | Наверх | Cообщить модератору

18. "Для ядра Linux предложена реализация функции memchr, работаю..."  +2 +/
Сообщение от Аноним (12), 12-Июл-22, 10:54 
Он ифдефов конечно же напихал. Но ничего хорошего в этом нет имхо.  

>> if defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64

Ответить | Правка | Наверх | Cообщить модератору

20. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 12-Июл-22, 10:58 
Способ назван "сломаным"

> 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.

https://lkml.org/lkml/2022/7/11/1329

Ответить | Правка | К родителю #16 | Наверх | Cообщить модератору

23. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Sw00p aka Jerom (?), 12-Июл-22, 11:59 
>Очень интересно, и каким же образом это делается

параллельный аппаратный компоратор, хотя тут есть один момент для строк вида, abac, aaaa и т. д. если ишем a.

Ответить | Правка | К родителю #16 | Наверх | Cообщить модератору

47. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Аноним (45), 12-Июл-22, 14:32 
С помощью #ifdef ... #else ?
Ответить | Правка | К родителю #16 | Наверх | Cообщить модератору

21. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 12-Июл-22, 11:11 
Осталось понять, что он там оптимизировал:

$ 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

Ответить | Правка | Наверх | Cообщить модератору

37. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (37), 12-Июл-22, 13:30 
> до 4 раз быстрее

Это же не реклама, зачем употребтять "до"? Тем более, что в оригинале написано "около" - "around ~4x".

Ответить | Правка | Наверх | Cообщить модератору

40. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (42), 12-Июл-22, 13:41 
> "around ~4x"

Каков радиус этого эраунда?

Ответить | Правка | Наверх | Cообщить модератору

41. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (37), 12-Июл-22, 13:44 
Это не важно, главное что центр в районе 4х
Ответить | Правка | Наверх | Cообщить модератору

87. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (42), 13-Июл-22, 01:32 
> центр в районе 4х

Точно-точно центр? Судя по цифрам из топика - это теоретический край.

Ответить | Правка | Наверх | Cообщить модератору

39. "Для ядра Linux предложена реализация функции memchr, работаю..."  +3 +/
Сообщение от Аноним (42), 12-Июл-22, 13:40 
> в больших строках новый вариант оказался быстрее старого примерно в 4 раза (например, для строк в 1000 символов)

В 4 раза - что планируем получить...

> В ядре Linux размер обрабатываемых в memchr() строк достигает 512 байт. Прирост производительности для 512 байтовых строк, в ситуации, когда искомый символ находится в конце строки, составляет 20%.

Максимум 20% - мягко сказать, уже далеко не в 4 раза.

> Общий прирост производительности подсистем ядра при использовании оптимизированного варианта "memchr()" пока не оценивался

В реальности - 0.0X%, что даже постыдились показать.

Ответить | Правка | Наверх | Cообщить модератору

43. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Аноним (37), 12-Июл-22, 13:48 
> Максимум 20%

С какого потолка взял?

> В реальности - 0.0X%, что даже постыдились показать.

Русским языком же написано "пока не оценивался", какие буквы ты не понял?

Ответить | Правка | Наверх | Cообщить модератору

57. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от n00by (ok), 12-Июл-22, 15:06 
Эта тема обещает быть самой весёлой переписью экспертов. ;)

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.

Ответить | Правка | Наверх | Cообщить модератору

88. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (42), 13-Июл-22, 01:33 
> С какого потолка взял?

Перечитай сабж внимательно.

Ответить | Правка | К родителю #43 | Наверх | Cообщить модератору

56. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Аноним (56), 12-Июл-22, 15:06 
Хоспадя. Сами в 2022 году писать не умеют, так хоть бы списывать учились. http://fastcode.sourceforge.net/
Ответить | Правка | Наверх | Cообщить модератору

68. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 12-Июл-22, 18:58 
> ... так хоть бы списывать учились. http://fastcode.sourceforge.net/

Эти тоже в Стэнфорде спионерили:  © 1997-2005 Шон Эрон Андерсон  https://graphics.stanford.edu/~seander/bithacks.html

Ответить | Правка | Наверх | Cообщить модератору

61. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (61), 12-Июл-22, 17:23 
А зачем в новой реализации исходная строка/указатель двигается?
Ответить | Правка | Наверх | Cообщить модератору

64. "Для ядра Linux предложена реализация функции memchr, работаю..."  –1 +/
Сообщение от Аноним (63), 12-Июл-22, 17:34 
Имя автора северокорейского засланца прочитай и всё поймешь
Ответить | Правка | Наверх | Cообщить модератору

67. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 12-Июл-22, 18:53 

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;
}


Ответить | Правка | Наверх | Cообщить модератору

86. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (56), 12-Июл-22, 22:35 
Ну наверное для MEMCHR_MASK_GEN
Ответить | Правка | Наверх | Cообщить модератору

71. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (71), 12-Июл-22, 19:32 
Я уж испугался. Думал на расте переписали и уделали Си )
Ответить | Правка | Наверх | Cообщить модератору

75. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от qwe (??), 12-Июл-22, 20:02 
А я уж думал, что подобное давно оптимизировали. Интересно, а компиляторы хотя бы до такой наивной оптимизации доросли?

if (strlen(s) == 5) --> if (strnlen(s, 6) == 5)

Это не сильно актуально при малых строках строках, а при огромных - выигрыш существенен. Тем не менее второй вариант кода - большая редкость.

Ответить | Правка | Наверх | Cообщить модератору

100. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 10:33 
> А я уж думал, что подобное давно оптимизировали.

Давно оптимизировали. Предлагаемый код пока вообще не работает.

> Интересно, а компиляторы хотя
> бы до такой наивной оптимизации доросли?
> 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.


Ответить | Правка | Наверх | Cообщить модератору

131. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от qwe (??), 13-Июл-22, 15:26 
>        -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 байта не ходить, что очень даже полезно в случае, если строка очень большая.

Ответить | Правка | Наверх | Cообщить модератору

138. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 19:40 
Да, опция для другого. Задействованный механизм позволяет иногда оптимизировать чуть лучше:

$ 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.s

test:
    subq    $8, %rsp
    call    strlen@PLT
    cmpq    $5, %rax
    sete    %al
    addq    $8, %rsp
    movzbl    %al, %eax
    ret

main:
    movl    $1, %eax // strlen вообще не вызывается
    ret


В асм листинге вырезал нерелевантный текст.

То, что Вы предлагаете - это не наивная оптимизация. Подсчёт кол-ва символов в строке помещает всю строку в кеш. Если её длина больше 5 - может именно это программисту и надо?

Ответить | Правка | Наверх | Cообщить модератору

140. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от qwe (??), 13-Июл-22, 20:38 
Чуть лучше, только если строка - это константа. Что же касается строки

strlen(s) == 5

То тут довольно очевидно что именно программисту нужно. По крайней мере когда результат выполнения strlen никуда не сохраняется.

Ответить | Правка | Наверх | Cообщить модератору

149. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 14-Июл-22, 17:28 
Мне не очевидно, даже не знаю, когда такое может потребоваться и почему в реальной задаче нельзя проверить s[5].
Ответить | Правка | Наверх | Cообщить модератору

153. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от qwe (??), 14-Июл-22, 18:43 
> Мне не очевидно, даже не знаю, когда такое может потребоваться и почему
> в реальной задаче нельзя проверить s[5].

Что если длина строки 2 а память, где хранится строка, перед этим была обнулена? А что если проверяемая длина лежит за границей выделенного блока памяти? Вы точно знаете как именно организованы строки в Си?

Ответить | Правка | Наверх | Cообщить модератору

154. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 15-Июл-22, 06:33 
>> Мне не очевидно, даже не знаю, когда такое может потребоваться и почему
>> в реальной задаче нельзя проверить s[5].
> Что если длина строки 2 а память, где хранится строка, перед этим
> была обнулена?

Вот поэтому и пишу "в реальной задаче". Могу придумать гипотетическую задачу, где надо как-то сгруппировать строки по длине. В таком случае эти нули окажутся проверены на предыдущих шагах.

> А что если проверяемая длина лежит за границей выделенного
> блока памяти?

Это частный случай вышеуказанного. В том числе и если по виртуальному адресу нет физической памяти.

> Вы точно знаете как именно организованы строки в Си?

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

Ответить | Правка | Наверх | Cообщить модератору

155. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от qwe (??), 15-Июл-22, 13:16 
Я спрашиваю про конкретную оптимизацию при использовании конкретной функции из стандартной библиотеки, вы же отвечаете непонятно на что, затем придумываете гипотетические задачи, в которых эта функция не используется вовсе. Если я вызываю strlen(s), то это означает, что мне неизвестна длина строки (внешние данные), а если я вызываю strnlen(s, 6), это означает что мне не нужна точная длина строки, я лишь хочу убедится, что ее длина больше 5.
Ответить | Правка | Наверх | Cообщить модератору

160. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 16-Июл-22, 07:17 
> Я спрашиваю про конкретную оптимизацию при использовании конкретной функции из стандартной
> библиотеки, вы же отвечаете непонятно на что,

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

> затем придумываете гипотетические задачи,
> в которых эта функция не используется вовсе.

Потому что реальную задачу Вы не показали.

> Если я вызываю 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.

Ответить | Правка | Наверх | Cообщить модератору

161. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от qwe (??), 16-Июл-22, 12:31 
> А я увидел человека, кто не может сгенерировать ассемблерный листинг и изучить
> его.

А если человек сгенерировал, изучил, но вам не доложил, как вы его отличите от того, кто не смог? Так вот, если вашей функции test выше скормить программно заполненный массив символов, то в asm листинге таки будет виден вызов strlen. Сюрприз? Мне почему-то показалось, что доказывать это нет необходимости. Мне не нужен вызов strlen("12345"), ибо чтобы узнать результат этого вызова компьютер не нужен. Я спрашивал о strlen(s), где s - это переменная, а не константа, зашитая в коде. Но не напрягайтесь, сейчас мне ваш ответ не нужен, только не после демонстрации вами вашей логики.

Ответить | Правка | Наверх | Cообщить модератору

162. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 16-Июл-22, 13:18 
>> А я увидел человека, кто не может сгенерировать ассемблерный листинг и изучить
>> его.
> А если человек сгенерировал, изучил, но вам не доложил, как вы его
> отличите от того, кто не смог?

Очень просто - априори я верю человеку на слово. Если он пишет "Интересно, а компиляторы хотя бы до такой наивной оптимизации доросли?" - значит ему действительно интересно узнать.

> Так вот, если вашей функции
> test выше скормить программно заполненный массив символов, то в asm листинге
> таки будет виден вызов strlen. Сюрприз? Мне почему-то показалось, что доказывать
> это нет необходимости.

Действительно, сюрприз. В том листинге, что я привёл, в test() есть вызов strlen. Но в main() нет вызова test(). Я полагал, что нет смысла объяснять очевидные вещи.

> Мне не нужен вызов strlen("12345"), ибо чтобы узнать
> результат этого вызова компьютер не нужен. Я спрашивал о strlen(s), где
> s - это переменная, а не константа, зашитая в коде. Но
> не напрягайтесь, сейчас мне ваш ответ не нужен, только не после
> демонстрации вами вашей логики.

Я и не напрягаюсь. Спрашивающий настрочил 4 ответа, но затруднился показать реальный пример со (strlen(s) == 5) - значит он такое никогда не писал. А раз даже он не писал, то и оптимизировать нет смысла.

Ответить | Правка | Наверх | Cообщить модератору

141. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (141), 13-Июл-22, 20:59 
По мне, слишком редкая операция - сравнение длины строки с заранее известной константой, чтобы тратить ресурсы на оптимизацию.

Если уж прям надо часто работать с длиной строки, то лучше использовать паскалевские-, с++- строки с длиной.

Ответить | Правка | К родителю #75 | Наверх | Cообщить модератору

76. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Атон (?), 12-Июл-22, 20:03 
Сколько раз в секунду ядро линукса ищет символ в массиве?   Чисто для понимания, насколько ускорится вся работа десктопа.
Ответить | Правка | Наверх | Cообщить модератору

78. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 12-Июл-22, 20:28 
В файловых системах должна часто использоваться. Например, для поиска (отсутствия) слешей.
Ответить | Правка | Наверх | Cообщить модератору

99. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 10:09 
Теперь прикиньте длину среднего имени файла и затраты на подготовку его быстрой функции (допустим, он в итоге всё-таки напишет рабочий вариант).
Ответить | Правка | Наверх | Cообщить модератору

103. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 10:55 
> затраты на подготовку его быстрой функции

Теоретик, ты даже не знаешь какие затраты. Насколько затраты больше, чем побайтовое чтение (невыравненного начала)?

Ответить | Правка | Наверх | Cообщить модератору

107. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 11:46 
Конечно, не знаю. Пока есть два нерабочих варианта "быстрой функции", и один Анонимный эксперт, который замерял rep scasb для 1 байта на i80386, знать как бы и не о чем.

Ответить | Правка | Наверх | Cообщить модератору

110. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 12:01 
> rep scasb для 1 байта на i80386

Теоретик, как раз на нем REP SCASB или другие стрковые инструкции с префиксом REP могут быть и быстрее, в отличии от суперскалярных процессоров с внеочередным исполнением команд.

Ответить | Правка | Наверх | Cообщить модератору

124. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 13:34 
Ну то есть цифр никаких так и нет, один трындёж.
Ответить | Правка | Наверх | Cообщить модератору

109. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 11:53 
> В файловых системах должна часто использоваться. Например, для поиска (отсутствия) слешей.

Если бы анонимный эксперт отвечал за свои слова, то поиск в тексте 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;

Ответить | Правка | К родителю #78 | Наверх | Cообщить модератору

112. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Аноним (-), 13-Июл-22, 12:05 
Спасибо, что отвечаешь за мои слова, а то было лень искать примеры.
Ответить | Правка | Наверх | Cообщить модератору

123. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 13:29 
Отвечаю. Вы, сударь, пустозвон:

* memchr_inv - Find an unmatching character in an area of memory.

Ответить | Правка | Наверх | Cообщить модератору

126. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 13:46 
> memchr_inv

кстати, оптимизированный, не побайтовый

Ответить | Правка | Наверх | Cообщить модератору

91. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от thhh (?), 13-Июл-22, 07:04 
Логика в чем по твоему? Если каждое звено по отдельности не в носит существенного вклада в производительность всей системы, то оптимизировать ничего не нужно?
Ответить | Правка | К родителю #76 | Наверх | Cообщить модератору

98. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 13-Июл-22, 10:05 
Это просто чувак захотел стать знаменитым. Там стоит почитать ответы. Он как бы исправил исходную ошибку (код вообще нерабочий изначально), вот новое:

Have you had a chance to read how strscpy() is implemented? Do you understand why it's done that way?

Ответить | Правка | К родителю #76 | Наверх | Cообщить модератору

142. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от Атон (?), 13-Июл-22, 21:36 
> Это просто чувак захотел стать знаменитым. Там стоит почитать ответы. Он как
> бы исправил исходную ошибку (код вообще нерабочий изначально), вот новое:

20 лет никто не замечал что код не работает. этим не рабочим кодом никто не пользовался. теперь им никто не будет пользоваться до 20% быстрее.

ну, ок.

Ответить | Правка | Наверх | Cообщить модератору

151. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 14-Июл-22, 17:40 
Пишу же - там читайте ответы. Исходная - в смысле в предлагаемом "ускорении" была ошибка и оно не собиралось даже на каких-то архитектурах. Потом была вторая попытка. Его вежливо спросили, понимает ли он вообще, что пишет. Вроде бы автор уже скис.
Ответить | Правка | Наверх | Cообщить модератору

163. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (163), 16-Июл-22, 14:06 
>20 лет никто не замечал что код не работает

Вся суть линукса в одной фразе

Ответить | Правка | К родителю #142 | Наверх | Cообщить модератору

164. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 16-Июл-22, 14:39 
>>20 лет никто не замечал что код не работает
> Вся суть линукса в одной фразе

Вся суть анонимных экспертов. Код не видели, ничего не поняли, но уже что-то мнят.

Ответить | Правка | Наверх | Cообщить модератору

77. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (77), 12-Июл-22, 20:21 
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

Ответить | Правка | Наверх | Cообщить модератору

80. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от _kp (ok), 12-Июл-22, 21:00 
Хмм. А что интенсивный поиск в больших строках в ядре делает?
Ну, если экзотический драйвер, понятно, можно в сам драйвер поместить недостающее.
Но, это не должна быть массовая функция.
Но, видимо кто то хочет 0нанизм с поиском и интенсивным копированием в ядро переместить.
Ответить | Правка | Наверх | Cообщить модератору

83. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от кубрик (?), 12-Июл-22, 22:04 
Да, растишке такое и не снилось.
Ответить | Правка | Наверх | Cообщить модератору

111. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 13-Июл-22, 12:02 
чот я не нашёл профита :)
# ./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);
}


Ответить | Правка | Наверх | Cообщить модератору

114. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 12:12 
Что с чем сравниваешь?

При чем тут ядро линукс?

> /* glibc */

Угадай с 3 раз, какая в glibc реализация memchr: побайтовая, пословная, sse, avx?

Ответить | Правка | Наверх | Cообщить модератору

116. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 13-Июл-22, 12:26 
> Угадай с 3 раз, какая в glibc реализация memchr: побайтовая, пословная, sse,
> avx?

Да пофиг, быстрее и всё.  

Ответить | Правка | Наверх | Cообщить модератору

117. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 12:30 
Согласен, надо glibc запихать в ядро.
Ответить | Правка | Наверх | Cообщить модератору

119. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 13-Июл-22, 12:44 
> Согласен, надо glibc запихать в ядро.

)))

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

В жлибсе вот эта юзается https://www.felixcloutier.com/x86/pcmpistri.html

Ответить | Правка | Наверх | Cообщить модератору

121. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Аноним (-), 13-Июл-22, 12:53 
> Не, просто поступил запрос на возможность впаять эту фичу в юзерспейс...

Облом, кто-то оказался шустрее.

В musl такая же пословная реализация memchr, вроде. Можешь сравнить.

Ответить | Правка | Наверх | Cообщить модератору

130. "Для ядра Linux предложена реализация функции memchr, работаю..."  +1 +/
Сообщение от n00by (ok), 13-Июл-22, 14:34 
> чот я не нашёл профита :)
> # ./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");
    }


Ответить | Правка | К родителю #111 | Наверх | Cообщить модератору

146. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от pavlinux (ok), 14-Июл-22, 00:17 
> ... они там "ускоряют"

printk выкинули бы, вот это был бы профит )))

Ответить | Правка | Наверх | Cообщить модератору

150. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 14-Июл-22, 17:38 
Я вообще в шоке.))) А если партия даст миллиону китайцев задание отправить такие ускорения?
Ответить | Правка | Наверх | Cообщить модератору

143. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от Непростое кино (?), 13-Июл-22, 22:38 
Я посмотрел код, непонятная магия сравнения байта со словом, если кто может, объясните плиз методу.
Ответить | Правка | Наверх | Cообщить модератору

145. "Для ядра Linux предложена реализация функции memchr, работаю..."  +3 +/
Сообщение от pavlinux (ok), 13-Июл-22, 23:48 
Вот тут почитай: 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"


Ответить | Правка | Наверх | Cообщить модератору

152. "Для ядра Linux предложена реализация функции memchr, работаю..."  +/
Сообщение от n00by (ok), 14-Июл-22, 17:53 
На русском есть книга Генри С. Уоррен мл. "Алгоритмические трюки для программистов", см главу "поиск в слове".
Ответить | Правка | К родителю #143 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру