#81: Reversing a string is slow --------------------+------------------------------------------------------- Reporter: rtoy | Owner: somebody Type: defect | Status: new Priority: major | Milestone: Component: Core | Version: 2013-05 Keywords: | --------------------+------------------------------------------------------- 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.
#81: Reversing a string is slow --------------------+------------------------------------------------------- Reporter: rtoy | Owner: somebody Type: defect | Status: new Priority: major | Milestone: Component: Core | Version: 2013-05 Keywords: | --------------------+-------------------------------------------------------
Comment(by rtoy):
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.
#81: Reversing a string is slow ---------------------+------------------------------------------------------ Reporter: rtoy | Owner: somebody Type: defect | Status: closed Priority: major | Milestone: Component: Core | Version: 2013-05 Resolution: fixed | Keywords: ---------------------+------------------------------------------------------ Changes (by toy.raymond@…):
* status: new => closed * resolution: => fixed
Comment:
commit 78cce51df441b220c071024fb5e616f1928184dd Author: Raymond Toy toy.raymond@gmail.com 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.