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

Question

У меня есть система, которая генерирует деревья решений и преобразует их во вложенный 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 миллисекунд. Почему такая простая структура занимает так много времени? Могу ли я что-нибудь сделать, чтобы существенно ускорить процесс, возможно, какое-нибудь заявление? Я был бы очень признателен за любые указатели, которые вы можете предложить.

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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