Reversing a string is slow

[Raymond Toy]

Consider this:

(defparameter *s* (make-string 1000000))
(defun time-rev (s)
  (dotimes (k 100 nil)
    (declare (fixnum k))
    (setf s (reverse s)))
  s)
(compile 'time-rev)
(time (prog1 t (time-rev *s*)))
; Evaluation took:
;   10.23 seconds of real time
;   10.151641 seconds of user run time
;   0.079628 seconds of system run time
;   31,310,669,055 CPU cycles
;   [Run times include 0.08 seconds GC run time]
;   0 page faults and
;   200,114,224 bytes consed.

Since strings are basically arrays of unsigned 16-bit integers, compare the time when reversing an array:

(defparameter *v* (make-array 1000000 :element-type '(unsigned-byte 16)))
(time (prog1 t (time-rev *v*)))
; Evaluation took:
;   3.62 seconds of real time
;   3.581727 seconds of user run time
;   0.039302 seconds of system run time
;   11,089,005,122 CPU cycles
;   [Run times include 0.05 seconds GC run time]
;   0 page faults and
;   200,116,120 bytes consed.

Reversing a string is 3 times slower. There is some cost since strings are utf-16 encoded, but we shouldn't be 3 times slower.

[Raymond Toy]

Here is another test, with surrogate pairs:

(defparameter *s2* (lisp::codepoints-string (loop for k from 0 below 1000000 collect (+ 65536 k))))
(time (prog1 t (time-rev *s2*)))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   10.08 seconds of real time
;   10.050677 seconds of user run time
;   0.017808 seconds of system run time
;   30,831,596,637 CPU cycles
;   [Run times include 0.14 seconds GC run time]
;   0 page faults and
;   400,215,072 bytes consed.

Although the string is twice as long (because of the surrogates), the time is the same.

[toy.raymond@…]

commit 78cce51df441b220c071024fb5e616f1928184dd Author: Raymond Toy <toy.raymond@…> Date: Sat May 18 17:44:02 2013 -0700

Fix ticket:81 and fix ticket:83.

From ticket 81, the tests are now:

(time (prog1 t (time-rev *s*)))
; Evaluation took:
;   0.49 seconds of real time
;   0.481813 seconds of user run time
;   0.003624 seconds of system run time
;   1,490,776,936 CPU cycles
;   [Run times include 0.13 seconds GC run time]
;   0 page faults and
;   200,073,704 bytes consed.

(time (prog1 t (time-rev *s2*)))
; Evaluation took:
;   0.97 seconds of real time
;   0.965893 seconds of user run time
;   0.005139 seconds of system run time
;   2,980,415,911 CPU cycles
;   [Run times include 0.23 seconds GC run time]
;   0 page faults and
;   400,005,560 bytes consed.

So the new string-reverse* is 20 times faster for strings without surrogates and 10 times faster for strings containing only surrogates.