ClosedCircles - #gamedeff going social
ClosedCircles - How coversations work

Как понятно из предыдущих серий, ClosedCircles формируют очень закрытые коммьюнити. Действительно, если вы не добавили человека в свой список - вы никогда не увидите, что он пишет по определению. Спрашивается - как же в такой системе люди вообще узнают друг о друге?

Есть несколько способов:

Friend List

Можно тыкнуть на Friend List и посмотреть, кто вообще еще есть на сервисе:

В Friends of Friends много народу, добавляйте тех, кого знаете. Линк в имени ведет на Facebook/G+ profile, в будущем мы добавим ЖЖ, Твиттеры итд.

Intro threads

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

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

Кроме представлений, интро-треды можно использовать многими разными способами - я, например, транслировал в реалтайме доклады с GDC. Надо попробовать лекцию устроить - есть еще идеи?

Интро-треды может делать каждый - надо тыкнуть на кнопку New Intro (над edit box) и выбрать, кто в нем будет учавствовать, галочками в контакт-листе.

Постить интересные дискуссии

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

О важном

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

Посему - даже с такими слабыми механизмами discovery, добавляйте осторожно.
“Скажи мне, кто твой друг, и я скажу тебе, кто ты”

Линки чтобы попробовать это все на себе - #gamedeff, #programming

В целом, все проходит более гладко чем я ожидал. ClosedCircles - новый медиум общения, который поначалу рвет башку, но к нему привыкаешь.

Давайте я опишу самое базовое.

Итак, как говорилось раньше, у каждого свой список людей в каждом топике, и кажому гарантируется что то, что он пишет - могут видеть только люди из его списка. Спрашивается, как это вообще работает? Ведь если просто взять групчат и прикрутить к нему фильтр по авторам сообщений, будут видны обрывки разговоров людей в твоем списке c людьми вне твоего списка! Причем они этого понимать не будут, у них же свой список! ААААААА!!

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

Смотрите, как это работает.

Предположим, у нас есть пользователи Барбара, Шэрон и Джен. Шэрон очень социальна и дружит со всеми, а Барбара и Джен друг друга не знают (real life story). Вот как выглядят их “социальные круги”:

Дженнифер нажимает кнопку “New Thread” и пишет сообщение, его видят все ее контакты:

Шэрон отвечает на это сообщение - для этого она тыкает на сообщение мышкой (сообщение подсвечивается синим) и потом вводит ответ. Видите там “reply @Jennifer”?
Этот ответ видит пересечение контактов Шэрон и Джен, то есть не видит Барбара, хотя они с Шэрон и друзья:

Это очень важный момент. Из-за того, что Шэрон выбрала ответ, ее сообщение не увидела Барбара, которая у нее в списке. Если бы Шэрон ошиблась и не тыкнула на сообщение Джен, ее ответ увидела бы и Барбара и ничего не поняла - причем тут node? Поэтому выбирать ответы надо обязательно. К счастью, привыкаешь быстро.

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

Последнее, что стоит упомянуть - что можно написать новое сообщение сразу какому-то пользователю, без ответа на другое. Для этого нужно тыкнуть на имя пользователя в списке контактов. Вот например Барбара пишет Шэрон. Разумеется, это увидит пересечение их контактов:

Это, на самом деле, не такой новый концепт. Почти так в Твиттере - в своей ленте ты видишь только ответы тех кого ты фолловишь к тем, кого ты фолловишь. И это крайне необходимая часть Твиттера, без нее он бы не работал.

Bottomline

К счастью, про все эти круги, пересечения и кто что видит - думать не надо. Есть всего два правила:
- Выбирай, на какое сообщение отвечаешь
- Добавляй только тех, кому доверяешь видеть все, что ты пишешь в этом канале

Треды, треды, треды

Кроме приватности, необходимость ответов структурирует чат удивительно полезным образом:
- Дискуссия сама по себе разбивается на треды, которые удобно читать отдельно, особенно когда скопилось 100+ сообщений (дабл-клик на сообщение покажет только его тред).
- Можно вменяемо вести несколько дискуссий, переключая треды
- Почти никогда не надо уточнять, к чему относился короткий ответ “да” или “нет”
- Нотификации становятся умнее - оно знает, что отвечают тебе, это куда лучше нотификаций в Skype и IRC.
- Hidden bonus: тыкните на разделитель слева, где написано threads

И там еще масса интересных следствий, stay tuned!

Линки чтобы попробовать это все на себе - #gamedeff, #programming

Чтобы было понятней, давайте я вкратце расскажу с чего все начиналось.

Как запечатлено в немногословной, но яркой хронике, gamedeff появился в 2004 году (страшно подумать, 8 лет скоро) после того, как на IRC-канале #gamedev сайта gamedev.ru стало слишком много шума.

Доступ был исключительно закрытым, новые люди исключительно по приглашениям и рекомендациям, жило это все на приватном IRC-канале #gamedeff. Оказалось, что это совершенно офигенный формат общения, народ стал подтягивать вменяемых знакомых и логи #ff читались до утренней почты и ЖЖ-ленты.

В 2007 году мы стали писать http://blog.gamedeff.com и достаточно активно писали до 2011.

В разное время размер тусовки менялся от, наверное, человек 7 до 30, с несколькими закатами и рассветами.

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

Итак, мега-тезис!

Уютные тусовки распадаются по двум (!) причинам:
* Слишком много новых людей
* Слишком мало новых людей

Это должно быть в общем-то очевидно, но на всякий случай подробнее.

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

А если новых людей слишком много, то скоро народ почувствует “кто все эти люди???” и общение, к которому они привыкли, потеряется в потоке остального. Тусовка вполне может выжить, но уже с другими людьми. Это то, как становятся популярными любые ресурсы и то, почему вы на них ходите меньше и с тоской вспоминаете про былые дни.

И с этой динамикой очень сложно что-то сделать, будь то Facebook group, LJ community, Skype group chat или IRC channel. Хуже того, чем больше народу - тем сложнее балансировать, что ограничивает размер коммьюнити.

И вот под благодатным Калифорнийским солнцем появилась идея.

Представьте себе групчатик, в котором список участников - у каждого свой. Разделенный на каналы, примерно как в IRC, но на каждом канале каждый добавляют людей сам.

Вот как, например, выглядит мой контакт-лист и Лехи Власова:

Как видно, контакт-листы пересекаются, но не одинаковы. Каждому гарантируется, что то, что он пишет, могут увидеть только те, кого он сам добавил в свой список. И так - для каждого участника.

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

Предвосхищая вопросы - в такой модели все интересно, это аццкая смесь G+, Twitter и IRC, я буду потихоньку ее описывать.

И главная прелесть концепта в том, что всей тусовке не надо быть закрытой, каждый выбирает степень уютности сам. Посему - кому интересно попробовать и пообщаться с нами, присоединяйтесь!

Это канальчик про разработку игр:
http://closedcircles.com/?invite=5283f620e93090c04650f50c58b225799b6d0755
Это про программирование вообще:
http://closedcircles.com/?invite=40830ab442b74e72f4f8dd795829490ef04a599e
Логиниться лучше через Фейсбук, чтобы оттуда сразу добавились контакты. Не беспокойтесь, Фейсбук только для логина, мы никогда ничего туда не постим.

Имейте ввиду, все в режиме раннего прототипа, поэтому подразумевается терпение и, что называется, early adopter mindset.

Сразу захотелось поглядеть внутрь, что там. Внутри вариации на тему 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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, хотим мы решить системку линейных уравнений в действительных числах. Берем какую-то 4×4 матричку коэффициентов A, приписали справа единичную матрицу со знаком минус.

7.00 8.00 2.00 5.00 |-1.00 0.00 0.00 0.00
3.00 3.00 9.00 8.00 | 0.00 -1.00 0.00 0.00
2.00 9.00 8.00 9.00 | 0.00 0.00 -1.00 0.00
1.00 7.00 3.00 3.00 | 0.00 0.00 0.00 -1.00

Получили 4 вектора длины 8, я разделяю их на две части знаком |, но это чисто визуализация, алгоритм работает с длинными векторами без всякого деления на половинки.

Упорядочим вектора в лексикографическом порядке и применим полную редукцию (алгоритм Гаусса - Бухбергера, назовем так этот процесс). Редукция вектора x по вектору y определяется просто - находим первый ненулевой коэффициент y_i и заменяем x на x - (x_y / y_i) * y. Убили x_i, молодцы, получили лексикографически меньший вектор. Будем редуцировать вектор из набора по всем остальным векторам, пока хоть что-то меняется. Для красоты я еще отнормирую вектора, чтобы первый ненулевой коэффициент был 1. Это мелочь.

Отредуцировали, получили вот такую красивую картинку:

1.00 0.00 0.00 0.00 |-0.13 -0.15 0.24 -0.09
0.00 1.00 0.00 0.00 | 0.00 0.04 0.03 -0.20
0.00 0.00 1.00 0.00 | 0.09 -0.32 0.39 -0.48
0.00 0.00 0.00 1.00 |-0.06 0.28 -0.55 0.65

Слева стоит единичная матрица, справа - какая-то. Замечу, что мы могли взять неквадратную матрицу коэффициентов, могли взять вырожденную матрицу. В алгоритме ничего не поменялось бы.

Решим теперь уравнение A x = b. К вектору b припишем справа нули, и полученный вектор длины 8 редуцируем относительно полученного базиса.

560.00 1763.00 1887.00 1882.00 | 0.00 0.00 0.00 0.00

Вуаля!

0.00 0.00 0.00 0.00 | 1.00 -96.01 -94.00 -91.01

Слева у нас нули, справа - искомый вектор x, решение. Если бы редукция не удалась (b не лежало бы в образе A), то у нас слева были бы ненулевые числа. Такой прикольный алгоритм Гаусса для произвольных систем. Линейка, ВУЗ, первый курс.

Повторим процесс для целочисленных векторов, матрица такая же, как и для предыдущего варианта.

7 8 2 5 | -1 0 0 0
3 3 9 8 | 0 -1 0 0
2 9 8 9 | 0 0 -1 0
1 7 3 3 | 0 0 0 -1

Применяем редукцию Гаусса-Бухбергера… Стоп, а как редуцировать один целочисленный вектор относительно другого? Ответ. As simple as x - y или x + y. Находим как и раньше первый ненулевой элемент y_i и смотрим, можем ли мы операцией + или минус уменьшить абсолютное значение x_i (читай, уменьшить вектор относительно лексикографического порядка). Редуцируем систему векторов, пока можем, получаем:

1 0 -2 -23 | 1 -6 12 -14
0 -1 1 19 | -1 5 -10 12
0 0 -3 -92 | 5 -25 49 -58
0 0 0 209 | -12 59 -114 135

Как и раньше, для решения уравнения A x = b берем b, приписываем к нему справа четверку нулей, редуцируем полученный вектор:

560 1763 1887 1882 | 0 0 0 0

относительно системы. Получаем… Шайтан, решение:

0 0 0 0 | -1 96 94 91

Напомню, если слева у нас получились не нули (которые дальше не хотят редуцироваться ни одним из векторов системы), то пиздец - решения нету. Иначе читаем решение в правой части. Например, наша система не имеет решения для любых векторов b = (0, 0, 0, число не кратное 209). Теория чисел, хороший ВУЗ, третий курс.

Двигаемся дальше. Все то же уравнение A x = b, но в целых положительных числах. Что надо делать, мы уже знаем - нарисовать вот такую красоту надо:

7 8 2 5 | -1 0 0 0
3 3 9 8 | 0 -1 0 0
2 9 8 9 | 0 0 -1 0
1 7 3 3 | 0 0 0 -1

Редуцируем систему… Функция редукции x относительно y очень простая - определим для вектора v положительную часть v+, как поэлементную операцию {max(v_i, 0)}. Скажем, что x можно редуцировать относительно y, если x+ поэлементно не меньше y+, а сама редукция равна в этом случае x - y. Редукция опять уменьшает вектор в лексикографическом смысле. Кроме этого она заебатая тем, что редукция от вектора с неотрицательными элементами снова неотрицательная. К сожалению, так просто все не работает. Редукции запрещают друг друга. Т.е. у нас есть выбор редуцировать вектор x с помощью вектора y или c помощью вектора z, каждый выбор в общем запрещает другую редукцию. Поэтому Бухбергер предложил очень простую вещь. Он сначала полностью редуцирует систему векторов друг относительно друга, а потом добавляет N^2 попарных разностей u - v. И действует так, пока базис не становится стабильным. Чудеса заключаются в том, что хоть число базисных векторов и растет (вообще говоря неконтролируемо), наш процесс останавливается. Добавление попарных разностей u - v гарантирует, что в процессе градиентного спуска мы не залезем в локальную яму.

Для данной системы результат выглядит как (осторожно, длинная простыня чисел):

http://www.everfall.com/paste/id.php?1ydzx51iwu6v

Хороший математический ВУЗ, кандидатский минимум по алгебре, “алгоритм Бухбергера построения базиса Гребнера в идеале полиномов”.  Это он и есть. Я только аккуратно закамуфлировал в алгоритме полиномы, так что их почти не видно.

Решаем систему, редуцируем вектор

560 1763 1887 1882 | 0 0 0 0

получаем (по свойству редукции опять вектор с неотрицательными компонентами):

0 0 21 17 | 0 94 93 92

В прошлой части мы получили решение с одной отрицательной компонентой. А вот тут обломились. Нету положительных решений. А вот для правой части b = (903 2155 1985 2127) находится решение x = (48 96 94 91). Если решений несколько, найдется лучшее с точки зрения лексикографического порядка.

Как маленький штришок, можно децл модифицировать алгоритм, и он будет искать не просто решение, а решение, где максимизируется целевая линейная функция. Т.е. вчистую решать задачи целочисленного линейного программирования. Надо всего лишь взять порядок не лексикографический, а чуть более другой. Но это в сторону.

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

сорцы:

http://www.everfall.com/paste/id.php?rpf69siiusru

внутри там, очевидно, какой-то способ выделить кусок памяти. в который мы скопируем результаты, по unlock-у. теперь фокус (следите за руками). если есть allocate, значит где-то есть free. т-е теоретически когда тот, кто рисует, закончил рисовать - он и делает free.

очередной раз гляжу на код, который делает free 3 кадра спустя - просто потому, что никак иначе не может узнать, когда-же GPU закончил рисовать. ps3. 2010 год. я плакаю, рыдаю.

интересно, а доблестный DirectX тоже такую-же херню делает? на цифру 3 я теперь реагирую как бык на красную тряпку. хочу верить в человечество. буду переписывать.

при написании этого поста пока что никто не пострадал…

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

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

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

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

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

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