SBCL "суб" эффективность - PullRequest
Новая
       49

SBCL "суб" эффективность

2 голосов
/ 15 февраля 2020

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

    (loop
       with bindings = ((symbol1 . 1) (sybmol2 . 2) ... (sybmoln . n))
       with x-copy
       for x in xs
       do
         ...
         (setq x-copy (copy-cpd x))
         (setf (cpd-identifiers1 x-copy) (subst-bindings bindings (cpd-identifiers1 x)))
         (setf (cpd-identifiers2 x-copy) (subst-bindings bindings (cpd-identifiers2 x)))
         ...)

subst-bindings выполняет рекурсивные вызовы subst внутренне: 

(defun subst-bindings (bindings generic)
  (cond ((null bindings) generic)
    (t (subst-bindings (cdr bindings)
               (subst (cdar bindings) (caar bindings) generic)))))

Я запустил свой фактический код с включенным статистическим профилировщиком и получил следующие результаты: 

           Self        Total        Cumul
  Nr  Count     %  Count     %  Count     %    Calls  Function
------------------------------------------------------------------------
   1   4585  45.8   6840  68.4   4585  45.8        -  (LABELS SB-IMPL::S :IN SUBST)
   2   2204  22.0   2205  22.1   6789  67.9        -  EQL
   3    489   4.9    489   4.9   7278  72.8        -  SUBST
   4    315   3.2   7537  75.4   7593  75.9        -  SUBST-BINDINGS
   5    150   1.5    235   2.3   7743  77.4        -  PPRINT-DISPATCH
   6    143   1.4    274   2.7   7886  78.9        -  SB-IMPL::%FIND-SYMBOL
   7    114   1.1    114   1.1   8000  80.0        -  SB-IMPL::%MAKE-STRING-OUTPUT-STREAM
   8    106   1.1    347   3.5   8106  81.1        -  SB-KERNEL:OUTPUT-SYMBOL-NAME
   9     94   0.9    113   1.1   8200  82.0        -  SB-IMPL::STRING-SOUT
  10     73   0.7    155   1.5   8273  82.7        -  SB-KERNEL::VALUES-SPECIFIER-TYPE-R
  11     70   0.7     70   0.7   8343  83.4        -  SB-KERNEL:UB32-BASH-COPY
  12     56   0.6     56   0.6   8399  84.0        -  SB-KERNEL:%SXHASH-SIMPLE-SUBSTRING
  13     51   0.5     51   0.5   8450  84.5        -  MAKE-CPD
  14     48   0.5    160   1.6   8498  85.0        -  GET-OUTPUT-STREAM-STRING
  15     48   0.5     48   0.5   8546  85.5        -  WRITE-STRING
  16     44   0.4     44   0.4   8590  85.9        -  SB-KERNEL:%COERCE-CALLABLE-TO-FUN
  17     43   0.4    741   7.4   8633  86.3        -  PRINC
  18     43   0.4     60   0.6   8676  86.8        -  POSITION
  19     39   0.4    151   1.5   8715  87.2        -  SB-IMPL::%WRITE-STRING
  20     39   0.4     46   0.5   8754  87.5        -  SB-KERNEL:STRING=*
  21     37   0.4    195   2.0   8791  87.9        -  SB-KERNEL::SPECIFIER-TYPE-R
  22     37   0.4    169   1.7   8828  88.3        -  OPERATE-FACTOR
  23     36   0.4     68   0.7   8864  88.6        -  SB-VM::GENERIC-+
  24     36   0.4     36   0.4   8900  89.0        -  COPY-LIST
  25     35   0.4    231   2.3   8935  89.4        -  SB-KERNEL:SPECIFIER-TYPE
  26     33   0.3    314   3.1   8968  89.7        -  SB-INT:%INTERN
  27     32   0.3   9146  91.5   9000  90.0        -  CANDIDATE-NODES
  28     31   0.3     31   0.3   9031  90.3        -  SB-IMPL::SETUP-PRINTER-STATE
  29     30   0.3     79   0.8   9061  90.6        -  COPY-SEQ
  30     30   0.3     45   0.4   9091  90.9        -  GET-FULLY-QUALIFIED-CPD-VARS
  31     30   0.3     30   0.3   9121  91.2        -  SB-IMPL::OUTPUT-SYMBOL
  32     28   0.3   1724  17.2   9149  91.5        -  GENERATE-CPD-VARS
  33     26   0.3     63   0.6   9175  91.8        -  SB-INT:EQUAL-BUT-NO-CAR-RECURSION
  34     25   0.3     25   0.3   9200  92.0        -  SB-IMPL::VECTOR-SUBSEQ-DISPATCH/SIMPLE-VECTOR
  35     24   0.2     24   0.2   9224  92.2        -  (SB-IMPL::OPTIMIZED-DATA-VECTOR-REF T)
  36     23   0.2     23   0.2   9247  92.5        -  SB-KERNEL:HAIRY-DATA-VECTOR-REF/CHECK-BOUNDS
  37     21   0.2    685   6.8   9268  92.7        -  (LABELS SB-IMPL::HANDLE-IT :IN SB-KERNEL:OUTPUT-OBJECT)
  38     20   0.2     70   0.7   9288  92.9        -  SB-IMPL::COMPUTE-SYMBOL-HASH
  39     19   0.2   1295  12.9   9307  93.1        -  COMBINE-SYMBOLS
  40     19   0.2    395   4.0   9326  93.3        -  INTERN
  41     19   0.2    104   1.0   9345  93.5        -  (FLET SB-IMPL::REPLACE-ALL :IN GET-OUTPUT-STREAM-STRING)
  42     19   0.2     19   0.2   9364  93.6        -  SB-C:RETURN-MULTIPLE
  43     19   0.2     19   0.2   9383  93.8        -  SB-KERNEL:VECTOR-SUBSEQ*
  44     18   0.2    133   1.3   9401  94.0        -  COPY-CPD

Руководство пользователя SBCL описывает, как интерпретировать эту таблицу:

Для каждой функции в таблице будут показаны три абсолютных и относительных числа выборок. Столбец Self показывает образцы, взятые при непосредственном выполнении этой функции. Столбец Total показывает выборки, взятые при выполнении этой функции или функций, вызванных из нее (выборка до глубины, определяемой платформой c). Столбец Cumul показывает сумму всех столбцов Self до и включая эту строку в таблице.

Как видите, две из первых трех записей относятся к функциям, связанным с sub, и проценту выборок. взятый во время этих функций непропорционально больше, чем остальные вызовы функций. Это заставляет меня задуматься: а subst эффективно реализован в sbcl? Если нет, есть ли более эффективные альтернативы, которые я мог бы использовать для замены?

Спасибо за вашу помощь

1 Ответ

5 голосов
/ 15 февраля 2020

Проверьте стандартные функции sublis и nsublis. Они используют список ассо c для подстановок. 

CL-USER > (sublis '((x . 10) (y . 20))
                  '(* x (+ x y) (* y y)))
(* 10 (+ 10 20) (* 20 20))

Стиль:

Я бы не писал функцию подстановки в рекурсивном стиле. 

(defun subst-bindings (bindings generic)
  (loop for (b v) in bindings
        do (setf generic (subst v b generic)))
  generic)

Выше гарантирует, что это на самом деле все oop и деструктуризация делает код немного короче для чтения в этом случае. В переносимых хвостовых рекурсивных функциях Common Lisp не всегда они преобразуются в эффективные l oop.

...