Racket: [cs] list? is slow compared to Racket BC

[sorawee]

Racket CS's list? is now an amortized constant-time operation. However, it's still somewhat significantly slower than that of Racket BC. Feel free to close this issue though if there's nothing that can be done about it.

Consider:

#lang racket

(define (iter xs)
  (cond
    [(null? xs) 0]
    [else
     (list? xs)
     (iter (cdr xs))]))

(define xs (range 1000000))
(time (iter xs))

On Racket CS, the program outputs cpu time: 466 real time: 483 gc time: 181. On Racket BC, it outputs only cpu time: 4 real time: 3 gc time: 0.

The list? operation is invoked every time first and rest is called, so a recursive function that uses first and rest could be significantly slower compared to Racket BC. E.g.,

#lang racket

(define (iter xs acc)
  (cond
    [(empty? xs) acc]
    [else
     (iter (rest xs) (+ (first xs) acc))]))

(define xs (range 1000000))
(time (iter xs 0))

outputs cpu time: 63 real time: 64 gc time: 0 and cpu time: 598 real time: 642 gc time: 195 in Racket BC and Racket CS respectively.

[mflatt]

The results on that first example are misleading: Racket BC optimizes away the list? call, since its result is not used, while Racket BC doesn't currently know that list? can be eliminated like that. If you change the first loop it to

(define (iter xs)
  (cond
    [(null? xs) 0]
    [else
     (and (list? xs)
          (iter (cdr xs)))]))

then both loops run in similar time.

It's possible to get Racket CS's performance close to Racket BC's performance by modifying the Chez Scheme GC to specially support list?. That may be worthwhile, and I'll experiment more.

[mflatt]

Of course, it would also be good for Racket CS to drop a list? call whose result is not used, but that's a different problem.

[rfindler]

On Sat, Apr 25, 2020 at 9:18 AM Matthew Flatt [e-mail]
wrote:

The results on that first example are misleading: Racket BC optimizes away
the list? call, since its result is not used, while Racket BC doesn't
currently know that list? can be eliminated like that. If you change the
first loop it to

The second "BC" is meant to be a "CS", right?

(define (iter xs)
(cond
[(null? xs) 0]
[else
(and (list? xs)
(iter (cdr xs)))]))

then both loops run in similar time.

It's possible to get Racket CS's performance close to Racket BC's
performance by modifying the Chez Scheme GC to specially support list?.
That may be worthwhile, and I'll experiment more.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/racket/racket/issues/3109#issuecomment-619386475, or
unsubscribe
https://github.com/notifications/unsubscribe-auth/AADBNMCQIT6PVPYVOQLIEWTROLWJRANCNFSM4MMEK6ZQ
.

[sorawee]

Yep, pretty sure that's what Matthew meant.

Btw, here's a result on the program that Matthew posted above:

Racket BC: cpu time: 44 real time: 44 gc time: 0
Racket CS: cpu time: 487 real time: 545 gc time: 194

Eliminating GC time will definitely help speeding it up, but there seems to be some other factors that make it slow too, I think?

[mflatt]

Yes, I did mean "CS".

The needed GC cooperation is not about reducing collection time but about finding a (cheaper) place to store up to two bits per cons cell.

[mflatt]

I've pushed changes that make CS list? about the same speed as BC on my machine.

[sorawee]

I just installed the snapshot build and tried it.

• Racket BC: cpu time: 47 real time: 47 gc time: 0
• Racket CS: cpu time: 72 real time: 73 gc time: 0

For the program that uses first and rest above, here're the results:

• Racket BC: cpu time: 67 real time: 68 gc time: 0
• Racket CS: cpu time: 95 real time: 96 gc time: 0

So yes, it works! Thanks so much :)