Попалась на глаза очень прикольная статья Сид Балы про объяснение принципа работы кодека H.264 — "H.264 is Magic". Перевод статьи на русский язык есть на хабре.

H.264 используется при передачи видеопотока, в формате Blu-ray, в телефонах и т.п. При кодировании фрейма производится сжатие с потерями с использованием частотного пространства. Потом производится цветовая субдискертизация, которая обрабатывает закодированные цвета таким образом, чтобы изображение использовало меньшее количество цветов.

После обработки фреймов наступает этап кодирования компенсации движения, когда выделяется базовый фрейм I-frame и последующие фреймы, которые кодируют смещение блоков 16x16 пикселей базового фрейма. Это позволяет эффективно сжимать движущиеся изображения на статичном фоне. После кодирования компенсации движения применяется энтропийное кодирование.

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

#algorithm #video

https://sidbala.com/h-264-is-magic/

Рич Снапп написал статью с объяснением того, почему лучше отказаться от использования reduce вместе со spread объектов — "The reduce ({...spread}) anti-pattern".

В современном JavaScript код для создания объекта из массива объектов с одинаковыми свойствами можно написать так:

let result = items.reduce((acc, item) => ({
   ...acc, [item.name]: item.value
}), {})

Как оказывается в v8 такой код будет выполняться с квадратичной сложностью. Рич доказывает существование этой проблемы, разбирая байткод, который генерирует движок. В качестве альтернативы он предлагает использовать reduce с мутированием, или for...of, которые справляются с этой задачей за линейное время.

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

#v8 #performance #algorithm

https://www.richsnapp.com/blog/2019/06-09-reduce-spread-anti-pattern

Никита Прокопов поделился своим опытом участия в ICFPC — международном соревновании команд программистов.

Соревнование шло три дня. Задание состояло в том, чтобы реализовать наиболее эффективный обход лабиринта с заданными ограничениями. Автор пишет, что Clojure не очень хорошо подходит для решения подобных задач, потому что итоговая оценка зависит от производительности написанного решения. Это подтверждается результатами соревнований. За несколько последних лет всё больше призовых мест берут команды, использующие C++, Java, JavaScript и т.п. Ирония в том, что соревнование приурочено к конференции по функциональному программированию.

Никита размышляет по поводу того, что можно было бы сделать по-другому: заранее подготовить инфраструктуру, больше использовать защитное программирование, создавать инструменты, помогающие в решении задачи, полноценно отдыхать.

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

#contest #algorithm

https://tonsky.livejournal.com/322258.html

Вчера на calendar.pefrplanet.com была опубликована статья Ника Джансма — разработчика Akamai — про оптимизацию библиотеки для сбора RUM (Real User Metrics) — "Boomerang Performance Update".

Boomerang — это библиотека с открытым исходным кодом. Она используется под капотом mPulse (сервис для сбора RUM-метрик от Akamai). В 2017 году был проведён аудит Boomerang, который выявил узкие места. Загрузчик основного скрипта использовал динамически создаваемый iframe. На старых девайсах создание iframe несло дополнительные издержки, увеличивая время инициализации на 20-40мс. После перехода на link preload в браузерах, которые его поддерживают, время инициализации уменьшилось до 1мс. Для сбора таймингов ресурсов сайта, они используют префиксное дерево (Trie), которое также было неоптимизировано. После исправления функция оптимизации дерева стала работать в четыре раза быстрее. Чтобы уменьшить размер основного скрипта, алгоритм хеширования MD5 был заменён на FNV-1. Скрипт уменьшился на 8 килобайт.

Статья очень интересная. Рекомендую почитать всем, кто интересуется темой оптимизации сайтов.

#performance #algorithm #library

https://calendar.perfplanet.com/2019/boomerang-performance-update/

Есть очень быстрая библиотека для работы с картами — Leaflet (используют в Facebook, Github, 2ГИС). Она была разработана Владимиром Агафонкиным. Вова помешан на производительности; и вот месяц назад он рассказал доклад "Fast by default: algorithmic performance optimization".

В докладе он рассказывает про случаи из практики, где применение алгоритмов помогло сильно оптимизировать код. Разобрал конкретные паттерны в коде, которые должны вызывать подозрение. В конце доклада поделился такими мыслями:
— изучайте исходный код инструментов и библиотек;
— копайтесь в фреймворках;
— участвуйте в open source проектах;
— не бойтесь изобретать колесо;
— постоянно упрощайте свой код;
— оптимизируйте свой код, это научит вас писать быстрый код сразу.

В общем, доклад крутой. Рекомендую посмотреть.

#talk #performance #algorithm

https://www.youtube.com/watch?v=hh6SohUq1yQ&feature=youtu.be

Гергели Орос — технический руководитель из Uber — рассказал про алгоритмы и структуры данных, с которыми ему приходилось сталкиваться на протяжении карьеры — "Data Structures & Algorithms I Actually Used Working at Tech Companies".

В статье есть много примеров использования алгоритмов: от обхода DOM-дерева для добавления поддержки голосового ввода для Skype на Xbox OS до гексогональных гридов с иерархическими индексами в Uber для оптимизации цены поездок. Интересная задача была в Skyskanner с поиском наиболее дешёвых билетов с маршрутом через несколько городов. Для её решения была использована модифицированная реализация алгоритма A*.

В статье есть мысли по поводу использования алгоритмических задач на собеседованиях, которые сейчас особенно популярны в Долине для поиска сильных инженеров. Но Гергели пишет, что не задаёт сложных алгоритмических задач на собеседованиях, и это не помешало ему собрать сильные команды разработчиков.

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

#algorithm #musings

https://blog.pragmaticengineer.com/data-structures-and-algorithms-i-actually-used-day-to-day/

Андрей Печкуров написал статью про внутреннее устройство Map в V8 — "[V8 Deep Dives] Understanding Map Internals".

В V8 для Map используется детерминированная хэш-таблица (deterministic hash table) — структура данных, которая гарантирует порядок обхода хранящихся в ней значений (в порядке их добавления в Map). Все данные для организации структуры данных находятся в одном большом массиве, который поделён на три логические части: заголовок, хэш-таблицу и данные. При добавлении и удалении значений из Map алгоритм периодически создаёт новую таблицу, поэтому операции вставки и удаления могут иметь временную сложность O(N). Операция извлечения данных из Map работает за O(1).

Интересная статья. Рекомендую почитать, если интересуетесь тем, как работает V8 изнутри.

#internals #v8 #algorithm

https://itnext.io/v8-deep-dives-understanding-map-internals-45eb94a183df

Артём Караваев на хабре написал статью о том, как складывать числа с плавающей запятой без потери точности.

Зачем это нужно. Представьте, что у вас есть большой массив чисел с плавающей запятой, и вам надо найти их сумму. Чем больше будет массив тем больше будет ошибка в вычислении из-за накопления погрешности.

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

s = a+b; // сумма
z = s-a;
t = b-z; // погрешность

Очень хорошая статья. Рекомендую почитать всем, кто заинтересовался этой темой.

#math #algorithm

https://habr.com/ru/post/523654/

Нашёл статью Эрика Лоуренса, в которой рассказывается про историю появления алгоритма сжатия Brotli.

Brotli — это детище Google, которое было разработано Юрки Алакуйяла и Золтаном Сабадка. До Brotli Юрки разработал алгоритм сжатия Zopfli, который был совместим с DEFLATE, но работал на 5% лучше всех альтернатив. Brotli — это идейное продолжение Zopfli, комбинирующее алгоритм Хаффмана и LZ77. Он был разработан для формата шрифтов WOFF2, но потом был адаптирован для сжатия передаваемых данных между браузером и web-сервером.

Ребята из Google до внедрения Brotli экспериментировали с другими форматами сжатия (bzip2, SDCH). Во время экспериментов иногда возникали проблемы совместимости с промежуточными прокси-серверами и шлюзами, поэтому для предотвращения проблем доставки данных было решено сделать так, чтобы Brotli был доступен только по HTTPS.

Статья была написана в 2015 году, и уже утекло много воды, например, поддержка Brotli появилась во всех актуальных браузерах. Тем не менее статью интересно почитать, как исторический артефакт.

#performance #algorithm #history

https://textslashplain.com/2015/09/10/brotli/

Алексей Трехлеб из Uber написал статью про изменение размера изображения с помощью алгоритма Seam Carving — "Изменение размеров изображения с учётом его содержимого в JavaScript".

Основная идея алгоритма Seam Carving заключается в изменении размера изображения с сохранением пропорций объектов изображения с помощью удаления "швов" — последовательности смежных пикселей с наименьшей энергией, идущих от одного края изображения к другому. Пикселем с наименьшей энергией считается такой пиксель, который очень похож на свои соседние пиксели. Для вычисления этой метрики используется формула:

const lEnergy = (lR-mR) ** 2 + (lG-mG) ** 2 + (lB-mB) ** 2;
const rEnergy = (rR-mR) ** 2 + (rG-mG) ** 2 + (rB-mB) ** 2;
const result = Math.sqrt(lEnergy + rEnergy);

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

Крутая статья. Очень рекомендую почитать.

#algorithm

https://trekhleb.dev/blog/2021/content-aware-image-resizing-in-javascript/
https://vas3k.club/post/9637/ (на русском языке)

Не пишите квадраты

Степан Зубашев критикует современные тренды написания JavaScript-кода — "Обращение к Javascript-сообществу: перестаньте писать квадраты".

Популярность функциональных методов для работы с массивами и современные фичи JavaScript открыли двери для очень лаконичного кода. Но иногда чрезмерное увлечение лаконичностью приводит к падению производительности. В статье на примере использования .concat() внутри .reduce() рассказывается, почему это может оказаться серьёзной проблемой.

source.reduce(
  (acc, item) => acc.concat(func(item)),    
  [] 
);

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

Степан призывает не ставить в абсолют краткость кода и задумываться о производительности.

#js #algorithm #performance

https://habr.com/ru/post/590663/