why is reverse a string in-place so much slower than a vector?

why is reverse a string in-place so much slower than a vector?

[Leo Liu]

(defun rev (a)
  (let ((l (length a)))
    (dotimes (i (floor l 2) a)
      (cl-rotatef (aref a i) (aref a (1- (- l i)))))))

-- 
Sent from my Emacs

Re: why is reverse a string in-place so much slower than a vector?

[Leo Liu]

On 2014-04-25 16:12 +0800, Leo Liu wrote:
> (defun rev (a)
>   (let ((l (length a)))
>     (dotimes (i (floor l 2) a)
>       (cl-rotatef (aref a i) (aref a (1- (- l i)))))))

Sorry didn't finish the post.

Assume we are in a buffer visiting subr.el:

(benchmark-run 1 (rev (buffer-string)))
(11.774416366 1 0.060193897999999635)

(benchmark-run 1 (rev (cl-coerce (buffer-string) 'vector)))
(0.067042623 0 0.0)

So why is this so much slower on string?

Leo

Re: why is reverse a string in-place so much slower than a vector?

[Rüdiger Sonderfeld]

On Friday 25 April 2014 16:17:42 Leo Liu wrote:
> So why is this so much slower on string?

This is a bit of a guess.  But I think the problem is that `aref' has to do 
more complicated operations for multi-byte strings to correctly decode them.  
While for a vector it can simply access every single bytes.

(with-current-buffer "subr.el" (multibyte-string-p (buffer-substring (point-
min) (point-max))))
-> t

Regards,
Rüdiger

Re: why is reverse a string in-place so much slower than a vector?

[Andreas Schwab]

Leo Liu <sdl.web@gmail.com> writes:

> Assume we are in a buffer visiting subr.el:
>
> (benchmark-run 1 (rev (buffer-string)))
> (11.774416366 1 0.060193897999999635)
>
> (benchmark-run 1 (rev (cl-coerce (buffer-string) 'vector)))
> (0.067042623 0 0.0)
>
> So why is this so much slower on string?

String random access has linear complexity: there is a single element
cache for the last known char->byte mapping for the last accessed
string, and the runtime depends on the distance from this point.  Your
rev function represents the worst case behaviour.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: why is reverse a string in-place so much slower than a vector?

[Leo Liu]

On 2014-04-25 11:14 +0200, Andreas Schwab wrote:
> String random access has linear complexity: there is a single element
> cache for the last known char->byte mapping for the last accessed
> string, and the runtime depends on the distance from this point.  Your
> rev function represents the worst case behaviour.

Thanks for this piece of critical information. I guess this is all due
to `string_char_to_byte'?

Leo

Re: why is reverse a string in-place so much slower than a vector?

[Andreas Schwab]

Leo Liu <sdl.web@gmail.com> writes:

> I guess this is all due to `string_char_to_byte'?

No, it is all due to the variable length nature of the UTF-8 encoding.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: why is reverse a string in-place so much slower than a vector?

[Leo Liu]

On 2014-04-25 13:00 +0200, Andreas Schwab wrote:
> No, it is all due to the variable length nature of the UTF-8 encoding.

Make sense and thanks again.

Leo