Comments 153
ОС могла закешировать часть файла и не читать каждый раз (например, первые 10 Гб), во вторых ssd на m.2 обычно заметно быстрее (на уровне 3 или даже 7 гигабайт в секунду на чтение).
Но исходный код в начале статьи вообще на питоне, его исполнение было бы ещё медленнее на несколько порядков.
Именно. Про файл маппинг в память видимо кто-то не слышал. Ох уж этот мир девопсеров.
Чтобы что-то замапить в память, надо это прочитать с диска, магическим образом байты в рам не залетают. При размере файла 40гб, рам 32гб и линейном чтении файловый кэш поучаствовать не сможет (даже при всём желании, ну разве что перед измеряющим запуском несколько раз запустить программу и нажать Ctrl+C до того, как она завершится, если подгадать момент, тогда можно успеть оставить бОльшую часть файла в кэше фс).
Погодите, маппинг в память и кэширование - это не одно и то же. Первое - это лишь таблица трансляции виртуальных адресов, доступных программе в реальные, доступные ОС.
так автор же писал, что, несколько раз запускал код с разными параметрами от меньших к большим, т.о. на третьем пуске закэшировалось Х первых гигабайт, и на четвертом Х первых гигабайт вычитало прям из кэша, а дальше как обычно.
А почему кстати при маппинге при увеличении числа время растёт? Маппинг ведь подразумевает расчёт указателя, верно? Если есть расчёт, то и файл не нужно читать с начала, а с произвольного индекса.
добавьте еще ELSE к IFам, пожалуйста, а то получается какой-то брут-форс )))
а что изменится?
Ну судя по тому что время работы программы у чела меняется в зависимости от введённого значения, то на асме он таки добавил элсы.
Без элсов любой запуск будет тратить одно и тоже время и считывать весь файл, а с элсами он будет считывать до ИФА с совпадающим значенияем введённого числа. Без элсов это аналог алгоритма каунт (посчитать все вхождения), а с элсами алгоритм фаинд (найти первое совпадение).
И ещё это демонстрация того, как легко получить undefined behavior в программе на C. Если запустить программу без параметров, то значение argv[1] - NULL, а поведение atoi c параметром NULL не определено в стандарте. Если argc равно 0 (впрочем, под Windows этого случится не может), то значение argv[1] не определено.
Даешь повторение эксперимента на Rust! Я бы посмотрел... на итоговую разницу. И результа запуска без параметров.
Потенциальные ошибки придётся обрабатывать каким-то образом. Что-то вроде
let number: u32 =
args().nth(1)
.expect("The program needs an argument")
.parse()
.expect("The first argument should be a positive number");
Ну, а дальше работа с загрузкой и исполнением недоверенного кода, которая не может быть безопасной по определению, так что придётся использовать unsafe.
Большая часть работы тут возложена на OS, так что измеримой разницы в производительности скорее всего не будет.
Не пойдет, ибо
if (argc < 2) {
printf("Need argument!\n");
return -1;
}Но это уже дополнительный код. А интересно именно без него... Особенно если вернуться к вашему верхнему комментарию.
Чудес не бывает. Undefined behavior нужно как-то определить, иначе он останется undefined. Раст доопределяет работу с аргументами программы как: "args().nth(n) возвращает None, если аргумента n не существует". Что с этим делать дальше зависит от программиста. Можно даже вернуть UB, используя unreachable_unchecked() в ветке обрабатывающей отсутствие аргумента.
Т.е. вопрос в целом не к atoi(), а к программисту, который не проверил ввод от пользователя и в целом это не зависит от языка? Я правильно понял?
А что произойдет с вашим кодом, если мы запустим
$ ./prog fortytwoВводим дополнительную проверку? Или все же "мусор на входе - мусор на выходе"?
Дополнительная проверка в комментарии выше уже есть - parse вернёт ошибку, если входная строка не будет представлять значение требуемого типа (здесь - u32). Для этого, собственно, и нужен второй expect.
Т.е. .pase() ведет себя не как atoi(), а как scanf(). Впрочем, при использовании scanf() в C можно было и argv[1] на NULL не проверять...
В целом очень странные чувства от анализа совершенно простого кода. С одной стороны да - при нештатном использовании (запуск без аргумента или с неподобающим аргументом) - и даже откровенно некрасиво написанная программа падает в корку. Чем явно и недвухсмысленно говорит программисту - ты не прав, надо исправляться. С другой стороны... Падение программы, вызывающее DoS - несколько не то поведение, которого ожидает заказчик. Тем более, что для такого поведения надо "нарушить правила" - т.е. создать специально условия, приводящие к ошибке. А война меча и щита - она вечная.
Да, пожалуй, DoS в большинстве случаев лучше, чем RCE. Но нужно быть гурманом...
Так не пиши .expect если падение нежелательно, это лишь один из вариантов обработки ошибки. Можно поставить вопросительный знак, тогда ошибка будет проброшена далее по стеку. Или же её можно обработать явно.
Важным моментом является тог, что не выбрав способа обработки ошибки до значения не добраться.
Ах да, ещё паники можно перехватывать, чтобы отправить в какой-нибудь Sentry, так что даже .except не роняет программу безусловно.
В результате запуска без параметров там будет что-нибудь вроде thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', т.е. ничего интересного.
Если же повторять эксперимент на Rust, то лучше засунуть все в здоровенный блок match и посмотреть, прожует компилятор 4 миллиарда записей в нем, или тоже решит, что это не для него.
Точно так. И код возврата не нулевой (надеюсь).
Не нулевой, а 101.
Match не годится, он может быть соптимизирован и вместо полного перебора получите O(log(N)).
Хорошая статья для пятницы.
По моему, автор доказал только одну вещь:
-можно реализовать любую фигню, любым образом, особенно если ты не ограничен ресурсами.
я думал статья будет про то как нейросети работают....
Если ваша лайвкодинг-сессия на интервью не похожа на это, то даже не зовите меня.
Все равно надо писать на Питоне: из полученного в качестве параметра числа он должен сделать программу на C, скомпилировать ее, запустить и вернуть результат.
Но глобально хотелось бы то же самое, но на микросервисах..
Было бы интересно посмотреть сравнение производительности. ИМХО куча операторов сравнения медленнее чем операция остатка от деления. Однако, если сделать некую таблицу (число-чётное или нет) и маппинг оффсета на каждое число, и хранить этот файл в RAM, то уже возможно, что будет быстрее. Но опять же, это все надо проверять.
Я слабо представляю, как что-то может быть быстрее, чем получение крайнего бита из бинарного представления в памяти целого числа.
Так нам ведь нужно не просто получить бит. Нам нужно:
Прочитать аргумент, представленный в виде строки.
Зачем-то сконвертить эту строку в число.
Получить бит от этого числа
В зависимости от бита осуществить переход.
Но ведь можно же никуда строку не конвертировать, а просто взять из неё последнюю цифру и проверять только её символьный код. Там и if'ов будет меньше, и переход можно вообще таблицей переходов (или switch) сделать.
А можно таки взять младший бит последней цифры) Расположение символов цифр в ascii соответствует четности самих чисел
Вы на полном серьезе рассуждаете как можно оптимизировать код из статьи?:)
Ну да, а что? Я считаю, что нужна пачка функций типа isEqualTo0, isEqualTo1, isEqualTo2 и так далее, которые проверяют (тоже перебором) равенство конкретному числу, а уже потом проверять пачкой вызовов типа if(isEqualTo3(number)) printf("odd\n"), так хотя бы O(N^2) будет, а не жалкое O(N).
Перебором неспортивно. Нужна рекурсия
Ну можно. Каждый из вызовов isEqualToX вызывает все остальные isEqualToY, чтобы убедиться, что каждый из них вернёт false. А чтобы избежать зацикливания – для каждого храним флаг, что он уже вызван. Правда, это будет не thread-safe, но, сдаётся мне, это наименьшая из проблем.
А где хаб "Ненормальное программирование"?
if (number == 5)
printf("odd\n");
4 миллиарда сравнений (каждое на 2 строчках), вот что бывает когда за код платят построчно:)
Забавно. А можно кластер из 2^32 нодов создать, чтобы каждый за свою цифру отвечал и ваш код как функцию распределения взять и ву-а-ля - можно поток цифр в реальном времени обрабатывать. :)
Это не троллинг 80 лвла. Это троллинг 40 ГБ лвла)))
На самом деле, показанный выше код — идеальный пример компромисса между временем и задействованной памятью.
Хорошая попытка, но нет. Автор кода просто не понимает что он делает.
а gcc -O3 это во сколько раз сожмет?
Просто превратит это в `if i % 2 ...` :)
42
Не сильно-то он это сжимает. Никто просто не догадался написать такую оптимизацию: https://godbolt.org/z/rsbaWx8Tr
А вот clang умеет делать из этого switch-case: https://godbolt.org/z/MnYse7PPc
Вот это сразу вспомнил: https://github.com/AceLewis/my_first_calculator.py
Куча if-ов - это уровень мидла, не выше. Сеньерское же решение будет таким:
bool is_even(int n) {
return n == 0 ? true : is_odd(n - 1);
}
bool is_odd(int n) {
return n == 0 ? false : is_even(n - 1);
}
изучив ограничения формата Portable Executable (.exe) для Windows, я обнаружил, что он не может обрабатывать больше, чем жалкие 4 ГБ
Мне кажется, что подход с автоматизированно-ручным написанием опкодов избыточно сложен для такой простой задачи.
Я бы на вашем месте воспользовался паттерном "разделяй и властвуй" и поэкспериментировал бы с созданием нескольких DLL-файлов, каждый из которых отвечает за свой диапазон чисел.
При таком подходе первичный работающий прототип можно получить довольно быстро. И далее уже смотреть в сторону оптимизации по скорости работы: чем меньше по размеру DLL-файл, тем быстрее он будет отрабатывать, но вместе с уменьшением размера будет расти количество файлов, соответственно, будет замедляться подгрузка файлов средствами ОС.
"Разделяй и "властвуй" это будет:
public static bool IsEven(int n) => n switch {
< 0 => IsEven(-n),
0 => true,
1 => false,
_ => IsEven(n / 2) && IsEven(n - n /2) || IsOdd(n / 2) && IsOdd(n - n / 2)
}
public static bool IsOdd(int n) => !IsEven(n);
Тоже сразу подумал про несколько DLL. Или можно вообще ничего не генерировать заранее, а создавать код в рантайме для диапазонов по миллиону чисел, например. Тогда exe-шник будет маленький, и даже не очень много памяти попросит.
Upd: Кстати, это позволит не ограничивать себя 32-битами.
Первая мысль при чтении про невлезание в размер "а когда-то для такого использовались оверлеи".
мне кажется у джуна из тиктока более производительный код, за счет else if
А зачем писать столько много?
Ведь можно отбросить все цифры, кроме последней. И работать с ней. Всего 10 if.
А можно и двумя обойтись
if(n==1||3||5.... И тд
А когда русскоязычное написание фамили Денниса как «Ритчи» сменили на «Ричи»? А Кернигана тоже на кого-то поменяли?
А разве недостаточно было проверять только последнюю цифру числа. Десяток ифов всего.
Надо было просто на CUDA все переложить. Я думаю, последние ускорители типа N100 должны справиться с подсчетом четных чисел. /s . Далее нам понадобится суперкомпьютер из топ100 для подсчета числа счастливых билетов.
Ну честно, какая то машина Голдберга получается с этими подходами)
Вот, с помощью BING'а набросал нечто подобное на SQL
Код для определения четности/нечетности числа на TRANSACT SQL
-- Create a stored procedure named CheckEven with one int parameter
CREATE PROCEDURE CheckEven @num int
AS
BEGIN
-- Declare a variable to store the result of the query
DECLARE @result int, @numint ;
-- Create a table named EvenNumbers with one field of int type
CREATE TABLE EvenNumbers (
Number int
);
-- Set a variable to store the current number
SET @num = 2;
-- Use a while loop to insert numbers from 2 to 32766 into the table
WHILE @num <= 32766
BEGIN
-- Insert the current number into the table
INSERT INTO EvenNumbers (Number) VALUES );
-- Increment the current number by 2
SET @num = @num + 2;
END
-- Select the count of the number from the EvenNumbers table
SELECT @result = COUNT(Number) FROM EvenNumbers
-- Use the parameter as the filter condition
WHERE Number = @num;
-- If the result is greater than zero, the number exists in the table
IF @result > 0
BEGIN
-- Print 'even' as the output
PRINT 'even';
END
-- Else, the number does not exist in the table
ELSE
BEGIN
-- Print 'odd' as the output
PRINT 'odd';
END
END
Преимущество этого кода в том, что данные для определения четности можно хранить во внешней памяти. Не ручаюсь за выполнимость кода, но идея должна быть понятной - создаем таблицу, заполняем ее четными числами, потом определяем, есть ли искомое число в этой таблице
WITH
OddOrEven(Num, IsEven)
AS
(
SELECT CAST(0 AS int) Num, CAST(1 AS bit) IsEven
UNION ALL
SELECT
oev.Num + 1 Num,
CASE
WHEN oev.IsEven = 0 THEN CAST(1 AS bit)
ELSE Cast(0 AS bit)
END IsEven
FROM OddOrEven oev
WHERE oev.Num < POWER(CAST(2 AS bigint), 31) - 1
)
SELECT IsEven
FROM OddOrEven
WHERE Num = @num;
Я понимаю, что это чисто поржать, но хоть бы массив забил что ли битовый статический, чтоб за о(1), или каскадировал через <, чтоб хотяб за логарифм...
Тут уже предлагали выше решить такую задачу на микросервисах. Я предлагаю пойти дальше. Чтобы по-настоящему хайпануть на трендах, надо взять какую-нибудь LLM архитектуру где-нибудь на 40B параметров и обучить исключительно на эту задачу. Считаю что это будет гораздо эпичнее.
И получить после обучения на пятизначное число долларов точность ответа более 90%!
Думаю, нужно сделать клиентское приложение, которое надо качать и ставить себе. Установившие такие приложения становятся нодами единой сети. Нода будет брать задачи из единого реестра, вычислять чётность/нечётность и отдавать результат в сеть. Задачу должны взять себе несколько нод, так чтобы один из ответов (чёт или нечет) был больше 50% мощности сети.
Хабр неостановимо пробивает днище за днищем
Я сторонник высокопроизводительного кода, поэтому решил реализовать это на языке программирования C, потому что он и сегодня остаётся самым быстрым языком в мире с большим отрывом от других (благодаря гению Денниса Ричи).
Мне кажется, или тут полное не понимание того, что секрет скорости не в некой «гениальности» си, а в миллиардах, вбуханных, в конкретные компиляторы? Странно такое видеть от человека, заявляющего что он «сторонник высокопроизводительного кода». Впрочем, современные последователи карго культа «блейзинг фаст» +/- все что-то подобное заявляют.
Не стоит преуменьшать заслуги Ричи, всегда считал, что секрет скорости ЯП в близости к железу, правда стоит уточнить, чем дальше от железа, тем быстрее разработка зато. Автор молодец, так заморочиться, спасибо, интересно было почитать.
Если бы автор написал как-то по-другому, ему не удалось бы написать шутку про Python ниже по тексту. А зачем вы пытаетесь искать глубокое понимание чего бы то ни было в откровенно стёбной статье?
эм, причём тут компиляторы, если питон в любом случае будет медленнее. На С можно писать код так, что его будет практически невозможно оптимизировать (т.к. он будет оптимален)
Даже если каждое сравнение будет использовать меньше одного байта, файл всё равно будет слишком тяжёлым.
Не факт.
Надеюсь эта статья не попадет в обучение следующих версий gpt
https://godbolt.org/z/7qE9863j4
Clang с O2 оптимизирует цепочку сравнений до выборки указателя из таблицы с последующим вызовом puts. Другие компиляторы не осиливают оригинальный код и оставляют кучу инструкций ветвления.
На C# я могу хоть триллион IF сделать.
Шаг №1 - Генерирую DLL на N штук IF - загружаю в память и использую
...
Шfг №M - Генерирую DLL на N штук IF - загружаю в память и использую
В итоге N * F операторов IF.
Вуаля !
Зарегался чтобы поставить лайк.
А не проще проверять последний бит числа
Если 1 четное иначе нечётное?
Всего 1 строка...
Простите, это что за наркомания ?
Value And 1 для слабаков ?
Проверка нулевого бита, алле...
Тема с оптимизацией алгоритмов не раскрыта КМК, можно было бы на питоне сгенерировать дерево if'ов. Код конечно слегка вырастет, зато какой прирост производительности!
Не совсем корректный ассемблерный код
Судя по подсветке синтаксиса, это вообще код на 1С ;)
Считаю, что о читаемости кода забывать нельзя и потому вместо INC EAX обязательно нужно было использовать SETE EAX.
я решил отобразить файл в адресное пространство, а не читать его целиком. Сделав так, мы притворимся, что весь файл уже находится в памяти
Досовские com-файлы восстают из пепла под 64-битной виндой, это ли не новогоднее чудо???
Автор выбрал другие хабы, там 5 ограничение, а так да может подойти.
@denis-19 «Ненормального программирования» здесь всё же больше, чем «алгоритмов».
P.S. При переводе потерялась часть шуток-прибауток из оригинала, читайте оригиналы!
Прошу рассмотреть возможность оформить это как npm-пакет через ffi, постоянно возникает такая задача
Когда учился универе, было групповое задние на семестр заниматься разработкой 16-бит ОС (не обязательно чтобы была полностью рабочей), и у меня было одно из заданий: реализовать динамическое распределение памяти malloc. При работе нужно было для теста выводить в консоль распределение памяти, но при этом была проблема, что функция для печати числа использовала память для перевода его в строку при печати. Для того чтобы тестировать память и печатать числа без выделения памяти, пришлось сгенерировать файл на 40к строк:
if(num == 123) {kprint("123");};
Ну, нет предела совершенству, можно же через if-else реализовать бинарные деревья, что сохранит нам один условный оператор и сильно увеличит скорость выполнения программы
Было больно читать статью и комментарии, но я справился.
Шикарная статья, получил море удовольствия, жду следующую:
"жервуем дисковым пространством ради скорости проверки на четность", где автор забьет ССД файлами с именами четных чисел и потом будет проверять четность наличием файла на диске.
Можно значительно уменьшить пенальти времени поиска файла, если хранить файлы не в виде папки с файлами, а в виде дерева подпапок с файлами, чтобы в каждой папке было не больше. Это был путь слабых.
А путь сильных это создать 4Гб файл на диске из 1 и 0, и при провере сикать по параметру сразу на позицию чтения. Смех-смехом, но подобная парадигма скорей всего это будет самой быстрой проверкой чисел "на простоватость".)
Очень любопытная тема с написанием огрызка компилятора Си/Ассемблера на Питоне который собирает исходники прямо в код процессора!
Существуют ли примеры компиляторов прямо в машинный код написанных на Питоне?
Еще вариант (C#) - для int тут не получается (из-за встроенного лимита на длину массивов), но для short вполне:
using System.Linq.Expressions;
var param = Expression.Parameter(typeof(short));
var trueFalse = new[] {
Expression.Constant(true),
Expression.Constant(false)
};
var body = Expression.Switch(
param,
defaultBody: trueFalse[1],
Enumerable.Range(0, short.MaxValue + 1)
.Select(i =>
Expression.SwitchCase(
body: trueFalse[i % 2],
Expression.Constant((short)i)))
.ToArray());
var isEven = Expression.Lambda<Func<short, bool>>(body, param).Compile();
for (short i = 0; i <= 42; i++)
{
Console.WriteLine($"{i}: {isEven(i)}");
}
можно создать массив с длиной расзмером с long или же int64, но конечно не через Enumerable.Range(..)
Не, по-моему таки нельзя. Для одномерных массивов максимальное число элементов ограничено значением свойства Array.MaxLength - и, во-первых, оно уже объявлено как int и больше чем int.MaxValue быть не может, во-вторых, если покопаться в исходниках, то выясняется, что там оно захардкожено как 0X7FFFFFC7, что даже немного меньше чем int.MaxValue. Для многомерных массивов теоретически методы класса Array поддерживают размеры в long, но, на деле (опять-таки, если посмотреть в исходники) этот long там везде приводится к int, и если он в него не влезает, то мы сразу получаем ArgumentOutOfRangeException, и, даже более того, если он помещается в int, но не помещается в Array.MaxLength то тогда получаем OutOfMemoryException с сообщением "Array dimensions exceeded supported range."
Не уж то чудооптимизатор сей не соптимизировал мильён ифов? Не пробовали? Просто интересно... Он, порой, такие оптимизации лепит, что суть всего алгоритма меняет)
Как насчёт использования оптимизированной функции в if-ах
bool optimised_is_even(int number) {
bool res = true;
for (int i = 0; i < number; i++)
res = !res;
return res;
}
Очень познавательная статья, добавил в закладки везде, даже на микроволновке!
Жду реализацию программы "FizzBuzz". Планируете ли выпускать книгу по вашим работам?
С нетерпением жду захватывающего продолжения с нахождением остатка от деления, реализованного ифами на ассемблере)
А можна исходник на гитхаб? ?
Коллеги, кто-нибудь попробуйте решить эту задачу на FreePascal для чисел разрядностью x64
Главный вопрос - зачем?))) Ну а если серьёзно, то только через подобные эксперименты узнаешь о разных тонкостях компиляторов/ОС.
Спасибо что не выложили весь исходный код в статью =)
4 миллиарда операторов if