На habrahabr появилась очередная статья, которая пытается научить гуманитариев вроде меня тому, чем являются числа с плавающей точкой.
Так как мне нужно было срочно компенсировать на ком-то свой комплекс неполноценности, я написал большой комментарий по поводу качества этого материала, даже дав себе труд подсказать как иначе можно обьяснять все тоже самое.
Вот статья: https://habr.com/ru/articles/745640/
Вот комментарий: https://habr.com/ru/articles/745640/#comment_25725790
Вот ссылка на перевод главы о которой я говорю в самом конце: https://habr.com/ru/articles/337260/
Так как мне нужно было срочно компенсировать на ком-то свой комплекс неполноценности, я написал большой комментарий по поводу качества этого материала, даже дав себе труд подсказать как иначе можно обьяснять все тоже самое.
Вот статья: https://habr.com/ru/articles/745640/
Вот комментарий: https://habr.com/ru/articles/745640/#comment_25725790
Вот ссылка на перевод главы о которой я говорю в самом конце: https://habr.com/ru/articles/337260/
Хабр
Числа с плавающей точкой для гуманитариев. Что это такое и как они работают
Введение В этой статье я бы хотел затронуть такую важную и фундаментальную тему для любого программиста, как числа с плавающей точкой. На данную тему уже написано большое количество статей, однако...
🔥12❤2🐳2🕊1
Этот материал, возник как попытка аргументировано ответить @RNG_r на его комментарий https://t.me/AsForJsTalks/5593
Я постараюсь сейчас пояснить почему я предельно категоричен в случае применения O нотации к языку Js как не только бесполезному инструменту, но и даже вредному.
Заранее прошу прощения за тон повествования, который может показаться менторским или снисходительным. Я нисколько не преследую этих целей задеть или обидеть. Напротив хочу быть максимально понятым, потому если вдруг будет складываться противоположное впечатления, я прошу отнестись к этому как признак общей эстетической недоразвитости автора.
Мы выносим за скобки саму математику - она для пояснения моего тезиса совершенно не важна. Важно понимание общего принципа.
⎡1. Проблематика⎦
В программировании, мы неизбежно сталкиваемся с рядом типовых задач, которые уже кто-то когда-то решал до нас.
Способы решения подобных типовых задач исследованы вдоль и поперек и зафиксированы в форме соответствующего решению алгоритма.
Очевидно, что решений одной и той же задачи, може быть несколько. Каким образом программист может сделать осознанный выбор, которое из решений ему более всего подходит?
Решением этого вопроса занимается теория сложности вычислений, в рамках которой сформировалось несколько механизмов наглядного описания алгоритма, которые позволяют сделать вывод о его адекватности к тем или иным условиям использования.
Big O нотация - это ОДИН ИЗ механизмов (существуют еще Тета нотация, Сигма нотация и так далее), позволяющих дать оценку алгоритму в плоскости необходимых для выполнения алгоритма шагов (ресурс процессора) и обьемом требуемой, для выполнения этих шагов, памяти ( оперативной, дисковой и т.д.)
Иными словами, когда у программиста возникает необходимость сделать выбор между всем множеством существущих решений, у него нет необходимости вникать в детали каждого алгоритма, но достаточно посмотреть на O нотацию, которая даст ему достаточно информации для того, чтобы сделать выбор в пользу того или иного решения.
⎡1.1. Проблематика => пример⎦
Стоит задача, найти первый индекс заданного символа в любом текстовом файле подаваемом на вход алгоритму.
Мы можем, прочитать условной одной командой весь файл в память и сделать поиск символа.
Такой алгоритм будет иметь наиболее выгодные цифры эффективности алгоритма с точки зрения необходимых для выполнения шагов. И наименее эффективные цифры с точки зрения потребления памяти.
Если у программиста, есть граничные условия на использования памяти. То ему нужно будет искать алгоритм, который не будет читать сразу весь файл в память, а реализует логику чтения в пределах установленого лимита, обеспечивая прозрачное передвижения алгоритма поиска символа по массиву считаных байт, осуществляя дополнительные операции чтения файла в то время, если изначально считанная часть файла не удовлетворила условиям и поиск нужо продолжлать дальше.
Такой алгоритм, с точки зрения сложности, даст худшую характеристику с точки зрения необходимых шагов, но при этом позволит подобрать параметр потребления памяти, который уложится в заданные.
⎡1.2. Проблематика => Резюме⎦
То есть мы для себя выяснили, что необходимость в оценке сложности алгоритма, появилась как ответ на необходимость иметь наглядный эффективный способ представления алгоритма, который бы позволил программисту, без необходимости вникать в его детали, принять решение (спрогнозировать) - удовлетворяет ли алгоритм, тем условиям в которых он решает задачу.
Иными словами, подобная машинерия обязана давать предсказуемый результат на всем множестве используемых решений. В противном случае в ней нет никакого толку.
Запомнили, что оценка вычислительной сложности в плоскости О нотации и ей подобных,
опирается на две фундаментальные характеристики:
1) количество шагов, которое необходимо выполнить для реализации алгоритма. Чем оно меньше - тем эффективнее характеристика.
2) и оценка необходимого количества памяти для обеспечения функционирования этиъ шагов
Я постараюсь сейчас пояснить почему я предельно категоричен в случае применения O нотации к языку Js как не только бесполезному инструменту, но и даже вредному.
Заранее прошу прощения за тон повествования, который может показаться менторским или снисходительным. Я нисколько не преследую этих целей задеть или обидеть. Напротив хочу быть максимально понятым, потому если вдруг будет складываться противоположное впечатления, я прошу отнестись к этому как признак общей эстетической недоразвитости автора.
Мы выносим за скобки саму математику - она для пояснения моего тезиса совершенно не важна. Важно понимание общего принципа.
⎡1. Проблематика⎦
В программировании, мы неизбежно сталкиваемся с рядом типовых задач, которые уже кто-то когда-то решал до нас.
Способы решения подобных типовых задач исследованы вдоль и поперек и зафиксированы в форме соответствующего решению алгоритма.
Очевидно, что решений одной и той же задачи, може быть несколько. Каким образом программист может сделать осознанный выбор, которое из решений ему более всего подходит?
Решением этого вопроса занимается теория сложности вычислений, в рамках которой сформировалось несколько механизмов наглядного описания алгоритма, которые позволяют сделать вывод о его адекватности к тем или иным условиям использования.
Big O нотация - это ОДИН ИЗ механизмов (существуют еще Тета нотация, Сигма нотация и так далее), позволяющих дать оценку алгоритму в плоскости необходимых для выполнения алгоритма шагов (ресурс процессора) и обьемом требуемой, для выполнения этих шагов, памяти ( оперативной, дисковой и т.д.)
Иными словами, когда у программиста возникает необходимость сделать выбор между всем множеством существущих решений, у него нет необходимости вникать в детали каждого алгоритма, но достаточно посмотреть на O нотацию, которая даст ему достаточно информации для того, чтобы сделать выбор в пользу того или иного решения.
⎡1.1. Проблематика => пример⎦
Стоит задача, найти первый индекс заданного символа в любом текстовом файле подаваемом на вход алгоритму.
Мы можем, прочитать условной одной командой весь файл в память и сделать поиск символа.
Такой алгоритм будет иметь наиболее выгодные цифры эффективности алгоритма с точки зрения необходимых для выполнения шагов. И наименее эффективные цифры с точки зрения потребления памяти.
Если у программиста, есть граничные условия на использования памяти. То ему нужно будет искать алгоритм, который не будет читать сразу весь файл в память, а реализует логику чтения в пределах установленого лимита, обеспечивая прозрачное передвижения алгоритма поиска символа по массиву считаных байт, осуществляя дополнительные операции чтения файла в то время, если изначально считанная часть файла не удовлетворила условиям и поиск нужо продолжлать дальше.
Такой алгоритм, с точки зрения сложности, даст худшую характеристику с точки зрения необходимых шагов, но при этом позволит подобрать параметр потребления памяти, который уложится в заданные.
⎡1.2. Проблематика => Резюме⎦
То есть мы для себя выяснили, что необходимость в оценке сложности алгоритма, появилась как ответ на необходимость иметь наглядный эффективный способ представления алгоритма, который бы позволил программисту, без необходимости вникать в его детали, принять решение (спрогнозировать) - удовлетворяет ли алгоритм, тем условиям в которых он решает задачу.
Иными словами, подобная машинерия обязана давать предсказуемый результат на всем множестве используемых решений. В противном случае в ней нет никакого толку.
Запомнили, что оценка вычислительной сложности в плоскости О нотации и ей подобных,
опирается на две фундаментальные характеристики:
1) количество шагов, которое необходимо выполнить для реализации алгоритма. Чем оно меньше - тем эффективнее характеристика.
2) и оценка необходимого количества памяти для обеспечения функционирования этиъ шагов
👍11
При этом тот факт, что основой для оценки алгоритма, является именно количество шагов (или итераций) говорит о том, что каждый подобный шаг имеет единую, общую - константную для каждого шага (итерации), стоимость использования.
В противном случае мы не могли бы опираться на то самое количество.
⎡2. Особенности оценки затраченного времени в шагах⎦
Фундаментальной особенностью всех нотаций подобных O нотации, является количественная мера требуемых шагов, при допущении того, что каждый шаг алгоритма имеет строго детерминированную оценку его стоимости.
То есть каждый шаг затрачивает всегда одно и тоже количество ресурсов.
Именно по этой причине считается количество шагов, чего считается достаточным для оценки сложности вычислений.
⎡2.1.Особенности оценки затраченного времени в шагах => компилируемые языки⎦
Поскольку, характерной чертой компилируемых языков, является, в рамках используемого алгоритма - статичность(неизменность) получаемого кода, то заявленной методологии более чем достаточно для того чтобы получаемый результат соотвествовал прогнозируемому.
То есть, заявленный способ оценки сложности всегда будет точен в относительных цифрах, что и требуется программисту.
⎡2.2. Особенности оценки затраченного времени в шагах => интерпретируемые языки⎦
Отличительной чертой современной архитектуры интерпретируемых языков, является то, что один и тот же код, может быть представлен в принципиально разных формах в зависимости от заложенных в среду критериев реагирования на тот или иной код. Когда, количество итераций, это один из важнейших критериев, который используется подобными средами, для принятия решения о изменении формы исходного исполняемого кода. ( Применения оптимизаций к нему)
Проще говоря, когда количество итераций, переходит какую-то граничную величину, то интерпретируемый код может быть приведен к форме, когда он уже более не интерпретируется, а получает представление на самом низком уровне той архитектуры где выполняется код. И стоимость такой формы, радикально отличается от базовой в сторону сокращения.
При этом, подобная форма, может изменяться несколько раз в процессе работы алгоритма, в том числе и приводить к деградации к представлению, которое будет медленнее чем базовое. То есть с определенного шага, мы можем получить форму, которая будет стоить дороже, чем та с которой мы начали.
Как следствие, стоимость одного алгоритмического шага, в подобных *интерпретируемых средах - не детерминирована*
Что противоречит основному принципу оценки сложности O нотации и ей подобных, где стоимость каждого шага алгоритма должна быть константной.
То есть, можно сформулировать такие условия задачи, которые будут провоцировать ряд шагов со стороны интерпретатора, которые будут приводить к изменению формы исходного кода, как следствие к изменению стоимости каждой итерации, как следствие результатам, которые будет противоречить прогнозу O нотации.
⎡2.3. Особенности оценки затраченного времени в шагах => Выводы⎦
Как мы убедились, применение нотаций, основанных на предположении, что каждая итерация будет иметь одну и туже стоимость в рамках компилируемых языков - справедлива.
Но для интерпретируемых языков, использование методологии, которая опирается на детерминированность используемых ресурсов для выполнения одного и того же кода, являетя в корне неверной, в силу динамичности используемой формы исполняемого кода, производительность которой может как кратно становиться быстрее, так и напротив деградировать в форму потребляющую ресусрво больше чем стартовый код.
⎡3. Проблемы метрики о затраченной памяти⎦
Сделать уверенный прогноз, относительно используемой памяти, можно только в тех языках программирования, где памятью управляют в ручную. Потому как, только в этом случае, мы можем гарантировать ровно туже самую детерминированность в предсказываемом результате.
В противном случае мы не могли бы опираться на то самое количество.
⎡2. Особенности оценки затраченного времени в шагах⎦
Фундаментальной особенностью всех нотаций подобных O нотации, является количественная мера требуемых шагов, при допущении того, что каждый шаг алгоритма имеет строго детерминированную оценку его стоимости.
То есть каждый шаг затрачивает всегда одно и тоже количество ресурсов.
Именно по этой причине считается количество шагов, чего считается достаточным для оценки сложности вычислений.
⎡2.1.Особенности оценки затраченного времени в шагах => компилируемые языки⎦
Поскольку, характерной чертой компилируемых языков, является, в рамках используемого алгоритма - статичность(неизменность) получаемого кода, то заявленной методологии более чем достаточно для того чтобы получаемый результат соотвествовал прогнозируемому.
То есть, заявленный способ оценки сложности всегда будет точен в относительных цифрах, что и требуется программисту.
⎡2.2. Особенности оценки затраченного времени в шагах => интерпретируемые языки⎦
Отличительной чертой современной архитектуры интерпретируемых языков, является то, что один и тот же код, может быть представлен в принципиально разных формах в зависимости от заложенных в среду критериев реагирования на тот или иной код. Когда, количество итераций, это один из важнейших критериев, который используется подобными средами, для принятия решения о изменении формы исходного исполняемого кода. ( Применения оптимизаций к нему)
Проще говоря, когда количество итераций, переходит какую-то граничную величину, то интерпретируемый код может быть приведен к форме, когда он уже более не интерпретируется, а получает представление на самом низком уровне той архитектуры где выполняется код. И стоимость такой формы, радикально отличается от базовой в сторону сокращения.
При этом, подобная форма, может изменяться несколько раз в процессе работы алгоритма, в том числе и приводить к деградации к представлению, которое будет медленнее чем базовое. То есть с определенного шага, мы можем получить форму, которая будет стоить дороже, чем та с которой мы начали.
Как следствие, стоимость одного алгоритмического шага, в подобных *интерпретируемых средах - не детерминирована*
Что противоречит основному принципу оценки сложности O нотации и ей подобных, где стоимость каждого шага алгоритма должна быть константной.
То есть, можно сформулировать такие условия задачи, которые будут провоцировать ряд шагов со стороны интерпретатора, которые будут приводить к изменению формы исходного кода, как следствие к изменению стоимости каждой итерации, как следствие результатам, которые будет противоречить прогнозу O нотации.
⎡2.3. Особенности оценки затраченного времени в шагах => Выводы⎦
Как мы убедились, применение нотаций, основанных на предположении, что каждая итерация будет иметь одну и туже стоимость в рамках компилируемых языков - справедлива.
Но для интерпретируемых языков, использование методологии, которая опирается на детерминированность используемых ресурсов для выполнения одного и того же кода, являетя в корне неверной, в силу динамичности используемой формы исполняемого кода, производительность которой может как кратно становиться быстрее, так и напротив деградировать в форму потребляющую ресусрво больше чем стартовый код.
⎡3. Проблемы метрики о затраченной памяти⎦
Сделать уверенный прогноз, относительно используемой памяти, можно только в тех языках программирования, где памятью управляют в ручную. Потому как, только в этом случае, мы можем гарантировать ровно туже самую детерминированность в предсказываемом результате.
👍10
⎡3.1. Проблемы метрики о затраченной памяти => Интерпретируемые среды⎦
В системах, где задачами распределения этого ресурса, занимается среда выполнения кода, особенностей которые следует учитывать для уверенного прогноза затраченных ресурсов - чрезвычайно много.
Но даже учитывая их все, едва ли можно было бы сделать уверенный прогноз соответствующий критериям O нотации.
⎡3.2. Проблемы метрики о затраченной памяти => Garbage Collector⎦
Типичный пример - срабатывание Garbage Collector-а (GC), в процессе выполнения алгоритма, может вносить значимые флюктуации в результирующее затраченное время. Само по себе срабатывания GC на прямую связано с использованием оперативной памяти. Как следствие, алгоритм, который ставит во главу угла свою производительность за счет чрезмерного расхода той самой памяти, может оказаться не у дел, в силу агрессивной политики стороннего механизма GC.
⎡3.2. Проблемы метрики о затраченной памяти => Особенности представления в памяти данных⎦
Другой типичный пример - это то каким образом в принципе организовывается работа с данными в интерпретируемых средах подобных JS. Характерным отличием которых, является тот факт, что *представление таких данных в памяти - не отвечает ожидаемому*
Например: создание двух идентификаторов, которые ссылаются на одну и туже строку:
Но что еще хуже, если бы мы в силу работы алгоритма сделали что-то подобное этому:
⎡3.2. Проблемы метрики о затраченной памяти => Данные в коде и данные в интерпретаторе могут быть представлены радикально по разному⎦
Другим примером является конкатинация строк, когда существует минимум два поведения среды:
либо действительно создать в памяти новую результирующую строку,
либо создать особую структуру, которая описывает факт конкатинации с сылками на две строки.
И зависит этот выбор от разного набора параметров: первый из которых длина самой строки.
Если строка больше какого-то минимума, то при конкатинации, новая строка никогда не будет создана, но будет создана структура описывающая логику того, где взять части и как их собрать вместе для получения результата.
При этом не стоит забывать, что очистка памяти от строк, на которые больше не ссылаются идентификаторы, происходит только в самых критических случаях, решение о которых принимает тот самый GC.
⎡3.4. Проблемы метрики о затраченной памяти => Выводы⎦
Как было показано выше, распределение памяти, для выполнения необходимых задач в средах, где отсутствует ручное управление, может приобретать неконтролируемые формы в силу особенностей работы алгоритмов GC. Что делает предсказание о расходе подобного ресурса, намного более сложной задачей, нежели простое предположение о инкрементном использовании ресурса.
Сама архитектура среды, может представлять данные в памяти образом, который предполагает целый ряд оптимизаций, исключающих избыточность потребления памяти. Например одни и те-же строки будут представлены один единсвенным образом. Что еще более увеличивает сложность оценки поведения подобного ресурса.
Пример с конкатенацией строк, лишь подчеркивает насколько далеко может зайти в принципе оптимизация процесса использования памяти. Что как минимум, потребует в рамках O нотации, изменение методологии оценки расхода этого ресурса. И, как максимум, сделает его невозможным в принципе.
⎡4. Примеры⎦
А теперь несколько примеров, наглядно демонстрирующих сказанное выше.
В системах, где задачами распределения этого ресурса, занимается среда выполнения кода, особенностей которые следует учитывать для уверенного прогноза затраченных ресурсов - чрезвычайно много.
Но даже учитывая их все, едва ли можно было бы сделать уверенный прогноз соответствующий критериям O нотации.
⎡3.2. Проблемы метрики о затраченной памяти => Garbage Collector⎦
Типичный пример - срабатывание Garbage Collector-а (GC), в процессе выполнения алгоритма, может вносить значимые флюктуации в результирующее затраченное время. Само по себе срабатывания GC на прямую связано с использованием оперативной памяти. Как следствие, алгоритм, который ставит во главу угла свою производительность за счет чрезмерного расхода той самой памяти, может оказаться не у дел, в силу агрессивной политики стороннего механизма GC.
⎡3.2. Проблемы метрики о затраченной памяти => Особенности представления в памяти данных⎦
Другой типичный пример - это то каким образом в принципе организовывается работа с данными в интерпретируемых средах подобных JS. Характерным отличием которых, является тот факт, что *представление таких данных в памяти - не отвечает ожидаемому*
Например: создание двух идентификаторов, которые ссылаются на одну и туже строку:
var theThing = "abc";не приведет к дополнительным расходам оперативной памяти для обеспечения функционирования второго идентификатора. Оба идентификатора будут ссылаться на одну и туже строку в памяти. Об этом позаботиться среда.
var theEnotheThing = "abc";
Но что еще хуже, если бы мы в силу работы алгоритма сделали что-то подобное этому:
var theThing = "abc";это не означало бы, что память используемая для представление строки
var theEnotheThing = "abc";
[...]
theThing = undefined;
theEnotheThing = undefined;
abc была бы освобождена. Более того, если бы где-то ниже в алгоритме снова использовалась бы строка abc то окружение снова бы сослалось на эту строку в памяти. ⎡3.2. Проблемы метрики о затраченной памяти => Данные в коде и данные в интерпретаторе могут быть представлены радикально по разному⎦
Другим примером является конкатинация строк, когда существует минимум два поведения среды:
либо действительно создать в памяти новую результирующую строку,
либо создать особую структуру, которая описывает факт конкатинации с сылками на две строки.
И зависит этот выбор от разного набора параметров: первый из которых длина самой строки.
Если строка больше какого-то минимума, то при конкатинации, новая строка никогда не будет создана, но будет создана структура описывающая логику того, где взять части и как их собрать вместе для получения результата.
При этом не стоит забывать, что очистка памяти от строк, на которые больше не ссылаются идентификаторы, происходит только в самых критических случаях, решение о которых принимает тот самый GC.
⎡3.4. Проблемы метрики о затраченной памяти => Выводы⎦
Как было показано выше, распределение памяти, для выполнения необходимых задач в средах, где отсутствует ручное управление, может приобретать неконтролируемые формы в силу особенностей работы алгоритмов GC. Что делает предсказание о расходе подобного ресурса, намного более сложной задачей, нежели простое предположение о инкрементном использовании ресурса.
Сама архитектура среды, может представлять данные в памяти образом, который предполагает целый ряд оптимизаций, исключающих избыточность потребления памяти. Например одни и те-же строки будут представлены один единсвенным образом. Что еще более увеличивает сложность оценки поведения подобного ресурса.
Пример с конкатенацией строк, лишь подчеркивает насколько далеко может зайти в принципе оптимизация процесса использования памяти. Что как минимум, потребует в рамках O нотации, изменение методологии оценки расхода этого ресурса. И, как максимум, сделает его невозможным в принципе.
⎡4. Примеры⎦
А теперь несколько примеров, наглядно демонстрирующих сказанное выше.
👍9
⎡4.1. Примеры => Память и две разные HOST среды⎦
Неделей ранее, было записано видео, где мы разбирали случай, когда в среде NodeJS, оперирование большим массивом данных состоящим из целых чисел в пределах от 0 до 30бит на число, требовало большего количества ресурсов процессора, нежели такой же обьем данных состоящий из чисел типа Double64. Что было 100% воспроизводимо на 64 битных системах, и показывало более прогнозируемый результат на 32 битных системах.
Причиной которого, стала именно особенность оперирования памятью в случае HOST среды NodeJs, в которой отключены существующие уже два года в оригинальном V8 оптимизации напрямую связанные с работой GC и сжатием указателей для 64 битных систем.
То есть, HOST среда d8 показывала производительность в три раза выше чем среда NodeJs.
И при этом, поведение d8 было предсказуемым для заданных задачей типов чисел (SMI vs Double64)
При этом, производительность в NodeJS удалось привести к состоянию прогнозируемой (целые числа быстрее) и соизмеримой d8, только компенсировав особенности этой HOST среды.
Напомню еще раз, что разница была более чем в три раза.
⎡4.2. Примеры => Рекурсия⎦
Одним из самых показательных примеров проблем O нотации и ей подобных, является оценка сложности алгоритмов использующих рекурсию, против алгоритмов ее не использующих.
O нотация, однозначным образом определяет алгоритмы основанные на рекурсии, как те, которое несоизмеримо хуже чем алгоритмы не использующие рекурсию.
Однако, в V8 по умолчанию, для WASM кода уже год как включена оптимизация, которая носит общизвестное название - хвостовая рекурсия. Алгоритм закрепленный спецификацией ECMA.
Согласно которому, например вычисление тех же чисел фибоначи, произойдет с применением этой оптимизации, которая превратит рекурсивные вызовы функции, в плоский код без единого вызова функции, производительность которого в общем случае будет выше традиционной реализации. Выше в силу того, что подобная оптимизация накладывает на программиста набор правил, следуя которым он получает как гарантии применения оптимизации, так и гарантии получения чрезвычайно оптимизированного кода.
Для JS эта оптимизация пока находится на стадии тестирования.
Хвостовая рекурсия - это стандарт дефакто для функциональных языков, где наличие циклов - то есть итарций вообще исключено. И решение происходит за счет использования абстракции - рекурсия.
Которая благодаря форме хвостовой рекурсии, преобразовывается RunTime в форму эффективнее типичного итерационного цикла.
Как результат O нотация, дает совершенно неверное предсказание относительно используемого алогоритма в подобных условиях.
⎡5. Вместо ИГОГО⎦
Я преследовал цель, наглядно продемонстрировать, что O нотация, не может использоваться как эффективный инструмент, для принятия решений в случае выбора алгоритма, реализация которого будет на языке JavaScript.
Язык JavaScript, как и любой другой динамический интепретируемый язык, живет в мире абстракций чрезвычайно высокого уровня. В котором не может быть место методологии, которая отталкивается от предельно упрощенных способов оценки потребляемых ресурсов базирующихся на детерминированности поведения. Это противоречит природе таких языков.
Иными словами, я заявляю, что на собеседованиях, или где либо еще, когда кто-то требует пояснение JS кода с точки зрения O нотации - этот кто-то некомпетентен.
При этом, я хочу подчеркнуть, что само по себе понимание принципов оценки сложности алгоритмов, в отрыве от их реализации в JavaScript, безусловно положительно скажется на навыках программиста.
Неделей ранее, было записано видео, где мы разбирали случай, когда в среде NodeJS, оперирование большим массивом данных состоящим из целых чисел в пределах от 0 до 30бит на число, требовало большего количества ресурсов процессора, нежели такой же обьем данных состоящий из чисел типа Double64. Что было 100% воспроизводимо на 64 битных системах, и показывало более прогнозируемый результат на 32 битных системах.
Причиной которого, стала именно особенность оперирования памятью в случае HOST среды NodeJs, в которой отключены существующие уже два года в оригинальном V8 оптимизации напрямую связанные с работой GC и сжатием указателей для 64 битных систем.
То есть, HOST среда d8 показывала производительность в три раза выше чем среда NodeJs.
И при этом, поведение d8 было предсказуемым для заданных задачей типов чисел (SMI vs Double64)
При этом, производительность в NodeJS удалось привести к состоянию прогнозируемой (целые числа быстрее) и соизмеримой d8, только компенсировав особенности этой HOST среды.
Напомню еще раз, что разница была более чем в три раза.
⎡4.2. Примеры => Рекурсия⎦
Одним из самых показательных примеров проблем O нотации и ей подобных, является оценка сложности алгоритмов использующих рекурсию, против алгоритмов ее не использующих.
O нотация, однозначным образом определяет алгоритмы основанные на рекурсии, как те, которое несоизмеримо хуже чем алгоритмы не использующие рекурсию.
Однако, в V8 по умолчанию, для WASM кода уже год как включена оптимизация, которая носит общизвестное название - хвостовая рекурсия. Алгоритм закрепленный спецификацией ECMA.
Согласно которому, например вычисление тех же чисел фибоначи, произойдет с применением этой оптимизации, которая превратит рекурсивные вызовы функции, в плоский код без единого вызова функции, производительность которого в общем случае будет выше традиционной реализации. Выше в силу того, что подобная оптимизация накладывает на программиста набор правил, следуя которым он получает как гарантии применения оптимизации, так и гарантии получения чрезвычайно оптимизированного кода.
Для JS эта оптимизация пока находится на стадии тестирования.
Хвостовая рекурсия - это стандарт дефакто для функциональных языков, где наличие циклов - то есть итарций вообще исключено. И решение происходит за счет использования абстракции - рекурсия.
Которая благодаря форме хвостовой рекурсии, преобразовывается RunTime в форму эффективнее типичного итерационного цикла.
Как результат O нотация, дает совершенно неверное предсказание относительно используемого алогоритма в подобных условиях.
⎡5. Вместо ИГОГО⎦
Я преследовал цель, наглядно продемонстрировать, что O нотация, не может использоваться как эффективный инструмент, для принятия решений в случае выбора алгоритма, реализация которого будет на языке JavaScript.
Язык JavaScript, как и любой другой динамический интепретируемый язык, живет в мире абстракций чрезвычайно высокого уровня. В котором не может быть место методологии, которая отталкивается от предельно упрощенных способов оценки потребляемых ресурсов базирующихся на детерминированности поведения. Это противоречит природе таких языков.
Иными словами, я заявляю, что на собеседованиях, или где либо еще, когда кто-то требует пояснение JS кода с точки зрения O нотации - этот кто-то некомпетентен.
При этом, я хочу подчеркнуть, что само по себе понимание принципов оценки сложности алгоритмов, в отрыве от их реализации в JavaScript, безусловно положительно скажется на навыках программиста.
👍15🔥2
В рамках программы - ото делать мне больше нечего
Что можно сегодня почитать:
Язык: Английский
Сложность: Средняя
JavaScript Bytecode
Авторы попробовали на нескольких примерах прояснить, что такое Байт код в V8
Что можно посмотреть:
Язык: Английский
Сложность: Минимальная
YoutTube 25 минут: Franziska Hinkelmann: JavaScript engines - how do they even?
Несмотря на то, что этому видео уже больше 6 лет, оно все еще остается актуальным на уровне формирования общего представления о том, как работает V8.
Что можно сегодня почитать:
Язык: Английский
Сложность: Средняя
JavaScript Bytecode
Авторы попробовали на нескольких примерах прояснить, что такое Байт код в V8
Что можно посмотреть:
Язык: Английский
Сложность: Минимальная
YoutTube 25 минут: Franziska Hinkelmann: JavaScript engines - how do they even?
Несмотря на то, что этому видео уже больше 6 лет, оно все еще остается актуальным на уровне формирования общего представления о том, как работает V8.
❤13🐳1💔1
Что можно сегодня почитать:
Язык: Английский
Сложность: Пред-средняя
Understanding V8’s Bytecode
Что можно посмотреть:
Язык: Русский
Сложность: Минимальная
⎡~1:43:18⎦ Vitaly Bragilevsky: Вводная лекция по теории алгоритмов
Язык: Английский
Сложность: Пред-средняя
Understanding V8’s Bytecode
Что можно посмотреть:
Язык: Русский
Сложность: Минимальная
⎡~1:43:18⎦ Vitaly Bragilevsky: Вводная лекция по теории алгоритмов
👍11❤2🔥2🐳2
Ай нє нє!
Сбор на макароны директору Табора
и его первому помощнику
нам чтобы дожить до конца месяца нужны:
150дол. 90дол
ВСЕ ГОРШОЧЕК НЕ ВАРИ
Кто чем может:
Карта Приват: 5168745021397333
USDT Tron (TRC20): TKoZu59WHiX6L6qvwYTYTsZJerDrnAHBTx
USDT etherium (erc20): 0x75fb8a62dfcf453b2e73f1ef1c407d46f918fffa
bitcoin: bc1qt74aru82v4d3alay7p53jdwkmxe4a5gz7fmvfm2?message=AsForJS&time=1686349743
PayPal: demimurych@protonmail.com
Сбор на макароны директору Табора
и его первому помощнику
нам чтобы дожить до конца месяца нужны:
ВСЕ ГОРШОЧЕК НЕ ВАРИ
Кто чем может:
Карта Приват: 5168745021397333
USDT Tron (TRC20): TKoZu59WHiX6L6qvwYTYTsZJerDrnAHBTx
USDT etherium (erc20): 0x75fb8a62dfcf453b2e73f1ef1c407d46f918fffa
bitcoin: bc1qt74aru82v4d3alay7p53jdwkmxe4a5gz7fmvfm2?message=AsForJS&time=1686349743
PayPal: demimurych@protonmail.com
👍5❤4
👍6
Что сегодня
почитать:
JavaScript engine fundamentals: optimizing prototypes
https://mathiasbynens.be/notes/prototypes
посмотреть:
00:37:45 Вячеслав Егоров — Производительность JavaScript через подзорную трубу
https://www.youtube.com/watch?v=HPFARivHJRY
почитать:
JavaScript engine fundamentals: optimizing prototypes
https://mathiasbynens.be/notes/prototypes
посмотреть:
00:37:45 Вячеслав Егоров — Производительность JavaScript через подзорную трубу
https://www.youtube.com/watch?v=HPFARivHJRY
YouTube
Вячеслав Егоров — Производительность JavaScript через подзорную трубу
Подробнее о конференции HolyJS: https://jrg.su/EM4wwV
— —
Кейноут: Вячеслав Егоров Производительность JavaScript через подзорную трубу
JavaScript конференция HolyJS 2016 Piter
Санкт-Петербург, 05.06.2016
Как JS движки оптимизируют ваш код, и почему тесты…
— —
Кейноут: Вячеслав Егоров Производительность JavaScript через подзорную трубу
JavaScript конференция HolyJS 2016 Piter
Санкт-Петербург, 05.06.2016
Как JS движки оптимизируют ваш код, и почему тесты…
❤4👍3❤🔥1
6:45 по Киеву.
Обсудим часть интервью D. Crockford: Why We Should Stop Using JavaScript
Обсудим часть интервью D. Crockford: Why We Should Stop Using JavaScript
YouTube
⎡msk⎦ ⎡talks⎦ Обсудим часть интервью D. Crockford: Why We Should Stop Using JavaScript
С Douglas Crockford было сделано большое интервью. Где в том числе, он высказывался о языке JavaScript.
Слова этого великого человека, вырванные из контекста, сейчас используются образом, искажающим смысл, который вкладывал он отвечая на заданный ему вопрос.…
Слова этого великого человека, вырванные из контекста, сейчас используются образом, искажающим смысл, который вкладывал он отвечая на заданный ему вопрос.…
❤3
09:30 По киеву
Разбираем видео: "Продвинутый JS (Григорий Бизюкин)"
Меня всегда интересовал один вопрос, почему от Яндекс, выступают люди, которые уже на протяжении нескольких лет рассказывают чушь с экрана, в то время, когда у них есть действительно сильные специалисты.
Прогнозируемое время около 2х часов.
Разбираем видео: "Продвинутый JS (Григорий Бизюкин)"
Меня всегда интересовал один вопрос, почему от Яндекс, выступают люди, которые уже на протяжении нескольких лет рассказывают чушь с экрана, в то время, когда у них есть действительно сильные специалисты.
Прогнозируемое время около 2х часов.
YouTube
⎡msk⎦ Разбираем видео: "Продвинутый JS (Григорий Бизюкин)"
Разберем видео, где его автор - Григорий Бизюкин, буде говорить о продвинутом JavaScript.
Меня всегда интересовал один вопрос, почему от Яндекс, выступают люди, которые уже на протяжении нескольких лет рассказывают чушь с экрана, в то время, когда у них…
Меня всегда интересовал один вопрос, почему от Яндекс, выступают люди, которые уже на протяжении нескольких лет рассказывают чушь с экрана, в то время, когда у них…
👍7😍7