The OpenNET Project / Index page

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

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


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

Оглавление

Избавление ядра Linux от кода, меняющего поведение для процессов, начинающихся на символ X, opennews (??), 09-Ноя-22, (0) [смотреть все] –1

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


113. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +2 +/–
Сообщение от pavlinux (ok), 10-Ноя-22, 02:44 
> А потом понял Это же C. И там нету нормального сравнения строк типа current->comm == "Xorg".

Oткрою секрет, где есть "нормальное" сравнение строк, оно работает вот так:


int strcmp(const char *cs, const char *ct)
{
    unsigned char c1, c2;
    while (1) {
        c1 = *cs++;
        c2 = *ct++;
        if (c1 != c2)
            return c1 < c2 ? -1 : 1;
        if (!c1)
            break;
    }
    return 0;
}

И ТАК ВО ВСЕХ ЯЗЫКАХ НА ПЛАНЕТЕ!!!  Быстрее не придумали.

Исключение -  ассемблерные версии с побайтной загрузкой сравниваемых строк или
целыми словами при наличии SSE4.2 https://www.strchr.com/strcmp_and_strlen_using_sse_4.2

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

126. "Избавление ядра Linux от кода, меняющего поведение для проце..."  –2 +/–
Сообщение от mumu (ok), 10-Ноя-22, 09:51 
Я правильно понял, что linux kernel не использует simd, даже если у меня свежий дистр и проц?
Даже если я гинтушник и всё собираю с AVX2, ядро всё-равно будет побайтово сравнивать строки, как деды завещали? о_О
Ответить | Правка | Наверх | Cообщить модератору

134. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +1 +/–
Сообщение от InuYasha (??), 10-Ноя-22, 11:35 
Покажите SIMD для ускорения строк. Я заинтересовался.
Ответить | Правка | Наверх | Cообщить модератору

146. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +1 +/–
Сообщение от pavlinux (ok), 10-Ноя-22, 12:45 
> Покажите SIMD для ускорения строк. Я заинтересовался.

Выше нарисовал. SSE - это Streaming SIMD Extension, внезапно

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

143. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 10-Ноя-22, 12:33 
> Я правильно понял, что linux kernel не использует simd, даже если у меня свежий дистр и проц?

Для всего кода ядра именно так.

> Даже если я гинтушник и всё собираю с AVX2,

Основная задача ядра - правильно передать данные от тебя в железяки. Не надо там ничего шибко умного считать.

> ядро всё-равно будет побайтово сравнивать строки, как деды завещали? о_О

Но SIMD юзать можно!

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

FPU нельзя.

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

158. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от n00by (ok), 10-Ноя-22, 14:03 
> Даже если я гинтушник и всё собираю с AVX2, ядро всё-равно будет
> побайтово сравнивать строки, как деды завещали? о_О

Смотрите ссылку, что дал pavlinux выше.

kernel_fpu_begin();
...
kernel_fpu_end();

Вот это существенно дольше, чем сравнивать короткие строки. Оправданно в видеодрайвере, где большие объёмы.

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

129. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от n00by (ok), 10-Ноя-22, 10:50 
Ну 4 то байта можно привести к двойному слову (одевает каску, убегает от Свидетелей UB).
Ответить | Правка | К родителю #113 | Наверх | Cообщить модератору

131. "Избавление ядра Linux от кода, меняющего поведение для проце..."  –2 +/–
Сообщение от Аноним (-), 10-Ноя-22, 11:01 
Стоп-стоп, речь шла про НОРМАЛЬНОЕ сравнение строк.

Где первый шаг - это сравнить s1.len==s2.len и на этом все может закончиться за O(1).

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

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

145. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +2 +/–
Сообщение от pavlinux (ok), 10-Ноя-22, 12:40 
> Стоп-стоп, речь шла про НОРМАЛЬНОЕ сравнение строк.
> Где первый шаг - это сравнить s1.len==s2.len
> s1.len==s2.len

== это всего лишь оператор языка, компилятор "правильного языка" проверит
что аргументы строковые и вызовет strcmp() :)


> и на этом все может закончиться за O(1).

А как ты представляешь сравнение строк менее, чем за O(n) ?

O(1) будет с твоей точке зрения, для проца это регистровый CMP.
Так что, сложность превращается в O(n/x), где х толщина регистра, x >= 1
  


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

148. "Избавление ядра Linux от кода, меняющего поведение для проце..."  –2 +/–
Сообщение от n00by (ok), 10-Ноя-22, 13:03 
Если известна длина строки, может быть O(1).
Ответить | Правка | Наверх | Cообщить модератору

149. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 10-Ноя-22, 13:07 
> Если известна длина строки, может быть O(1).
> ---- Так что, сложность превращается в O(n/x), где х толщина регистра, x >= 1

Какой там AVX сейчас самый толстый? 256 бит? ... Ну вот, строку из 32 байт можно за раз.


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

cmp - 40 тактов,
jnz - 10

А какой-нибудь VPCMPUQ - 2500 тактов... и нахрен он нужен для сравнения "127.0.0.1" с "192.168.0.1"

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

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

153. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 10-Ноя-22, 13:17 
> Если длины различаются, содержимое не надо сравнивать.

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

И опять таки, ты не узнаешь размеры содержимого,
пока побайтово не проверишь strlen(), причем два раза. :D


Вот и думай, что выгоднее

char *A = 127.0.0.1";
char *B = "192.168.0.1";

if ( strlen(A) == strlen(B))
    strcmp(A, B);


иль просто загнать сразу в strcmp(A, B) и отошьёт при неравенстве.  


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

154. "Избавление ядра Linux от кода, меняющего поведение для проце..."  –2 +/–
Сообщение от n00by (ok), 10-Ноя-22, 13:20 
>> Если длины различаются, содержимое не надо сравнивать.
> Это уже алгоритмическая задача, а не вычислительная.

– Видите, Ватсон – перед вами типичный пример программиста.
– Почему Вы так решили, Холмс?
– Ну во-первых он очень долго думал над простым вопросом, во-вторых он ответил _АБСОЛЮТНО_ правильно, и в-третьих – нам от его ответа нет никакой пользы.

> И опять таки, ты не узнаешь размеры содержимого,
> пока побайтово не проверишь strlen(), причем два раза. :D

Я узнаю. У меня есть ядрёная std::string.

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

155. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 10-Ноя-22, 13:24 
> Я узнаю. У меня есть ядрёная std::string.

:)))

FORK(TO_BEER);
GOTO BEGIN   https://www.opennet.ru/openforum/vsluhforumID3/128887.html#113


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

156. "Избавление ядра Linux от кода, меняющего поведение для проце..."  –3 +/–
Сообщение от n00by (ok), 10-Ноя-22, 13:59 
>> Я узнаю. У меня есть ядрёная std::string.
> :)))
> FORK(TO_BEER);
> GOTO BEGIN   https://www.opennet.ru/openforum/vsluhforumID3/128887.html#113

Вообще-то стандарту там аналог strncmp(), а не требования вызывать Си библиотеку. operator!=() и operator==() возможно оптимизировать для различающихся длин.

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

157. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от Аноним (-), 10-Ноя-22, 14:01 
> ты не узнаешь размеры содержимого, пока побайтово не проверишь strlen()

Это верно только для поинтера на кусок null-terminated памяти.

Если бы строки были нормальные - которые знают свой размер - програмер бы спокойно вызвал сравнение с "X", понимая, что под капотом оно проверит и длину, и сравнит первый и единственный символ, и не пожрет производительность.

А не лепил бы такой баг, когда любой процесс начинающийся с Х удовлетворит условию...

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

237. "Избавление ядра Linux от кода, меняющего поведение для проце..."  –1 +/–
Сообщение от Аноним (-), 11-Ноя-22, 14:55 
Если тебе нефиг делать, можешь сделать struct, вот именно таким и пользоваться им наздоровье. Однако всякие системные вызовы операционки не в курсе этого счастья и при взаимодействии с ос ты познаешь все прелести конверсии.
Ответить | Правка | Наверх | Cообщить модератору

236. "Избавление ядра Linux от кода, меняющего поведение для проце..."  –1 +/–
Сообщение от Аноним (-), 11-Ноя-22, 14:54 
> char *A = 127.0.0.1";
> char *B = "192.168.0.1";
> if ( strlen(A) == strlen(B))
>     strcmp(A, B);

Совершенно неиллюстративный пример - оптимизатор может это все свернуть до одной вгрузки константы если повезет. Или даже нихрена, если это никак дальше не используется. Ну и сколько тактов вгрузка константы в регистр займет?

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

284. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 12-Ноя-22, 20:12 
>> char *A = "127.0.0.1";
>> char *B = "192.168.0.1";
>> if ( strlen(A) == strlen(B))
>>     strcmp(A, B);
> Совершенно неиллюстративный пример

Вместо "127.0.0.1" и  "192.168.0.1" должный быть строки неизвестной длины.
Но вы этот пример них.. не поняли, про динамич. размеры бесполезно.  

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

262. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от Аноним (262), 12-Ноя-22, 08:38 
Эта информация, без сомнения, ценна, но речь про нормальные строки, где strlen не нужен для вычисления размера. Например, про такие строки: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2...
Ответить | Правка | К родителю #153 | Наверх | Cообщить модератору

285. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 12-Ноя-22, 20:13 
> Эта информация, без сомнения, ценна, но речь про нормальные строки, где strlen
> не нужен для вычисления размера. Например, про такие строки: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2...

Причём тут С++ ??? ... ну ладно,  __lhs.size() == __rhs.size()  кто и как вычисляют?

...

template<typename _CharT, typename _Traits, typename _Alloc>
    _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
    inline bool
    operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    _GLIBCXX_NOEXCEPT
    {
      return __lhs.size() == __rhs.size()
           && !_Traits::compare(__lhs.data(), __rhs.data(), __lhs.size());
    }


Это пздц, это в мусор, хлама на 100500 лишних тактов.

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

184. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от Аноним (184), 10-Ноя-22, 22:50 
> Если длины различаются, содержимое не надо сравнивать.

Смотря для чего ты функцию делаешь. Если вдруг потребуется отсортировать массив строк по возрастанию/убыванию, то твоя "длина" даст неподходящие для большинства случаев результаты...

Для себя конечно можешь всё что угодно изобретать, но вот поведение strcmp определено стандартом чётко и там различают результаты >, == и < как раз по содержимому строк. Так что приходится сравнивать отдельные символы строки (если нужна реализация, соответствующая стандарту).

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

200. Скрыто модератором  +/–
Сообщение от n00by (ok), 11-Ноя-22, 08:29 
Ответить | Правка | Наверх | Cообщить модератору

172. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от Lex20email (ok), 10-Ноя-22, 15:07 
Фига у вас такты, никаких мегагерц не хватит
Ответить | Правка | К родителю #149 | Наверх | Cообщить модератору

231. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 11-Ноя-22, 14:12 
> Фига у вас такты, никаких мегагерц не хватит

А чо, SIMD очень прожорливые.

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

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

286. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 12-Ноя-22, 21:20 
> Ну так они чтобы зарядить большой кус и сжевать все оптом.

Ну вон живой пример... сравнение айпишников. в макс длине "111.222.333.444\0" 16 символов.
Даже пусть 1 лям коннектов/сек. strnsmp() или в SIMD пихать?

...

Если функционал позволяет... возможно собрать в матрицу 16x16 иль даже 16x32,
умножить на хитрожопую матрицу (траспонированую, эмиртову, ... забыл уже ),
кароч на выходе будет диагональная матрица с только "0" и "1",  ...

Опять же нужно считать, что быстрее трах с матричной алгеброй или 16 раз stcmp()      
  

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

289. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от n00by (ok), 13-Ноя-22, 09:10 
>> Ну так они чтобы зарядить большой кус и сжевать все оптом.
> Ну вон живой пример... сравнение айпишников. в макс длине "111.222.333.444\0" 16 символов.

Действительно в текстовом виде сравниваются? Где?

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

290. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от pavlinux (ok), 14-Ноя-22, 00:03 
> Где?

Где используется strcmp()? Везде.


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

291. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от n00by (ok), 14-Ноя-22, 07:37 
>> Где?
> Где используется strcmp()?

Зачем ты вырезал слово «АЙПИШНИКИ»? Лично ты их хранишь в текстовом виде и так сравниваешь?

> Везде.

Зачем ты врёшь? По _стандарту_ плюсов strcmp() не используется для сравнения строк. Да и в Си во многих случаях длина строки заранее известна (в частности, ограничена размером буфера). Ты для ядра только конфиги правил, я верно понимаю твои прошлые понты про коммиты?

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

190. "Избавление ядра Linux от кода, меняющего поведение для проце..."  +/–
Сообщение от Аноним (5), 11-Ноя-22, 06:01 
Все знают что строки это синтаксический сахар, а длину нужно вычислить только перебором всех символов за O(n) и никак иначе
Ответить | Правка | К родителю #131 | Наверх | Cообщить модератору

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

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




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

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