wizzard: (Default)
Какие вы знаете безопасные (в смысле статически верифицируемые) виртуальные машины или форматы байткода?

(Также известно как typed assembly, proof-carrying assembler, managed code и такое прочее). Слайды по теме: http://www.cs.umd.edu/class/fall2006/cmsc631/lectures/talpcc.pdf

Я знаю BEAM (проконсультировался, увы, нет) и CLR.
JVM не подходит, потому что существующие формальные модели (http://cseweb.ucsd.edu/~gmporter/papers/formaljvm-ecoop01.pdf) не моделируют permissions, а смотрят только за integrity самого рантайма.

Требования примерно такие:

Level 0 protection: прога доказанно не может развалять рантайм (с этим проще всего, любой гипервизор или ОС на процессоре с MMU и ring levels подходит), на OOM, slowloris и прочее пока забьем для упрощения.

Level 1: прога доказанно не может развалять соседнюю прогу, иначе как через API (браузеры, JVM, dalvik, nacl, linux/bsd/windows/android итд итп)

Level 2: есть прога, из trusted library + untrusted code, антрастед код может звать методы из трастед либрари без оверхеда на IPC но доказанно не может обойти проверки, встроенные в них, даже если трастед лайбрари делает колбэки в untrusted код (CLR)

Level 3: в общем случае, можно навесить constraints на код, в виде security capabilities, и статически показать, что этот код будет доказанно их придерживаться (F*?)

репост с привлечением комментов в оригинал приветствуется. и, да, стоит ли на английском это написать? на stackoverflow такие вопросы не любят, увы.
wizzard: (Default)
Почему я считаю pointer chasing универсальной абстракцией вычислений?

Потому что он turing-complete!

> 29C3: Page Fault Liberation Army or Gained in Translation (EN)
> (произвольные вычисления на x86 MMU)
> http://www.youtube.com/watch?v=Y1ypnYIyzKk
> Обсуждение: http://news.ycombinator.com/item?id=5261598
wizzard: (Default)
tl;dr: почему у нас до сих пор нет игр с супер-пупер живым миром? а вот почему.

я вот недавно жаловался на то, что железо современное плохое и не подходит для симуляторов ( http://wizzard0.livejournal.com/278128.html )

и вот расписал, как именно оно плохое ( http://wizzard0.livejournal.com/282769.html )

короче самое печальное что из этих эстимэйтов можно вывести - что если любое вычисление выполняется за константное время (==это таблица ранее вычисленных значений), то можно выполнить за кадр не более 150к независимых вычислений. зависимых - в 50 раз больше, в идеальном случае (тупое последовательное копирование) - в 500 раз. но реально таки 150к вычислений.

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

Вроде бы, не так уж мало.
"можно закрасить экран iPad обьектами площадью в 10 пикселей" -- vgrichina

Для 2D игр, действительно, достаточно. А вот с 3D и мультиплеером - ситуация уже не столь радостная.

1. давеча thesz тут ( http://thesz.livejournal.com/1359825.html ) ужасался использованию Stackless Python в EVE Online и тому, что одновременно на узле могут присутсвовать "всего" 3000 игроков.

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

2. Если мы хотим *симулировать* сколько-нибудь большой мир - мы вынуждены делать либо пошаговую игру, либо упрощать обьекты вдалеке от игрока. Само по себе это не так плохо, и для single-player очень даже работает.

А вот в мультиплеере бюджет обьектов сьедается очень быстро, ведь, хоть игроки и кучкуются, но все равно у нас получается уже N "окрестностей игрока", а не 1 окрестность

3. Даже в "одной окрестности", если мир трехмерный, симулировать 50 метров по высоте и 400 м по ширине (квартал города в GTA) означает 8 млн куб.м. По 100м^3 на обьект. Или по материальной точке (точнее, обьекту, который описывается конечным автоматом, таблица состояний которого помещается в RAM) через каждые 4 метра. При этом изрядную часть этого бюджета сьедает графика.

Minecraft? Нет, не пойдет. Там ландшафт статичен. Хотя даже там дистанция отрисовки ненамногим больше магических 200 метров, хотя из динамических обьектов только коровы, лампочки и redstone.

Roblox ( http://www.youtube.com/user/roblox ) гораздо ближе. Вообще, Семен призывается в тред рассказать, какие у них реально получаются там размеры сцен.

4. "динамически понижать детализацию по удалению от игрока" - можно. и нужно. Но уметь надо. Для user-generated content это ой как непросто. Никого в GTA не раздражало, что если преследуемая машина свернет за угол (а то и если просто ненароком камеру повернуть) - она исчезнет навсегда? Вот я примерно об этом.

Comments welcome.
wizzard: (Default)
Хехехе. После долгих и упорных экспериментов, у нас есть штуковина, которая в round-robin режиме успевает обойти 1 млн тредов в секунду, и выдать каждому по 0.6 мкс процессорного времени :))) (на одном амд-шном ядре)

Что резко переносит идею "1 актор - 1 процесс" из области теории очень близко к практике.

* да, я знаю про асинхронность. но что делать, если обработчики сообщений занимают непредсказуемое время (CPU-bound, а не IO-bound?) нужна вытесняющая многозадачность, а ее на соплях из колбеков не сделаешь.

До бредовых идей типа делать интерпретатор байткода на GPU я так и не добрался, а жаль :)

Теперь надо разобраться, насколько у нас все плохо с префетчем и починить хотя бы memory IO (есть ощущение, что с кэшами все не просто плохо, а очень плохо...)
wizzard: (Default)

Надо отметить, что год от года сабж становится все лучше и лучше.

Когда-то это было синонимом тормозов и глюков, по крайней мере для реалтайма.

Теперь же можно спокойно запустить в одной VM фильм, в другой – Deus Ex (да, я извращенец), в третьей – visual studio с браузерами и решарпером, разбросать это на разные мониторы\RDP, и ничего не тормозит, и инпут не глючит, колонки с микрофонами правильно роутятся, лепота вообще.

таким образом за счет одного мощного десктопа можно будет довольно долго не апгрейдить все остальное :)

ах да, и хост-машина при всех этих мультимедийных извращениях не падает, это тоже очень актуально :)

Раздражают только сильно умные детекторы железа – игрушки под рдп редко запускаются, хотя если залогиниться *после* – отлично работают. Ну и 8-гиговых планочек RAM хочется, но пока что жаба давит :)

wizzard: (Default)

(редактированный лог)

основная проблема в том, что я не знаю слов, в которых можно сформулировать этот вопрос :)

грубо говоря, есть dataflow-система - граф потоков и обработчиков.
если считать, что она синхронная, то ее достаточно тривиально типизировать как функцию, которая принимает туплы и выдает туплы, или как монаду List (если я правильно понимаю). при этом у нас получается, скажем так, одномерная система
одна размерность у нас "время", в смысле, функция t -> inputState
а сам обработчик у нас типа () -> (t -> inputState) -> (t -> outputState) (как-то так)

так вот, что делать, если мы хотим разрешить изменение обработчика в процессе?
тогда у нас получается двумерная система, она же "битемпоральная" (не путать с традиционным определением битемпоральной системы, это ниже)
одна ось у нас "время", другая - "версия обработчика". иначе говоря, "данные, известные на момент реального времени Х + обработчик версии Y = результат"
для реалистичной реализации, к сожалению, нужна еще одна ось - данные поступают в виде кортежей (время поступления события, время актуальности события, событие)

так вот, хочется создать систему, которая принимает поток извещений о событиях и поток модификаций
и позволяет посмотреть "видение мира в момент реального времени Х на базе данных, поступивших на момент Y, системой версии Z"
а для того, чтобы она была проще для понимания и поддержания, в ней хочется видеть, как минимум, referential transparency,
и явный контроль side effect'ов.

так вот, все мысли которые приходят мне в голову, разбиваются о то, что эти оси дискретные и хреново дифференцируются
с pure дифференцируемыми total функциями всё как-то намного проще, а вот инстанцирование обьекта в коллекции мне рвет крышу

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

вопросы, наверное, такие:
1. чего читать?
2. куда смотреть?
3. кто еще думал про такое?

wizzard: (Default)

(захотелось мыслю написать и сюда тоже)

еще одна причина трепыханий с собственным JS рантаймом - потому что хочется сделать подобие Application Domains из .NET для JS, чтобы компоненты могли что угодно творить. ибо без eval (или кодогенерации, как кому угодно), все-таки, львиная доля привлекательности динамических языков теряется.

плюс, когда рантайм свой, можно делать как hard так и soft resource quotes, и попробовать все-таки осилить его сериализацию и сделать тот самый holy grail ака мигрирующие в пространстве (между машинами) и во времени (сейв-лоад) аппликухи.

а йаваскрипт, а не другой язык, просто потому, что популярный.

wizzard: (Default)

есть ли смысл клепать свой собственный язык программирования? :)

wizzard: (Default)

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

wizzard: (Default)

тем временем я все более и более прихожу к выводу что наличие массивов в языке как встроенных типов, а не библиотеки, есть жуткая ересь

wizzard: (Default)
ура!!!!

оно заработало!!!! теперь дело за малым, написать всё остальное %)
а сейчас можно и спать ложиться...

между делом, соорудил собственный value-type (копирует себя при присваивании) в Python'e ^_^

(наверное, это совсем black magic, но в противном случае если method привязан (bound) более чем к одной инстанции класса, то при попытке сериализации оно нафик рушится. поэтому понадобилась фигня которая при присваивании себя копирует и прибиндивает копию. еще б разобраться, как прикрутить новый контекст замыканий, а то часть имен отваливаются и потом "внезапно" got NoneType, expected 'str', и т.д.) Но пока и так сойдет.


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

wizzard: (Default)

сделал на досуге крохотный ивент-дривен рантайм, потом подумал “надо бы внести в мир равенство и справедливость, давайте сделаем по потоку на обьект?”

сказано-сделано, работает. правда, в голову лезут два назойливых вопроса:

  1. нафига это надо? :)
  2. как на этом правильно программировать?

после где-то двух суток размышлений внезапно попёрло и начался

мысленный понос )
wizzard: (Default)

выспавшись и подумав, решил написать пока прототип на Stackless, чтоб яснее представлять себе,
что нужно – и без чего можно обойтись.

там видно будет.

wizzard: (Default)

пока меня поразило устройство двух виртуальных машин

- Macromedia/Adobe Flash AVM2 (эволюция превратила маленькую кавайную зверушку в огромного хаотичного монстра)
- виртуальная машина PyPy (концептуально и круто, и, эмм, ест моск. очень сильно ест моск)

что ищется в первую очередь:

- code serializaltion [a.k.a. serialize(eval(‘lambda x, y: x+y’)) ]
- thread serialization (tasklets, threadlets, кто как называет)
- контроль над исполнением потоков (ручной scheduler и\или управляемое preemptive multitasking)
- наличие интерпретатора\компилятора языка высокого уровня под данную VM
- работающего под ней же ;)

что было бы прикольно иметь:

- в идеале – замкнутость, т.е. чтобы внутри этой VM можно было запустить экземпляр такой же VM, но это не обязательно
- code instrumentation (как минимум _pentry/_pexit, в идеале – встроенный profiling)
- встроенный debugger было бы без сомнения круто, но в случае чего его можно и дописать
- еще интересна рефлексия программы и\или рефлексия самой VM.
- быстродействие вторично, но все же лучше, чтобы скорость не отличалась более чем в 1000 раз от кода на C



UPD: еще одно применение thread serialization - для ускорения запуска тяжелых программ (fread+memcpy явно быстрее загрузки чего-либо, даже тривиального), вспомнил после прочтения http://zhengxi.livejournal.com/73471.html

wizzard: (Default)
кажется, у них всех едет крыша. на фоне Flash, Silverlight и JavaFX, может, идеи по запуску native кода в браузере и хороши, но:

- это ведет к closed-source, мертвым после изменения внутренностей API бинарям, вирусам и антивирусам для веб-приложений (потому что шеллкод, как ни крути, читать не так удобно, как javascript), продлеванию жизни ущербной Интеловской платформы и обрастания браузера толстенными слоями совместимости со старыми версиями бинарей (см. windows :) - конечно, это не столь актуально в свете наличия auto-update, но я не думаю, что каждый вендор будет поддерживать каждый свой продукт пожизненно)

- люди пойдут искать баги в процессорах (впрочем, это в каком-то смысле хорошо, вот только голов лететь будет много)

- и баги в проверялке, коих, если не оставить в х86 только арифметику, очень и очень много

- в любом случае идет лесом аппаратное ускорение видео, 3D и прочее (если дать возможность бросать произвольные данные "туда" - то птичка вылетит из клетки. за примером тоже далеко ходить не надо, тот же Xbox360 взломали именно так)

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

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

да и еще мне крайне интересно, как эта штука относится к 64-бит, не-х86, мобильным платформам наконец?

http://googleonlinesecurity.blogspot.com/2008/12/native-client-technology-for-running.html

похоже, придется переходить на замечательный браузер NetFront под PSP :)
(суть не в браузере, а в MIPS процессоре, если кто не понял :) )

crossposted to [livejournal.com profile] ru_programming 
wizzard: (Default)
Все краем уха где-то слышали, что .NET MSIL-код - интерпретируется. И я слышал. Еще большинство слышало, что для оптимизации его компилируют в native code. Но не всегда.

В итоге, поиски интерпретатора MSIL привели... ни к чему.

Интерпретаторов MSIL нет. Все имеющиеся в природе closed- и open-source реализации - только компилирующие :(

MS .NET Framework - компилирует в x86/x64/IA64 (Win) native, интерпретатора нет
MS .NET Compact Framework (XNA, Silverlight) - компилирует в ARM/PPC/MIPS/x86/x64 (Win/Xbox/WinMobile) код, интерпретатора нет
MS .NET Micro Framework - при билде (!) компилирует в native или direct-threaded код, в зависимости от характеристик устройства. Компиляция производится при билде, а не в run-time (т.е. сборки, не обработанные NGEN'ом, просто отказываются запускаться)
Rotor (SSCLI) - компилирует в x86 native
Mono - до версии 0.2х интерпретировал, теперь там есть два различающихся по оптимальности компилятора. Внимательный просмотр кода версии 2.0.1 следов интерпретатора не нашел (хотя место, куда воткнуть, в принципе есть)
Net60 Compact Framework - компилирует в ARM (Symbian) код на лету
Portable.NET, он же dotGNU - компилирует в direct-threaded код на лету
DotNetAnywhere - компилирует в direct-threaded код на лету.
CrossNet - генерирует C++ код
Volta - генерирует JavaScript код (с одной стороны, это ахтунг, с другой стороны, интерпретатор MSIL на JS был бы еще на два порядка медленнее)


Усе, приехали. Если кто вдруг знает еще дотнет-рантаймы :-D - буду рад узнать. Особенно, если это будет таки чистый MSIL интерпретатор.

А, да. direct-threaded code - это нечто среднее между байткодом и native, по эффективности сравнимо с native кодом, который генерирует неоптимизирующий компилятор.

one-liner

Aug. 28th, 2008 03:01 pm
wizzard: (Default)
Компилятор - это рекурсивная сюръективная функция, отображающая точки пространства операторов на пространство функций и ошибок.

бреды на питоне )

Profile

wizzard: (Default)
wizzard

May 2017

S M T W T F S
 123456
78 910111213
14 151617181920
2122232425 2627
28293031   

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated May. 27th, 2017 11:10 pm
Powered by Dreamwidth Studios