Если я правильно предполагаю, то автор пишет про "Сортировку Таноса" (автор называл её "Русской сортировку половинками", но я категорически против использования такого названия), которая является велосипедом вариантом QuickSort. Видимо по некомпетентности valemak не распознал велосипед и написал вышеупомянутую статью (ничего страшного, бывает).
Однако, дальше хуже:
valemak пригласил на Хабр пользователя Danilin78 (автор упомянутой сортировки), который умудрился отличится двумя вариантами своей статьи (1, 2) получившими недвусмысленную оценку "бред" и т.п.
Теперь valemak пригласил пользователя HabrArkady, который написал обсуждаемую статью о "вновь разработанном алгоритме сортировки", демонстрируя элементарное незнание темы, без описания алгоритма и/или демонстрации исходного кода, неся откровенную пургу в комментариях и т.д и т.п.
Поэтому у меня вопрос к valemak: кто все эти люди и что вы там все употребляете?
В Windows это действительно убого, но по другим причинам:
Через API невозможно создать отображение больше размера файла (только посредством NtExtendSection()).
Нельзя уменьшить отображенный в память файл.
Отсутствует аналог madvise().
Так что если отобразить в память 64Гб файла нулевого размера, то в этот файл сначала будет записано 64 Гб нулей, что внешне может выглядеть как описывает qrck13.
Изобретать/исследовать новые алгоритмы, инженерить применение известных и просто "кодить" — сильно разные роды занятий, но все попадают под определение "программизма".
Мне представляется что индустрии в 80-90% случаев нужны кодеры, а им совсем не обязательно знать о "2,7,61" (в продолжение isPrimeNumber) и ещё о куче всяких подобных вещей. В том смысле, что в жизни есть ещё масса интересного, на что можно потратить время (в том числе избавиться от "клипового" мышления). Люди довольно быстро понимают, что умение быстро слепить что-то из пары-другой js-библиотечек с бОлшим шансами и быстрее приведёт их к целевой зарплате, их нельзя в этом упрекать.
Те же кого интересует создание новых алгоритмов и/или высокая инженерия (как мне кажется) сами найдут дорогу. Им следует давать возможность учиться и шанс проявить способности (рабочие места с нормальными задачами). Но что-то мне подсказывает, что в резюме у них не будет слов "fullstack" и "developer" ;)
Рано или поздно придется что-то менять с нарушением совместимости.
При этом я бы предпочел явно видеть все подобные изменения и иметь возможность совмещать старый и новый код.
Поэтому я не вижу другого решения и не понимаю почему решили отрезать кошке хвост частями.
Не могу согласиться.
Это не проблемы, а неизбежное следствие развития.
Как мне кажется, при наличии std11::, std14::, std17:: и std20:: обсуждаемой проблемы ABI просто не было-бы. Но возможно я тупо не в курсе какой-то общеизвестной причины? antoshkka?
С точки зрения алгоритма это довольно простая и не особо интересная задачка. При определенно опыте достаточно очевидно, что в зависимости от поколения CPU и компилятора можно достаточно близко подойти к пределу (memory bandwidth). Собственно я об этом заявил примерно сразу.
Второй поток тут не нужен, точнее вреден. Достаточно организовать обработку блоками по 64 байта (кэш-линиями) и уменьшить зависимость по данным (несколько счетчиков, которые сложить в конце). Если совсем "упороться", то нужно делать prefech или упреждающее потоковое чтение с учетом кол-ва активных каналов к памяти (т.е.
с учетом актуального интерливинга банков DDR при отображении на адреса).
Но к теме этой статьи это не имеет отношения, по крайней мере пока в Хаскель не завезли интриниски для SIMD ;)
А теперь понятно, а то я всё смотрел на это через предсказатель переходов.
Короче, по вашей наводке (спасибо) я понял что немного продолбал пока возился с /dev/urandom. Сначала при экспериментах я чистил выхлоп для получения ASCII-текста (посредством tr). Получил подтверждение гипотезы, перенес результаты в текст. Но после решил убрать "чистку" для упрощения, замерив результаты заново. Но вот цифры в выражении 1871822210 / 210195110 = 8.9 не обновил :(
Да, но чем меньше N чем хуже у бранч-предиктора с угадыванием переходов. Поэтому исходные тестовые данные с 40-буквенными словами искажали реальное положение дел, о чем собственно и написано в тексте статьти.
Короче, я уже примерно совсем не понимаю о чем разговор.
В статье говориться:
первоначальные тестовые данные плохие (потому что очень длинные слова).
просто "случайный мусор" будет честнее по длине слов и позволит увидеть проблему.
перепроверка "Шекспиром" всё подтвердила.
Позволяют ли случайные данные что-то предсказывать бранч-предиктору?
Да, конечно. ибо для всех условных переходов статистика существенно отличается от 50/50 (это изначально очевидно).
Позволяют ли случайные данные (со средней длинной слова 8.9) предиктору предсказывать переход на 9 символе?
нет, потому что нет значимой статистической разницы.
даже если будет генерироваться такое предсказание, то толку не будет.
исходя их статистики предиктор будет предсказывать переходы в продолжение не-пробельных символов (их просто больше).
Ну так и что в итоге с "сортировкой воронкой"?
Если дадите ссылку на исходный код референстной или оптимизированной реализации, то обещаю выложить результаты тестов с исходниками.
Если я правильно предполагаю, то автор пишет про "Сортировку Таноса" (автор называл её "Русской сортировку половинками", но я категорически против использования такого названия), которая является
велосипедомвариантом QuickSort. Видимо по некомпетентности valemak не распознал велосипед и написал вышеупомянутую статью (ничего страшного, бывает).Однако, дальше хуже:
Поэтому у меня вопрос к valemak: кто все эти люди и что вы там все употребляете?
Вставка такого объема одной транзакцией может не пройти без подстройки конфигурации, а несколькими транзакциями будет накладно для диска.
Но вот если взять libmdbx, то точно будет проще и быстрее.
Вполне возможно что в 10-100 раз быстрее постгреса и без докера.
Справедливости ради — netmap появился на FreeBSD.
Хм, по-мне так это как-раз таки формулировка упомянутого "перла" в виде сухих аргументов.
В Windows это действительно убого, но по другим причинам:
NtExtendSection()).madvise().Так что если отобразить в память 64Гб файла нулевого размера, то в этот файл сначала будет записано 64 Гб нулей, что внешне может выглядеть как описывает qrck13.
Изобретать/исследовать новые алгоритмы, инженерить применение известных и просто "кодить" — сильно разные роды занятий, но все попадают под определение "программизма".
Мне представляется что индустрии в 80-90% случаев нужны кодеры, а им совсем не обязательно знать о "2,7,61" (в продолжение
isPrimeNumber) и ещё о куче всяких подобных вещей. В том смысле, что в жизни есть ещё масса интересного, на что можно потратить время (в том числе избавиться от "клипового" мышления). Люди довольно быстро понимают, что умение быстро слепить что-то из пары-другой js-библиотечек с бОлшим шансами и быстрее приведёт их к целевой зарплате, их нельзя в этом упрекать.Те же кого интересует создание новых алгоритмов и/или высокая инженерия (как мне кажется) сами найдут дорогу. Им следует давать возможность учиться и шанс проявить способности (рабочие места с нормальными задачами). Но что-то мне подсказывает, что в резюме у них не будет слов "fullstack" и "developer" ;)
И?
Рано или поздно придется что-то менять с нарушением совместимости.
При этом я бы предпочел явно видеть все подобные изменения и иметь возможность совмещать старый и новый код.
Поэтому я не вижу другого решения и не понимаю почему решили отрезать кошке хвост частями.
Неизбежно коснётся, но будет шанс дойти до более существенных граблей.
Не могу согласиться.
Это не проблемы, а неизбежное следствие развития.
Как мне кажется, при наличии
std11::,std14::,std17::иstd20::обсуждаемой проблемы ABI просто не было-бы. Но возможно я тупо не в курсе какой-то общеизвестной причины? antoshkka?Пардон, но как могут быть те же проблемы с новыми именами. Кто мешает ломать совместимость каждые 10 лет в новом
std::?А кто первый предложил перейти на "
std42::", т.е. тупо использовать разные неймспейсы для новых ABI?С точки зрения алгоритма это довольно простая и не особо интересная задачка. При определенно опыте достаточно очевидно, что в зависимости от поколения CPU и компилятора можно достаточно близко подойти к пределу (memory bandwidth). Собственно я об этом заявил примерно сразу.
Второй поток тут не нужен, точнее вреден. Достаточно организовать обработку блоками по 64 байта (кэш-линиями) и уменьшить зависимость по данным (несколько счетчиков, которые сложить в конце). Если совсем "упороться", то нужно делать prefech или упреждающее потоковое чтение с учетом кол-ва активных каналов к памяти (т.е.
с учетом актуального интерливинга банков DDR при отображении на адреса).
Но к теме этой статьи это не имеет отношения, по крайней мере пока в Хаскель не завезли интриниски для SIMD ;)
А теперь понятно, а то я всё смотрел на это через предсказатель переходов.
Короче, по вашей наводке (спасибо) я понял что немного продолбал пока возился с
/dev/urandom. Сначала при экспериментах я чистил выхлоп для получения ASCII-текста (посредствомtr). Получил подтверждение гипотезы, перенес результаты в текст. Но после решил убрать "чистку" для упрощения, замерив результаты заново. Но вот цифры в выражении1871822210 / 210195110 = 8.9не обновил :(Да, но чем меньше N чем хуже у бранч-предиктора с угадыванием переходов. Поэтому исходные тестовые данные с 40-буквенными словами искажали реальное положение дел, о чем собственно и написано в тексте статьти.
Короче, я уже примерно совсем не понимаю о чем разговор.
В статье говориться:
Позволяют ли случайные данные что-то предсказывать бранч-предиктору?
Позволяют ли случайные данные (со средней длинной слова 8.9) предиктору предсказывать переход на 9 символе?
Он его как-то не к месту поднял.
Конечно так можно оценивать насколько эффективно (близко к пределу) работает та или иная реализация (особенно образом SIMD).
Но это сложнее и НЕ РАЦИОНАЛЬНО если требуется просто выяснить что быстрее (при запуске на одной машине, т.е. в равных постоянных условиях).
Не понял что вы посчитали и как.
Поясните.
Нет, подумайте.
Для данных из
/dev/urandomсоотношение не-пробельных символов к пробельным (пробел и все что меньше 14) будет равно(256-14-1)/(1+14) = 16,06(6).Замечательно ;)
Тогда покажите, пожалуйста, как средняя длина слов получилась 8.9, а не 42?
Ну и какова средняя длина цепочек единичных бит (the runs of ones) в данных из
/dev/urandom?Все результаты и выводы подтвердились для ghc 8.8.3, LLVM-бакендом и на текстах Шекспира.
См под спойлером в конце статьи.