优化Chicken Scheme的CSV解析器：性能差异困惑求解

我正在学习Chicken Scheme，想搞懂这门语言的性能陷阱。我写了个CSV解析器，用130MB测试文件解析要7分钟，但只读取所有行只需要毫秒级，问题显然在解析逻辑。我想尽量保持Lisp风格，少用Chicken的低级构造，通过优化加深对Scheme性能的理解。

后来我写了两个独立解析器：一个基于列表，一个基于string-ref。我原本以为string-ref方案因为线性内存特性会更快，但测试结果完全相反，希望能搞懂背后的原因。

性能测试结果 #

基于列表的方案（编译后） #

37.658s CPU time, 1.2s GC time (major), 258575354/244106 mutations (total/tracked), 1160/317431 GCs (major/minor), maximum live heap: 306.33 KiB

基于string-ref的方案（编译后） #

644.939s CPU time, 1.308s GC time (major), 167854392/243430 mutations (total/tracked), 1281/1023116 GCs (major/minor), maximum live heap: 305.51 KiB

基于列表的实现 #

; List based solution
(import (chicken string))
(import utf8)
(import list-utils)

(define (lookahead-list ahead lst) 
  (cond [(null? ahead) #t]
    [(and (not (null? lst)) (not (null? ahead))) 
     (if (eq? (car ahead) (car lst)) (lookahead-list (cdr ahead) (cdr lst)) #f)]
    [else #f]
  )
)

(define (null-blist? blist) (null? (car blist)))

(define (lookahead-blist ahead blst) (lookahead-list ahead (car blist)))

(define (read-blist blist)
    (if (null? blist) #!eof
        (let ([head (caar blist)]) (set-car! blist (cdar blist)) head))
)

; Csv parsing


(define (csv/read-atom blist)
    (let loop ([res '()] [cmode #t]) 
      (cond [(lookahead-blist '(#\" #\") blist) (read-blist blist) (loop (cons (read-blist blist) res) cmode)]
        [(lookahead-blist '(#\") blist) (read-blist blist) (loop res (not cmode))]
        [(and cmode (lookahead-blist '(#\,) blist)) (reverse-list->string res)]
        [(null-blist? blist) (reverse-list->string res)]
        [else (loop (cons (read-blist blist) res) cmode)]
      ))
)


(define (csv/parse-non-blank-line blist)
    (reverse 
    (let loop ([res '()])
        (let ([nres (cons (csv/read-atom blist) res)])
             (if (lookahead-blist '(#\,) blist) 
               (begin (read-blist blist) (loop nres)) nres)
        )
    ))
)

(define (csv/parse-line str)
    (if (equal? str "") '() (csv/parse-non-blank-line (list (string->list str))))
)

(define (csv/parse func init port)
    (let loop ([acc init] [line (read-line port)])
        (if (eq? line #!eof) acc
            (loop (func acc (csv/parse-line line)) (read-line port))
        )
    )
)

(define (csv/parse-table func init port) 
    (let ([format (csv/parse-line (read-line port))]) 
        (define (shim acc elem) 
            (func acc (zip-alist format elem))
        )
        (csv/parse shim init port)
    )
)


(define (csv/parse-table-file func init fname) (call-with-input-file (lambda (p) (csv/parse-table func init p))))

基于string-ref的实现 #

; String-ref based solution
(import (chicken io))
(import (chicken string))
(import utf8)
(import list-utils)


; Cursor string
(define (string->cstring str)
    (cons 0 str)
)

(define (cstring/forward cstr) 
    (cons (+ 1 (car cstr)) (cdr cstr))
)

(define (cstring/peek cstr)
    (if (cstring/null? cstr)
        #!eof
        (string-ref (cdr cstr) (car cstr))
    )
)

(define (cstring/forward! cstr)
    (let ([ret (cstring/peek cstr)]) 
        (set-car! cstr (+ 1 (car cstr)))
        ret
    )
)

(define (cstring/null? cstr)
    (>= (car cstr) (string-length (cdr cstr)))
)

(define (lookahead-cstring ahead cstr) 
  (cond [(null? ahead) #t]
    [(and (not (cstring/null? cstr)) (not (null? ahead))) 
     (if (eq? (car ahead) (cstring/peek cstr)) (lookahead-cstring (cdr ahead) (cstring/forward cstr)) #f)]
    [else #f]
  )
)



; Csv parsing


(define (csv/read-atom cstr)
    (let loop ([res '()] [cmode #t]) 
      (cond [(lookahead-cstring '(#\" #\") cstr) (cstring/forward! cstr) (loop (cons (cstring/forward! cstr) res) cmode)]
        [(lookahead-cstring '(#\") cstr) (cstring/forward! cstr) (loop res (not cmode))]
        [(and cmode (lookahead-cstring '(#\,) cstr)) (reverse-list->string res)]
        [(cstring/null? cstr) (reverse-list->string res)]
        [else (loop (cons (cstring/forward! cstr) res) cmode)]
      ))
)



(define (csv/parse-non-blank-line cstr)
    (reverse 
    (let loop ([res '()])
        (let ([nres (cons (csv/read-atom cstr) res)])
             (if (lookahead-cstring '(#\,) cstr) 
               (begin (cstring/forward! cstr) (loop nres)) nres)
        )
    ))
)

(define (csv/parse-line str)
    (if (equal? str "") '() (csv/parse-non-blank-line (string->cstring str)))
)

(define (csv/parse func init port)
    (let loop ([acc init] [line (read-line port)])
        (if (eq? line #!eof) acc
            (loop (func acc (csv/parse-line line)) (read-line port))
        )
    )
)

(define (csv/parse-table func init port) 
    (let ([format (csv/parse-line (read-line port))]) 
        (define (shim acc elem) 
            (func acc (zip-alist format elem))
        )
        (csv/parse shim init port)
    )
)


(define (csv/parse-table-file func init fname) (call-with-input-file fname (lambda (p) (csv/parse-table func init p))))

性能差异原因分析 #

1. lookahead-cstring的低效内存分配 #

string-ref方案的lookahead-cstring每次调用cstring/forward都会创建新的cons单元格，而列表方案的lookahead-list只是遍历现有列表，无额外分配。CSV解析需要频繁检查字符（引号、逗号），这种小对象的频繁分配会触发大量minor GC——测试结果显示string-ref方案的minor GC次数是列表方案的3倍多，GC开销累积后严重拖慢速度。

2. 可变cursor的额外操作成本 #

string-ref方案用带修改操作的cursor（cstring/forward!），每次访问都要操作cons的car和cdr；而列表方案的read-blist直接修改传入列表的头部，操作更直接。此外，Chicken Scheme编译器对不可变列表的遍历优化优于可变cons操作。

3. string-ref的累积调用开销 #

每次cstring/peek都会调用string-ref，这是需要计算索引的操作；而列表方案直接访问car是更高效的指针操作。每个字符都要执行一次string-ref，累积的开销非常可观。

4. 缓存友好性差异 #

string->list生成的列表是连续内存结构，遍历缓存友好；而string-ref方案的索引访问字符串，容易出现更多缓存失效，尤其是长字符串场景下。

内容的提问来源于stack exchange，提问作者user3600107