forum.opennet.ru

"Для ядра Linux предложена реализация функции memchr, работающая до 4 раз быстрее"

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

Исходное сообщение

[ Отслеживать ]

Подсказка: Для слежения за появлением новых сообщений в нити, нажмите "Проследить за развитием треда".

. "Для ядра Linux предложена реализация функции memchr, работаю..."	+/–
Сообщение от n00by (ok), 15-Июл-22, 06:33
>> Мне не очевидно, даже не знаю, когда такое может потребоваться и почему >> в реальной задаче нельзя проверить s[5]. > Что если длина строки 2 а память, где хранится строка, перед этим > была обнулена? Вот поэтому и пишу "в реальной задаче". Могу придумать гипотетическую задачу, где надо как-то сгруппировать строки по длине. В таком случае эти нули окажутся проверены на предыдущих шагах. > А что если проверяемая длина лежит за границей выделенного > блока памяти? Это частный случай вышеуказанного. В том числе и если по виртуальному адресу нет физической памяти. > Вы точно знаете как именно организованы строки в Си? Как считает целесообразным для решения задачи программист, так и организует. Если часто нужна длина, она не вычисляется каждый раз, а хранится отдельно. На практике, если программа более-менее серьёзно работает с текстом, strlen оказывается в каких-то вспомогательных местах, если вообще есть.
Ответить \| Правка \| Наверх \| Cообщить модератору

Оглавление

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

Я думал и так уже оптимизировали все что можно для 64бит, Аноним, 12-Июл-22, 09:26 (1) //
- Оно и оптимизировано уже более 10 лет Называется аппаратная предвыборка данных , n00by, 12-Июл-22, 10:06 (8) //
  - Вы немного ошибаетесь Никакие prefetch и прочие не избавят числодробилку от поб, _hide_, 12-Июл-22, 10:11 (10) //
    - А ещё я немного смотрю, чего оно там числодробит nl memchr line, n , end -, n00by, 12-Июл-22, 10:24 (14)
    - Сразу видно человека не разбирающегося в теме, Аноним, 16-Июл-22, 02:09 (158)
  - Когда-то давно сравнивал свою реализацию strlen это почти memchr, только чуть д, Аноним, 12-Июл-22, 12:51 (29) //
    - То есть не догадались посчитать теоретический предел чтения из памяти и сравнить, n00by, 12-Июл-22, 13:13 (35)
  - А в Эльбрусах, Итаниках и прочих VLIW такой есть , Аноним, 12-Июл-22, 14:34 (48) //
    - Попробуйте дочитать моё сообщение до конца - там вся суть Что касается вопроса,, n00by, 12-Июл-22, 14:49 (54)
  - Интересно, а как предвыборка может изменить тот факт что телепать по 1 байту за , Аноним, 13-Июл-22, 03:25 (89) //
    - Для недочитавших моё сообщение повторяю цитату автора for long strings Больша, n00by, 13-Июл-22, 09:16 (92)
      - Насколько помню, этот вариант проиграл варианту на условных переходах Продолжа, Аноним, 13-Июл-22, 11:19 (105)
        
        Как бы не важно, кто и что там якобы помнит, когда вот код из реального мира co, n00by, 13-Июл-22, 11:30 (106)
        
        Это было сказано про мое сравнение реализаций strlen В ядре линукс мало кого инт, Аноним, 13-Июл-22, 11:49 (108)
        
        Нет никакого сравнения ни цифр, ни подробностей о железе А на самом деле аноним, n00by, 13-Июл-22, 12:06 (113)
        
        производительностью которого заинтересовались и предлагают варианты , Аноним, 13-Июл-22, 12:17 (115)
        
        Пока нет никаких измерений производительности С какой целью Вы упорно пишете чу, n00by, 13-Июл-22, 13:49 (127)
        
        Может, он и там тупил, ну они его и того , ммнюмнюмус, 13-Июл-22, 22:46 (144)
      - Я что-то не уверен что ядро в принципе таким оперирует Там длинное это наверное, Аноним, 13-Июл-22, 16:15 (132)
        
        Разумеется, не оперирует Но автор написал long Вспоминаем определение кеш-памя, n00by, 13-Июл-22, 20:05 (139)
- Тут, курица или яйцо Работает медленно -- ищем решение без поиска в лоб, не исп, _hide_, 12-Июл-22, 10:08 (9)
- Наоборот всегда было главное единообразие чтобы обеспечить переносимость Наопти, Аноним, 12-Июл-22, 10:12 (12) //
  - Обычно имеются в начичии и оптимизированные варианты для известных архитектур, и, Аноним, 12-Июл-22, 14:17 (45)
- Раздуто, а не оптимизированно , Ананас, 12-Июл-22, 10:54 (17) //
  - Было бы оптимизировано, то не получилось бы сделать раздуто Было бы супермегане, Аноним, 12-Июл-22, 10:55 (19)
  - В итоге получат, что толстое ядро тормозит сильнее, чем микроскопическое ускорен, Аноним, 12-Июл-22, 13:46 (42)
- Оно оптимизировано Просто надо ещё мест, где можно очереднус спектр запустить п, Аноним, 12-Июл-22, 20:54 (79)
Как в glibc 129303 , pashev.ru, 12-Июл-22, 09:29 (2) //
- Там разве не sse и avx 512 с до 64 байтами за раз , Аноним, 12-Июл-22, 09:39 (4) //
  - avx 512 в здравом уме в ядре использовать никто не будет, потому что на интелах, Онаним, 12-Июл-22, 12:50 (28) //
    - Это монолит, нет смысла апеллировать к здравому смыслу , Аноним, 12-Июл-22, 12:59 (33)
      - Ну, бОльшая часть ядра до последнего времени таки здравому смыслу соответствовал, Онаним, 12-Июл-22, 19:11 (69)
        
        Что за урина Это uring чтоли так назвали Оно может и брейнфак, но ОЧЕНЬ БЫСТРЫ, Аноним, 13-Июл-22, 03:28 (90)
    - спасибо за инфу смысул этих инструкций и новых процев околонулевой пожалуй , п, иисус господь евреев, 12-Июл-22, 19:34 (73)
      - https colfaxresearch com skl-avx512 , Аноним, 13-Июл-22, 16:32 (135)
        
        Английского не знаю Судя по тексту Я сайт перевёл хорошо если не отлично , Аноним, 13-Июл-22, 16:33 (136)
    - А что правда не так с avx-512 Я то наоборот стараюсь использовать векторизацию,, ммнюмнюмус, 14-Июл-22, 15:17 (147)
      - Когда контекст исполнения поток переключается, регистры процессора надо сохран, n00by, 14-Июл-22, 17:18 (148)
      - Не так в нём то, что оно превращает в кипятильник весь камень, и частоты падают , Онаним, 15-Июл-22, 22:11 (156)
      - и это не так из эксплуатационного Ещё с ним не так то, что разные процы поддерж, Онаним, 15-Июл-22, 22:11 (157)
  - А так да, скорее всего оптимизации касаются как раз SSE 2 и AVX 2 - но честно , Онаним, 12-Июл-22, 12:51 (30) //
    - В принципе и даже на стандартных регистрах можно через поиск нуля после вычитани, Онаним, 12-Июл-22, 12:52 (31)
      - В принципе даже просто выровненный забор и 4-8 сравнений на стандартных регистра, Онаним, 12-Июл-22, 12:54 (32)
  - В ядре не используются команды фпу, ссе и авх, с22, 12-Июл-22, 19:30 (70) //
    - glibc используется , Аноним, 12-Июл-22, 19:32 (72)
    - Первый найденный случайный файл https git kernel org pub scm linux kernel git , Аноним, 12-Июл-22, 19:43 (74)
      - Нашёл баш-программиста ядра Смотрим не Makefile, а первый найденный случайный к, n00by, 13-Июл-22, 09:33 (93)
        
        напечатай из ядра sin M_PI 19 , pavlinux, 13-Июл-22, 10:39 (102)
        
        В ядре не используются команды печати , Аноним, 13-Июл-22, 11:08 (104)
        
        открой для себя printkhttps www opennet ru man shtml topic printk DESCRIPTION, pavlinux, 13-Июл-22, 12:53 (120)
        
        Вот, чёрт , Аноним, 13-Июл-22, 12:59 (122)
        
        Ну вывести 0 16459459028 как бы не проблема Вопрос был к утверждавшим, что FPU , n00by, 13-Июл-22, 13:45 (125)
    - Еще как используются, всякие там хеш-функции и прочие подобные вещи в нескольких, 67332, 12-Июл-22, 21:43 (82)
      - Посмотрите, _как_ оно во всяких там используется Человек прав в принципе, но , n00by, 13-Июл-22, 09:40 (94)
- Специально скопирую сюда из glibc string memchr cчто бы люди могли почитать ком, n00by, 12-Июл-22, 11:22 (22) //
  - Покажи ещё sysdeps x86_64 multiarch memrchr-evex Shttps sourceware org git p g, Аноним, 12-Июл-22, 12:25 (26) //
    - Суть вот где Handle the first few bytes by reading one byte at a time , n00by, 12-Июл-22, 13:15 (36)
      - Давай так Напиши свой наивный побайтовый алгоритм memchr можешь даже префетч п, Аноним, 12-Июл-22, 13:35 (38)
        
        Ещё раз, для не уловивших суть предлагаемое в ядро в общем случае НЕ РАБОТАЕТ, , n00by, 12-Июл-22, 14:51 (55)
        
        Вернемся к нашим скачущим баранам Тогда зачем в ветке про glibc ты приводишь ко, Аноним, 12-Июл-22, 16:38 (58)
        
        В ответ на заявление Как в glibc 129303 я показал, что оно - ложно Затем, ч, n00by, 12-Июл-22, 17:13 (60)
        
        как в glibc , было сказано на счет позволяет за раз сравнивать как минимум 4 б, Аноним, 12-Июл-22, 17:32 (62)
        
        Ещё раз в данном случае оно не сравнивает, оно даже прочитать память не может, , n00by, 13-Июл-22, 09:44 (96)
        
        У тебя вообще ничего не работает, и ты сидишь на оффтопе и рассуждаешь, что долж, Аноним, 13-Июл-22, 10:37 (101)
        
        Дублирую цитаты I think you re missing the point Loads at unaligned addresses m, n00by, 13-Июл-22, 14:01 (128)
        Тем временем существует оптимизированный memchr_inv, Аноним, 13-Июл-22, 14:07 (129)
  - ох уж эта сишка и ее проблемы с типами на разных архитектурах , achtosluchilos, 12-Июл-22, 21:26 (81) //
    - Хрустик как-то спасёт тебя от разного размера регистров в проце , Онаним, 13-Июл-22, 09:42 (95)
    - Кстати, может ли Rust защитить от реальной проблемы предлагаемого ускорения - , n00by, 13-Июл-22, 09:51 (97)
      - А вот не факт Скорее всего исключение от железки поймает в тыкву и не факт что , Аноним, 13-Июл-22, 16:20 (133)
        
        Интересно, можно ли нарушение alignment requirements поймать на этапе трансляции, n00by, 13-Июл-22, 19:20 (137)
См абсолютное и относительное улучшение 8212 https pashev ru nnt, pashev.ru, 12-Июл-22, 09:31 (3)
Такого количества багов, костылей и рудиментов не было даже в ранней винде после, Аноним, 12-Июл-22, 09:39 (5) //
- а что ты хотел, 31 год идёт ядру, его ещё причёсывают хотя бы хоть как-то, Аноним, 12-Июл-22, 10:05 (6) //
  - а что ты хотел, 1031 год идёт ядру, его ещё причёсывают хотя бы хоть как-тоP S , Аноним, 12-Июл-22, 14:41 (51)
- Ну да, в то время люди задавались вопросом какие такие строки, как часто и заче, n00by, 12-Июл-22, 10:12 (11)
- Ты ещё исходники индусской 11 не видел , КО, 12-Июл-22, 10:14 (13) //
  - Я нормальный линукс десктоп не видел хотя бы на уровне XP, Аноним, 12-Июл-22, 12:08 (24) //
    - Ага, мы уже все видел тулчейн в исходниках XP, можешь не продолжать, вот где кос, commiethebeastie, 12-Июл-22, 12:13 (25)
      - Плохому линуксоиду виндоус мешает, Аноним, 12-Июл-22, 12:47 (27)
        
        ЛЮБОМУ линуксоиду виндоуз мешает , Аноним, 12-Июл-22, 13:00 (34)
        А виндузоид не видел десктопа лучшего, чем XP , Аноним, 12-Июл-22, 14:12 (44)
        
        Это классика, это знать надо, Аноним, 12-Июл-22, 14:36 (49)
        
        Да знаю - синдром утёнка , Аноним, 12-Июл-22, 14:46 (53)
        
        Переходи на армянский алфавит Как не хочешь У тебя синдром утёнка Логика , Тот_Самый_Анонимус, 12-Июл-22, 22:24 (84)
        
        Это некрофилия а не классикаТупой ты баран , Конь Антон, 16-Июл-22, 06:08 (159)
  - Кстати Я, старый линуксовод не помню XP, то есть перешёл до появления XP неда, Аноним, 12-Июл-22, 16:47 (59) //
    - В поддержанных неттопах Windows 7 есть, 11-я в новых Будь осторожен это начало п, Аноним, 12-Июл-22, 18:36 (65)
      - Это что-то со скрижалей фанатиков , Тот_Самый_Анонимус, 12-Июл-22, 22:25 (85)
- Тебе M тогда исходники показывал ранней Венды , Аноним, 12-Июл-22, 14:26 (46) //
  - Уж лучше чем у этой студенческой подделкиJust for fun Как говорится , Аноним, 12-Июл-22, 14:38 (50) //
    - Ну так показывал или фантазёр , Аноним, 12-Июл-22, 14:43 (52)
  - На изучай сколько угодно хоть вин2000 хоть нт4magnet xt urn btih 66a26447f563c3, Аноним, 12-Июл-22, 17:32 (63) //
    - Лютое не нужно , Аноним, 12-Июл-22, 18:37 (66)
    - Гораздо новее есть исходники, windows server 2003 , commiethebeastie, 13-Июл-22, 12:39 (118)
- Это ты погорячился и просто не видел в Win3 x 9x их типа-кернелы - настолько раз, Аноним, 13-Июл-22, 16:22 (134)
Очень интересно, и каким же образом это делается с учётом что ожидается некотора, Бывалый смузихлёб, 12-Июл-22, 10:43 (16) //
- Он ифдефов конечно же напихал Но ничего хорошего в этом нет имхо , Аноним, 12-Июл-22, 10:54 (18)
- Способ назван сломаным Exactly The initial code is broken, NAK P S At least yo, n00by, 12-Июл-22, 10:58 (20)
- параллельный аппаратный компоратор, хотя тут есть один момент для строк вида, ab, Sw00p aka Jerom, 12-Июл-22, 11:59 (23)
- С помощью ifdef else , Аноним, 12-Июл-22, 14:32 (47)
Осталось понять, что он там оптимизировал grep -R e __HAVE_ARCH_MEMCHR arch, n00by, 12-Июл-22, 11:11 (21)
Это же не реклама, зачем употребтять до Тем более, что в оригинале написано , Аноним, 12-Июл-22, 13:30 (37) //
- Каков радиус этого эраунда , Аноним, 12-Июл-22, 13:41 (40) //
  - Это не важно, главное что центр в районе 4х, Аноним, 12-Июл-22, 13:44 (41) //
    - Точно-точно центр Судя по цифрам из топика - это теоретический край , Аноним, 13-Июл-22, 01:32 (87)
В 4 раза - что планируем получить Максимум 20 - мягко сказать, уже далеко не , Аноним, 12-Июл-22, 13:40 (39) //
- С какого потолка взял Русским языком же написано пока не оценивался , какие бук, Аноним, 12-Июл-22, 13:48 (43) //
  - Эта тема обещает быть самой весёлой переписью экспертов If you fix the issue,, n00by, 12-Июл-22, 15:06 (57)
  - Перечитай сабж внимательно , Аноним, 13-Июл-22, 01:33 (88)
Хоспадя Сами в 2022 году писать не умеют, так хоть бы списывать учились http , Аноним, 12-Июл-22, 15:06 (56) //
- Эти тоже в Стэнфорде спионерили 1997-2005 Шон Эрон Андерсон https graphic, pavlinux, 12-Июл-22, 18:58 (68)
А зачем в новой реализации исходная строка указатель двигается , Аноним, 12-Июл-22, 17:23 (61) //
- Имя автора северокорейского засланца прочитай и всё поймешь, Аноним, 12-Июл-22, 17:34 (64)
code void memchr const void p, int c, size_t length u64 mask, val co, pavlinux, 12-Июл-22, 18:53 (67) //
- Ну наверное для MEMCHR_MASK_GEN, Аноним, 12-Июл-22, 22:35 (86)
Я уж испугался Думал на расте переписали и уделали Си , Аноним, 12-Июл-22, 19:32 (71)
А я уж думал, что подобное давно оптимизировали Интересно, а компиляторы хотя б, qwe, 12-Июл-22, 20:02 (75) //
- Давно оптимизировали Предлагаемый код пока вообще не работает -Wno-strin, n00by, 13-Июл-22, 10:33 (100) //
  - И как сие работает Сдается мне, что эта опция совсем не для этого Я имею ввиду, qwe, 13-Июл-22, 15:26 (131) //
    - Да, опция для другого Задействованный механизм позволяет иногда оптимизировать , n00by, 13-Июл-22, 19:40 (138)
      - Чуть лучше, только если строка - это константа Что же касается строкиstrlen s , qwe, 13-Июл-22, 20:38 (140)
        
        Мне не очевидно, даже не знаю, когда такое может потребоваться и почему в реальн, n00by, 14-Июл-22, 17:28 (149)
        
        Что если длина строки 2 а память, где хранится строка, перед этим была обнулена , qwe, 14-Июл-22, 18:43 (153)
        
        Вот поэтому и пишу в реальной задаче Могу придумать гипотетическую задачу, гд , n00by, 15-Июл-22, 06:33 (154)
        
        Я спрашиваю про конкретную оптимизацию при использовании конкретной функции из с, qwe, 15-Июл-22, 13:16 (155)
        
        А я увидел человека, кто не может сгенерировать ассемблерный листинг и изучить е, n00by, 16-Июл-22, 07:17 (160)
        
        А если человек сгенерировал, изучил, но вам не доложил, как вы его отличите от т, qwe, 16-Июл-22, 12:31 (161)
        
        Очень просто - априори я верю человеку на слово Если он пишет Интересно, а ком, n00by, 16-Июл-22, 13:18 (162)
- По мне, слишком редкая операция - сравнение длины строки с заранее известной кон, Аноним, 13-Июл-22, 20:59 (141)
Сколько раз в секунду ядро линукса ищет символ в массиве Чисто для понимания,, Атон, 12-Июл-22, 20:03 (76) //
- В файловых системах должна часто использоваться Например, для поиска отсутстви, Аноним, 12-Июл-22, 20:28 (78) //
  - Теперь прикиньте длину среднего имени файла и затраты на подготовку его быстрой , n00by, 13-Июл-22, 10:09 (99) //
    - Теоретик, ты даже не знаешь какие затраты Насколько затраты больше, чем побайто, Аноним, 13-Июл-22, 10:55 (103)
      - Конечно, не знаю Пока есть два нерабочих варианта быстрой функции , и один Ано, n00by, 13-Июл-22, 11:46 (107)
        
        Теоретик, как раз на нем REP SCASB или другие стрковые инструкции с префиксом RE, Аноним, 13-Июл-22, 12:01 (110)
        
        Ну то есть цифр никаких так и нет, один трындёж , n00by, 13-Июл-22, 13:34 (124)
  - Если бы анонимный эксперт отвечал за свои слова, то поиск в тексте ext4 выдал бы, n00by, 13-Июл-22, 11:53 (109) //
    - Спасибо, что отвечаешь за мои слова, а то было лень искать примеры , Аноним, 13-Июл-22, 12:05 (112)
      - Отвечаю Вы, сударь, пустозвон memchr_inv - Find an unmatching character in a, n00by, 13-Июл-22, 13:29 (123)
        
        кстати, оптимизированный, не побайтовый, Аноним, 13-Июл-22, 13:46 (126)
- Логика в чем по твоему Если каждое звено по отдельности не в носит существенног, thhh, 13-Июл-22, 07:04 (91)
- Это просто чувак захотел стать знаменитым Там стоит почитать ответы Он как бы , n00by, 13-Июл-22, 10:05 (98) //
  - 20 лет никто не замечал что код не работает этим не рабочим кодом никто не поль, Атон, 13-Июл-22, 21:36 (142) //
    - Пишу же - там читайте ответы Исходная - в смысле в предлагаемом ускорении был, n00by, 14-Июл-22, 17:40 (151)
    - Вся суть линукса в одной фразе, Аноним, 16-Июл-22, 14:06 (163)
      - Вся суть анонимных экспертов Код не видели, ничего не поняли, но уже что-то мня, n00by, 16-Июл-22, 14:39 (164)
Fedora 36 uname -aLinux 5 18 10-200 fc36 x86_64 1 SMP PREEMPT_DYNAMIC Thu Jul 7, Аноним, 12-Июл-22, 20:21 (77)
Хмм А что интенсивный поиск в больших строках в ядре делает Ну, если экзотическ, _kp, 12-Июл-22, 21:00 (80)
Да, растишке такое и не снилось , кубрик, 12-Июл-22, 22:04 (83)
чот я не нашёл профита a outARRAY SIZE 1048576LIB 20754NEW 25628 code , pavlinux, 13-Июл-22, 12:02 (111) //
- Что с чем сравниваешь При чем тут ядро линукс Угадай с 3 раз, какая в glibc реал, Аноним, 13-Июл-22, 12:12 (114) //
  - Да пофиг, быстрее и всё , pavlinux, 13-Июл-22, 12:26 (116) //
    - Согласен, надо glibc запихать в ядро , Аноним, 13-Июл-22, 12:30 (117)
      - Не, просто поступил запрос на возможность впаять эту фичу в юзерспейс Чтоб, pavlinux, 13-Июл-22, 12:44 (119)
        
        Облом, кто-то оказался шустрее В musl такая же пословная реализация memchr, врод, Аноним, 13-Июл-22, 12:53 (121)
- Если чего ещё не нашли - они там ускоряют drivers misc lkdtm heap c то есть во, n00by, 13-Июл-22, 14:34 (130) //
  - printk выкинули бы, вот это был бы профит , pavlinux, 14-Июл-22, 00:17 (146) //
    - Я вообще в шоке А если партия даст миллиону китайцев задание отправить такие, n00by, 14-Июл-22, 17:38 (150)
Я посмотрел код, непонятная магия сравнения байта со словом, если кто может, объ, Непростое кино, 13-Июл-22, 22:38 (143) //
- Вот тут почитай https graphics stanford edu seander bithacks html ValueInWor, pavlinux, 13-Июл-22, 23:48 (145)
- На русском есть книга Генри С Уоррен мл Алгоритмические трюки для программист, n00by, 14-Июл-22, 17:53 (152)

Форумы | Темы | Пред. тема | След. тема

Партнёры:

Хостинг:

Закладки на сайте
Проследить за страницей

Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру