Pull to refresh

Comments 13

Когда я прочёл спеку VM, сразу решил писать на C++, о чём в последствии ни разу не пожалел.
Кода получилось меньше, чем на Nemerle, кстати:
orbit.hpp + orbit.cpp
А дальше этой VM можно воспользоваться из чего угодно.
Это я так подробно расписал просто :) На самом деле в первом рабочем варианте кода получалось ~40 строк вместе с загрузкой из файла.

Еще, в P.S. я упоминал, что на c# у меня так же получилось — выборка/декодирование/исполнение. На Nemerle не так — во время загрузки программы происходит и декодирование, а затем просто из готового списка вызываются замыкания, никакие инструкции во время исполнения программы декодировать уже не надо.

Третий вариант, который я видел у одной из команд-- это спецификация кодогенератора для VM программой: для входного байткода кодогенератор выдавал хардкодную реализацию VM на Си. Тоже работало. Но я так не стал делать, так как опасался, что не смогу отладить :)
В 40 не верю. Одна свёртка + соответстующие типы уже 30; да и я за краткостью не гнался.
Насчёт замыканий, это да, на RSDN была тема про то, как такое решение на OCaml обогнало решение на Си в лоб. Интересно было бы сравнить OCaml и Nemerle, так как их решения в данном случае совпадают.
Кстати, на Nemerle же потенциально возможно грузить файл в compile-time и макросами генерировать код выполнения на самом же Nemerle, а не писать VM. Так не пробовали? По крайней мере такое предлагали для ЛИСПа, но на Nemerle тоже реально. Получается та же кодогенерация, но не в текст, а более прямым методом.
Нет, в самом деле порядка 40-50 строк. Альясы я не считал, enum были представлены как константы, код написан на верхнем уровне вне класса, а вместо класса OVMState юзался кортеж.

Вот так выглядит все декодирование (~30 строк).
decode_instr( addr : int, instr : int ) : INSTR {  
  match(( instr & OP_MASK ) >> OP_SHIFT) {
    | 0x0 => {
      def (op,r1,imm) = (((instr & S_OP_MASK ) >> S_OP_SHIFT) :> SOpCodes, (instr & S_R1_MASK ) >> S_R1_SHIFT, imm = ((instr & S_IMM_MASK ) >> S_IMM_SHIFT) :> ImmOpcodes);
      match(op){
        | SOpCodes.Noop => fun(s : OVMState ) { s; };
        | SOpCodes.Cmpz => match(imm) {    
            | ImmOpcodes.Ltz => fun(s) { s.STATUS = (s.MEM[r1] < 0.0); s }
            | ImmOpcodes.Lez => fun(s) { s.STATUS = (s.MEM[r1] <= 0.0);  s }
            | ImmOpcodes.Eqz => fun(s) { s.STATUS = (Math.Abs(s.MEM[r1] ) < 1e-10);  s }
            | ImmOpcodes.Gez => fun(s) { s.STATUS = (s.MEM[r1] >= 0.0);  s }
            | ImmOpcodes.Gtz => fun(s) { s.STATUS = (s.MEM[r1] > 0.0); s}
          }
        | SOpCodes.Sqrt => fun(s) { s.MEM[addr] = Math.Sqrt(Math.Abs(s.MEM[r1]));s };
        | SOpCodes.Copy => fun(s) { s.MEM[addr] = s.MEM[r1]; s };
        | SOpCodes.Input => fun(s) { s.MEM[addr] = s.INS[r1];s };      
      }
    | _ => {
      def (r1,r2) = ((instr & D_R1_MASK ) >> D_R1_SHIFT, (instr & D_R2_MASK ) >> D_R2_SHIFT);
      match(opcode) {
      | DOpCodes.Add => fun(s : OVMState) { s.MEM[addr] = s.MEM[r1] + s.MEM[r2]; s }
      | DOpCodes.Sub => fun(s : OVMState) { s.MEM[addr] = s.MEM[r1] - s.MEM[r2];s;}
      | DOpCodes.Mult => fun(s) { s.MEM[addr] = s.MEM[r1] * s.MEM[r2]; s }
      | DOpCodes.Div => fun(s) { s.MEM[addr] = if( Math.Abs( s.MEM[r2] ) < 1e-10 ) 0.0 else s.MEM[r1] / s.MEM[r2]; s}
      | DOpCodes.Phi => fun(s) { s.MEM[addr] = if( s.STATUS ) s.MEM[r1] else s.MEM[r2]; s}
      | DOpCodes.Output => fun(s) { s.OUTS[r1] = s.MEM[r2]; s; }
    }
  }
}


* This source code was highlighted with Source Code Highlighter.
Если сравнивать OCalm и Nemerle, то не думаю, что была бы какая-то качественная разница.
Насчет макросов — то, что вы предложили (AST-генерация), более чем реально. Просто в настоящее время отлаживать макросы несколько сложнее по сравнению с обычным кодом в Nemerle, потому я и не пошел этим путем — то решение, что я предложил, и так вполне шустрое.

Кстати, некоторые умельцы на контесте подхачили VM, чтобы считать только положение своего спутника, а не остальных (дабы «отточтить» исключительно собственную траекторию), в итоге VM стала считать в 10 раз быстрее. Вот где оптимизация! :)
Про такой хак не слышал, интересно :)
Слышал, что некоторые реализовывали по формулам из спеки нативный симулятор, но не помню, совпадали ли результаты.
Я на F# написал компилятор/конвертатор кода виртуальной машины спутника в .NET сборку (фактически один класс на C#).
Сначала я сделал тупую конвертацию в лоб, когда в классе были все нужные массивы памати, входа и выхода.
Например, для первой задачи сгенерированный код получился таким (не приведен код класса, от которого происходит наследование, но он тривиальный).
На моем компе (DualCore Intel Core 2 Duo E8500, 3166 MHz) 10 миллионов шагов (каждый шаг — одна секунда виртуального времени) выполнялись за 10,7695036 секунд, т.е. для первой задачи (266 инструкций в одном шаге) скорость получалась 928'547 виртуальных шагов за единицу нашего реального времени.
После этого я решил, что компилятор не знает, что некторые ячейки памяти фактически являются временными переменными и нигде глобально не используются. Тогда я решил немного оптимизировать кодогенеряцию — просто разделил ячейки памяти на локальные, глобальные и константы, а также отказался от использования массивов для памяти и сам класс ни от кого не наследуется. Новый сгенерированный код выглядит так.
Такая простая оптимизация увеличила скорость в 4,36 раза. :) Теперь для первой задачи 10 миллионов шагов выполнялись за 2,4674865 секунды, таким образом скорость возросла до 4'052'707 виртуальных шагов за единицу нашего реального времени.
Код, которым мерялясь скорость.
Да, последняя оптимизация позволяет быстро клонировать состояние виртуальной машины и также быстро узнавать, что будет в далеком будущем, если бабочка взмахнет левым крылышком на пару процентов сильнее, чем правым… :) Т.е. в принципе, можно применять генетические алгоритмы, динамическое программирование, методы монте-карло и т.д. и т.п. для того, чтобы максимизировать функцию «вознаграждения» для спутника.
Ага, я видел такую штуку, но на С. Могу сказать только «О_о, жестя» :)
Вариант на C, наверное, должен еще быстрее работать, хотя… тут бабушка надвое сказала. :) Было бы интересно сравнить.
правильно ли я понимаю, что на каждый вызов make_add создаётся новое замыкание?
насколько это дорого? если код хранится отдельно от данных, то получается совсем ничего… правда?
Ага, правильно. Всего создается замыканий по числу инструкций в программе (для первой задачи ~220).
Не знаю, что считать дорогим, поэтому не могу ответить на вопрос, дорого ли это.
Список замыканий для этой задачи — первое, что приходит в голову)

У меня тоже все начиналось со списка замыканий (в Питоне), который был потом за 5 минут переделан в компилятор в Питон-код, а еще позднее так же быстро в машинный код с помошью Cython.

На мой взгляд было бы интересней сделать VM задания 2006 года на Немереле)
Это он приходит в голову, если вы пишете в ФП. Для императивщиков куда более привлекательным выглядит прямое решение cycle_on( read->decode->execute ). Вот я и пытался «расширить сознание» :) — в принципе, с последними вещами того же CSharp подобное можно провернуть даже в нем )

До 2006 — еще не добрался =) Кстати, решение 2004 (про VM для муравьев) — идет в samples к Nemerle: там реализован DSL на N-макросах, на котором и описаны стратегии поведения. Кажется, победители так и делали.
Вот это уже не напишеш в CSharp, по крайней мере — пока что.



Почитал ваш отчет, порадовался точной аналитике; я делал простой расчет стартового импульса для выхода в зону ± 5-50км + PID-регулятор на конечном участке траектории, доруливающий в заданную траекторию =)
Sign up to leave a comment.

Articles