如何提高在Common Lisp中逐行读取大文件的速度

Question

最近，我有一个任务要处理一个大文件，文件大小为460MB，包含5777672行。当我使用linux内置命令'wc'计算文件行号时，速度很快：

time wc -l large_ess_test.log
5777672 large_ess_test.log

real    0m0.144s
user    0m0.052s
sys     0m0.084s

然后，我使用以下代码计算Common Lisp（SBCL 1.3.7 64位）中的行号

#!/usr/local/bin/sbcl --script
(defparameter filename (second *posix-argv*))
(format t "nline: ~D~%"
        (with-open-file (in filename)
          (loop for l = (read-line in nil nil)
             while l
             count l)))

结果令我感到失望，因为与“ wc”命令相比，它确实很慢。我们只计算行号，即使没有任何其他操作：

time ./test.lisp large_ess_test.log
nline: 5777672

real    0m3.994s
user    0m3.808s
sys     0m0.152s

我知道SBCL提供了C函数接口，通过它我们可以直接调用C过程。我相信如果直接调用C函数，性能将会提高，因此我编写了以下代码：

#!/usr/local/bin/sbcl --script
(define-alien-type pointer (* char))
(define-alien-type size_t  unsigned-long)
(define-alien-type ssize_t long)
(define-alien-type FILE*   pointer)

(define-alien-routine fopen FILE*
  (filename c-string)
  (modes    c-string))

(define-alien-routine fclose int
  (stream FILE*))

(define-alien-routine getline ssize_t
  (lineptr (* (* char)))
  (n       (* size_t))
  (stream  FILE*))

;; The key to improve the performance:
(declaim (inline getline))
(declaim (inline read-a-line))

(defparameter filename (second *posix-argv*))

(defun read-a-line (fp)
  (with-alien ((lineptr (* char))
               (size    size_t))
    (setf size 0)
    (prog1
        (getline (addr lineptr) (addr size) fp)
      (free-alien lineptr))))

(format t "nline: ~D~%"
        (let ((fp (fopen filename "r"))
              (nline 0))
          (unwind-protect
               (loop
                  (if (= -1 (read-a-line fp))
                      (return)
                      (incf nline)))
            (unless (null-alien fp)
              (fclose fp)))
          nline))

当心有两个“声明”行。如果我们不写这两行，那么性能几乎与以前的版本相同：

;; Before declaim inline:

;; time ./test2.lisp large_ess_test.log
;; nline: 5777672

;; real 0m3.774s
;; user 0m3.604s
;; sys  0m0.148s

但是，如果我们写这两行，性能将大大提高：

;; After delaim inline:

;; time ./test2.lisp large_ess_test.log
;; nline: 5777672

;; real 0m0.767s
;; user 0m0.616s
;; sys  0m0.136s

我认为第一个版本的性能问题是，“读取行”除了从流中读取一行外，还做很多其他事情。另外，如果我们可以获取“读取行”的内联版本，速度将会提高。问题是我们可以做到吗？是否有任何其他（标准）方法可以在不依赖FFI（非标准）的情况下提高读取性能？

Answer 1

该wc实用程序专门用于此任务（例如，使用fadvise）。如果必须快速执行任务，我可能会考虑从Lisp使用它：

CL-USER> (time (parse-integer
                 (trivial-shell:shell-command "wc -l /tmp/large") 
                 :junk-allowed t))
Evaluation took:
  0.160 seconds of real time
  0.007343 seconds of total run time (0.000000 user, 0.007343 system)
  4.38% CPU
  381,646,599 processor cycles
  2,176 bytes consed

5777672
7

以下是Common Lisp版本（SBCL 1.3.7）的2.8倍慢：

1. 使用(UNSIGNED-BYTE 8)元素的缓冲区并搜索10（LF）
2. 依靠 READ-SEQUENCE
3. 显式计数元素（否COUNT）
4. 添加优化声明

正如评论中所解释的那样，这假设换行符的特定编码在所有情况下都不会起作用（这很糟糕，但是在这里我们复制了wc工作原理）。

用例

我制作了一个文件，其中包含所需的行数以及每行随机的大数字。

$ head /tmp/large
40721464513295045164409764141337171283743839234004114007016385954846624941161940739262754532145351336011544635983803337802
302688650332823972161024925841738216684275519674144853512935484321121382058207767892999110099
12127138342525644979456951336948881438967488255401497749747122531372644240417582283720034330082860221222236934955
28004461699214617943893203751119815181262623130442209320081054856344182547684
2368224648283244549917005208294446715375229403128245954161044012485784650329544448732041119652238003906938784265044644012743487917338526
10187414801460188523874389448625131601828345073853512891
18139254731161634077170374183629006496541918416200333307681019211073598374443624027089513206284736438073440343464515605950135369987
264133633737591502517649433121708413001893239265224973146093724444415999323412026140148811107315275274514969546676171233513940820
266634202314513982469064052528307445611038540754445234380948245264834237744595384991230031062233083375534272384684213524515821
17743431383885515663346469524228524653280663312275122927140858199583669032542409846791571021743570930576483101689249445164712663940464

$ time wc -l /tmp/large
5777672 /tmp/large

real    0m0.180s
user    0m0.119s
sys 0m0.061s

$ du -h /tmp/large
388M    /tmp/large

计数线

(defun count-lines (file &optional (buffer-size 32768))
  (declare (optimize (speed 3) (debug 0) (safety 0))
           (type fixnum buffer-size))
  (let ((buffer
         (make-array buffer-size
                     :element-type #1='(unsigned-byte 8)))
        (sum 0)
        (end 0))
    (declare (type fixnum sum end))
    (with-open-file (in file :element-type #1#)
      (loop
         (setf end (read-sequence buffer in))
         (when (= end 0)
           (return sum))
         (dotimes (i end)
           (declare (type fixnum i)
                    (dynamic-extent i))
           (when (= 10
                    (aref buffer i))
             (incf sum)))))))

测试

CL-USER> (time(count-lines #P"/tmp/large"))

Evaluation took:
  0.493 seconds of real time
  0.493113 seconds of total run time (0.409636 user, 0.083477 system)
  100.00% CPU
  1,179,393,504 processor cycles
  1,248 bytes consed

5777672

如果您需要对该行进行其他操作，请改用字符串缓冲区，然后直接重复使用它而不进行复制。但是，您可能需要将最后一个字符块（在缓冲区中最后一个换行符之后）复制到开头，以便再次填充缓冲区。