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