Улучшение скорости манипуляций с строками

Question

Это следующий вопрос, вроде этого: Write an efficient string replacement function?.

Будущее (хотя и отдаленное) будущее, я надеюсь получить обработку естественного языка. Конечно, из-за этого важна скорость манипулирования строками. Случайно, я наткнулся на этот тест: http://raid6.com.au/~onlyjob/posts/arena/ - все тесты предвзяты, это не исключение. Однако он поднял для меня важный вопрос. И поэтому я написал несколько тестов, чтобы увидеть, как я делаю:

Это была моя первая попытка (я буду называть его #A):

#A

(defun test() 
    (declare (optimize (debug 0) (safety 0) (speed 3))) 
    (loop with addidtion = (concatenate 'string "abcdefgh" "efghefgh") 
    and initial = (get-internal-real-time) 
    for i from 0 below (+ (* (/ 1024 (length addidtion)) 1024 4) 1000) 
    for ln = (* (length addidtion) i) 
    for accumulated = addidtion 
    then (loop with concatenated = (concatenate 'string accumulated addidtion) 
      for start = (search "efgh" concatenated) 
      while start do (replace concatenated "____" :start1 start) 
      finally (return concatenated)) 
    when (zerop (mod ln (* 1024 256))) do 
     (format t "~&~f s | ~d Kb" (/ (- (get-internal-real-time) initial) 1000) (/ ln 1024))) 
    (values)) 

(test) 

разделительными перегородками с результаты, я пытался использовать cl-ppcre - я не знаю, что я надеялся, но результаты вышли, как на самом деле плохо ... Вот код, который я использовал для тестирования:

#b

(ql:quickload "cl-ppcre") 

(defun test() 
    (declare (optimize (debug 0) (safety 0) (speed 3))) 
    (loop with addidtion = (concatenate 'string "abcdefgh" "efghefgh") 
    and initial = (get-internal-real-time) 
    for i from 0 below (+ (* (/ 1024 (length addidtion)) 1024 4) 1000) 
    for ln = (* (length addidtion) i) 
    for accumulated = addidtion 
    then (cl-ppcre:regex-replace-all "efgh" (concatenate 'string accumulated addidtion) "____") 
    when (zerop (mod ln (* 1024 256))) do 
     (format t "~&~f s | ~d Kb" (/ (- (get-internal-real-time) initial) 1000) (/ ln 1024))) 
    (values)) 

(test) 

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

#C

(defun replace-all (input match replacement) 
    (declare (type string input match replacement) 
      (optimize (debug 0) (safety 0) (speed 3))) 
    (loop with pattern fixnum = (1- (length match)) 
    with i fixnum = pattern 
    with j fixnum = i 
    with len fixnum = (length input) do 
     (cond 
     ((>= i len) (return input)) 
     ((zerop j) 
      (loop do 
       (setf (aref input i) (aref replacement j) i (1+ i)) 
       (if (= j pattern) 
        (progn (incf i pattern) (return)) 
        (incf j)))) 
     ((char= (aref input i) (aref match j)) 
      (decf i) (decf j)) 
     (t (setf i (+ i 1 (- pattern j)) j pattern))))) 

(defun test() 
    (declare (optimize (debug 0) (safety 0) (speed 3))) 
    (loop with addidtion string = (concatenate 'string "abcdefgh" "efghefgh") 
    and initial = (get-internal-real-time) 
    for i fixnum from 0 below (+ (* (/ 1024 (length addidtion)) 1024 4) 1000) 
    for ln fixnum = (* (length addidtion) i) 
    for accumulated string = addidtion 
    then (replace-all (concatenate 'string accumulated addidtion) "efgh" "____") 
    when (zerop (mod ln (* 1024 256))) do 
     (format t "~&~f s | ~d Kb" (/ (- (get-internal-real-time) initial) 1000) (/ ln 1024))) 
    (values)) 

(test) 

Почти медленный как cl-ppcre! Теперь это невероятно! Здесь нет ничего такого, что могло бы привести к такой плохой работе ... И все же это сосать :(

Понимая, что стандартные функции выполнялись лучше всего, я заглянул в источник SBCL и после некоторых чтение я пришел с этим:

#D

(defun replace-all (input match replacement &key (start 0)) 
    (declare (type simple-string input match replacement) 
      (type fixnum start) 
      (optimize (debug 0) (safety 0) (speed 3))) 
    (loop with input-length fixnum = (length input) 
    and match-length fixnum = (length match) 
    for i fixnum from 0 below (ceiling (the fixnum (- input-length start)) match-length) do 
     (loop with prefix fixnum = (+ start (the fixnum (* i match-length))) 
      for j fixnum from 0 below match-length do 
      (when (<= (the fixnum (+ prefix j match-length)) input-length) 
       (loop for k fixnum from (+ prefix j) below (the fixnum (+ prefix j match-length)) 
       for n fixnum from 0 do 
        (unless (char= (aref input k) (aref match n)) (return)) 
       finally 
        (loop for m fixnum from (- k match-length) below k 
         for o fixnum from 0 do 
         (setf (aref input m) (aref replacement o)) 
         finally 
         (return-from replace-all 
          (replace-all input match replacement :start k)))))) 
     finally (return input))) 

(defun test() 
    (declare (optimize (debug 0) (safety 0) (speed 3))) 
    (loop with addidtion string = (concatenate 'string "abcdefgh" "efghefgh") 
    and initial = (get-internal-real-time) 
    for i fixnum from 0 below (+ (* (/ 1024 (length addidtion)) 1024 4) 1000) 
    for ln fixnum = (* (length addidtion) i) 
    for accumulated string = addidtion 
    then (replace-all (concatenate 'string accumulated addidtion) "efgh" "____") 
    when (zerop (mod ln (* 1024 256))) do 
     (format t "~&~f s | ~d Kb" (/ (- (get-internal-real-time) initial) 1000) (/ ln 1024))) 
    (values)) 

(test) 

Наконец, я могу выиграть, хотя незначительная часть производительности против стандартной библиотеки - но это все еще очень-очень плохо по сравнению с почти все остальное ...

Вот таблица с результатами:

| SBCL #A | SBCL #B | SBCL #C | SBCL #D | C gcc 4 -O3 | String size | 
|-----------+-----------+------------+-----------+-------------+-------------| 
| 17.463 s | 166.254 s | 28.924 s | 16.46 s | 1 s   | 256 Kb  | 
| 68.484 s | 674.629 s | 116.55 s | 63.318 s | 4 s   | 512 Kb  | 
| 153.99 s | gave up | 264.927 s | 141.04 s | 10 s  | 768 Kb  | 
| 275.204 s | . . . . . | 474.151 s | 251.315 s | 17 s  | 1024 Kb  | 
| 431.768 s | . . . . . | 745.737 s | 391.534 s | 27 s  | 1280 Kb  | 
| 624.559 s | . . . . . | 1079.903 s | 567.827 s | 38 s  | 1536 Kb  | 

Теперь вопрос: Что я сделал не так? Это что-то неотъемлемое для строк Лиспа? Может ли это быть смягчено через ... что?

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

---

EDIT: Просто для записи, я сейчас пытаюсь использовать эту библиотеку: https://github.com/Ramarren/ropes, чтобы иметь дело со строками конкатенации. К сожалению, в нем нет функции замены, и выполнение нескольких замещений не очень тривиально. Но я буду держать этот пост обновленным, когда у меня что-то есть.

---

Я попытался немного изменить вариант huaiyuan для использования заполнения указателей буях вместо конкатенации (чтобы достичь чего-то похожее на StringBuilder предложил Пауло Мадейры. Это, вероятно, может быть оптимизирована дальше, но я не уверен, о типах/который будет метод быстрее/это будет стоит пересмотреть типы для * и +, чтобы заставить их работать только на fixnum или signed-byte Во всяком случае, вот код и тест:.

(defun test/e() 
    (declare (optimize speed)) 
    (labels ((min-power-of-two (num) 
      (declare (type fixnum num)) 
      (decf num) 
      (1+ 
       (progn 
       (loop for i fixnum = 1 then (the (unsigned-byte 32) (ash i 1)) 
        while (< i 17) do 
        (setf num 
          (logior 
          (the fixnum 
           (ash num (the (signed-byte 32) 
               (+ 1 (the (signed-byte 32) 
                 (lognot i)))))) num))) num))) 
      (join (x y) 
      (let ((capacity (array-dimension x 0)) 
        (desired-length (+ (length x) (length y))) 
        (x-copy x)) 
       (declare (type fixnum capacity desired-length) 
         (type (vector character) x y x-copy)) 
       (when (< capacity desired-length) 
       (setf x (make-array 
          (min-power-of-two desired-length) 
          :element-type 'character 
          :fill-pointer desired-length)) 
       (replace x x-copy)) 
       (replace x y :start1 (length x)) 
       (setf (fill-pointer x) desired-length) x)) 
      (seek (old str pos) 
      (let ((q (position (aref old 0) str :start pos))) 
       (and q (search old str :start2 q)))) 
      (subs (str old new) 
      (loop for p = (seek old str 0) then (seek old str p) 
       while p do (replace str new :start1 p)) 
      str)) 
    (declare (inline min-power-of-two join seek subs) 
      (ftype (function (fixnum) fixnum) min-power-of-two)) 
    (let* ((builder 
      (make-array 16 :element-type 'character 
         :initial-contents "abcdefghefghefgh" 
         :fill-pointer 16)) 
      (ini (get-internal-real-time))) 
     (declare (type (vector character) builder)) 
     (loop for i fixnum below (+ 1000 (* 4 1024 1024 (/ (length builder)))) 
     for j = builder then 
      (subs (join j builder) "efgh" "____") 
     for k fixnum = (* (length builder) i) 
     when (= 0 (mod k (* 1024 256))) 
     do (format t "~&~8,2F sec ~8D kB" 
        (/ (- (get-internal-real-time) ini) 1000) 
        (/ k 1024)))))) 

---

1.68 sec  256 kB 
    6.63 sec  512 kB 
    14.84 sec  768 kB 
    26.35 sec  1024 kB 
    41.01 sec  1280 kB 
    59.55 sec  1536 kB 
    82.85 sec  1792 kB 
    110.03 sec  2048 kB 

Answer 1

Шея бутылки - это функция search, которая, возможно, не оптимизирована в SBCL. Следующая версия использует position, чтобы помочь ему пропустить невозможно регион и около 10 раз быстрее, чем ваша версия #A на моей машине:

(defun test/e() 
    (declare (optimize speed)) 
    (labels ((join (x y) 
      (concatenate 'simple-base-string x y)) 
      (seek (old str pos) 
      (let ((q (position (char old 0) str :start pos))) 
       (and q (search old str :start2 q)))) 
      (subs (str old new) 
      (loop for p = (seek old str 0) then (seek old str p) 
        while p do (replace str new :start1 p)) 
      str)) 
    (declare (inline join seek subs)) 
    (let* ((str (join "abcdefgh" "efghefgh")) 
      (ini (get-internal-real-time))) 
     (loop for i below (+ 1000 (* 4 1024 1024 (/ (length str)))) 
      for j = str then (subs (join j str) "efgh" "____") 
      for k = (* (length str) i) 
      when (= 0 (mod k (* 1024 256))) 
       do (format t "~&~8,2F sec ~8D kB" 
         (/ (- (get-internal-real-time) ini) 1000) 
         (/ k 1024)))))) 

Answer 2

Тесты на этой странице, являются действительно предвзято, так что давайте посмотрим, насколько , Автор утверждает, что для проверки манипуляций со строками, но вот то, что программы в этом тесте страницы:

• Строки конкатенация
• управления памятью, либо явный (C) или неявных
• В некоторых языках, регулярные выражения
• В других алгоритмов строки поиска и замены подстрок
  • доступа памяти, которая имеет границы проверки на нескольких языках

Существует слишком много аспектов только здесь. Вот как это измеряется:

• Реальное время в секундах

Это печально, так как компьютер должен быть полностью посвящен запуску только этот тест для разумных значений, без каких-либо других процессов вообще, такие как сервисы, антивирусы, браузеры, даже ожидающие * nix оболочки. Время CPU было бы намного более полезным, вы могли бы даже запустить тесты на виртуальной машине.

Другой аспект заключается в том, что символы в C, C++, Perl, Python, PHP и Ruby являются 8-разрядными, но они являются 16-разрядными во многих других тестируемых языках. Это означает, что использование памяти подчеркивается в самых разных количествах, по крайней мере, в 2 раза. Здесь промахи в кеше гораздо заметнее.

Я подозреваю, что Perl настолько быстр, что проверяет свои аргументы один раз перед вызовом функции C, а не постоянно проверяет границы. Другие языки с 8-битными строками работают не так быстро, но все же достаточно быстрые.

JavaScript V8 имеет строки, которые являются ASCII, если возможно, поэтому, если добавленный и замененный токен был «ëfgh», вы заплатили бы гораздо больше в этой реализации.

Python 3 почти в три раза медленнее, чем Python 2, и я предполагаю, что это связано с внутренним представлением строк wchar_t * vs char *.

JavaScript SpiderMonkey использует 16-разрядные строки. Я не копал много источников, но файл jsstr.h упоминает веревки.

Java настолько медленный, потому что String s неизменяемы, и поэтому для этого эталона это определенно не соответствующий тип данных. Вы платите цену за создание огромной строки после каждого .replace(). Я не тестировал, но, вероятно, StringBuffer был бы намного быстрее.

Итак, этот ориентир должен приниматься не только с солью, но и с горсткой.

---

В Common Lisp, проверки границ и типа диспетчеризации в aref и его setf, вероятно, узкие места.

Для хорошей производительности вам нужно будет вырезать общие последовательности string и использовать simple-string s или simple-vector s, в зависимости от того, какая ваша оптимизация будет оптимальной. Затем у вас должен быть способ сделать звонки schar или svref и их setf способным формам, которые обходят проверку границ. Отсюда вы можете реализовать свои собственные simple-string-search или simple-character-vector-search (и replace-simple-string или replace-simple-vector, хотя они играют гораздо меньшую роль в этом конкретном примере) с полной оптимизацией скорости и объявлениями типов с проверкой границ в начале каждого вызова вместо каждого доступ к массиву.

Достаточно умный компилятор ™ сделал бы все это для вас, учитывая «правильные» декларации. Проблема в том, что вам нужно будет использовать (concatenate 'simple-string/simple-vector ...), потому что ни простые строки, ни простые векторы не настраиваются.

С уплотняющим/движущимся GC, в этих случаях всегда существует штраф (например, копирование массива/объекта), и выбор между настройкой массива и конкатенацией должен действительно зависеть от проверок профилирования. В противном случае настройка может быть быстрее, чем конкатенация, тогда как для увеличения массива достаточно свободной памяти.

Вы можете использовать регулируемые массивы, если реализация будет получить доступ фактических элементов непосредственно после непродолжительной проверки границ во главе оптимизированных звонков/расширения search и replace с регулируемыми массивами (например, имея внутренние определения, которые принимают фактические смещенный вектор/массив и начальные и конечные смещения).

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

---

В качестве примечания, пример код C полон ошибки, такие как выключение за одним (-1, на самом деле) распределение (на strcat вызов написать дополнительные байты, то нуль строки терминатор), неинициализированный нуль строка gstr (первое strcat произведения удачи, потому что память не может быть инициализирована до 0), преобразования из size_t и time_t к int и предположению этих типов в строке в printf формате, неиспользованная переменная pos_c который инициализируется первым распределением для gstr, которое увеличивается без учета того, что realloc м ay перемещать буфер и вообще не обрабатывать ошибки.