| 1 |
(add-load-path ".") |
| 2 |
|
| 3 |
(use data.sparse) |
| 4 |
(use util.match) |
| 5 |
(use gauche.time) |
| 6 |
(use srfi.27) |
| 7 |
|
| 8 |
(define *problem-size* 200000) |
| 9 |
|
| 10 |
(define *num-repeat* (ceiling->exact (/. 10000000 *problem-size*))) |
| 11 |
|
| 12 |
(define *problem-set* |
| 13 |
(let1 ht (make-hash-table 'eqv?) |
| 14 |
(let loop ((i 0) (r '())) |
| 15 |
(if (= i *problem-size*) |
| 16 |
r |
| 17 |
(let1 k (random-integer (expt 2 32)) |
| 18 |
(if (hash-table-exists? ht k) |
| 19 |
(loop i r) |
| 20 |
(loop (+ i 1) (cons k r)))))))) |
| 21 |
|
| 22 |
(define (null) |
| 23 |
(dolist [n *problem-set*] n)) |
| 24 |
|
| 25 |
(define (ht-set ht) |
| 26 |
(dolist [n *problem-set*] |
| 27 |
(hash-table-put! ht n n))) |
| 28 |
|
| 29 |
(define (ht-ref ht) |
| 30 |
(dolist [n *problem-set*] |
| 31 |
(hash-table-get ht n))) |
| 32 |
|
| 33 |
(define (sv-set spv) |
| 34 |
(dolist [n *problem-set*] |
| 35 |
(sparse-vector-set! spv n n))) |
| 36 |
|
| 37 |
(define (sv-ref spv) |
| 38 |
(dolist [n *problem-set*] |
| 39 |
(sparse-vector-ref spv n))) |
| 40 |
|
| 41 |
(define (st-set st) |
| 42 |
(dolist [n *problem-set*] |
| 43 |
(sparse-table-set! st n n))) |
| 44 |
|
| 45 |
(define (st-ref st) |
| 46 |
(dolist [n *problem-set*] |
| 47 |
(sparse-table-ref st n n))) |
| 48 |
|
| 49 |
(define (bench-speed name %make %ref %set %cleanup) |
| 50 |
(let ([null-timer (make <user-time-counter>)] |
| 51 |
[set-timer (make <user-time-counter>)] |
| 52 |
[ref-timer (make <user-time-counter>)]) |
| 53 |
|
| 54 |
(define (calc-time timer) |
| 55 |
(* (/. (- (time-counter-value timer) (time-counter-value null-timer)) |
| 56 |
*num-repeat* |
| 57 |
*problem-size*) |
| 58 |
1e9)) ;nanosec |
| 59 |
|
| 60 |
(dotimes [i *num-repeat*] |
| 61 |
(with-time-counter null-timer (null)) |
| 62 |
(let1 obj (%make) |
| 63 |
(with-time-counter set-timer (%set obj)) |
| 64 |
(with-time-counter ref-timer (%ref obj)) |
| 65 |
(%cleanup obj))) |
| 66 |
|
| 67 |
(print name " insertion: " (calc-time set-timer)) |
| 68 |
(print name " lookup: " (calc-time ref-timer)) |
| 69 |
)) |
| 70 |
|
| 71 |
(define (active-memory-size) |
| 72 |
(gc) (gc) |
| 73 |
(let1 s (gc-stat) |
| 74 |
(- (cadr (assq :total-heap-size s)) (cadr (assq :free-bytes s))))) |
| 75 |
|
| 76 |
(define (bench-mem thunk) |
| 77 |
(let1 pre (active-memory-size) |
| 78 |
(dotimes [i *num-repeat*] (thunk)) |
| 79 |
(- (active-memory-size) pre))) |
| 80 |
|
| 81 |
(define (main args) |
| 82 |
(match (cdr args) |
| 83 |
[("ht" "speed") (bench-speed "Hash table" (cut make-hash-table 'eqv?) |
| 84 |
ht-ref ht-set hash-table-clear!)] |
| 85 |
[("sv" "speed") (bench-speed "Sparse vector" (cut make-sparse-vector) |
| 86 |
sv-ref sv-set sparse-vector-clear!)] |
| 87 |
[("suv" "speed") (bench-speed "Sparse u32vector" (cut make-sparse-vector 'u32) |
| 88 |
sv-ref sv-set sparse-vector-clear!)] |
| 89 |
[("st" "speed") (bench-speed "Sparse table" (cut make-sparse-table 'eqv?) |
| 90 |
st-ref st-set sparse-table-clear!)] |
| 91 |
|
| 92 |
[("ht" "mem") (print "Hash table mem: " |
| 93 |
(bench-mem (cut ht-set (make-hash-table 'eqv?))))] |
| 94 |
[("sv" "mem") (print "Sparse vector mem: " |
| 95 |
(bench-mem (cut sv-set (make-sparse-vector))))] |
| 96 |
[("suv" "mem") (print "Sparse u32vector mem: " |
| 97 |
(bench-mem (cut sv-set (make-sparse-vector 'u32))))] |
| 98 |
[("st" "mem") (print "Sparse table mem: " |
| 99 |
(bench-mem (cut st-set (make-sparse-table 'eqv?))))] |
| 100 |
[_ (exit 1 "Usage: bench ht|sv|st speed|mem")]) |
| 101 |
(print "size: " *problem-size*) |
| 102 |
0) |