Почему? В смысле, с ним не больше боли, чем в самом тс.
P.S. ну понятное дело, что в идеале any должен значить unknown, а реальный any должен называться untyped/typehole. Но это отдельный разговор, т.к. на уровне самого кодгена несложно заменить any на unknown.
Понятное дело, что динамика медленная. Но в качестве фоллбэка вполне себе норм. Потому что просто выкинуть существенно часть языка — решение такое себе.
Не очень понятно, а какую цель преследовали, зачем именно отказываться от v8? Может лучше было сделать фреймворк для биндингов, чтобы можно было легко вызывать ts код. В v8, емнип, довольно хорошо эта история должна быть проработана.
Ну и вопрос сравнений перфа, наверное, тоже не осветили. Хотя набор бенчиакров здесь сложновато найти, конечно.
Почему не смогли поддержать any? Его же можно в условный AnyJsValue транслировать и использовать динамические возможности... Смотрели в эту сторону?
А там эти примеры без достаточных пояснений и раскрытия того что "между строк"
Я не знаю, в каких учебниках Вы смотрели, но когда я изучал рекурсию, там было вполне себе рассказано, что происходит между строк. Поэтому не могу согласиться с этим порывом.
Да, и что "рекурсия вредит читаемости кода/усложняет код" и то что рекурсия не просто бывает медленной, а может оказаться внезапно и трудно предсказуемо ресурсоёмкой (медленно лишь один из аспектов ресурсоёмкости), а это тоже про "вредит читаемости".
Так не пойдёт. Эти тезисы находятся в конфликте, поэтому не имеет смысла пытаться их доказывать одновременно - просто получите кашу из мнений. Читаемость важна в первую очередь в "желтой" и "зелёной" зоне проекта, а вот ресурсоёмкость становиться важна, в основном, в красной зоне проекта. Пытаться доказать их одновременно - это доказательство запутыванием (ввиду неясного контекста!).
Ассимтотически, по крайней мере в этих примерах, и рекурсия и цикл оба работают за линейное/логарифмическое время (в зависимости от примера). Поэтому ассимптотически они одинаково оптимальные, либо неоптимальны*.
А наличие лишнего прохода - это как раз про "такты". Потому что если мы не учитываем такты, то замедление алгоритма даже в 2-10 раз, зачастую не является принципиальным.
*: ну если придираться, то рекурсия в этих примерах использует линейную доп. память, против константного у циклов. Но это по большей части вызвано вырожденностью этих примеров.
А вот ваша версия ... звучит конечно короче, но у меня в голове укладывается плохо ;)
Всё очень просто. Если знать и активно применять динамическое программирование, то подход половинного деления абсолютно естественный и его проще придумать. Аналогично, если иметь много опыта с разделяй и властвуй. Если быть от этого далёким - то действительно может быть непривычно.
А вот подход с двоичным разложением существенно завязан на структуру задачи. Двоичное разложение редко когда применимо к задачам. И нужно быть достаточно сильно погружённым в домен, чтобы догадаться до такого инварианта как двоичное разложение. Иными словами, этот подход достаточно тяжело переносить на другие задачи.
Как аналогию можно сравить дерево отрезков и дерево фенвика. Дерево отрезков гораздо проще придумать и доказать. Также в дерево отрезков гораздо проще вносить всякие интересные вариации. С деревом фенвика это делать гораздо сложнее.
Ну и в целом, я, например, достаточно много трачу времени на то, чтобы устранить рекурсию. И это очень сложно (ну кроме банального эмулирования стека - но это медленно довольно таки). Поэтому всё же в общем случае рекурсия более общий механизм чем циклы. Рекурсию можно заменить на цикл только в очень ограниченном наборе юзкейсов - и лишь в части из них, это выглядит естественно.
Банально, попробуйте написать поиск в дереве отрезков без рекурсии и сложность кода.
Обычно, под "алгоритмической эффективностью" подразумевают что-то в стиле "оптимальная ассимптотика". Поэтому возможно стоит сменить термин.
В приведённых здесь примерах этого нет, но дальше такие примеры появятся.
Так может стоило начать именно с таких примеров? Потому что пока что приведённые примеры весьма нереалистичны (никто не пишет факториал в виде рекурсии кроме как в учебниках по программированию :)). Впрочем, редко кто вообще пишет факториал (потому что его нужно либо фьюзить, либо просто предпосчитать во всех практических кейсах)
А "не будет" относится к тому что не будет приписывать второй цикл, который выполняет исключительно бессмысленные действия.
Вообще, с эффективностью в плане "не делать лишнего".есть всякие неочевидные сложности. Например, можете ли Вы сказать, оптимален ли такой код (с точки зрение Вашей "алгоритмической эффективности"):
Скрытый текст
size_t bespoke_strlcpy(char *dst, const char *src, size_t size)
{
size_t len = 0;
for (; src[len] != '\0'; ++len) {} // strlen() loop
if (size > 0) {
size_t to_copy = len < size ? len : size - 1;
for (size_t i = 0; i < to_copy; ++i) // memcpy() loop
dst[i] = src[i];
dst[to_copy] = '\0';
}
return len;
}
Первый проход здесь почти бесмысленный. Можно его легко совместить со вторым проходом.
Ответ
При совмещении проходов код станет более "оптимальным", но при этом более "медленным" :) (тык)
Поэтому говорить об оптимальности без бенчмарков - как минимум странно.
P.S. Я честно говоря, не до конца понимаю, какой тезис Вы пытаетесь отстоять в данной статье. То ли, что "рекурсия вредит читаемости кода/усложняет код", то ли что "рекурсия - это медленно". Это, если что, разные тезисы, которые обычно могут быть важны в разных ситуациях (и чаще всего несовместимы!).
"Неправильно" - это я с методологической точки зрения. Не важно, есть там использование стека или нет, важно что дебаг-принты и отладчик нельзя использовать для анализа на уровне "тактов" - они просто рисуют фантазию на тему, а не реальное поведение.
А так, понятное дело, что оптимизации компиляторозависимы. Более того, эти оптимизации ещё могут отваливаться при любом обновлении компилятора. Но, как уже говорил, подсчёт тактов в целом компиляторозависим.
Здесь наглядно видно результат работы обоих псевдоциклов. Увидеть эти циклы можно и при пошаговой отладке программы. Но в программе с рекурсией (код 1.2) мы не видим никаких циклов, а значит у программиста нет возможности выкинуть лишний цикл. Это иллюстрация того что рекурсия неуправляема и плохо читаема (красивый лаконичный код рекурсии не соответствует реальному поведению программы и надо разбираться что там подразумевается между строк).
Вообще, Вы в этой статье смешиваете семантический уровень и уровень железа. Как там оно будет исполняться на железе - вопрос весьма нетривиальный, на который в общем случае ответить нельзя. Например в том же хаскеле рекурсия не тратит стек в принципе (и там вообще нет стека в привычном понимании).
Рекурсия захламляет стек не только последовательностью n-1, n-2, n-3, ..., а ещё и адресом возврата из функции, но здесь и далее разбор этих "накладных расходов" опущен, поскольку рекурсия здесь рассматривается с точки зрения алгоритмической эффективности.
А что именно в Вашем понимании "алгоритмическая эффективность"?
Edit:
здравомыслящий программист не станет писать громоздкий и нелогичный код 2.3 вместо простого и наглядного кода 2.1, но именно код 2.3 является наглядной демонстрацией алгоритма работы "простого и красивого" рекуррентного кода 2.2.
Явно писать код со стеком - конечно не будет. Но это не означает, что наличие этого стека как-то мешает. В тот момент, когда глубина стека, или наличие там лишних значений становиться проблемой - тогда уже не мыслят категориями "рекурсия"/"цикл". В таких ситуациях мыслят бенчмарками и асмом. А в типовом коде, рекурсию используют не потому что быстро - а потому что просто - и с этим, вроде, даже Вы согласны, что никаких проблем нет.
Определенно меньше, достаточно лишь проанализировать одну диспач функцию, чтобы всё встало на места.
Здесь не очень очевидно. Речь же, разумеется, идёт не о том, чтобы анализировать руками — речь об автоматическом анализе. И там в одном случае нужно хешмап разворачивать, а в другом следить за указателем в данных. Но не суть — что то, что другое решаются.
Этот подход создаёт не больше трудностей (а то и меньше), чем виртуализация. По идее, хороший анализ девиртуализации спокойно может отменить все подобные приседания. Поэтому такой подход не масштабируется.
Если его пытаться масштабировать, то получится что-то в стиле vmprotect. То есть просто сделать виртуальную машину и транслировать код под эту вм. При этом, одна инструкция этой вм может делать весьма много действий. А чтобы масштабировать защиту, вм генерируется при каждой компиляции новая.
Да, но это же не имеет прямого отношения к шифрованию. Любой драйвер должен это учитывать, даже если он не занимается никаким шифрованием вовсе, разве не так?
Проблема не в ip. С достаточной прозрачностью доставки обновлений, делать таргетированные апдейты нельзя.
Впрочем, если брать условный дебиан, то, по идее, если скомпрометировать популярные зеркала то, по идее, можно попробовать отдать таргетированно другую информацию... Хотя достаточно сложные условия на атаку (Option, уловить момент обновления, уловить нужные зеркала и пр.).
В любом случае, на порядок сложнее, чем в браузере
Понятно, что пробовали писать приложение на смеси c++ и TS. Вопрос в том, почему взялись за компиляцию, а не за интеграцию условного v8?
Ну, bun или v8 не так уж и важно. Это в любом случае меньше работы, чем написать комплиятор
Почему? В смысле, с ним не больше боли, чем в самом тс.
P.S. ну понятное дело, что в идеале any должен значить unknown, а реальный any должен называться untyped/typehole. Но это отдельный разговор, т.к. на уровне самого кодгена несложно заменить any на unknown.
Как раз наоборот. Динамика обычно требует pro, чтобы работать не прям совсем медленно.
Понятное дело, что динамика медленная. Но в качестве фоллбэка вполне себе норм. Потому что просто выкинуть существенно часть языка — решение такое себе.
Не очень понятно, а какую цель преследовали, зачем именно отказываться от v8? Может лучше было сделать фреймворк для биндингов, чтобы можно было легко вызывать ts код. В v8, емнип, довольно хорошо эта история должна быть проработана.
Ну и вопрос сравнений перфа, наверное, тоже не осветили. Хотя набор бенчиакров здесь сложновато найти, конечно.
Почему не смогли поддержать any? Его же можно в условный AnyJsValue транслировать и использовать динамические возможности... Смотрели в эту сторону?
Справедливости ради, подсчёт чисел Фибоначчи через цикл - это и есть тот самый другой алгоритм :)
Я не знаю, в каких учебниках Вы смотрели, но когда я изучал рекурсию, там было вполне себе рассказано, что происходит между строк. Поэтому не могу согласиться с этим порывом.
Так не пойдёт. Эти тезисы находятся в конфликте, поэтому не имеет смысла пытаться их доказывать одновременно - просто получите кашу из мнений. Читаемость важна в первую очередь в "желтой" и "зелёной" зоне проекта, а вот ресурсоёмкость становиться важна, в основном, в красной зоне проекта. Пытаться доказать их одновременно - это доказательство запутыванием (ввиду неясного контекста!).
Ассимтотически, по крайней мере в этих примерах, и рекурсия и цикл оба работают за линейное/логарифмическое время (в зависимости от примера). Поэтому ассимптотически они одинаково оптимальные, либо неоптимальны*.
А наличие лишнего прохода - это как раз про "такты". Потому что если мы не учитываем такты, то замедление алгоритма даже в 2-10 раз, зачастую не является принципиальным.
*: ну если придираться, то рекурсия в этих примерах использует линейную доп. память, против константного у циклов. Но это по большей части вызвано вырожденностью этих примеров.
Не придирайтесь к словам. От того, что компьютеры представляют числа в двоичной системе, двоичное разложение никуда не делось.
Всё очень просто. Если знать и активно применять динамическое программирование, то подход половинного деления абсолютно естественный и его проще придумать. Аналогично, если иметь много опыта с разделяй и властвуй. Если быть от этого далёким - то действительно может быть непривычно.
А вот подход с двоичным разложением существенно завязан на структуру задачи. Двоичное разложение редко когда применимо к задачам. И нужно быть достаточно сильно погружённым в домен, чтобы догадаться до такого инварианта как двоичное разложение. Иными словами, этот подход достаточно тяжело переносить на другие задачи.
Как аналогию можно сравить дерево отрезков и дерево фенвика. Дерево отрезков гораздо проще придумать и доказать. Также в дерево отрезков гораздо проще вносить всякие интересные вариации. С деревом фенвика это делать гораздо сложнее.
Ну и в целом, я, например, достаточно много трачу времени на то, чтобы устранить рекурсию. И это очень сложно (ну кроме банального эмулирования стека - но это медленно довольно таки). Поэтому всё же в общем случае рекурсия более общий механизм чем циклы. Рекурсию можно заменить на цикл только в очень ограниченном наборе юзкейсов - и лишь в части из них, это выглядит естественно.
Банально, попробуйте написать поиск в дереве отрезков без рекурсии и сложность кода.
Обычно, под "алгоритмической эффективностью" подразумевают что-то в стиле "оптимальная ассимптотика". Поэтому возможно стоит сменить термин.
Так может стоило начать именно с таких примеров? Потому что пока что приведённые примеры весьма нереалистичны (никто не пишет факториал в виде рекурсии кроме как в учебниках по программированию :)). Впрочем, редко кто вообще пишет факториал (потому что его нужно либо фьюзить, либо просто предпосчитать во всех практических кейсах)
Вообще, с эффективностью в плане "не делать лишнего".есть всякие неочевидные сложности. Например, можете ли Вы сказать, оптимален ли такой код (с точки зрение Вашей "алгоритмической эффективности"):
Скрытый текст
Первый проход здесь почти бесмысленный. Можно его легко совместить со вторым проходом.
Ответ
При совмещении проходов код станет более "оптимальным", но при этом более "медленным" :) (тык)
Поэтому говорить об оптимальности без бенчмарков - как минимум странно.
P.S. Я честно говоря, не до конца понимаю, какой тезис Вы пытаетесь отстоять в данной статье. То ли, что "рекурсия вредит читаемости кода/усложняет код", то ли что "рекурсия - это медленно". Это, если что, разные тезисы, которые обычно могут быть важны в разных ситуациях (и чаще всего несовместимы!).
"Неправильно" - это я с методологической точки зрения. Не важно, есть там использование стека или нет, важно что дебаг-принты и отладчик нельзя использовать для анализа на уровне "тактов" - они просто рисуют фантазию на тему, а не реальное поведение.
А так, понятное дело, что оптимизации компиляторозависимы. Более того, эти оптимизации ещё могут отваливаться при любом обновлении компилятора. Но, как уже говорил, подсчёт тактов в целом компиляторозависим.
Наглядно, но неправильно. Правильно смотреть вот здесь: https://godbolt.org/z/86nxErzxW - найдите 10 отличий.
Вообще, Вы в этой статье смешиваете семантический уровень и уровень железа. Как там оно будет исполняться на железе - вопрос весьма нетривиальный, на который в общем случае ответить нельзя. Например в том же хаскеле рекурсия не тратит стек в принципе (и там вообще нет стека в привычном понимании).
А что именно в Вашем понимании "алгоритмическая эффективность"?
Edit:
Явно писать код со стеком - конечно не будет. Но это не означает, что наличие этого стека как-то мешает. В тот момент, когда глубина стека, или наличие там лишних значений становиться проблемой - тогда уже не мыслят категориями "рекурсия"/"цикл". В таких ситуациях мыслят бенчмарками и асмом. А в типовом коде, рекурсию используют не потому что быстро - а потому что просто - и с этим, вроде, даже Вы согласны, что никаких проблем нет.
Здесь не очень очевидно. Речь же, разумеется, идёт не о том, чтобы анализировать руками — речь об автоматическом анализе. И там в одном случае нужно хешмап разворачивать, а в другом следить за указателем в данных. Но не суть — что то, что другое решаются.
Этот подход создаёт не больше трудностей (а то и меньше), чем виртуализация. По идее, хороший анализ девиртуализации спокойно может отменить все подобные приседания. Поэтому такой подход не масштабируется.
Если его пытаться масштабировать, то получится что-то в стиле vmprotect. То есть просто сделать виртуальную машину и транслировать код под эту вм. При этом, одна инструкция этой вм может делать весьма много действий. А чтобы масштабировать защиту, вм генерируется при каждой компиляции новая.
Да, но это же не имеет прямого отношения к шифрованию. Любой драйвер должен это учитывать, даже если он не занимается никаким шифрованием вовсе, разве не так?
Скорее, в каждом замке есть встроенный мастер-ключ, который его открывает (даже при смене основного ключа). Но да, что-то в этом роде
А почему шифрование должно влиять на производительность nvme, оно же просто делается а памяти ОС, в качестве предобработки?
Тут скорее дело в том, что сам драйвер шифрования могли криво написать, который в принципе плохо с nvme работает — даже с выключенным шифрованием.
Проблема не в ip. С достаточной прозрачностью доставки обновлений, делать таргетированные апдейты нельзя.
Впрочем, если брать условный дебиан, то, по идее, если скомпрометировать популярные зеркала то, по идее, можно попробовать отдать таргетированно другую информацию... Хотя достаточно сложные условия на атаку (Option, уловить момент обновления, уловить нужные зеркала и пр.).
В любом случае, на порядок сложнее, чем в браузере