[racket] why does in-indexed / in-range slow down my program?

Hi all,

I've implemented the quick-find algorithm in Racket (you can find it here [0], or see code attached below), and found some weirdness during profiling.

(*DISCLAIMER*: I know there's a faster algorithm called quick-union, but let's focus on this one.)

The first version of my program runs extremely slow, taking over 4 minutes to process about 23,000 lines of data (sample data is here: [1]), while the same algorithm implemented in Go (you can find it here: [2]) can finish within 15s. So I added profiling code in Racket to track down the part that slows it down.

As the profiler shows, the most time-consuming part lies in the for-loop of procedure "qf-connect!", and after a few experiments, I figure it out: it is the "in-indexed" procedure that makes it slow. I replaced "in-indexed" with separate calls to "in-range" and "in-vector" - the running time gets reduced from 4m to 27s. Why?

And it's not the end of the story: if I removed the call to "in-range" or "in-vector" (which makes the algorithm not working correctly, of course), it can speed up further down to 18s. (Again) Why?

I'm new to Racket and not clear about the performance implication of the for-loop usage. Any suggestion or hints?

Thanks in advance.

[0]: https://gist.github.com/4576816
[1]: http://static.iwinux.info/pairs.txt
[2]: http://github.com/iwinux/gomisc/tree/master/algorithms/union-find

;; --------------------------------------------------------
;; quick-find.rkt
;; Usage: racket quick-find.rkt < pairs.txt

#lang racket/base

(require racket/list)
(require racket/string)
(require profile)

(module+ main (profile-thunk main))

(define (main)
  (let* ([n (string->number (read-line))]
         [set (make-qf-set n)])
    (for ([line (in-lines)])
      (let* ([pair (string-split line " " #:trim? #f)]
             [p (string->number (car pair))]
             [q (string->number (cadr pair))])
        (unless (qf-connected? set p q)
          (qf-connect! set p q)
          (printf "connected ~a to ~a\n" p q))))
    (printf
     "Quick-find Set with ~a connected components: ~a\n"
     (qf-count set)
     (string-join
      (for/list ([n (in-vector (qf-items set))])
        (number->string n))
      #:before-first "[" #:after-last "]"))))

(struct qf-set ([count #:mutable] items) #:transparent)
(define (make-qf-set n) (qf-set n (make-qf-items n)))
(define (make-qf-items n) (list->vector (range n)))

(define (qf-connected? set p q)
  (= (qf-find set p)
     (qf-find set q)))

;; VERY SLOW - it takes over 4 minutes to finish
;; (define (qf-connect! set p q)
;;   (let ([p-root (qf-find set p)]
;;         [q-root (qf-find set q)]
;;         [items (qf-set-items set)])
;;     (unless (= p-root q-root)
;;       (for ([(v i) (in-indexed items)])
;;         (when (= v p-root)
;;           (vector-set! items i q-root)))
;;       (set-qf-set-count! set (- (qf-set-count set) 1)))))

;; better - it takes about 28s to finish
;; but still slower than the Golang version
(define (qf-connect! set p q)
  (let* ([p-root (qf-find set p)]
         [q-root (qf-find set q)]
         [items (qf-set-items set)]
         [n (vector-length items)])
    (unless (= p-root q-root)
      (for ([i (in-range n)] ;; it is weird that adding this line slows down the program by about 10s
            [v (in-vector items)])
        (when (= v p-root) (vector-set! items i q-root)))
      (set-qf-set-count! set (- (qf-set-count set) 1)))))

(define (qf-find set p)
  (let ([items (qf-set-items set)])
    (if (p . < . (vector-length items))
      (vector-ref items p)
      #f)))

(define qf-count qf-set-count)
(define (qf-items set)
  (vector->immutable-vector (qf-set-items set)))