Как я могу ускорить компиляцию операторов Common Lisp `IF`? - PullRequest
Новая
       29

Как я могу ускорить компиляцию операторов Common Lisp `IF`?

0 голосов
/ 12 сентября 2018

У меня есть система, которая генерирует деревья решений и преобразует их во вложенные операторы Common Lisp if с предикатами, которые проверяют, является ли значение переменной >= или <= заданным целым числом, например 

(LAMBDA (V1 V2)
  (IF (>= V1 2)
      (IF (<= V1 3)
          (IF (<= V2 3)
              (IF (>= V2 2) 16 (IF (>= V2 1) 6 0))
            (IF (<= V2 4) 10 0))
        (IF (<= V1 4)
            (IF (>= V2 1) (IF (<= V2 3) 6 0) 0)
          0))
    (IF (>= V1 1)
        (IF (>= V2 2) (IF (<= V2 4) 10 0) 0)
      0)))

Затем я использую eval для компиляции кода на Лиспе, создавая функции, которые работают намного быстрее, чем интерпретация исходного дерева решений.Этот этап компиляции занимает удивительно много времени: функция с 5000 вложенными ifs компилируется за минуту (в Clozure Common Lisp на powerbook), хотя генерация оператора if заняла около 100 миллисекунд.Почему такая простая структура занимает так много времени?Могу ли я что-нибудь сделать, чтобы существенно ускорить процесс, возможно, какое-нибудь заявление?Буду очень признателен за любые указатели, которые вы можете предложить.

Ответы [ 2 ]

0 голосов
/ 12 сентября 2018

Фактическая переносимая функция для компиляции функций называется COMPILE.

Вы можете сказать компилятору Common Lisp инвестировать меньше работы с низкими optimize качествами для speed, space, debug и compilation-speed - зависит ли это от реализации.

Компилятор Clozure CL обычно не самый яркий, но относительно быстрый. Обычно я думаю, что сопровождающий компилятора может дать вам больше советов, как ускорить компиляцию. Вообще я бы искал три

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

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

0 голосов
/ 12 сентября 2018

Вы, конечно, можете (declare (optimize (compilation-speed 3))) и, возможно, уменьшить другие качества (см. http://clhs.lisp.se/Body/d_optimi.htm#optimize).

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

Я бы также подумал о том, какие оптимизации вы можете сделать самостоятельно, используя свои знания предметной области.анализируя вывод disassemble в ваших сгенерированных функциях.

Наконец, возможно, вы можете преобразовать свои деревья решений в таблицы поиска, если число различных значений не слишком велико.

...