Здравствуйте, Sinclair, Вы писали:

S>·>Ансейф это возможность машинной проверки инвариантов, например, выход за границы массива или системы типов. Если ты используешь ансейф, то у тебя эта проверка пропадает. Скажем, ты решил написать unsafe quicksort, чтобы range check не мешался. Сделал "mid = (lo + hi) / 2" — поклялся на библии, что range check не нужен и... Оппа!
S>Вы как-то однобоко понимаете unsafe. Это во-первых.
S>Во-вторых, проверка никуда не пропадает. Вот в этом коде проверок границ массива ровно столько же, сколько и без unsafe:
А смысл unsafe в этом коде?

S>unsafe всего лишь разрешает использовать определённые конструкции, которые без unsafe запрещены.
Определённые это которые? Которые не safe?

S>·>Погоди... Оно же тоже юзермод. Мы вроде кернелмод vs юзермод сравниваем. Я верю, что можно сделать http-сервер быстрее nginx, но не верю, что для этого необходим кернелмод.
S>Ну так я и говорю — что по вашей ссылке изложена история, когда кернелмодный TUX проиграл юзермодному nginx, который ещё и не самый быстрый юзермодный http сервер.
S>Какие выводы мы должны из этого сделать?
S>По вашей ссылке делается вывод "кернел-мод перформансу не помогает". Я высказыаю гипотезу "кернел мода сама по себе перформанса не добавляет; ей надо уметь пользоваться".
А я высказываю гипотезу, что кернел мода не нужна для перформанса, по крайней мере в случае http. А с т.з. безопасности — её не надо использовать. И если винда не умеет перформанс без кернел-моды — ну её в топку.

S>>>В винде тоже. Там, где это оправдано.
S>·>Чем оправдывается http в кернелмоде?
S>Возможностью отдавать данные, не выходя в юзермод. Юзермодные драйвера пишут там, где всё равно присутствует переключение контекста — и чем больше работы мы выносим из кернелмоды в юзермод, тем больше мы получаем гибкости и надёжности.
И зачем нужна эта возможность?

S>>>Ну и что? Это же всё ортогонально кернелмодности драйвера. Вон, в линухах нашли в прошлом году уязвимость в libSSL.
S>·>Это меняет степень риска. Даже прав рута может быть недостаточно для того, чтобы установить хакнутый kernel module, если secure boot работает. Если через публичный, видимый всему интернету порт http можешь выполнять любой код с правами ядра — это совсем другая история.
S>Я недостаточно квалифицирован для конструктивного продолжения данной ветки. В любом случае в мир смотрит какой-то кернелмодный драйвер. Уберёте http.sys — найдут дыру в tcpip.sys, делов-то.
Дыры в tcpip не зависят от дыр в http. Уменьшается количество уязвимых узлов. Сравнивая две системы с "http + tcpip" и "tcpip" с т.з. безопасности — вторая очевидно лучше. Более того, tcp протокол таки попроще, чем http.

S>>>первое что нагуглилось.
S>·>Это практически неэксплуатируемо в реальном production-окружении. Это надо чтобы оно тянуло пекеджы без ssl и ещё и mitm суметь организовать. А вот как защитить 80-й порт веб-сервера?
S>Ну при этом по обоим CVE винды есть ровно 0 использований. То есть парни работают, дыры латают.
Обнадёживает. Гы.

S>·>Нет, важна не частота и "лишние" затраты, а общее влияние на производительность.
S>·>И memory footprint тоже сам по себе не обладает абсолютной ценностью. Тут же компромисс — удобный простой дешевый в разработке поддержании код vs цена планки памяти.
S>Совершенно верно. Поэтому нам важна возможность писать hi-performance код на "основном" языке, без перепрыгиваний между C#/C++/asm вставками, не переписывая при этом половину стандартной библиотеки, и не перемешивая "прикладной" код с кодом "фреймворка".
Может быть... Мне кажется на плюсах код писать проще, чем "не перепрыгивать".

S>·>А _насколько_ дорого? Ведь он скорее всего будет branch predicted и на фоне остальных полезных действий в итоге затеряется. Это должно очень не повезти с задачей, чтобы эффект range check был больше десятка процентов. Зато avx позволяет ускорять в разы.
S>Ну вот на моём CPU почему-то branch prediction нихрена не помогает. Код C4-фильтрации 2d массива интов при убирании проверок границ ускоряется примерно в 2.7 раза; а вот добавление avx не помогает.
S>Не исключаю, что я его просто не сумел правильно приготовить — так и не дошли руки подключиться и посмотреть реальный ассемблер, который там генерируется.
Хм. Странно. Мне интуиция подсказывает, что там в чём-то ещё проблема была... не может один условный jump замедлять настолько. Т.е. выходит, что одна доп машинная инструкция работает в несколько раз медленнее всех остальных инструкций полезных вычислений.

S>·>Да, современные jvm умеют сворачивать код в avx512, правда плохо и слабо предсказуемо. И, уверен, при достаточном опыте и удаче можно сделать json-парсер, использующий такие оптимизации.
S>Ну, либо пойти в дотнет, и нарулить код на Vector<byte>
Ну наруливать спец-код вручную — скучно... и не факт, что выйдет хоть в чём-то лучше плюсов или ещё чего.

Здравствуйте, ·, Вы писали:

·>А смысл unsafe в этом коде?
Никакого. Но у меня с телепатией туго, я не понимаю, какой код вы имеете в виду при фразе "Сделал "mid = (lo + hi) / 2" — поклялся на библии, что range check не нужен и... Оппа!".
Может быть, вы напишете пример кода, иллюстрирующего ваш ход мысли?

S>>unsafe всего лишь разрешает использовать определённые конструкции, которые без unsafe запрещены.
·>Определённые это которые? Которые не safe?
все манипуляции с указателями, плюс декларации fixed-size buffers в структурах.

·>А я высказываю гипотезу, что кернел мода не нужна для перформанса, по крайней мере в случае http. А с т.з. безопасности — её не надо использовать. И если винда не умеет перформанс без кернел-моды — ну её в топку.
Ну, для точного ответа нам нужно честное сравнение IIS под виндой с nxweb под линуксом, на том же железе.

·>И зачем нужна эта возможность?
Для производительности.

·>Дыры в tcpip не зависят от дыр в http. Уменьшается количество уязвимых узлов. Сравнивая две системы с "http + tcpip" и "tcpip" с т.з. безопасности — вторая очевидно лучше. Более того, tcp протокол таки попроще, чем http.


S>>·>Это практически неэксплуатируемо в реальном production-окружении. Это надо чтобы оно тянуло пекеджы без ssl и ещё и mitm суметь организовать. А вот как защитить 80-й порт веб-сервера?
S>>Ну при этом по обоим CVE винды есть ровно 0 использований. То есть парни работают, дыры латают.
·>Обнадёживает. Гы.
Не меньше, чем ваше рассуждения о практической неэксплуатируемости.

·>Может быть... Мне кажется на плюсах код писать проще, чем "не перепрыгивать".
С точки зрения тулчейна — сложнее.

·>Хм. Странно. Мне интуиция подсказывает, что там в чём-то ещё проблема была... не может один условный jump замедлять настолько. Т.е. выходит, что одна доп машинная инструкция работает в несколько раз медленнее всех остальных инструкций полезных вычислений.
Для 2D там не один условный jump, а четыре проверки.

·>Ну наруливать спец-код вручную — скучно... и не факт, что выйдет хоть в чём-то лучше плюсов или ещё чего.
Ну, быть не хуже плюсов — уже достижение.
Резервы по тому, чтобы быть лучше плюсов, могут быть только в runtime codegeneration. Плюсы ограничены тем, что надо заранее компилировать весь код. Там, конечно, умельцы уже освоили всяких трюков типа динамического выбора уместной реализации при загрузке библиотеки, и прочего; но порождение кода на ходу в управляемых средах всё ещё остаётся невыносимо более лёгким.
По большому счёту, это всё упирается в идеи частичной компиляции ещё времён Ершова. Берём общий алгоритм, параметризованный чем-то; специализируем его под данные значения параметров (неважно там — разрядность регистров, или ядро фильтра, или количество измерений; или кодировка строк), оптимизируем пожёстче, а потом гоняем оптимальную версию вплоть до изменения параметров.

Здравствуйте, ·, Вы писали:

V>>Например, часто массивы используются как indexed map, в этом смысле "уплотнение" по ссылке, скорее всего, всё ухудшит в сравнении с исходной последовательностью создания объектов при наполнении такого массива.
·>map обычно означает hash-table. Т.е. тот же массив, который можно бы и уплотнить, например, после рехаша.

Тут я согласен с vdimas@ — map это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.
А дальше вопрос в стиле отображения и том, как этот стиль называется в конкретном языке.
В C++ почему-то map это то, что в Java — NavigableMap, то есть в нём есть движения вперёд-назад от конкретного ключа. Зато в Java явно назвали HashMap то, что в C++ названо более правильно — unordered_map.

Насколько его уплотнять — вопрос цели. Например, сейчас есть реализации navigable map в памяти как B-дерево. (Ну, B⁺, если существенно отличие.)
Там естественным образом получается компактность хранения соседних ключей.
Но со структурой хранения, как в Java до введения value types, тебе просто нечем подсказать, какие данные и почему ты рекомендуешь системе хранить рядом.
Кстати, почему бы не ввести на это какие-то специальные аннотации/атрибуты в дополнение к values types? Тут концепция, конечно, родится не сразу, но шансы лет за 10 довести до ума — вполне есть.

Здравствуйте, Sinclair, Вы писали:

S>·>А смысл unsafe в этом коде?
S>Никакого. Но у меня с телепатией туго, я не понимаю, какой код вы имеете в виду при фразе "Сделал "mid = (lo + hi) / 2" — поклялся на библии, что range check не нужен и... Оппа!".
S>Может быть, вы напишете пример кода, иллюстрирующего ваш ход мысли?
Ход мысли в том, что safe код даёт гарантии, даже если есть логическая ошибка. Если мы используем unsafe, то мы можем лишь надеяться, что ошибок нет и код работает как ожидается. В пример я привёл классическую граблю, когда pivot в qsort считается как (lo+hi)/2 и приводит к out of range. Пример кода — лень писать. Просто представь себе обычный qsort на fixed-указателе и считай pivot по этой формуле.

S>>>unsafe всего лишь разрешает использовать определённые конструкции, которые без unsafe запрещены.
S>·>Определённые это которые? Которые не safe?
S>все манипуляции с указателями, плюс декларации fixed-size buffers в структурах.
А что будет в случае fixed (int* pdata = data) pdata[-5] = 42?

S>·>А я высказываю гипотезу, что кернел мода не нужна для перформанса, по крайней мере в случае http. А с т.з. безопасности — её не надо использовать. И если винда не умеет перформанс без кернел-моды — ну её в топку.
S>Ну, для точного ответа нам нужно честное сравнение IIS под виндой с nxweb под линуксом, на том же железе.
Судя по той статье tux обходил http.sys. А x-15 работал как tux. Или думаешь это было нечестное сравнение?

S>·>И зачем нужна эта возможность?
S>Для производительности.
Вроде как доказали для линуха, что для производительности это не требуется.

S>>>·>Это практически неэксплуатируемо в реальном production-окружении. Это надо чтобы оно тянуло пекеджы без ssl и ещё и mitm суметь организовать. А вот как защитить 80-й порт веб-сервера?
S>>>Ну при этом по обоим CVE винды есть ровно 0 использований. То есть парни работают, дыры латают.
S>·>Обнадёживает. Гы.
S>Не меньше, чем ваше рассуждения о практической неэксплуатируемости.
Ну как сказать. Разворачиваение системы майтенанса и администрирования это одно. А когда проблема в самом сервисе, собственно для которого всё и затевается — это другое.

S>·>Может быть... Мне кажется на плюсах код писать проще, чем "не перепрыгивать".
S>С точки зрения тулчейна — сложнее.
Если тулчейн кто-то для тебя уже сделал, то да, но с точки зрения общей картины — совсем нет. Вот если завтра выпустят какой-нибудь процессор с avx100500 — он сразу же будет доступен из intel compiler и можно его сразу использовать на полную из натива. А когда он дойдёт до jit или даже Vector<byte>... Сколько надо тулов перечейнить?

S>Для 2D там не один условный jump, а четыре проверки.
А, ну может быть.

S>·>Ну наруливать спец-код вручную — скучно... и не факт, что выйдет хоть в чём-то лучше плюсов или ещё чего.
S>Ну, быть не хуже плюсов — уже достижение.
S>Резервы по тому, чтобы быть лучше плюсов, могут быть только в runtime codegeneration. Плюсы ограничены тем, что надо заранее компилировать весь код. Там, конечно, умельцы уже освоили всяких трюков типа динамического выбора уместной реализации при загрузке библиотеки, и прочего; но порождение кода на ходу в управляемых средах всё ещё остаётся невыносимо более лёгким.
S>По большому счёту, это всё упирается в идеи частичной компиляции ещё времён Ершова. Берём общий алгоритм, параметризованный чем-то; специализируем его под данные значения параметров (неважно там — разрядность регистров, или ядро фильтра, или количество измерений; или кодировка строк), оптимизируем пожёстче, а потом гоняем оптимальную версию вплоть до изменения параметров.
Вот этим JIT и занимается собственно. Ты просто упомянул Vector<byte>, он, как я понял, просто генерит соответсвующие simd-конструкции. Или оно тоже как-то что-то оптимизировать может?

Здравствуйте, netch80, Вы писали:

V>>>Например, часто массивы используются как indexed map, в этом смысле "уплотнение" по ссылке, скорее всего, всё ухудшит в сравнении с исходной последовательностью создания объектов при наполнении такого массива.
N>·>map обычно означает hash-table. Т.е. тот же массив, который можно бы и уплотнить, например, после рехаша.
N>Тут я согласен с vdimas@ — map это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.
А я с ним и не спорил по этому поводу, я лишь пытался выяснить накой это он всё рассказывает. Разговор начался с того, что gc умеет компактификацию, т.е. перемещение связанных данных более компактно, что может дать преимущество в производительности. И это работает для массивов, которые лежат в основе многих структур данных, в т.ч. hash-tables. Т.е. по сути без каких-либо усилий со стороны программиста можно иметь более оптимальное расположение данных в памяти благодаря gc. Тут vdimas начал рассказывать про sso и всякие разные хитрые виды map — накой — непонятно. Ну да, лом японской бензопилой пилить не стоит, спорить не буду, но и всегда вручную топорами рубить — тоже так себе идейка.

N>А дальше вопрос в стиле отображения и том, как этот стиль называется в конкретном языке.
N>В C++ почему-то map это то, что в Java — NavigableMap, то есть в нём есть движения вперёд-назад от конкретного ключа. Зато в Java явно назвали HashMap то, что в C++ названо более правильно — unordered_map.
Ты немного напутал и потому запутался. Сишный std::map это TreeMap. А NavigableMap это интерфейс, у которого есть две реализации — TreeMap и ConcurrentSkipListMap (в jdk, а так — имплементаций гораздо больше ясен пень). А ещё есть Map, внезапно как ты хочешь "это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.".
В Java интерфейсы определяют контракт, т.е. что класс умеет, а классы — как этот map реализован вунутре. В принципе терминология java более информативна и точна. В отличие от map и unordered_map — вообще ноль информации.

N>Насколько его уплотнять — вопрос цели. Например, сейчас есть реализации navigable map в памяти как B-дерево. (Ну, B⁺, если существенно отличие.)
N>Там естественным образом получается компактность хранения соседних ключей.
N>Но со структурой хранения, как в Java до введения value types, тебе просто нечем подсказать, какие данные и почему ты рекомендуешь системе хранить рядом.
Всегда можно топорами порубить.

N>Кстати, почему бы не ввести на это какие-то специальные аннотации/атрибуты в дополнение к values types? Тут концепция, конечно, родится не сразу, но шансы лет за 10 довести до ума — вполне есть.
Тут дело в целесообразности. В большинстве случаев на java можно запилить какую-угодно структуру данных, которая будет располагать данные как тебе хочется без всей этой магии. Value types могут улучшить читабельность и структуру кода, но и собственно всё, производительности сами по себе они не добавят. А собственно главная цель value types вроде как улучшать производительность.
Притом, я например, уже упоминал, value types закрывают лишь один подход организации расположения данных — array of structures, и не помогут при реализации structure of arrays. Т.е. тоже не универсальный всемогутер, а очередной синтаксический сахарок по сути, не более.

Здравствуйте, ·, Вы писали:

N>>·>map обычно означает hash-table. Т.е. тот же массив, который можно бы и уплотнить, например, после рехаша.
N>>Тут я согласен с vdimas@ — map это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.
·>А я с ним и не спорил по этому поводу, я лишь пытался выяснить накой это он всё рассказывает. Разговор начался с того, что gc умеет компактификацию, т.е. перемещение связанных данных более компактно, что может дать преимущество в производительности. И это работает для массивов, которые лежат в основе многих структур данных, в т.ч. hash-tables. Т.е. по сути без каких-либо усилий со стороны программиста можно иметь более оптимальное расположение данных в памяти благодаря gc. Тут vdimas начал рассказывать про sso и всякие разные хитрые виды map — накой — непонятно. Ну да, лом японской бензопилой пилить не стоит, спорить не буду, но и всегда вручную топорами рубить — тоже так себе идейка.

Скорее его вопрос в таком своеобразном стиле был, как именно в случае этих таблиц можно объяснить тому GC, что надо группировать именно как-то связанные ключи (и потому их размещение рядом имеет смысл для temporal locality). И я считаю нужным тоже поддержать этот вопрос.
Как именно оно решает, какие ключи будут друг с другом так связаны? Как это проецируется на размещение объектов в памяти, если ключи, как типично в Java, являются ссылками?
Что важнее — соседство ключей друг с другом или соседство ключей со значениями?
И так далее.

N>>А дальше вопрос в стиле отображения и том, как этот стиль называется в конкретном языке.
N>>В C++ почему-то map это то, что в Java — NavigableMap, то есть в нём есть движения вперёд-назад от конкретного ключа. Зато в Java явно назвали HashMap то, что в C++ названо более правильно — unordered_map.
·>Ты немного напутал и потому запутался. Сишный std::map это TreeMap.

Нет. У сишного std::map нет никакого жёсткого требования делать именно деревом. То, что большинство реализаций так сделало — это особенность текущей алгоритмической базы. Стандарт требует только функциональность и гарантии скорости.
Я принимаю упрёк, что NavigableMap — это интерфейс, а std::map — реализация, но не привязку к TreeMap.

·> А NavigableMap это интерфейс, у которого есть две реализации — TreeMap и ConcurrentSkipListMap (в jdk, а так — имплементаций гораздо больше ясен пень). А ещё есть Map, внезапно как ты хочешь "это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.".

Да, именно, Map не предполагает порядка между ключами.
И это ещё один камешек в твою сторону. Если этого порядка нет, как мы будем его вводить и почему?

N>>Но со структурой хранения, как в Java до введения value types, тебе просто нечем подсказать, какие данные и почему ты рекомендуешь системе хранить рядом.
·>Всегда можно топорами порубить.

Я эту реплику совсем не понял.

N>>Кстати, почему бы не ввести на это какие-то специальные аннотации/атрибуты в дополнение к values types? Тут концепция, конечно, родится не сразу, но шансы лет за 10 довести до ума — вполне есть.
·>Тут дело в целесообразности. В большинстве случаев на java можно запилить какую-угодно структуру данных, которая будет располагать данные как тебе хочется без всей этой магии. Value types могут улучшить читабельность и структуру кода, но и собственно всё, производительности сами по себе они не добавят. А собственно главная цель value types вроде как улучшать производительность.
·>Притом, я например, уже упоминал, value types закрывают лишь один подход организации расположения данных — array of structures, и не помогут при реализации structure of arrays. Т.е. тоже не универсальный всемогутер, а очередной синтаксический сахарок по сути, не более.

Structure of arrays обычно в разы менее важно оптимизировать, чем array of structures, по крайней мере с современной спецификой кэшей — позиции с одним индексом и так заметно разделены.
Универсальных всемогуторов не предвидится, но оптимизировать важные частные случаи — надо.

Здравствуйте, netch80, Вы писали:

N>>>Тут я согласен с vdimas@ — map это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.
N>·>А я с ним и не спорил по этому поводу, я лишь пытался выяснить накой это он всё рассказывает. Разговор начался с того, что gc умеет компактификацию, т.е. перемещение связанных данных более компактно, что может дать преимущество в производительности. И это работает для массивов, которые лежат в основе многих структур данных, в т.ч. hash-tables. Т.е. по сути без каких-либо усилий со стороны программиста можно иметь более оптимальное расположение данных в памяти благодаря gc. Тут vdimas начал рассказывать про sso и всякие разные хитрые виды map — накой — непонятно. Ну да, лом японской бензопилой пилить не стоит, спорить не буду, но и всегда вручную топорами рубить — тоже так себе идейка.
N>Скорее его вопрос в таком своеобразном стиле был, как именно в случае этих таблиц можно объяснить тому GC, что надо группировать именно как-то связанные ключи (и потому их размещение рядом имеет смысл для temporal locality). И я считаю нужным тоже поддержать этот вопрос.
N>Как именно оно решает, какие ключи будут друг с другом так связаны? Как это проецируется на размещение объектов в памяти, если ключи, как типично в Java, являются ссылками?
Этот вопрос уже был отвечен много раз. Судя по той статье "laid out in memory in array order", т.е. в том порядке как распологаются ссылки в Object[]. Какие конкретно ещё есть оптимизации — я точно не знаю. И это не имеет вообще никакого отношения к "map это отображение в общем смысле".

N>Что важнее — соседство ключей друг с другом или соседство ключей со значениями?
N>И так далее.
Собственно это уже вообще непонятные вопросы. Это зависит от устройства конкретной структуры данных. Например, он упомянул реализацию map поверх массивов. Тут можно сделать два вида реализации
class {Object []keys; Object []vals;} или class {Object []keyValuePairs;} и используя знание о "array order" выбирать соответствующую реализацию в зависимости от юзкейсов.

N>>>А дальше вопрос в стиле отображения и том, как этот стиль называется в конкретном языке.
N>>>В C++ почему-то map это то, что в Java — NavigableMap, то есть в нём есть движения вперёд-назад от конкретного ключа. Зато в Java явно назвали HashMap то, что в C++ названо более правильно — unordered_map.
N>·>Ты немного напутал и потому запутался. Сишный std::map это TreeMap.
N>Нет. У сишного std::map нет никакого жёсткого требования делать именно деревом. То, что большинство реализаций так сделало — это особенность текущей алгоритмической базы. Стандарт требует только функциональность и гарантии скорости.
Интересно, какие ещё реализации могут подойти с такими требованиями? Прям получается как знаменитое "любого цвета если он черный". И очень далеко от "отображение в общем смысле".

N>Я принимаю упрёк, что NavigableMap — это интерфейс, а std::map — реализация, но не привязку к TreeMap.
Что значит "привязку"?

N>·> А NavigableMap это интерфейс, у которого есть две реализации — TreeMap и ConcurrentSkipListMap (в jdk, а так — имплементаций гораздо больше ясен пень). А ещё есть Map, внезапно как ты хочешь "это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.".
N>Да, именно, Map не предполагает порядка между ключами.
N>И это ещё один камешек в твою сторону. Если этого порядка нет, как мы будем его вводить и почему?
Ээээ. Map это интерфейс. Как его реализуешь, так и будет упорядочено.

N>>>Но со структурой хранения, как в Java до введения value types, тебе просто нечем подсказать, какие данные и почему ты рекомендуешь системе хранить рядом.
N>·>Всегда можно топорами порубить.
N>Я эту реплику совсем не понял.
Ну я имел в виду, что можно вручную запилить как надо, _если_ нам надо бороться за производительность.

N>·>Тут дело в целесообразности. В большинстве случаев на java можно запилить какую-угодно структуру данных, которая будет располагать данные как тебе хочется без всей этой магии. Value types могут улучшить читабельность и структуру кода, но и собственно всё, производительности сами по себе они не добавят. А собственно главная цель value types вроде как улучшать производительность.
N>·>Притом, я например, уже упоминал, value types закрывают лишь один подход организации расположения данных — array of structures, и не помогут при реализации structure of arrays. Т.е. тоже не универсальный всемогутер, а очередной синтаксический сахарок по сути, не более.
N>Structure of arrays обычно в разы менее важно оптимизировать, чем array of structures, по крайней мере с современной спецификой кэшей — позиции с одним индексом и так заметно разделены.
N>Универсальных всемогуторов не предвидится, но оптимизировать важные частные случаи — надо.
Все случаи важные, но некоторые важнее... и тут начнётся флейм, а кому именно важные?

Здравствуйте, ·, Вы писали:
·>Ход мысли в том, что safe код даёт гарантии, даже если есть логическая ошибка. Если мы используем unsafe, то мы можем лишь надеяться, что ошибок нет и код работает как ожидается. В пример я привёл классическую граблю, когда pivot в qsort считается как (lo+hi)/2 и приводит к out of range. Пример кода — лень писать. Просто представь себе обычный qsort на fixed-указателе и считай pivot по этой формуле.
Ясно. Да, в идеале хотелось бы иметь qsort, который одновременно быстрый и с гарантиями IndexOutOfRange вместо прохода по памяти в случае логической ошибки.
С другой стороны, объём unsafe кода у нас достаточно маленький для того, чтобы отверифицировать его вручную.

S>>все манипуляции с указателями, плюс декларации fixed-size buffers в структурах.
·>А что будет в случае fixed (int* pdata = data) pdata[-5] = 42?
Ничего хорошего не будет.

·>Судя по той статье tux обходил http.sys. А x-15 работал как tux. Или думаешь это было нечестное сравнение?
Не увидел сравнения tux с http.sys. О какой статье идёт речь?

S>>Для производительности.
·>Вроде как доказали для линуха, что для производительности это не требуется.
Нет. Всё, что доказали для линуха — что в нём отдельно взятый кернелмодный сервер проиграл другому отдельно взятому юзерспейс серверу.
Это может означать всё что угодно. Помимо вашей гипотезы есть ещё минимум два варианта, не противоречащих сделанным наблюдениям:
— кернелмодный TUX был плохо написан. Изначально он выиграл у сравнительно плохо написанного апача благодаря кернел моде, но потом юзермодные альтернативы продолжили развиваться, а TUX так и застрял в 2000. То есть, переписав TUX c учётом опыта, накопленного в nginx/nxweb, мы получим ещё большее быстродействие
— архитектура линукса сама по себе такова, что в ней кернел-мода тормозит сильнее, чем в винде.
·>Ну как сказать. Разворачиваение системы майтенанса и администрирования это одно. А когда проблема в самом сервисе, собственно для которого всё и затевается — это другое.
А вы уверены, что это — единственная дыра с рутовым RCE в линуксе? SSL вот помнится был дыряв сверху донизу.

·>Если тулчейн кто-то для тебя уже сделал, то да, но с точки зрения общей картины — совсем нет. Вот если завтра выпустят какой-нибудь процессор с avx100500 — он сразу же будет доступен из intel compiler и можно его сразу использовать на полную из натива. А когда он дойдёт до jit или даже Vector<byte>... Сколько надо тулов перечейнить?
Собственно JIT и System.Numerics. С учётом нынешних темпов развития Net.Core этот тулчейн скорее всего доедет до вас быстрее, чем коммерческая доступность упомянутого процессора.

S>>По большому счёту, это всё упирается в идеи частичной компиляции ещё времён Ершова. Берём общий алгоритм, параметризованный чем-то; специализируем его под данные значения параметров (неважно там — разрядность регистров, или ядро фильтра, или количество измерений; или кодировка строк), оптимизируем пожёстче, а потом гоняем оптимальную версию вплоть до изменения параметров.
·>Вот этим JIT и занимается собственно. Ты просто упомянул Vector<byte>, он, как я понял, просто генерит соответсвующие simd-конструкции. Или оно тоже как-то что-то оптимизировать может?
В дотнете JIT SSE/AVX не занимается, увы. Всё именно так, как вы поняли — арифметика над Vector<T> порождает либо simd-конструкции интринсиками, либо фолбэкается на честный управляемый код с циклами (который ещё и медленнее ручных операций с массивами T)

Здравствуйте, Sinclair, Вы писали:

S>·>Ход мысли в том, что safe код даёт гарантии, даже если есть логическая ошибка. Если мы используем unsafe, то мы можем лишь надеяться, что ошибок нет и код работает как ожидается. В пример я привёл классическую граблю, когда pivot в qsort считается как (lo+hi)/2 и приводит к out of range. Пример кода — лень писать. Просто представь себе обычный qsort на fixed-указателе и считай pivot по этой формуле.
S>Ясно. Да, в идеале хотелось бы иметь qsort, который одновременно быстрый и с гарантиями IndexOutOfRange вместо прохода по памяти в случае логической ошибки.
S>С другой стороны, объём unsafe кода у нас достаточно маленький для того, чтобы отверифицировать его вручную.
Хых. Простенькая сортировка всего строк ~400... Не уверен насколько такое практично верифицировать. Больше пользы принесёт улучшение jit.

S>>>все манипуляции с указателями, плюс декларации fixed-size buffers в структурах.
S>·>А что будет в случае fixed (int* pdata = data) pdata[-5] = 42?
S>Ничего хорошего не будет.
Т.е. не "все манипуляции с указателями"?

S>·>Судя по той статье tux обходил http.sys. А x-15 работал как tux. Или думаешь это было нечестное сравнение?
S>Не увидел сравнения tux с http.sys. О какой статье идёт речь?
"IIS / NT outperforming Apache / Linux 2.2 at web serving [как выяснилось благодаря in-kernel accelerator], Ingo Molnar leveraged the wide-ranging scalability improvements in the Linux 2.4 kernel to create the TUX in-kernel HTTP accelerator, which crushed everything that existed at that time"
"The initial Windows in-kernel accelerator, http.sys, appeared later, in IIS 6.0 / Windows 2003"
Но тут логически остаётся возможность, что http.sys сделали ещё быстрее, чем оригинальный kernel http accelerator.

Любопытно почему сейчас бенчмарков нет.

S>>>Для производительности.
S>·>Вроде как доказали для линуха, что для производительности это не требуется.
S>Нет. Всё, что доказали для линуха — что в нём отдельно взятый кернелмодный сервер проиграл другому отдельно взятому юзерспейс серверу.
S>Это может означать всё что угодно. Помимо вашей гипотезы есть ещё минимум два варианта, не противоречащих сделанным наблюдениям:
S>- кернелмодный TUX был плохо написан. Изначально он выиграл у сравнительно плохо написанного апача благодаря кернел моде, но потом юзермодные альтернативы продолжили развиваться, а TUX так и застрял в 2000. То есть, переписав TUX c учётом опыта, накопленного в nginx/nxweb, мы получим ещё большее быстродействие
Это вряд ли. Мало того, был ещё khttpd и хрен знает ещё что от всяких солярисов.

S>- архитектура линукса сама по себе такова, что в ней кернел-мода тормозит сильнее, чем в винде.
Да, такое теоретически возможно.

S>·>Ну как сказать. Разворачиваение системы майтенанса и администрирования это одно. А когда проблема в самом сервисе, собственно для которого всё и затевается — это другое.
S>А вы уверены, что это — единственная дыра с рутовым RCE в линуксе?
Мне удалось найти ещё CVE-2016-10229 — что-то в udp с каким-то особым флагом... Тоже экзотика, по-моему. Собственно всё.

S>SSL вот помнится был дыряв сверху донизу.
ssl вроде как не под рутом работает обычно. Неясно как можно получить kernel rce.

S>·>Если тулчейн кто-то для тебя уже сделал, то да, но с точки зрения общей картины — совсем нет. Вот если завтра выпустят какой-нибудь процессор с avx100500 — он сразу же будет доступен из intel compiler и можно его сразу использовать на полную из натива. А когда он дойдёт до jit или даже Vector<byte>... Сколько надо тулов перечейнить?
S>Собственно JIT и System.Numerics. С учётом нынешних темпов развития Net.Core этот тулчейн скорее всего доедет до вас быстрее, чем коммерческая доступность упомянутого процессора.
intel вроде выпускает свой тулчейн и потом по нему уже клепают другие. Но в любом случае, это всё с боку примочки. Такие и для jvm есть.

Здравствуйте, ·, Вы писали:
·>Хых. Простенькая сортировка всего строк ~400... Не уверен насколько такое практично верифицировать. Больше пользы принесёт улучшение jit.
Ну,это если он устранит все проверки диапазонов в квиксорте.

S>>Ничего хорошего не будет.
·>Т.е. не "все манипуляции с указателями"?
Я потерял нить вопроса.

S>>·>Судя по той статье tux обходил http.sys. А x-15 работал как tux. Или думаешь это было нечестное сравнение?
S>>Не увидел сравнения tux с http.sys. О какой статье идёт речь?
·>"IIS / NT outperforming Apache / Linux 2.2 at web serving [как выяснилось благодаря in-kernel accelerator], Ingo Molnar leveraged the wide-ranging scalability improvements in the Linux 2.4 kernel to create the TUX in-kernel HTTP accelerator, which crushed everything that existed at that time"
·>"The initial Windows in-kernel accelerator, http.sys, appeared later, in IIS 6.0 / Windows 2003"
·>Но тут логически остаётся возможность, что http.sys сделали ещё быстрее, чем оригинальный kernel http accelerator.
Естественно. Оригинальный апач проигрывал даже убогому IIS 5.0. TUX его гордо зааутперформил.
http.sys вышел три года спустя. Я бы лично удивился, если бы при его разработке пацаны из Редмонда ни разу не посмотрели на TUX. Скорее всего, именно он-то и подвиг их копать в эту сторону.
·>Любопытно почему сейчас бенчмарков нет.
Вот и мне любопытно.

S>>·>Ну как сказать. Разворачиваение системы майтенанса и администрирования это одно. А когда проблема в самом сервисе, собственно для которого всё и затевается — это другое.
S>>А вы уверены, что это — единственная дыра с рутовым RCE в линуксе?
·>Мне удалось найти ещё CVE-2016-10229 — что-то в udp с каким-то особым флагом... Тоже экзотика, по-моему. Собственно всё.
CVE-2017-7494


S>>SSL вот помнится был дыряв сверху донизу.
·>ssl вроде как не под рутом работает обычно. Неясно как можно получить kernel rce.
Спецы пишут что можно.


S>>Собственно JIT и System.Numerics. С учётом нынешних темпов развития Net.Core этот тулчейн скорее всего доедет до вас быстрее, чем коммерческая доступность упомянутого процессора.
·>intel вроде выпускает свой тулчейн и потом по нему уже клепают другие. Но в любом случае, это всё с боку примочки. Такие и для jvm есть.
Интел клепает свой тулчейн к выходу процессора. Но если свежевышедший процессор заказать в РФ — через сколько он приедет? То-то и оно: коммит в гитхаб приезжает всяко быстрее.

Здравствуйте, ·, Вы писали:

_>>Свой вариант — это совсем не то. Там помимо того, что это надо самим писать, ещё и не передашь его ни в какие функции, требующие string. Старый вариант тем и был хорош, что по сути было доступно два поведение одного и того же класса. Лучше этого только вариант из плюсов, в котором для этих целей две отдельные сущности (и при этом весь остальной код (включая и сторонние библиотеки) рассчитан принимать и ту и другую).
·>Ты просто воспринимаешь String как универсальный всемогутер. Это класс общего назначения, применяемый много для чего самой jdk. И с практической точки зрения гораздо выгоднее когда он работает, пусть даже чуть медленнее (ты кстати, это ещё никак не доказал), чем падает с ООМ. Те места, где поведение такого класса вызывает проблемы с производительностью — всегда можно найти и подпилить. С практической точки зрения гораздо выгоднее и безопаснее ускорять работающую программу, чем чинить падующую.

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

Так что обсуждаемое изменение реализации служит исключительно для возможности использования более слабых программистов, в ущерб и быстродействию и расходу памяти. И да, это полностью укладывается изначальную идеологию Java, так что в каком-то смысле изменение полностью логично.

_>>Единственная возможная проблема от такой схемы — пожелание наличия мозга у программиста... Но да, похоже в некоторых областях индустрии это действительно проблема. )))
·>Не пожелание мозга, а необходимость на пустом месте напрягать мозги.

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

·>Ты не учитываешь много нюансов. Например, такие подстроки могут переползать между тредами убегая из TLAB, начать удерживать куски памяти слишком долго и всё это дело уползёт в медленный Old Generation. А если ещё вспомнить какие-нибудь нежданчики типа копирования между numa и прочая locality... В итоге, в одном месте вроде как заоптимизировали, зато потом это вылилось в тормоза в другом месте. В итоге сумма оказалась отрицательной. Ты как первый раз...

Ещё раз повторюсь: ссылки естественно не всегда более правильный путь, однако в старой схеме можно было использовать И копирование И ссылки.

_>>·>И чтобы было совсем интересно — придумай так, чтобы оно не фиксилось таким же тривиальным образом.
_>>Как ты себе представляешь "пофиксить" время, затрачиваемое на ненужное копирование строк? )
·>Убрать ненужное копирование строк, например. Или использовать StringBuilder.

Нуу ты покажи непосредственно код. Вот предложим, что мне надо получить подстроку некой нашей тестовой строки, начиная с 5-го символа и до конца. И полученный результат передать в некую другую функцию-парсер (принимающую string). При старой схеме я мог сделать это и через копирование (с затратой лишней памяти и процессорных циклов) и через ссылку. А как при новой схеме сделать это без копирования?

_>>>>В смысле зачем? Это в одну строчку убирает описываемую тобой проблему (с удержанием в памяти гигантского куска текста из-за пары букв). Ну а то, что это надо указывать руками, а не по дефолту — так это цена за возможность использования ещё и ссылок.
_>>·>Поговорка есть такая. Умный находит решение проблемы, мудрый — проблему не создаёт.
_>>В принципе если продолжить эту мысль, то и сами Java/C# не нужны в принципе, т.к. есть например Питон. )
·>Ы?

Питон ещё более удобен, ценой ещё большего провала в производительности. Непонятно зачем ограничиваться полумерами, если уж идти по этому пути.

Кстати, лично я активно использую Питон, но не для всех целей...

_>>·>Ты как маленький... Никогда не встречался на практике, когда O(много) работает лучше O(мало)?
_>>Да, такое вполне реально во многих случаях при малых значениях N. Поэтому в правильных тестах контейнеров и т.п. всегда приводят набор результатов для разных N.
·>Хорошо, но уже лучше. Теперь если подумать, действительно ли это хорошя идея иметь String для больших значений N? Ведь даже в Плюсах ты задумаешься о вменяемости такого кода, скорее всего возьмёшь std::vector или типа того.

Я же уже написал, что для данного конкретного случая O(1) — это всего лишь копирования одного указателя и двух целочисленных значений, так что будет быстрее считай что при любых строках, даже самых маленьких.

_>>Однако в обсуждаемом нами случае, это очевидно не актуально, т.к. копирование одного указателя и двух целочисленных значений очевидно всегда будет быстрее чем выделение нового буфера под строку и посимвольного копирования в него изначальной строки.
·>Стронгли белив. Кстати, буферы копируются не посимвольно.

Даже если там работа через AVX512, то это всё равно будет O(N). )))

_>>Безусловно. Но в мире Java изначально (ещё при создание языка) пожертвовали ею ради безопасности. И продолжают эту традицию дальше во всех мелочах. Так что данное решение по изменению реализации было вполне себе в духе Java.
·>В данном случае это лишь твой стронгли белив, что пожертвовали.

Угу, стронгли белив в математику...

_>>>>Но с производительностью в Java и так всё настолько печально, что ещё небольшое ухудшение (ради спокойного сна обезьянок) точно никто не заметит. )))
_>>·>Ага-ага.
_>>Именно так. Собственно только ради этого данный язык и создавался и именно за это (за возможность нанимать толпы дешёвых, взаимозаменяемых программистов) его очень любит крупный бизнес.
·>Даже если это и так, то не понимаю, почему ты так говоришь, как будто это что-то плохое.

Это не хорошо и не плохо — это просто ключевое свойство языка, определяющее его нишу.

Здравствуйте, ·, Вы писали:

_>>Ну это было не моё утверждение — я бы не стал так обще утверждать, т.к. не пробовал "всё на свете" (мало ли что там кто насоздавал). Однако если говорить про конкретные технологии (типа Java/C#/JS/Python и т.д.), то вполне можно утверждать, что пока не научились SIMD.
·>Java таки чуть-чуть научилась.
·>Кому-то повезло(?) и оно дало преимущество в реальном коде.
·>Вот тут микробенчмарки... непонятно насколько полезны в реальности.

Нуу ОК, хотя я сам такого не замечал в разных тестах, но поверим этим ссылкам. Тогда если перейти от бинарной градации (есть/нет) использования SIMD к некой непрерывной функции от 0 до 1, то видимо у Java будет значение больше нуля (хотя и не сильно ). И у С++ (если мы говорим про автовекторизатор, а не про интринсики) значение тоже поменьше 1 будет пока что.

Здравствуйте, alexzzzz, Вы писали:

A>>>- мой вариант C#: 4,6с
_>>Похоже на правду, хотя и чуть подправленный у тебя там алгоритм (оригинальный будет всё же порядка 5 секунд). Ну и надо отмечать, что это unsafe код, а safe вариант работает больше 10 секунд.

A>Что ты к unsafe привязался? Safe-вариант C++ работает больше 20 секунд, если таковым считать отладочный билд с разными проверками.

Возможно потому, что там абсолютно разный код внутри? ) Или быть может ты покажешь как переключаться между safe и unsafe вариантами данного алгоритма с помощью просто опции компилятора? )

A>>>- похожий C# в Unity: 2,6с
_>>А вот тут у тебя уже совсем другой алгоритм (более простой для SIMD оптимизации). И если запустить его аналог на C++ (см. предыдущее сообщение), то будут совсем другие результаты (и на моей машине и на твоей).
A>Алгоритм там везде один и тот же: перебрать все ячейки и каждую неравную FFFFFF заменить на среднее значение восьми её соседей. Идея сравнивать, как себя ведёт одинаковый до буквы код в разных языках, мне непонятна. Есть входные данные и есть представление, как должны выглядеть выходные. Берёшь в руки конкретный язык с его инструментами и с их помощью трансформируешь.

Потому что у меня это тест языков/платформ/компиляторов, а не людей. И да, определённые особенности языков там используются (именно поэтому для C# всегда было два варианта кода: safe и unsafe), но в пределах сохранения алгоритма. Если бы у меня стояла задача написать максимально быструю реализацию под эту конкретную задачу, то решение было бы совсем другим. Но здесь мне интересно не это, а то насколько эффективно компилятор/интерпретатор умеет организовывать проход по двухмерному массиву.

A>Вот · на Яве подошёл к проблеме кардинальнее, принципиально изменив порядок действий. И честно говоря, правильно сделал. Задача любой программы ― трансформировать одни данные в другие данные. Если программа работает правильно и быстро, каким образом она этого достигает, никого парить не должно. Можно лишь завидовать.

Он изменил не порядок действий, а вообще основную идею теста: у него реализован проход не по двухмерному массиву, а по одномерному. И да, для данной конкретной задачи это могло сработать (хотя при этом всё равно получился код в разы медленнее прохода по двухмерному массиву на C++), но для других реальных задач этот фокус не прошёл бы. Так что подобное извращение теста обесценивает весь его смысл.

A>По оптимизациям, там в результате какая-то длиннющая лапша из SSE и AVX. Ни малейшего представления, что вообще происходит. Но если исходный код цикла немного помассировать, можно получить ещё два варианта: простейший тупой на «обычных» регистрах (буквально десяток операций) и ещё один, по сути как предыдущий, но на SSE-регистрах. Эти два варианта отличались от лучшего на несколько десятых секунды и признаков векторизации в них не замечено. (Если конечно мне показывали правильный дизасм).

Так ты так и не ответил на простейший вопрос: что будет с этим твоим кодом, если заменит math.select на if?

_>>Для gcc и clang любых версий и под любыми ОС правильными опциями для подобных тестов будут: -std=c++17 -march=native -O3.
A>Core i5-2500K @4,5ГГц / DDR3 1333 МГц
A>[cut=-gcc: 6,0c][q]H:\Users\Alex\Desktop\CPP>g++ --version
A>g++ (x86_64-win32-seh-rev0, Built by MinGW-W64 project) 8.1.0

Вот у меня практически точно такой же компилятор (только posix потоки, а не win32) и собрав им тот же код специально под твой процессор (-std=c++17 -march=sandybridge -O3) я получил исполняемый файл http://files.rsdn.org/98162/C++.exe, который выполняется на моём компьютер за 1,8 секунды. И внутри у него SSE автовекторизация.

_>>Ну пока что из принципиальных различий я вижу замену if'а на некий math.select — это было обязательно делать? Неужели такая базовая операция как if запрещена? Или это ты сделал не вынужденно, а для нечестной оптимизации (см. ниже)?
A>Чего не честный-то? Я не понимаю логику. Если у тебя в С++ ?: работает быстрее if, зачем искусственно замедлять собственный код? Не всё ли равно, с какой скоростью в каком-то условном Коболе будет работать оператор ?: и есть ли он там вообще. Мне лично плевать. Надо сделать быстрее ― берёшь и делаешь быстрее, без оглядки на посторонних.

Потому что в реальном коде (а не в данном тесте) вполне может встретиться такой if, который невозможно сконвертировать к ?:.

A>Конкретно math.select — интринзик, если может, мапится в blendvps или типа того, если не может, то
A>

/// <summary>Returns b if c is true, a otherwise.</summary>
A>[MethodImpl(MethodImplOptions.AggressiveInlining)]
A>public static int select(int a, int b, bool c)    { return c ? b : a; }

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

A>Кстати, у меня замена if на ?: дала нулевой эффект. Проверил на всех четырёх компиляторах. Если и есть изменения, то в сотых долях секунды.
A>А, не, это я дебил. Воткнул ?: внутрь if. Перепроверил:

A>- gcc: 2,6 вместо 6,0

Вот, это уже очень похоже на реальность. Хотя всё же странно что медленнее моего результат почти в 1,5 раза на одном и том же бинарном коде, при близкой частоте процессора. Возможно там уже доступ в память начинает давать о себе знать.

A>- clang: 6,1 вместо 6,0

А у тебя clang то через msvs или gcc работает? )

A>- msvc: 5,4 вместо 5,2

Ожидаемо слабый результат.

A>- icc: 4,6 ― без изменений

Хм, странно, возможно что-то с опциями не так.

_>>Кроме этого, я вижу что работа идёт с некими NativeArray, а не стандартными .net массивами. Хотя это естественно не минус, но код всё же явно требует ручного портирования, а не просто некой перекомпиляции.
A>NativeArray ― это struct-обёртка над памятью, типа Span<T>/Memory<T>, но со встроенными защитными механизмами раннего отлова потенциальных race conditions. Например, если в одном потоке такой массив помечен атрибутом только для чтения, а в другом разрешён для записи, и если потоки не были правильно формально синхронизированы, то NativeArray гарантирует, что код мгновенно упадёт с объяснением, в каком месте проблема, в чём заключается и как исправить. Даже если потоки разошлись по времени и в данный момент проблемы как бы нет; достаточно лишь теоретической вероятности гонки. Или, допустим, потоки могут читать/писать в один и тот же массив, но каждый только в свою область; если поток по ошибке заденет чужую, то сразу стоп машина и красный флаг. Реально полезная штука.

Так я не говорю, что оно плохо. Я говорю о том, что для работы с этим инструментом недостаточно просто перекомпиляции — надо переделывать код.

A>В принципе, числодробилка может принимать на вход обычные управляемые массивы; если хочет, делать себе поверх них NativeArray<T>, безопасно работать с ними во множестве потоков, а результаты будут отображаться в исходные массивы. Пока не пробовал, но по идее можно работать и со Span<T>/Memory<T>, так даже универсальнее, чем только с массивами, но менее безопасно, чем с NativeArray<T>.

Ммм, т.е. ты можешь показать пример с int[], как в оригинальном C# коде? )

Здравствуйте, Sinclair, Вы писали:

_>>1. любой ?: можно записать через if
_>>2. любой if нельзя записать через ?: (более того, даже для тех случаев, когда это возможно в теории, оптимизатор не факт что заметит это)
_>>3. операция ?: записывается в одну ассемблерную инструкцию (без всяких прыжков по коду, характерных для ветвлений) как для скалярного кода, так и для векторного. Однако если для скалярного случая не всё так однозначно (ветвление на процессорах Intel выполняется быстрее, а вот на AMD наоборот), то для векторного ветвление означает ужас ужас ужас. )))
S>Ваше рассуждение №3 означают, что оптимизатор С++ конвертирует прямо C++ syntax tree в ассемблерные инструкции, что меня очень сильно удивляет. Не говоря уже о том, что я настолько давно не занимался ассемблером, что не могу сходу вспомнить, о какой инструкции для ?: идёт речь.

CMOVxx для скалярного кода и VPBLENDx для векторного, если мы говорим про x86. Однако на современных процессорах Intel CMOV иногда исполняется медленнее обычного ветвления (если есть хорошие условие для работы предсказателя переходов), так что компиляторы не всегда используют эту инструкцию при компиляции под эту платформу (существенно зависит от названия конкретного семейства целевой архитектуры). А вот векторный вариант практически всегда будет быстрее, однако его не всегда можно применить (или даже компилятор не всегда это видит)...

S>Я ожидал, что компилятор всё же делает какую-то трассировку значений; при трассировке у нас все присваивания в d[x] приобретают форму ?:, а уже потом мы смотрим, какой код для этого породить.
S>Там же много всего — и common subexpression evaluation, и loop invariant, и прочее.

Определённая трассировка то там в любом случае есть, иначе бы не работала та самая автовекторизация (там же куча ограничений есть, удовлетворение которых можно увидеть только из высокоуровневого кода). А вот насчёт преобразования всех присваиваний — это уже сомнительная мысль. )

Здравствуйте, netch80, Вы писали:

_>>Может моя фраза на нормальном русском языке показалась какой-то сложной? ) Попробую тогда переформулировать тоже самое более математически — может так зайдёт? ) И так очевидные факты:
_>>1. любой ?: можно записать через if
_>>2. любой if нельзя записать через ?: (более того, даже для тех случаев, когда это возможно в теории, оптимизатор не факт что заметит это)
N>SSA сейчас используется в: GCC, Clang, MSVC начиная с 2015 (если не врут)...

И?

N>Берём два примера кода, просим выхлоп в текстовой форме LLVM.
N>

N>int f(int a, int b, int c) {
N>        return a ? b : c;
N>}
N>int f2(int a, int b, int c) {
N>        if (a) {
N>                return b;
N>        }
N>        else {
N>                return c;
N>        }
N>}
N>

N>clang -S -emit-llvm -O tbr1.c, и видим (шапку и хвост файла — срезал):
N>

N>; Function Attrs: norecurse nounwind readnone uwtable
N>define i32 @f(i32, i32, i32) local_unnamed_addr #0 {
N>  %4 = icmp eq i32 %0, 0
N>  %5 = select i1 %4, i32 %2, i32 %1
N>  ret i32 %5
N>}
N>; Function Attrs: norecurse nounwind readnone uwtable
N>define i32 @f2(i32, i32, i32) local_unnamed_addr #0 {
N>  %4 = icmp eq i32 %0, 0
N>  %5 = select i1 %4, i32 %2, i32 %1
N>  ret i32 %5
N>}
N>

N>Разницы просто нет.

И? Что ты хотел показать то этим примером? Или ты вот сейчас реально пытался поспорить с фразой "любой if нельзя записать через ?:" с помощью одного примера, в котором это можно? ))) Возможно тебе стоит повторить школьный курс математики, где объясняли как надо доказывать подобные вещи? Там ещё были такие кванторы как ∃ и главное ∀...

N>Разумеется, если бы под if было бы что-то более сложное, то он бы так не сэкономил. Но дело в том, что phi, получаемая в SSA при слиянии потоков команд, по любому объединяет все изменяемые переменные, так что тут такой select получается естественным образом.
N>Это к тому, что "оптимизатор может не заметить". Ему в принципе при SSA невозможно это не заметить, хотя можно сломать, если он решит, что при слиянии можно обойтись без модификации одной стороны.

Ну так раз всё так однозначно, то что же ты привёл IR код для примера выше, а не для обсуждаемого в этой теме? Может потому, что там он генерируется разный, что нарушает твою теорию?

N>Ну а потом это превращается в
N>

N>f:                                      # @f
N>        testl   %edi, %edi
N>        cmovel  %edx, %esi
N>        movl    %esi, %eax
N>        retq
N>

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

_>>3. операция ?: записывается в одну ассемблерную инструкцию (без всяких прыжков по коду, характерных для ветвлений) как для скалярного кода, так и для векторного. Однако если для скалярного случая не всё так однозначно (ветвление на процессорах Intel выполняется быстрее, а вот на AMD наоборот), то для векторного ветвление означает ужас ужас ужас. )))
N>Где "ужас ужас ужас"? Просто надо разделять две ситуации:
N>1. Если ветвление производится для выбора значений векторной операции одинаково для всех в обработанной группе. Например, ты через AVX2 (256 бит) обрабатываешь 4 double (64 бита), но условие для всех одинаково.
N>Тогда подходят обычные команды. И от того, что вокруг векторных операций возникают ветвления — сами эти операции ничуть не искажает. Ну да, надо учесть, что операции дороже (там, где дороже — как AVX2 на многих моделях делается как 2*128 последовательно).

Это вообще не ситуация, а высосанная из пальца фантазия, которую вряд ли кто-то когда-то видел в реальной жизни. Ты вообще представляешь себе сценарий автовекторизации, в котором условие было бы одинаково для каждых N (причём это N ещё и не известно на момент написания кода, т.к. зависит от целевого процессора) элементов массива?

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

N>2. Если ветвление в таком векторе делается раздельно для каждого значения.

Вот это единственный интересный для обсуждения сценарий.

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

Маски — это верно, но их использовать можно по разному. И в стиле if и в стиле ?:. Ты похоже в курсе только про второй вариант, но компилятор умеет и первый. Могу продемонстрировать, на конкретном примере, обсуждаемом в данной темке:

Для обоих случаев в начале вычисляется маска (стандартный vpcmpeqd), но далее идут различия.

Для кода с if у нас идёт загрузка по маске в соответствующий регистр (vpmaskmovd) каждого операнда (у нас там сложение из 8-ми элементов массива) и только после этого собственно сложение (vpaddd, с первым операндом в виде регистра). Соответственно имеет ещё семь пар таких команд. Ну и на последнем этапе у нас идёт обратная выгрузка в память с той же маской (тот же vpmaskmovd) — никаких "слияний" здесь не надо.

Для кода с ?: у нас идёт простая (без маски — vmovdqu) загрузка первого операнда, затем семь операций сложения (тот же vpaddd, но с операндом в виде памяти, а не регистра), затем выбор значений по маске (с помощью vpblendvb) и затем простая выгрузка обратно в память без маски (vmovdqu).

Для данного конкретного случая, второй вариант очевидно быстрее (в первом собственно даже инструкций в 2 раза больше получается, не говоря уже об играх с масками). Но в целом видно, что оба варианта не идеальны — пока компиляторы работают с SIMD всё же хуже, чем люди руками. Надеюсь это скоро изменится...

N>Вот это — нормальное объяснение техническим языком, а не "ужас ужас ужас"

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

Здравствуйте, vdimas, Вы писали:

_>>>>- для такого-то хоста и другого Url: перенаправить запрос (через WSGI или FastCGI или что-то подобное) такому-то локальному приложению
V>>>И это не есть "приложение", это ф-ии роутера.
_>>Какая разница через роутер или нет
V>Разница в эффективности.
V>Де-факто сетка в линухах и так медленная, а тут еще лишние пересылки.

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

Здравствуйте, Ночной Смотрящий, Вы писали:

_>>если он действительно медленнее и при этом винда подходила бы для использования в нагруженных системах, то очевидно что данные в общей статистике были бы совсем другие
НС>Или LB на винде не делают, предпочитают микролинукс. Тупо из-за цены.

Т.е. ты вот это серьёзно сейчас утверждаешь, что компании с хайлоад-сервисами (т.е. априори не бедные) предпочитают сэкономить на нескольких (речь же только про LB, не так ли?) лицензиях Винды, наплевав на существенное улучшение качества их сервиса? )))

Да, кстати, а собственно под Виндой то вообще есть реализации LB на базе этого самого хвалёного http.sys?

Здравствуйте, alex_public, Вы писали:

_>И? Что ты хотел показать то этим примером? Или ты вот сейчас реально пытался поспорить с фразой "любой if нельзя записать через ?:" с помощью одного примера, в котором это можно? ))) Возможно тебе стоит повторить школьный курс математики, где объясняли как надо доказывать подобные вещи? Там ещё были такие кванторы как ∃ и главное ∀...

Возможно, тебе вместо размахивания кванторами стоит остановиться и подумать, что если после SSA такой реализации неважно, был if или ?:, то вообще надо рассматривать реализацию не в этих понятиях. Хотя у тебя, похоже, цель не разъяснить.

_>Ну так раз всё так однозначно, то что же ты привёл IR код для примера выше, а не для обсуждаемого в этой теме? Может потому, что там он генерируется разный, что нарушает твою теорию?

Он не нарушает теорию, он показывает, что ты всех запутываешь рассказами на посторонние темы.

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

Безусловно, кэп.

_>Это вообще не ситуация, а высосанная из пальца фантазия, которую вряд ли кто-то когда-то видел в реальной жизни. Ты вообще представляешь себе сценарий автовекторизации, в котором условие было бы одинаково для каждых N (причём это N ещё и не известно на момент написания кода, т.к. зависит от целевого процессора) элементов массива?

От N зависит, какой комплект команд выгоднее использовать.
Сценарий видел: вычисления, которые производятся в квадратных блоках в большой матрице. Условие является универсальным для блока, блоки берутся размером в степень двойки.

_>На практике у нас или отдельное условие для каждого элемента массива (тогда см. ниже) или же общее для всего массива и тогда оно просто выносится из цикла, ни на что не влияя.

99%, наверно, да.

_>Маски — это верно, но их использовать можно по разному. И в стиле if и в стиле ?:. Ты похоже в курсе только про второй вариант, но компилятор умеет и первый. Могу продемонстрировать, на конкретном примере, обсуждаемом в данной темке:

Это не "стиль if и стиль ?:", это разные методы группировки действий.

_>Для обоих случаев в начале вычисляется маска (стандартный vpcmpeqd), но далее идут различия.

_>Для кода с if у нас идёт загрузка по маске в соответствующий регистр (vpmaskmovd) каждого операнда (у нас там сложение из 8-ми элементов массива) и только после этого собственно сложение (vpaddd, с первым операндом в виде регистра). Соответственно имеет ещё семь пар таких команд. Ну и на последнем этапе у нас идёт обратная выгрузка в память с той же маской (тот же vpmaskmovd) — никаких "слияний" здесь не надо.

_>Для кода с ?: у нас идёт простая (без маски — vmovdqu) загрузка первого операнда, затем семь операций сложения (тот же vpaddd, но с операндом в виде памяти, а не регистра), затем выбор значений по маске (с помощью vpblendvb) и затем простая выгрузка обратно в память без маски (vmovdqu).

Отлично. Но на уровне промежуточного кода тут различие не между if и ?:, а в том, как ты оформил разные конструкции и сгруппировал действия по условию.
А уж рассказ про то, vpaddd берёт из регистра или из памяти — вообще тут тридесятый фактор и упоминать его можно только для запутывания.

_>Для данного конкретного случая, второй вариант очевидно быстрее (в первом собственно даже инструкций в 2 раза больше получается, не говоря уже об играх с масками). Но в целом видно, что оба варианта не идеальны — пока компиляторы работают с SIMD всё же хуже, чем люди руками. Надеюсь это скоро изменится...

N>>Вот это — нормальное объяснение техническим языком, а не "ужас ужас ужас"

_>Хы, это не нормальное объяснение, а выданные с пафосным видом банальности, которые нет смысла даже обсуждать, т.к. они подразумеваются априори.

В том и дело, что для собеседника оказалось совсем не "априори", а когда ты грузишь мифами, то вначале нужны такие банальности, чтобы освободиться от груза. И только тогда можно начинать рассматривать уже то, как на внутреннее представление ложится конкретика и как она дальше отрабатывается в векторах.

Здравствуйте, ·, Вы писали:

N>>Что важнее — соседство ключей друг с другом или соседство ключей со значениями?
N>>И так далее.
·>Собственно это уже вообще непонятные вопросы. Это зависит от устройства конкретной структуры данных. Например, он упомянул реализацию map поверх массивов. Тут можно сделать два вида реализации
·>class {Object []keys; Object []vals;} или class {Object []keyValuePairs;} и используя знание о "array order" выбирать соответствующую реализацию в зависимости от юзкейсов.

Так по keys или по vals в первом варианте? Они могут друг другу заметно противоречить.

N>>Нет. У сишного std::map нет никакого жёсткого требования делать именно деревом. То, что большинство реализаций так сделало — это особенность текущей алгоритмической базы. Стандарт требует только функциональность и гарантии скорости.
·>Интересно, какие ещё реализации могут подойти с такими требованиями? Прям получается как знаменитое "любого цвета если он черный". И очень далеко от "отображение в общем смысле".

Даже в пределах деревьев есть AVL, RB и B, есть splay tree, AA-tree (оно же general balanced tree, полезно для ФЯ и прочих случаев, где выгодно copy-on-write), есть ещё несколько вариантов.
Кроме деревьев есть skip lists. Есть log-structured merge, его, как и B-деревья, раньше применяли только для диска, но есть причины делать это и для RAM. Это только то, что вспомнилось навскидку. Те, у кого есть ACM членство, наверняка накопают ещё десяток более экзотических подходов.

N>>Я принимаю упрёк, что NavigableMap — это интерфейс, а std::map — реализация, но не привязку к TreeMap.
·>Что значит "привязку"?

По смыслу в обсуждении.

N>>·> А NavigableMap это интерфейс, у которого есть две реализации — TreeMap и ConcurrentSkipListMap (в jdk, а так — имплементаций гораздо больше ясен пень). А ещё есть Map, внезапно как ты хочешь "это отображение в общем смысле. То, для чего есть ключ, а есть значение, в которое этот ключ отображён.".
N>>Да, именно, Map не предполагает порядка между ключами.
N>>И это ещё один камешек в твою сторону. Если этого порядка нет, как мы будем его вводить и почему?
·>Ээээ. Map это интерфейс. Как его реализуешь, так и будет упорядочено.

Ещё раз: Map как интерфейс не предполагает порядка между ключами, не обеспечивает средствами для работы с таким порядком (то, что в NavigableMap — floorKey() и аналогичные методы).

N>>>>Но со структурой хранения, как в Java до введения value types, тебе просто нечем подсказать, какие данные и почему ты рекомендуешь системе хранить рядом.
N>>·>Всегда можно топорами порубить.
N>>Я эту реплику совсем не понял.
·>Ну я имел в виду, что можно вручную запилить как надо, _если_ нам надо бороться за производительность.

Вот в этом и вопрос. Всё предыдущее обсуждение было о том, что в .NET, с точки зрения собеседника, "вручную запилить" 1) уже есть средства, 2) управление ими достаточно просто и понятно, а для Java предполагается (или нет) какая-то магия, которая сама догадывается, что почём и почему.
Я не до конца верю, что дотнетовская помощь в виде того, что в struct всё гарантированно лежит рядом, тут как-то существенно посодействует, но там хотя бы есть явное, простое и понятное средство для этого. А рассказы про магию Java, которая сама может догадаться сложить данные с общей temporal locality вместе, меня, мягко говоря, не убеждают без описания конкретных механизмов.

N>>Structure of arrays обычно в разы менее важно оптимизировать, чем array of structures, по крайней мере с современной спецификой кэшей — позиции с одним индексом и так заметно разделены.
N>>Универсальных всемогуторов не предвидится, но оптимизировать важные частные случаи — надо.
·>Все случаи важные, но некоторые важнее... и тут начнётся флейм, а кому именно важные?

Те, которые типовым образом встречаются с достаточной частотой на практике.
У разработчиков языков обычно есть неплохая связь с пользователями. Дальше зависит от того, насколько они способны слышать и отрабатывать запросы пользователей.

Здравствуйте, alex_public, Вы писали:

_>Да, кстати, а собственно под Виндой то вообще есть реализации LB на базе этого самого хвалёного http.sys?

Там пониже уровень будет, для TCP/IP.
https://docs.microsoft.com/en-us/windows-server/networking/technologies/network-load-balancing