highly professional scums

Компания google выложила библиотечку компрессии snappy http://code.google.com/p/snappy/. Библиотечка сжимает и разжимает со скоростью работы  SSD дисков, правда коэффициент компрессии не фонтан, хуже gzip. Но с дурацкими lzo, quicklz и прочей шушерой вполне сравнима.

Сразу захотелось поглядеть внутрь, что там. Внутри вариации на тему lz, 70 годы прошлого века.  Отсюда  поинт - вечное не тухнет. Что такое lz? Это две команды. Первая команда “прочитай N байт из потока и положи в буфер распаковки”, вторая команда “прочитай из буфера распаковки по смещению OFFSET от текущей позиции MATCH байт и опять положи в буфер распаковки”.

Компрессор snappy так и жмет примерно.  Он умеет кодировать OFFSET с помощью 1, 2 или 4 байт.

Сразу захотелось написать свое. Выходные, все такое. Решил, что мой код будет еще проще. Буду кодировать OFFSET с помощью 1 байта, всегда. А методу распаковки выдам лимит в 32 строчки С++ кода.

Родилось вот такое: http://www.everfall.com/paste/id.php?o3ug124i2l7p . Назовем его yappy.

Код распаковки там со строчки 14 по 45. Кроме распаковки там нет ничего интересного. Разве что эвристика, как выбираются 224 разных значения пар [OFFSET / 256: MATCH].

Сразу захотелось измерить пипиську творению.

Возьмем тестовые данные от snappy,  положим их без компрессии в tar архив, сожмем.

SNAPPY: [b 4096K] bytes 4638720 -> 2165687 46.7%  comp 214.9 MB/s  uncomp 683.6 MB/s

SNAPPY: [b 4K] bytes 4638720 -> 2445428 52.7%  comp 226.9 MB/s  uncomp 681.2 MB/s

За буковкой b идет размер блока в килобайтах. А теперь сожмем yappy:

YAPPY: [b 4096K] bytes 4638720 -> 2021663  43.6%  comp  49.2 MB/s  uncomp 1432.3 MB/s

YAPPY: [b 4K] bytes 4638720 -> 2268955  48.9%  comp  49.2 MB/s  uncomp 1476.1 MB/s

Видно две вещи. Вещь первая - что google выложил неудачные тестовые данные. Они слишком короткие, чтобы snappy со своими смещениями в 2 и 4 байта мог развернуться. Очевидно, что на больших продакшн данных все должно сжиматься лучше. Вещь вторая, что программисты google кабаны, они сделали чертовски быструю компрессию.  Собственно, ради чего все и затевалось - чтобы быть всюду быстрее сети и диска.

А теперь… Возьмем одну из компонент продакшн индекса в Яндексе. Она блочная, блоки по 4k. Готовится оффлайн, время компрессии нас не очень волнует.

Сожмем snappy и yappy.

SNAPPY: [b 4K] bytes 1328385387 -> 750585721 56.5%  comp 182.2 MB/s  uncomp 623.4 MB/s

YAPPY: [b 4K] bytes 1328385387 -> 686910077  51.7%  comp  48.5 MB/s  uncomp 1399.8 MB/s

Отсюда  мораль. Тырьте хорошие идеи, тырьте у грандов. И, вдруг, получите немножко технического экселенса, который приятен.

Оклюжен кулинга сейчас наверное нету только у ленивых. Некоторые используют HW OC, у которых есть очевидные недостатки в виде латентностии какой никакой нагрузки на гпу. Другие используют софтовую растеризацию. К примеру, мы можем растеризовать глубину близлежащих оклюдеров ( специальной или прямо рендер геометрии ), затем проверять баунд боксы отрисовываемых объектов относительно этой глубины. Радостей от такого подхода может быть несколько. Во-первых, мы может рисовать это всё в уменьшенном разрешении. Во-вторых, такая отрисовка достаточно легко паралелится на несколько потоков, что в наше время непрерывного увеличения числа ядер у цпу является приятным бонусом. Для растеризации есть два основных алгоритма - сканлайны и халфспейсы. При использовании сканлайнов мы просто рисуем горизонтальные линии межде ребрами треугольника. При использовании халфспейсов - строим вьюпорт спейс баунд рект треугольника, итерируемся по всем пикселям которые в нём, и, если пиксель внутри треугольника то рисуем его. Но в целом нам достаточно определить сам факт того, скрыта ли тестируемая геометрия оклюдерами или нет.

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

1. Трансформировать треугольники в вьюпорт спейс
2. Определить границы тайлов
3. Распределить треугольнички по всем тайлам, которых они касаются
4. Отсортировать от ближних к дальних очереди треугольников каждоготайла (использую zmin для тест треугольников и zmax для треугольников оклюдеров)
5. Нарисовать отсортированные списки ( для тест треугольников проверяется виден ли какой либо пиксель его сканлайнов, для оклюдеров записываются битики сканлайнов в буфер тайла)

Вообщемто базовую версию алгоритма не сложно реализовать и проверить самим. Моя текущая имплементация может рисовать 300к+ треугольников снапшота с игровой камеры Death Track примерно за 20мсек ( 12 мсек трансформаци + 8 мсек растеризация ) в 720п, что не плохо. И надо понимать что это однопоточная синхронная версия. Думаю, на архитектурах с большим числом регистров будет чуть лучше. Если прикрутить потоки - опять же думают станет ощутимо лучше. Очень органично ложится на концепцию Job Manager. Интересным также выглядит попытка автоматической генерации оклюдеров и тест геометрии. Респекты и уважухи Пете за крутую идею и обсуждение деталей реализации.

А ещё опубликовал в своём секретном бложике

Есть три задачи. Задача первая - решить матричное уравнение A x = b, где A - матрица, x - неизвестный вектор, а b - заданная правая часть, опять вектор. Коэффициенты - действительные числа.

Во второй задаче коэффициенты (и у матрицы и у векторов) - целые числа.

А в третьей задаче все то же самое, только коэффициенты целые положительные, и уравнение надо решить в целых положительных числах.

Накал пиздеца постепенно крепчает. Целые числа мы не всегда можем делить друг на друга. Впрочем, взяв пару чисел (a, b), мы можем вычесть из большего по модулю числа меньшее по модулю, и такая процедура редукции нам отлично заменит деление.

А целые положительные числа мы можем вычитать, только меньшее из большего.

Однако, алгоритм Гаусса решения линейных систем уравнений работает во всех трех случаях (на то он и Гаусс).

Умные дядьки про третью задачу пишут страшное, примерно такое: http://documents.kenyon.edu/math/CWendler.pdf Это страшные люди, разобраться в их алгебре практически невозможно.

Попытаюсь на пальцах.

Continue reading ‘Три задачи с одним решением’ »

“n-way ассоциативный продьюсер”

тяжела доля моя консультантская
Continue reading ‘это очень интересно, что там спрятано внутри’ »

Наш уважаемый shodan горячо зажег на devpoint.

А так как он скромный,  и линк сам не запостит, то придется самому:

http://devpoint.ru/video/f/devpoint2/46778_Andrey_Aksyonov_vtoroy_doklad.html

Так как по тексту упоминается 3D полигон, то вовсе не оффтопик.

Конечно, есть к докладчику замечания - щитаю, что много текста и мало картинок! Есть куда двигаться, чтобы было совсем заебок.

Вот: http://company.yandex.ru/public/yac/

Ваш покорный слуга выступает в качестве содокладчика Ильи Сегаловича (это технический директор Яндекса). О чем успею рассказать за 30 минут - не знаю. Хотелось бы чуть-чуть о поисковом теке рассказать. Приходите, регистрация свободная, вам наверняка будет занятно послушать про совсем другие, нежели в игроделании, технические проблемы.

Примерные слайды: “что дешевле, железка или мозги”, “сжать до меньше энтропии”, “мегаэффективный нанопараллелизм”

Как известно, художники любят большие детализированные текстуры. Такие, что в игре видны только их мипмапы ненулевого уровня. Например, текстура 512×512 на наконечнике копья.
Борис Баткин рассказывал про интересный трюк, как быстро находить такие текстуры в игре: надо в загрузчике текстур заменить мипмапы на отладочные. У которых нулевой мип-уровень залит зелёным цветом, 1-й синим, 2-й - жёлтым, 3й - оранжевым, 4й и дальше - красным. Таким образом, если камера вблизи объекта и он не зелёный - это повод бить тревогу.
Continue reading ‘Разноцветные мип-мапы’ »

всё очень и очень неинтересно

/me ОРЁТ: гадкий кризис это очень и очень хорошо. чем хуже, тем лучше. чем гаже, тем быстрее сдохнут софтверные патенты. повсеместно.

Определение: коэффициент пидорастичности текстуры (или любого другого файла):
размер текстуры в байтах, делённый на степень сжатия в zip.

напр. если файл в 800 байт сжимается до 400, то его коэффициент равен 800/(400/800) = 1600

Скрипт для нахождения самых пидорских текстур (напр. одноцветного голубого неба 2048×2048 в RGBA формате):
Continue reading ‘Коэффициент пидорастичности файла.’ »