I'm skeptical of an unbounded cache.
If we go by the sample from DrRacket's start up, then we don't really
need a cache to do better than the built-in number->string. Below is
some code that takes the version I had earlier with what I understood
to be Gustavo's suggestions and then just does better on the fixnums
between 0 and 9. I then changed the random inputs to sample from the
distribution that DrRacket demonstrated and you won't be surprised to
learn that this does better than having a cache. Below is the code.
I also tried to collect the arguments to number->string during
rebuilding all of the .zo files. Of the first 2.3 million calls about
99.5% of them were exact integers between 0 and 9 so probably this is
the only optimization we need to do. (My sampling method turned out to
be noisy, tho, but I don't think it affects the results.)
... unless someone comes up with some other benchmark or app we care about?
Robby
#lang racket
(require (for-syntax syntax/parse))
(define-syntax (mk-sample stx)
(syntax-parse stx
[(_ (value:exact-nonnegative-integer
occurrences:exact-nonnegative-integer) ...)
(define-values (cond-clauses count)
(for/fold ([other-cases '()]
[so-far 0])
([value (in-list (syntax->list #'(value ...)))]
[occurrences (in-list (syntax->list #'(occurrences ...)))])
(define next-count (+ so-far (syntax-e occurrences)))
(values (cons #`[(< x #,next-count) #,value] other-cases)
next-count)))
#`(λ ()
(define x (random #,count))
(cond #,@(reverse cond-clauses)))]))
(define sample/drr
(mk-sample
(0 2399)
(1 8116)
(2 4278)
(3 2196)
(4 1346)
(5 901)
(6 364)
(7 230)
(8 106)
(9 96)
(10 42)
(11 5)
(12 3)
(72 1)
(100 34)
(241 1)))
(define number->string**
(let ([digits (list->vector (string->list "0123456789"))]
[cache (make-hasheqv)])
(λ (N)
(hash-ref! cache N
(λ ()
(list->string
(let loop ([N N][acc empty])
(define q (quotient N 10))
(define next-acc (cons (vector-ref digits
(remainder N 10)) acc))
(if (zero? q)
next-acc
(loop q next-acc)))))))))
(define (number->string* N)
(cond [(and (exact-nonnegative-integer? N) (< N 10))
(string (integer->char (+ (char->integer #\0) N)))]
[else
(let* ([short-size 10]
[str (make-string short-size)])
(let loop ([N N] [digits null] [i short-size])
(cond
[(zero? N)
(if (<= i 0)
(if (null? digits)
str
(string-append (apply string digits) str))
(substring str i short-size))]
[else
(define q (quotient N 10))
(define r (remainder N 10))
(define d (integer->char (+ r (char->integer #\0))))
(cond
[(<= i 0)
(loop q (cons d digits) i)]
[else
(string-set! str (- i 1) d)
(loop q '() (- i 1))])])))]))
(define-syntax-rule (test-it id ...)
(begin
(module+ test
(require rackunit)
(check-equal? (id 1234567890987654321)
(number->string 1234567890987654321))
(for ([x (in-range 10000)])
(check-equal? (id x )
(number->string x)))) ...))
(test-it number->string**)
(test-it number->string*)
(define iterations 10000)
(define-syntax-rule (time-it id ...)
(begin
(define numbers (for/list ([i (in-range 1000)])
(sample/drr)))
(begin
(collect-garbage)
(time
(for* ([x (in-range iterations)]
[n (in-list numbers)])
(id n))
(printf "~a " 'id))) ...))
(time-it number->string number->string* number->string**)
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
