Migliorare la velocità delle manipolazioni di stringhe

Question

Questa è una domanda di follow-up, simile a questa: Write an efficient string replacement function?.

In un futuro (anche se lontano) spero di riuscire a eseguire l'elaborazione del linguaggio naturale. Naturalmente la velocità della manipolazione delle stringhe è importante per questo. Per inciso, ho inciampato su questo test: http://raid6.com.au/~onlyjob/posts/arena/ - tutti i test sono di parte, non fa eccezione. Tuttavia, ha sollevato una domanda importante per me. E così ho scritto un paio di test per vedere come sto facendo:

Questo era il mio primo tentativo (lo chiamerò #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) 

Sconcertato con i risultati, ho cercato di usare cl-ppcre - non so quello che speravo per, ma il risultato è venuto fuori come davvero male ... Ecco il codice che ho usato per il test:

#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) 

Bene, allora, nella speranza di eludere forse alcune generalizzazioni, ho deciso di scrivere il mio, anche se la versione un po 'ingenua:

#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) 

Quasi come lento come cl-ppcre! Ora, è incredibile! Non c'è nulla che possa individuare qui tale da risultare in una prestazione così scarsa ... E comunque fa schifo :(

Rendendosi conto che le funzioni standard hanno funzionato al meglio finora, ho esaminato la fonte SBCL e dopo alcuni lettura mi si avvicinò con questo:

#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) 

Infine, posso vincere, anche se una piccola frazione delle prestazioni rispetto della libreria standard - ma è ancora molto-molto male rispetto a quasi tutto il resto ...

Ecco la tabella con i risultati:

| 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  | 

Ora, la domanda: Che cosa ho fatto di sbagliato? È qualcosa di inerente alle stringhe Lisp? Questo può probabilmente essere mitigato attraverso ... cosa?

Nel lungo periodo, prenderei in considerazione la possibilità di scrivere una libreria specializzata per l'elaborazione delle stringhe. Se il problema non è il mio codice errato, ma piuttosto l'implementazione. Avrebbe senso farlo? Se sì, quale lingua suggeriresti per farlo?

---

EDIT: Solo per la cronaca, ora sto cercando di utilizzare questa libreria: https://github.com/Ramarren/ropes a che fare con le stringhe concatenazione. Sfortunatamente, non ha una funzione di sostituzione e fare sostituzioni multiple non è molto banale. Ma terrò aggiornato questo post quando avrò qualcosa.

---

Ho provato a cambiare un po 'la variante di Huaiyuan utilizzare fill-puntatori di matrice invece di concatenazione di stringhe (per ottenere qualcosa di simile a StringBuilder suggerito da Paulo Madeira. Probabilmente può essere ottimizzato ulteriormente, ma io non sono sicuro circa i tipi /, che sarà il metodo essere più veloce/sarà la pena di ridefinire i tipi per * e + di farli operare solo su fixnum o signed-byte ad ogni modo, ecco il codice e il punto di riferimento:.

(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

Il collo della bottiglia è la funzione search, che forse non è ottimizzata in SBCL. La seguente versione utilizza position per aiutarla a saltare oltre regione impossibile ed è circa 10 volte più velocemente la vostra versione #A sulla mia macchina:

(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

I test in quella pagina sono davvero di parte, vediamo di quanto . L'autore sostiene di testare manipolazione delle stringhe, ma ecco quello che i programmi in quella pagina di prova:

• concatenazione di stringhe
• gestione della memoria, sia esplicita (C) o implicita
• In alcune lingue, espressioni regolari
• In altri, algoritmi di ricerca di stringa e la sostituzione sottostringa
  • di accesso alla memoria, che ha controlli limite a diverse lingue

Ci sono troppi aspetti proprio qui. Ecco come vengono misurati:

• in tempo reale in secondi

Questo è un peccato, visto che il computer doveva essere completamente dedicato al correre solo questo test per i valori ragionevoli, senza altri processi di sorta, come ad come servizi, antivirus, browser, persino una shell * nix in attesa. Il tempo della CPU sarebbe molto più utile, potresti persino eseguire i test in una macchina virtuale.

Un altro aspetto è che i caratteri in C, C++, Perl, Python, PHP e Ruby sono a 8 bit, ma sono 16 bit in molte delle altre lingue testate. Ciò significa che l'utilizzo della memoria è stressato in quantità molto diverse, di almeno un fattore 2. Qui, i messaggi mancanti della cache sono molto più evidenti.

Sospetto che il motivo per cui Perl è così veloce è che controlla i suoi argomenti una volta prima di richiamare una funzione C, invece di controllare costantemente i limiti. Altre lingue con stringhe a 8 bit non sono così veloci, ma sono comunque ragionevolmente veloci.

JavaScript V8 ha stringhe che sono ASCII se possibile, quindi se il token aggiunto e sostituito era "ëfgh", si pagherebbe molto di più in tale implementazione.

Python 3 è quasi tre volte più lento di Python 2 e suppongo sia dovuto alla rappresentazione interna wchar_t * rispetto a char * di stringhe.

JavaScript SpiderMonkey utilizza stringhe a 16 bit. Non ho scavato molto il sourced, ma il file jsstr.h menziona le corde.

Java è così lento perché String s sono immutabili, e quindi per questo benchmark, non è sicuramente il tipo di dati appropriato. Stai pagando il prezzo di generare una stringa enorme dopo ogni .replace(). Non ho provato, ma probabilmente un StringBuffer sarebbe molto più veloce.

Quindi, questo punto di riferimento deve essere preso non solo con un granello di sale, ma con una manciata di esso.

---

In Common Lisp, il controllo dei limiti e digitare dispacciamento in aref e la sua setf sono probabilmente i colli di bottiglia.

Per prestazioni ottimali, è necessario abbandonare le sequenze generiche string e utilizzare simple-string s o simple-vector s, a seconda di quale sia l'ottimizzazione ottimale. Quindi, si dovrebbe avere un modo per effettuare chiamate a schar o svref e ai loro moduli setf in grado di ignorare il controllo dei limiti. Da qui, è possibile implementare il proprio simple-string-search o simple-character-vector-search (e replace-simple-string o replace-simple-vector, sebbene svolgano un ruolo molto più piccolo in questo particolare esempio) con ottimizzazione a velocità piena e dichiarazioni di tipo, con controllo dei limiti all'inizio di ogni chiamata anziché a ogni accesso alla matrice.

Un compilatore sufficientemente intelligente farebbe tutto questo per te con dichiarazioni "appropriate". Il problema è che dovresti usare (concatenate 'simple-string/simple-vector ...), perché né le stringhe semplici né i vettori semplici sono regolabili.

Con una compattazione/GC movimento, c'è sempre una penalità in questi casi (ad esempio matrice/oggetto copiatura), e scegliendo tra matrice e regolazione concatenazione deve realmente dipendere profilatura test. Altrimenti, la regolazione può essere molto più veloce della concatenazione, mentre c'è abbastanza memoria libera per far crescere la matrice.

Si potrebbe usare matrici regolabili, se l'applicazione potrebbe accedere agli elementi effettivi direttamente dopo una breve verifica dei limiti alla testa di chiamate ottimizzate per/espansioni di search e replace con gli array regolabili (ad esempio avendo definizioni interne che prendono l'effettivo vettore/array spostato e inizio e fine offset).

Ma sto speculando molto qui, devi compilare, ispezionare la compilazione e il profilo in ogni implementazione per fatti reali.

---

Come nota laterale, il codice di esempio C è piena di insetti, come off-by-one (-1, in realtà) allocazioni (i strcat chiamate scrivere un byte aggiuntivo, il terminatore di stringa terminata da zero), un inizializzata stringa alla terminazione gstr (primi strcat opere di fortuna, perché la memoria non potrebbe essere inizializzato a 0), conversioni size_t e time_t a int ed assunzione di questi tipi in una stringa di formato printf, una variabile inutilizzata pos_c inizializzato con la prima allocazione per gstr che viene incrementata senza tenere conto del fatto che realloc m spostare il buffer e nessun errore di gestione di sorta.