Racket: [cs] list? is actually not an amortized constant-time operation

[sorawee]

In Racket CS, the following program:

#lang racket

(define xs (time (build-list 100003 values)))

(time (for ([i 10000]) (list? xs)))

outputs:

cpu time: 2 real time: 2 gc time: 0
cpu time: 6580 real time: 6722 gc time: 51

In contrast, when running it in Racket BC, it outputs

cpu time: 2 real time: 2 gc time: 0
cpu time: 1 real time: 1 gc time: 0

[sorawee]

For what it's worth, this came up when @Metaxal and I discussed about how length in Racket is expensive. It got me interested to know how Racket makes list? constant time. I searched the repo and found https://github.com/racket/racket/blob/master/racket/src/cs/rumble/list.ss, so I played around and discovered the issue.

[sorawee]

Here's the code that I played with, FWIW:

#lang racket

(define lists (make-hasheq))

(define CHECK-AFTER-LEN 64)
(define CHECK-EVERY 4)
(define none (gensym))

(define cost 0)

(define (list? v [count 0])
  (cond
    [(null? v) #t]
    [(not (pair? v)) #f]
    [(<= count CHECK-AFTER-LEN) (list? (cdr v) (+ count 1))]
    [else
     (let loop ([fast (cdr v)]
                [slow v]
                [slow-step? #f]
                [countdown 0])
       (define (return result)
         (hash-set! lists slow result)
         (let loop ([slow slow] [count (- CHECK-EVERY 1)])
           (unless (or (eq? slow fast)
                       (= count 0))
             (hash-set! lists slow result)
             (loop (cdr slow) (- count 1))))
         result)
       (cond
         [(null? fast) (return #t)]
         [(not (pair? fast)) (return #f)]
         [(eq? fast slow) (return #f)] ; cycle
         [(= 0 countdown)
          (define is-list? (hash-ref lists fast none))
          (cond
            [(eq? is-list? none)
             (set! cost (add1 cost))
             (loop (cdr fast)
                   (if slow-step? (cdr slow) slow)
                   (not slow-step?)
                   CHECK-EVERY)]
            [else (return is-list?)])]
         [else
          (set! cost (add1 cost))
          (loop (cdr fast)
                (if slow-step? (cdr slow) slow)
                (not slow-step?)
                (- countdown 1))]))]))


(define iterations 100)

(define-syntax-rule (report-cost body ...)
  (begin
    (set! cost 0)
    body ...
    (printf "cost: ~a\n" (~r (/ cost iterations)
                             #:precision 3))))


(define k 100000)
(for ([n (in-range k (+ 20 k))])
  (printf "n = ~a\n" n)
  (define xs (build-list n values))
  (report-cost (for ([i iterations]) (list? xs))))

[mflatt]

Looks like the problem is an off-by-two in the return loop:

• The first off-by-one is that we need to set (+ 1 CHECK-EVERY) items. The CHECK-EVERY constant should be renamed SKIP-CHECK-N, since that's how it's otherwise used, and "check every" is really one more than that.

• The second off-by-one is that the first iteration of the return loop duplicates the hash-set! before the loop.

Does that sound right?

[sorawee]

The first one sounds right to me. The second one sounds true but that's just a minor issue I think?

Also, it might be possible to lift (eq? slow fast) outside the loop (in the return function)?

[mflatt]

The second one is important, because if slow isn't incremented, then the loop is still recording too few pairs.

I think the (eq? slow fast) is needed within the loop in case we find a non-pair before skipping so many items (e.g. in the second pair after CHECK-AFTER-LEN pairs).

[mflatt]

Here's the potential repair: https://github.com/mflatt/racket/commit/56b2c6c342cb466cb1ed4c6236009341122a853e

[mflatt]

Thanks for reviewing — repair push.