The OpenNET Project / Index page

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

форумы
правила/FAQ
поиск
регистрация
вход
слежка
RSS


Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы [ Отслеживать ]

Оглавление

Для ядра Linux предложена реализация функции memchr, работающая до 4 раз быстрее, opennews (??), 12-Июл-22, (0) [смотреть все]

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


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ообщить модератору

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

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




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

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