Почему списки быстрее, чем векторы для простого доступа? - PullRequest
Новая
       51

Почему списки быстрее, чем векторы для простого доступа?

3 голосов
/ 13 апреля 2020

Я знаю, что есть похожие вопросы, например, Массивы и списки в Лиспе: почему списки намного быстрее в приведенном ниже коде? , но списки кажутся быстрее, чем векторы, даже для простого доступа к элементам, что нелогично. Вот мой пример: 

(let ((x '(0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(let ((x #(0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

Первый блок на моей машине работает с SBCL почти в два раза быстрее, чем второй блок. (И если я тестирую время доступа для чтения, то и списки, и векторы имеют почти одинаковое время). Я ожидаю, что список будет примерно в 10 раз медленнее, потому что ему нужно пройти до конца, чтобы найти 9-й элемент. Почему список быстрее?

Ответы [ 2 ]

4 голосов
/ 13 апреля 2020

Странное поведение связано с тем, что вы изменяете постоянные данные, и это может привести к неопределенному поведению (см. руководство ):

Последствия не определены, если литеральные объекты (включая объекты в кавычках) деструктивно изменены.

Если вы измените два выражения, чтобы изменить две не буквальные структуры данных, как в: 

(let ((x (list 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(let ((x (vector 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

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

3 голосов
/ 13 апреля 2020

Я не могу воспроизвести ваши наблюдения. Здесь ниже то, что я измеряю, наряду с двумя другими тестами с различными типами массивов. Прежде всего обратите внимание, что мой установочный скрипт выполняет следующие действия: 

(sb-ext:restrict-compiler-policy 'debug 3)
(sb-ext:restrict-compiler-policy 'safety 3)

Это может повлиять на компиляцию кода.

Ваши тесты 

(print :list)
(let ((x (list 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(print :simple-vector)
(let ((x (vector 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

Трассировка выглядит следующим образом : 

:LIST 
Evaluation took:
  6.649 seconds of real time
  6.649545 seconds of total run time (6.649545 user, 0.000000 system)
  100.02% CPU
  21,224,869,441 processor cycles
  0 bytes consed


:SIMPLE-VECTOR 
Evaluation took:
  0.717 seconds of real time
  0.716708 seconds of total run time (0.716708 user, 0.000000 system)
  100.00% CPU
  2,287,130,610 processor cycles
  0 bytes consed

Что касается вашего исходного вопроса, разница между использованием списков и векторов почти в 10 раз выше (9,27). Я не знаю, почему ваши тесты показывают по-другому (правка: так, очевидно, это было связано с неопределенным поведением, я видел, как вы мутировали постоянные данные и исправляли их в моем коде, не думая, что они могут быть связаны: /)

Специализированный массивы

Я также попытался описать массив как можно точнее, объявив в его типе тип элементов, которые он содержит, (mod 10) и размеры массива (10). Фактический тип элемента массива в SBCL - (UNSIGNED-BYTE 4), что означает, что массив может быть упакован: несколько элементов массива могут быть сохранены в машинном слове (32 или 64 бита). Упаковка хороша для места, но для хранения / доступа к элементам требуются этапы кодирования / декодирования. 

(print :packed-array)
(let ((x (make-array 10
                     :element-type '(mod 10)
                     :initial-contents '(0 1 2 3 4 5 6 7 8 9))))
  (declare (type (array (mod 10) (10)) x)
           (optimize (speed 3)))
  (time (dotimes (i 1000000000)
          (setf (aref x 9) (the (mod 10) 0)))))

У меня также есть версия, где фактический тип элемента массива (unsigned-byte 32), который должен избегать выполнения преобразований: 

(print :unpacked-array)
(let ((x (make-array 10
                     :element-type '(unsigned-byte 32)
                     :initial-contents '(0 1 2 3 4 5 6 7 8 9))))
  (declare (type (array (unsigned-byte 32) (10)) x)
           (optimize (speed 3)))
  (time (dotimes (i 1000000000)
          (setf (aref x 9) (the (mod 10) 0)))))

Дополнительные тесты: 

:PACKED-ARRAY 
Evaluation took:
  1.168 seconds of real time
  1.167929 seconds of total run time (1.167929 user, 0.000000 system)
  100.00% CPU
  3,727,528,968 processor cycles
  0 bytes consed

Здесь вы можете видеть, что использование наиболее точного типа на самом деле замедляет тесты в данном конкретном случае. Это, вероятно, может быть объяснено накладными расходами операций декодирования / кодирования (?) 

:UNPACKED-ARRAY 
Evaluation took:
  0.231 seconds of real time
  0.231094 seconds of total run time (0.231094 user, 0.000000 system)
  100.00% CPU
  737,633,062 processor cycles
  0 bytes consed

С массивами 32-битных значений время выполнения меньше.

Если вы вызываете disassemble для тесты для обоих типов векторов (просто уберите вызов time, который добавляет много шума и, возможно, понизит уровни отладки), в итоге разница сводится к тому, какой тип регистра используется в l oop:

Простой вектор использует 64 бита (RCX), поскольку вектор должен иметь возможность хранить объекты типа T: 

; C0: L2:   B900000000       MOV ECX, 0
; C5:       48894A49         MOV [RDX+73], RCX
; C9:       4883C002         ADD RAX, 2
; CD: L3:   483D00943577     CMP RAX, 2000000000
; D3:       7CEB             JL L2

В тесте с 32-битным массивом используется регистр ECX (32 бита) . 

; 960: L2:   31C9             XOR ECX, ECX
; 962:       894A25           MOV [RDX+37], ECX
; 965:       4883C002         ADD RAX, 2
; 969: L3:   483D00943577     CMP RAX, 2000000000
; 96F:       7CEF             JL L2

Также смещения отличаются, но соответствуют типам: 

- 37 = 4 (bytes) * 9 (index) + 1 (storage for array size?)
- 73 = 8 (bytes) * 9 (index) + 1 (storage for array size?)
...