Оптимизация SBCL: можем ли мы составить эффективный подсчет популяции для битовых векторов? - PullRequest
Новая
       115

Оптимизация SBCL: можем ли мы составить эффективный подсчет популяции для битовых векторов?

4 голосов
/ 19 июня 2020

SBCL, реализация Lisp, которую я использую, знает, что нужно компилировать (logcount x) в инструкцию x86-64 POPCNT, если x набирается как достаточно короткий unsigned-byte. Предполагая, что simple-bit-vector сохраняется SBCL в сегменте непрерывной памяти, выровненном по словам, как можно заставить компилятор выполнить аналогично оптимизированный подсчет населения в нем? Стандарт не предоставляет (bit-vector-logcount) (на мой взгляд, странное упущение); при этом он не позволяет мне (coerce) преобразовать fixnum.

Умышленно наивная реализация выглядит следующим образом; обратите внимание, что существует также Ω (1) -временной , тогда как метод Harley-Seal [1] может быть лучшим выбором для больших векторов. Но это достаточно просто, чтобы оптимизирующий компилятор мог определить намерение: 

(defun bit-vector-unsigned-logcount (x)
  "Not worrying about negative interpretations of X."
  (declare (type (simple-bit-vector 32) x)
           (optimize (speed 3) (safety 0) (debug 0)))
  (loop for b across x
        count (not (zerop b))))

На SBCL 2.0.1 я получаю следующее: 

; disassembly for BIT-VECTOR-UNSIGNED-LOGCOUNT
; Size: 67 bytes. Origin: #x52B88079                          ; BIT-VECTOR-UNSIGNED-LOGCOUNT
; 79:       31D2             XOR EDX, EDX
; 7B:       31C0             XOR EAX, EAX
; 7D:       31C9             XOR ECX, ECX
; 7F:       EB2C             JMP L1
; 81:       660F1F840000000000 NOP
; 8A:       660F1F440000     NOP
; 90: L0:   488BD0           MOV RDX, RAX
; 93:       48D1FA           SAR RDX, 1
; 96:       480FA35301       BT QWORD PTR [RBX+1], RDX
; 9B:       19D2             SBB EDX, EDX
; 9D:       83E202           AND EDX, 2
; A0:       4883C002         ADD RAX, 2
; A4:       4885D2           TEST RDX, RDX
; A7:       7404             JEQ L1
; A9:       4883C102         ADD RCX, 2
; AD: L1:   4883F840         CMP RAX, 64
; B1:       7CDD             JL L0
; B3:       488BD1           MOV RDX, RCX
; B6:       488BE5           MOV RSP, RBP
; B9:       F8               CLC
; BA:       5D               POP RBP
; BB:       C3               RET

Я дам руководство SBCL шанс высказаться.

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

Я подозреваю, что столкнулся с таким случаем, и я был бы рад помочь, но я почти ничего не знаю о взломе VOP помимо просмотра статей Пола Кхуонга здесь и здесь .

x86-64/arith.lisp определяет пару VOP, unsigned-byte-64-count и positive-fixnum-count, которые выглядят как будто их можно было бы перепрофилировать для работы, если бы мы могли разделить bit-vector на части.

[1] Muła, W., Kurz, N., & Lemire, D. (2017). Более быстрый подсчет населения с помощью инструкций AVX2 . Компьютерный журнал, 61 (1), 111–120. DOI: 10.1093 / comjnl / bxx046

...