efficient implementation of string-replace-substring / string-replace-all

[Arne Babenhauserheide]

Hi,

For wisp I created an efficient implementation of substring replacement and 
thought it might be useful for guile in general.

I optimized it a bit to get rid of (likely) quadratic behaviour:


; ,time (string-replace-substring (xsubstring "abcdefghijkl" 0 99999) "def" 
"abc")
; 1.140127s real time, 1.139714s run time.  0.958733s spent in GC.
; 0.885618s real time, 0.885350s run time.  0.742805s spent in GC.
; second number after multiple runs
(define (string-replace-substring s substring replacement)
       "Replace every instance of substring in s by replacement."
       (let ((sublen (string-length substring)))
           (let replacer
               ((newstring s)
                 (index (string-contains s substring)))
               (if (not (equal? index #f))
                  (let ((replaced (string-replace newstring replacement index 
(+ index sublen))))
                    (replacer replaced (string-contains replaced substring 
index)))
                  newstring))))


This fast and elegant approach is thanks to ijp.

I tested a two alternative approaches. The following uses explicit readonly 
substrings and is fast, the one afterwards always searches from the beginning 
and shows drastic slowdown on long strings. 

; efficient version from rev 12266d455bb0 of the wisp hg repo
; ,time (string-replace-substring-fast-but-long (xsubstring "abcdefghijkl" 0 
99999) "def" "abc")
; 1.316090s real time, 1.315626s run time.  1.129857s spent in GC.
; 0.668212s real time, 0.667948s run time.  0.482193s spent in GC.
; 0.868419s real time, 0.868131s run time.  0.685472s spent in GC
; Second and third are after multiple runs
(define (string-replace-substring-fast-but-long s substring replacement)
       "Replace every instance of substring in s by replacement."
       (let ((sublen (string-length substring)))
           (let replacer
               ((newstring s)
                 (startindex 0)
                 (addindex (string-contains s substring)))
               (if (not (equal? addindex #f))
                  (let*
                      ((index (+ startindex addindex))
                        (replaced (string-replace newstring replacement index 
(+ index sublen)))
                        (newaddindex (string-contains (substring/read-only 
replaced index) substring)))
                      (replacer replaced index newaddindex))
                  newstring))))


; less efficient version from rev a887aeb0dfe2
; ,time (string-replace-substring-slow (xsubstring "abcdefghijkl" 0 99999) 
"def" "abc")
; 5.242456s real time, 5.240834s run time.  0.358750s spent in GC.
; 5.727069s real time, 5.724973s run time.  0.835445s spent in GC.
; switches between fast and slow version
(define (string-replace-substring-slow s substring replacement)
       "Replace every instance of substring in s by replacement."
       (let ((sublen (string-length substring)))
           (let replacer
               ((newstring s)
                 (index (string-contains s substring)))
               (if (not (equal? index #f))
                  (let ((replaced (string-replace newstring replacement index 
(+ index sublen))))
                    (replacer replaced (string-contains replaced substring)))
                  newstring))))
               


ijp suggested renaming to (string-replace-all, but I do not know enough about 
conventions in guile to judge that).

Best wishes,
Arne