2
\$\begingroup\$

I have been experimenting with methods to read large text files into a Scheme program as a single string in a performant manner. Development has been in R7RS Scheme, specifically Chibi-Scheme.

After trying many approaches, some quite complex and involved, the best performing have been quite simple. Following are three examples of such along with some example usages and timing results.

(import (scheme base)
        (scheme time))

;; Use with-input-from-file.
;; Return the contents of a text file as a single string,
;; #\newlines included.
(define (file->string1 path)
  (let* ((start-time (current-second)))
    (let ((lst (with-input-from-file path
                 (lambda ()
                   (let ((p (current-input-port)))
                     (let loop ((ch (read-char p))
                                (acc '()))
                       (if (eof-object? ch)
                           acc
                           (loop (read-char p) (cons ch acc)))))))))
      (let ((result (list->string (reverse lst)))
            (duration (- (current-second) start-time)))
        (display "file->string1 complete in ")
        (display duration)
        (display " seconds.\n")
        result))))

;; Use call-with-input-file.
;; Return the contents of a text file as a single string,
;; #\newlines included.
(define (file->string2 path)
  (let ((start-time (current-second))
        (lst (call-with-input-file path
               (lambda (p)
                 (let loop ((ch (read-char p))
                            (acc '()))
                   (if (eof-object? ch)
                       acc
                       (loop (read-char p) (cons ch acc))))))))
    (let ((result (list->string (reverse lst)))
          (duration (- (current-second) start-time)))
      (display "file->string2 complete in ")
      (display duration)
      (display " seconds.\n")
      result)))

;; Use an output string to collect the data read.
;; Return the contents of a text file as a single string,
;; #\newlines included.
(define (file->string3 path)
  (let* ((start-time (current-second))
         (result (call-with-input-file path
                   (lambda (p)
                     (let ((out (open-output-string)))
                       (let loop ()
                         (cond
                          ((eof-object? (peek-char p))
                           (get-output-string out))
                          (else
                           (write-char (read-char p) out)
                           (loop))))))))
         (duration (- (current-second) start-time)))
    (display "file->string3 complete in ")
    (display duration)
    (display " seconds.\n")
    result))

;; Example usage and results loading "War and Peace" from the
;; Project Gutenberg.
;; https://www.gutenberg.org/cache/epub/2600/pg2600.txt
;;
;; ➜  david in schemacs on branch: (main) ! rlwrap chibi-scheme
;; > (load "file-ops.scm")
;; > (define wap1 (file->string1 "war-and-peace.txt"))
;; file->string1 complete in 0.6330661773681641 seconds.
;; > (define wap2 (file->string2 "war-and-peace.txt"))
;; file->string2 complete in 5.0067901611328125e-06 seconds.
;; > (define wap3 (file->string3 "war-and-peace.txt"))
;; file->string3 complete in 0.48236799240112305 seconds.
;; > (string-length wap1)
;; 3227709
;; > (string-length wap2)
;; 3227709
;; > (string-length wap3)
;; 3227709
;; > (string=? wap1 wap2 wap3)
;; #t

As a test case, I have used a copy of "War and Peace" obtained from Project Gutenberg as the file to read. It consists of 3,227,709 characters, including some preamble and final comments from Project Gutenberg.

All three procedures produce identical results, but the second consistently reports a much faster execution time. Timing values close to those above have been reported on repeated runs. Using a copy of "Moby Dick" as the file to read yields a similar timing relationship between the procedures.

I can't see any reason for the difference in timings for the second procedure. Are the results bogus for some reason?

Is one procedure preferable to the others for stylistic reasons?

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Thank you for this very nice investigation into timings. With all due respect, I don't view those figures as performant at all. More on that later.


file->string1 uses let* to assign start-time, and then (with confusing indentation) computes the read result.

file->string2 uses a single let for two assignments. It is allowed to do them in either order. The optimizer probably noticed that one of them had more dependencies to resolve and should be scheduled first, possibly exploiting overlap with computation of the other expression. Which took ~ five microseconds to evaluate.

tl;dr: Benchmarking is hard to get right. Sweat the details.


Let's take a step back and critique this from a higher level. I confess I'm not happy with the whole business of reading more than 3 million characters and examining each one to see "is this EOF?", "is this one EOF?".

Surely scheme offers a POSIX bulk read primitive? Something like with-input-from-file, and then use read-string with char-set:full, or maybe :designated or even :standard or :printing.

If not, I recommend using FFI foreign function interface to call the chapter 2 C read() function directly.


Let's switch gears for a moment to python, which no one would accuse of being a "fast" language.

from pathlib import Path
from time import time
import requests

temp = Path("/tmp")

def read_war_and_peace(url="https://www.gutenberg.org/ebooks/2600.txt.utf-8"):
    cache = temp / Path(url).name
    if not cache.exists():
        resp = requests.get(url)
        cache.write_text(resp.text)
    print(cache.stat().st_size)
    with open(cache) as fin:
        return fin.read()


if __name__ == "__main__":
    t0 = time()
    print(len(read_war_and_peace()), time() - t0)

There's two things going on here. We read 3_359_372 binary bytes, and then we decode them to 3_227_489 code points (characters) of UTF8 text. Doing that with fin.read() was trivial to specify.

Observed performance? On a 2.2 GHz (2015) MacBook Air I observed 16 msec elapsed time, or ~ 202 MiB / sec. Relative to evaluation of bytecode, almost all of that time was devoted to C code. Scheme compilers are quite sophisticated, so scheme applications can reasonably be competitive with Rust or C if they are using appropriate data structures that let the compiler shine.


I submit that the three functions we see here are Fine but are not Performant. The 30x haircut seems like more than we'd want to accept. And if we wish to complete in less than 482 msec, we should operate on large chunks rather than character-at-a-time.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for the careful and insightful review. Clearly the title did not convey that I am looking for something with better performance. Enforcing the expected order of binding in #2 fixed that bug. It performs about the same as the others now. Some of the other methods I tried including reading big byte vector blocks, with no benefit. The comment about Scheme compilers is fair, but I really like chibi -- just read the standard and write your program. Thanks again. \$\endgroup\$
    – clartaq
    Jan 15 at 15:50
  • \$\begingroup\$ Oh, sorry if I was unclear. I definitely meant to include Chibi in with scheme compilers. The technology has come a long way and I am accustomed to scheme and lisp compilers doing impressive things, on par with C compilers, if the app author gives them room to optimize. There's sort of two usual gotchas that can prevent that. Assigning mixed types to one identifier is a no no; I don't see that here. And then there is "list vs vector". In the reviewed code, the biggest thing I railed against was cons'ing up each character. Better to have a giant string, right? Or at least a string per line. \$\endgroup\$
    – J_H
    Jan 15 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.