ICFPC2006,VM на C# имеет право на жизнь?

Dasar

есть вот такая VM, какие еще есть очевидные способы ее ускорить (под профайлером пока не смотрел)


using System;

using System.Collections.Generic;

using System.Text;

using System.IO;



namespace Um

{

  class Program

  {

    static uint[] ReadProgram(string name)

    {

      byte[] bytes = File.ReadAllBytes(name);

      List<uint> program = new List<uint>

      for (int i = 0; i < bytes.Length; i += 4)

      {

        byte[] array = new byte[4];

        for (int j = 0; j < 4; ++j)

          array[j] = bytes[i+3-j];

        program.Add(BitConverter.ToUInt32(array, 0;

        //program.Add(BitConverter.ToUInt32(bytes, i;

      }

      return program.ToArray;

    }

    static void Main(string[] args)

    {

      const string programName = "codex.umz";

      //const string programName = "sandmark.umz";

      uint[] program = ReadProgram(programName);

      Run(program);

    }

    static void Run(uint[] program)

    {

      uint ip = 0;



      uint[] registers = new uint[8];

      Dictionary<uint, UmArray> arrays = new Dictionary<uint, UmArray>

      uint freeArrayIndex = 1;    



      arrays[0] = new UmArray(program);



      for (; ; )

      {

        uint b = program[ip++];

        Command command = (Commandb & 0xf0000000u);

        uint A = (b >> 6) & 0x07;

        uint B = (b >> 3) & 0x07;

        uint C = b & 0x7;



        try

        {

          switch (command)

          {

            case Command.ConditionalMove:

              if (registers[C] != 0)

                registers[A] = registers[B];

              break;

            case Command.Addition:

              registers[A] = unchecked(registers[B] + registers[C]);

              break;

            case Command.Multiplication:

              registers[A] = unchecked(registers[B] * registers[C]);

              break;

            case Command.Division:

              registers[A] = unchecked(registers[B] / registers[C]);

              break;

            case Command.ArrayIndex:

              registers[A] = arrays[registers[B]].Array[registers[C]];

              break;

            case Command.ArrayAmendment:

              {

                uint _A = registers[A];

                //if (_A == 0)

                //  Console.WriteLine("selfmodified");

                UmArray array = arrays[_A];

                if (array.IsShared)

                {

                  arrays[_A] = array = array.Clone;

                }

                array.Array[registers[B]] = registers[C];

                break;

              }

            case Command.Allocation:

              uint index = freeArrayIndex++;

              arrays[index] = new UmArray(new uint[registers[C]]);

              registers[B] = index;

              break;

            case Command.Abandonment:

              arrays.Remove(registers[C]);

              break;

            case Command.Orthography:

              A = (b >> 25) & 0x07;

              uint value = b & 0x01FFFFFFu;

              registers[A] = value;

              break;

            case Command.LoadProgram:

              {

                uint _B = registers[B];

                if (_B != 0)

                {

                  UmArray array = arrays[_B];

                  array.IsShared = true;

                  arrays[0] = array;

                  program = array.Array;

                }

                ip = registers[C];

                break;

              }

            case Command.NotAnd:

              registers[A] = ~(registers[B] & registers[C]);

              break;

            case Command.Output:

              Console.Writechar)registers[C]);

              break;

            case Command.Input:

              int ch = Console.In.Read;

              if (ch == -1)

                registers[C] = 0xFFFFFFFF;

              else

               registers[C] = (byte)ch; 

              break;

            case Command.Halt:

              return;

            default:

              Console.WriteLine("Invalid command: {0}", command);

              OutputCommands(program, ip - 1, 40);

              return;

          }

        }

        catch (Exception exc)

        {

          Console.WriteLine("Error: {0}", exc);

          OutputCommands(program, ip - 1, 40);

        }

      }

    }

    class UmArray

    {

      public UmArray(uint[] array)

      {

        this.Array = array;

      }

      public bool IsShared = false;

      public readonly uint[] Array;

      public UmArray Clone

      {

        return new UmArrayuint[])Array.Clone;

      }

    }

    static void OutputCommands(uint[] program, uint index, int count)

    {

      for (int i = 0; i < Math.Min(count, program.Length); ++i)

      {

        uint b = program[index+i];

        Command command = (Command) (b & 0xf0000000u);

        uint registerA = (b >>6) & 0x07;

        uint registerB = (b >> 3) & 0x07;

        uint registerC = b & 0x7;

        if (command != Command.Orthography)

          Console.WriteLine("{0} {1} {2} {3}", command, registerA, registerB, registerC);

        else

        {

          registerA = (b>>25) & 0x07;

          uint value = b & 0x01FFFFFFu;

          Console.WriteLine("{0} {1} {2}", command, registerA, value);

        }

      }

    }

  }

  enum Command

  {

    ConditionalMove = 0 << 28,

    ArrayIndex = 1 << 28,

    ArrayAmendment = 2 << 28,

    Addition = 3 << 28,

    Multiplication = 4 << 28,

    Division = 5 << 28,

    NotAnd = 6 << 28,

    Halt = 7 << 28,

    Allocation = 8 << 28,

    Abandonment = 9 << 28,

    Output = 10 << 28,

    Input = 11 << 28,

    LoadProgram = 12 << 28,

    Orthography = 13 << 28

  }

}

agaaaa

Ускорять, думаю, смысла нет. Есть смысл добавить дамп вывода при каждом запуске (помимо вывода на консоль). И ещё мб будет полезно нечто вроде хибернации - сохранение всех массивов и ip в файлик/загрузка из него.
UPD. Есть предложение обсуждать всё связанное с ICFPC в одном треде. Тогда будет понятно, кто, возможно, будет учавствовать.

Dasar

> Есть смысл добавить дамп вывода при каждом запуске (помимо вывода на консоль). И ещё мб будет полезно нечто вроде хибернации - сохранение всех массивов и ip в файлик/загрузка из него.
первое уже сделал.
что надо добавить хибернацию согласен.
также нужна возможность в любой момент временно перенаправить вывод/ввод в другой файл/программу.
это позволит ту же самую задачу с hack-ом решать на любом внешнем языке, а не на встроенном basic-е.

Dasar

Ускорять, думаю, смысла нет.
в целом - да, если не брать операцию decrypt - работает довольно шустро.

ermsoft

А насколько шустро?
За сколько проходит sandmark?

Dasar

одна итерация - 4 секунды

agaaaa

Я подозреваю, что для вольного перенаправления в любой момент всё-таки нужен GUI.

Dasar

> Я подозреваю, что для вольного перенаправления в любой момент всё-таки нужен GUI.
само собой, но это не сложно.
к этой же программе добавить в начале


new Thread(delegate{Application.Run(new MainForm;}).Start;

karkar

Кажися, классическая оптимизация таких машин - переход от case к массиву укателей на функции.

Dasar

> Кажися, классическая оптимизация таких машин - переход от case к массиву укателей на функции.
так такую оптимизацию и компилятор делает.

psm-home

Ты не встречал случайно при написании UM такого результата sandmark? А то я ради забавы налабал быстренько на яве UM и видимо где-то ошибся и не вижу где .


trying to Allocate array of size 0..

trying to Abandon size 0 allocation..

trying to Allocate size 11..

trying Array Index on allocated array..

trying Amendment of allocated array..

checking Amendment of allocated array..

trying Alloc(a,a) and amending it..

comparing multiple allocations..

pointer arithmetic..

check old allocation..

simple tests ok!

about to load program from some allocated array..

Index in 0-array fail

katrin2201

JIC, видимо оно на операторе 12 (Load Program) наепывается.

Dasar

Index in 0-array fail
текущую позицию работы после LoadProgram правильно меняешь?

psm-home

да

Dasar

в том числе, даже если происходит загрузка из 0-array-а (уже исполняемого массива)?

psm-home

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

Dasar

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

Dasar

код покажи

psm-home

Да, точно. Я торможу, видел же что у тебя там COW. Кода-то нет практически. Вот для инструкции LoadProgram:
                    

                case 12:

                    

                    long[] temp = arrays.get( (int) registers[b] );

                    final long[] newProgram = new long[temp.length];

                    System.arraycopy( temp, 0, newProgram, 0, temp.length );

                    arrays.set( 0, newProgram );

                    finger = (int)registers[c];

                    break;

Dasar

проблема скорее всего где-то рядом, а не в самом LoadProgram, поэтому приведи лучше весь код

Dasar

[телепатия] скорее всего ты ip плюсуешь в конце цикла, даже когда инструкцию LoadProgram обратываешь, а в этом случае ip менять не надо.

psm-home

да, скорее всего так и есть спасибо

karkar

А как в этой VM делаются условные переходы? Все через LoadProgram?
Например, если надо перейти куда-то по условию A<B?

Dasar

А как в этой VM делаются условные переходы? Все через LoadProgram?
да, через LoadProgram

bleyman

Или через самомодифицирующийся код!

Dasar

> Или через самомодифицирующийся код!
и как ты представляешь себе переход через самомодифицирующийся код?
через самомодифицирующий код можно делать какие-то хитрые переходы на основе LoadProgram, но все равно все будет завязано именно на LoadProgram.

katrin2201

В виду имелся, наверное, не переход, а выполнение разных команд при разных входных данных.
А это уже можно сделать.

Dasar

> В виду имелся, наверное, не переход, а выполнение разных команд при разных входных данных.
> А это уже можно сделать.
сделать можно, но зачем?... для того, чтобы выполнить разный код, это разный код надо где-то взять, т.е. откуда-то взять и поместить как следующие команду.
внимание вопрос, зачем заниматься таким перекопированием информации, если можно сразу перейти и выполнить этот код без перекопирования?
самомодификация удобна только в нескольких случаях:
1. самораспаковка кода
2. при отсуствии в оп-ах косвенной адресации
3. JIT-оптимизация

katrin2201

А я и не думаю, что ФиДжей это всерьез предложил.
Просто так можно. Но, разумеется, не нужно.
Оставить комментарий
Имя или ник:
Комментарий: