Хорошо, поэтому первое, что я хочу сделать, это объяснить, что означает «принуждение к указателю».
(Предварительные условия: понимание того, что такое память в машине, биты и приблизительное представление о Cмодель памяти).
В Лиспе, который динамически типизирован, значения имеют типы, а не переменные.Следовательно, вам нужно некоторое согласованное представление памяти, которое можно использовать для передачи любого значения любого типа, и вы должны быть в состоянии определить тип для этого.(Обратите внимание, что в некоторых строго типизированных функциональных языках все еще может потребоваться некоторое представление структурированной памяти для сборки мусора, чтобы следовать указателям, или единый способ представления всех указателей в слове, чтобы полиморфизм работал).Типичным выбором для этого является указатель, который всегда является словом (скажем, 8 байтов), и тогда объект, на который указывает указатель, может иметь заголовок с дополнительной информацией о его типе.В C это будет выглядеть примерно так:
struct LispObj_s {
uint32_t length;
uint16_t gc_data;
uint16_t type_code;
union {
int64_t as_smallint;
float as_float
double as_double;
char as_string;
... /* bignums, arrays, cons, structs, etc */
}
}
typedef LispObj_s * LispObj
Это плохо, потому что тогда многие часто используемые вещи (а именно целые числа) имеют огромные накладные расходы: одно слово для указателя на объект, другое для заголовка (говоря «я целое число, и я 1 слово в длину»), и один для самого числа.Это накладные расходы на 200%, и это означает, что целые числа требуют разыменования указателя и возможного промаха кэша.Итак, есть оптимизация: вы используете несколько наименее значимых битов указателей, чтобы сказать, что это за тип (они бесплатны, так как все выровнено по словам, поэтому три младших значащих бита всегда равны 0).Тогда вы можете иметь, что если (скажем) последний бит равен 0, то у вас есть фиксированный номер (небольшое число, где арифметика быстрая, в данном случае 63 бита), если ваши последние биты равны 101, у вас есть указатель на консоль,если они равны 111, то указатель на двойное число, 011 на число с плавающей запятой и 001 указатель на что-то еще.Теперь целые числа, умножения и числа с плавающей точкой дешевле, и это хорошо, но недостатком является то, что теперь вам нужно быть немного осторожнее, чтобы убедиться, что теги всегда правильные.Проблема в том, что мы не можем сделать то же самое для двойников, что мы сделали для целых чисел.На самом деле невозможно просто отрубить 2 бита от двойного, как вы делаете с целыми числами, особенно если вы хотите совместимости с внешними программами.
В скомпилированном коде вы хотите работать с объектами (например, с плавающей точкой) сами ипоэтому храните их в необработанном виде в регистрах или в стеке.Только скомпилированный код может получить к ним доступ, и он знает, к какому типу они относятся.
Когда вы хотите вернуть или передать (например) число с плавающей точкой в качестве аргумента, код, получающий его, не обязательно знает, какого рода объектон получит, и код, отправляющий его, конечно, не будет знать, что получатель хочет получить определенный тип данных.Таким образом, вам нужно преобразовать его в некую унифицированную форму, в которой также указано, к какому типу он относится, и для этого вам нужно выделить для него некоторую память и передать тегированный указатель на эту память.При вызове функции вы не знаете, что вызываемая функция будет делать с плавающей точкой, и поэтому вы не можете (см. Позже) разместить ее в стеке, потому что вызываемый объект может, например, поместить ее в глобальную переменную, а затемчуть позже эта переменная будет указывать на мусорные данные или не отображенную память.Еще хуже, когда вы возвращаетесь, поскольку вы будете размещать float в своем собственном кадре стека, который вы собираетесь уничтожить.Распределение имеет тенденцию быть медленным (хотя и намного быстрее, чем, например, в C; главным образом потому, что вы пишете в память, а не в кэш), а чтение выделенных объектов имеет тенденцию быть медленным (потому что вам нужно проверять и удалять теги и разыменовывать указатель, и частоиз-за отсутствия кэша) именно поэтому sbcl жалуется, когда оптимизатору приходится выделять и упаковывать объект.
Одна вещь, которую можно сделать, чтобы всеocation быстрее объявить динамический экстент.Это говорит Лиспу, что вы обещаете, что какой-то объект не будет указывать куда-либо после окончания текущей динамической области и, следовательно, он может быть размещен в стеке.Распределение стека происходит быстрее, а локальный кэш больше, а освобождение стека в основном бесплатное, поскольку gc не задействован.Вы можете сделать это при передаче аргументов, но не при возврате.
Использование values немного похоже на размещение возвращаемого списка в стеке (параметр & rest для функции также может быть выделен в стеке, если динамический экстент в sbcl)за исключением того, что это возможно, и поэтому это более эффективный способ вернуть несколько значений.К сожалению, из-за единообразного представления памяти невозможно получить преимущество от распределения чисел.
Ответ
Однако, если мы знаем о функции, которую мы вызываем, мы можем сложить-выделите пространство для его возвращаемых значений заранее и затем поместите функцию туда.Если мы сделаем это, мы также сможем избежать приведения типа с плавающей точкой к указателю следующим образом: sbcl имеет оптимизированное представление для массивов с плавающей точкой, где вместо массива указателей на плавающие числа плавающие элементы хранятся напрямую (например, как float*, а не float**):
(defun foo3 (a1 a2 a3 b1 b2 b3 result)
(declare (optimize (speed 3) (safety 0))
(type double-float a1 a2 a3 b1 b2 b3)
(type (simple-array double-float (3)) result))
(setf (aref result 0) (+ a1 b1)
(aref result 1) (+ a2 b2)
(aref result 2) (+ a3 b3))
nil)
И тогда мы можем назвать это следующим запутанным способом:
(let ((foo-result (make-array '(3) :element-type 'double-float :initial-element 0d0)))
(declare (dynamic-extent foo-result))
(foo a1 a2 a3 b1 b2 b3 foo-result)
(let ((c1 (aref foo-result 0)) ...)
...))
Таким образом, мы выделяем пространство для результатов в стеке, затем foo3заполняет их, затем мы извлекаем их из стека, предположительно в регистры.Это должно быть почти так же быстро, как foo3, возвращающее свой результат в регистрах, и, что особенно важно, не требует выделения кучи ((Edit: я не думаю, что это так), если sbcl предполагает, что функция не изменится, она может вызватьпроверка типа / распаковка прямо в ядро функции).
К сожалению, синтаксис неприятен, но в Lisp: есть макросы.Можно реализовать специальные макросы для определения функции, такие как foo3, и специальный макрос для вызова и привязки результатов, но это плохо, потому что вы теперь разбили мир на два типа функций и не можете использовать функции более высокого порядка дляfoo, и вы, возможно, делаете макросы-генерации макросов, которые сложно отладить.Вместо этого идея заключается в следующем: мы генерируем быструю версию с нашим странным соглашением о вызовах и функцией-оберткой, которая вызывает ее и устанавливается в строку.Затем всякий раз, когда мы вызываем функцию-обертку, мы получаем преимущество быстрого вызова, и компилятор снимает с нее все расходы на обертку.
(defmacro fast-defun (name num-values lambda-list &body body)
(assert (and (integerp num-values) (plusp num-values)))
(let ((fast-name (gensym (symbol-name name)))
(result (gensym "RESULT"))
(vars (loop repeat num-values collect (gensym "V")))
`(progn
(defun ,fastname ,(cons result lambda-list) ;;FIXME: this only works if lambda-list is a list of symbols
(declare (optimize (speed 3) (safety 0))
(type (simple-array double-float (,num-values))))
;; Todo: move declarations here from body
(multiple-value-bind ,vars (progn ,@body)
,@(loop for v in vars
for n from 0
collect `(setf (svref ,result ,n) ,v))
nil))
(declaim (inline ,name))
(defun ,name ,lambda-list
(let ((,result (make-array '(,num-values) :element-type 'double-float :initial-element 0d0)))
(declare (dynamic-extent ,result) (optimize (speed 3)))
(,fast-name ,result ,@lambda-list)
(values ,@(loop for n below num-values collect `(aref ,result n))))))))
Этот макрос не в самом общем виде, но вы можете использовать его так же, как и (defun foo выше, но (fast-defun foo 3.
После еще нескольких экспериментовКажется, что это на самом деле не быстрее.Каким-то образом все еще происходит, и я не могу понять, как избежать этого, не вставляя все.Я также попытался сделать входной массив динамическим экстентом, но это, похоже, не помогло.
После осмотра немного больше, я не смог найти способ посмотреть на промежуточные результаты в конвейере компиляции, который заставил меняпечально, но я просмотрел исходный код и думаю, что, хотя компилятор может (иногда) специализировать вызов функций, он не может специализироваться на возврате значений с плавающей точкой.