[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: why is reverse a string in-place so much slower than a vector?
|
From: |
Andreas Schwab |
|
Subject: |
Re: why is reverse a string in-place so much slower than a vector? |
|
Date: |
Fri, 25 Apr 2014 11:14:11 +0200 |
|
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) |
Leo Liu <address@hidden> 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, address@hidden
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5
"And now for something completely different."