Opened 11 years ago
Closed 11 years ago
#81 closed defect (fixed)
Reversing a string is slow
Reported by: | Raymond Toy | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | Core | Version: | 2013-05 |
Keywords: | Cc: |
Description
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.
Change History (2)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
commit 78cce51df441b220c071024fb5e616f1928184dd Author: Raymond Toy <toy.raymond@…> Date: Sat May 18 17:44:02 2013 -0700
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.
Note: See
TracTickets for help on using
tickets.
Here is another test, with surrogate pairs:
Although the string is twice as long (because of the surrogates), the time is the same.