[racket] Super basic question about strings

On Nov 17, 2010, at 10:16 AM, Neil Van Dyke wrote:

> For new students, I would show them examples like Eli and Matthias did.  For production work, I usually build up strings using string ports.
> 
> Compared to various ways of building lists and doing "string-append", or to simply doing lots of incremental "string-append" or "format", using a string port usually permits more tail calls, and sometimes reduces allocations or otherwise inefficient calls.  (Note that I assume that the string port implementation itself is very efficient internally.)
> 
> For example, a first attempt using string ports, without performance tuning:
> 
> (define (alist->string alist)
> (if (null? alist)
>     ""
>     (let ((os (open-output-string)))
>       (let loop ((alist alist))
>         (write      (caar alist) os)
>         (write-char #\=          os)
>         (write      (cdar alist) os)
>         (if (null? (cdr alist))
>             (begin0 (get-output-string os)
>               (close-output-port os))
>             (begin (write-char #\space os)
>                    (loop (cdr alist))))))))
> 
> The string ports example is a lot more verbose than Matthias's string-join/map/format example, but in a couple quick profiles of 100,000 iterations just now, on an alist of only 5 elements, the string ports example ran in 74%-76% of the time.  In a couple additional profiles, this performance edge seems to increase with the length of the alist and/or length of the output string.
> 
> For programs that are sufficiently fast, this particular performance edge is insignificant.  But when you're building large production systems, I've seen attention to grungy low-level performance details in Racket result in boosts of 2x, 10x, 50x...  That makes a big difference when you want your Web site to respond in a fraction of a second under load or you're buying/renting application servers.


The bottleneck is format. I tried two different versions in addition to yours: 
 [1] merge the two passes into one (string-join + map is kind of a fold)
 [2] eliminate format as follows:  

(define (alist->string.v5 alist)
  (string-join (map (lambda (x) (string-append (symbol->string (car x)) "=" (number->string (cdr x)))) alist) " "))

Here is how I measured it all: 

(define alist '((a . 1) (b . 2) (c . 3) (d . 4) (e . 5)))

(define (timing msg alist->string)
  (check-equal? (alist->string alist) "a=1 b=2 c=3 d=4 e=5 " (object-name alist->string))
  (display msg)
  (collect-garbage) (collect-garbage) (collect-garbage)
  (time (for ((i (in-range 100000))) (alist->string alist))))

Results: 

1. I can confirm that my functional version is 50% slower than your imperative version on my MacMini. 

2. I found out that 'loop fusion' consistently slows down the program by an epsilon. [That's a surprise.]

3. My format-less functional version is 5x faster than your imperative version. 

The nice thing about this all is that I don't teach format to my students so that they would be forced to write alist->string.v5, i.e., the fastest version around. 

Naturally, if this were the bottleneck, I'd abstract over the symbol->string and number->string versions so that I can reuse the function as needed. 

-- Matthias