Блог

Используя SBCL 1.4.12, я рассматриваю упражнение 17.9 из книги Стюарта Шапиро Common Lisp: интерактивный подход и синхронизацию reverse функции, применяемой к списку из 10 000 элементов. Когда я использую эту функцию, используя один и тот же список, time функция каждый раз сообщает разное количество байтов.

Вот код для этой reverse функции:

 (defun reverse2 (l1 l2)
  "Returns a list consisting of the members of L1 in reverse order
   followed by the members of L2 in original order."
  (check-type l1 list)
  (check-type l2 list)
  (if (endp l1) l2
      (reverse2 (rest l1)
                (cons (first l1) l2))))

(defun reverse1 (l)
  "Returns a copy of the list L1
   with the order of members reversed."
  (check-type l list)
  (reverse2 l '()))
 

Я сгенерировал список в REPL с помощью:

 (defvar *test-list* '())
(dotimes (x 10000)
  (setf *test-list* (cons x *test-list*)))
 

Вот результаты четырех тестовых запусков:

 CL-USER> (time (ch17:reverse1 *test-list*))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  520,386 processor cycles
  145,696 bytes consed

CL-USER> (time (ch17:reverse1 *test-list*))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  260,640 processor cycles
  178,416 bytes consed

CL-USER> (time (ch17:reverse1 *test-list*))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  279,822 processor cycles
  178,416 bytes consed

CL-USER> (time (ch17:reverse1 *test-list*))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  264,700 processor cycles
  161,504 bytes consed
 

Второй и третий тестовые прогоны (с интервалом в несколько минут) показывают одинаковое количество использованных байтов, но два других показывают разные числа. Я ожидал, что время будет меняться, но я не ожидал, что количество передаваемых байтов будет меняться. Я вижу, что в HyperSpec говорится о time функции, которая:

Как правило, эти тайминги не гарантированно являются достаточно надежными для маркетинговых сравнений. Их ценность в первую очередь эвристическая, для целей настройки.

Но я ожидал, что это относится к таймингам, а не к количеству байтов. Являются ли значения, передаваемые в байтах time , недостоверными? Существует ли за кулисами оптимизация, которая отвечает за это? Что я упускаю из виду?

Количество передаваемых байтов (в смысле «выделенных байтов памяти») зависит от всего:

• это зависит от того, сколько объектов каких типов вы выделяете;
• это зависит от тонких деталей реализации распределителя, таких как то, распределяет ли он большими порциями и записывается ли «распределение» между выделением больших порций;
• это зависит от сборщика мусора — был ли он запущен? если да, то какого рода? насколько сложным является GC? выделяет ли сам GC? как подсчитывается распределение по GCS?
• это зависит от того, выполняет ли система другое распределение, например, в других потоках, и учитывается ли это распределение или нет в вашем потоке — есть только один распределитель или есть распределители для каждого потока?
• это зависит от фазы Луны и от того, является ли Плутон планетой;
• и так далее.

В общем, если у вас очень простая однопоточная реализация с очень простым распределителем и очень простым GC, то отслеживать распределение легко, и вы получите надежные цифры. Многие реализации Lisp когда-то были такими: их было легко понять, и вам приходилось пить много чая, пока они что-то делали (хорошо, тогда машины были медленнее, но все же они часто были впечатляюще медленными даже по стандартам того времени). Теперь у Lisp есть несколько потоков, сложные распределители и GCS, и они действительно быстры, но сколько происходит выделение, стало вопросом, на который очень сложно ответить и часто немного непредсказуемо.