[plt-scheme] From hash-table to generator

>> The problem is thus to write hash-table->generator efficiently. As it 
>> turns out, the inversion via call/cc looses big time to the 
>> convert-to-list approach.
>>
>> So the next question, is: Is there a better way to turn a hash-table 
>> into a generator?
> 
> Hi Jens,
> 
> I'm interested: how does the following approach compare, 
> performance-wise, to the version with continuations?
> 
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
> (module hash-table-generator mzscheme
>   (require (lib "etc.ss")
>            (lib "contract.ss"))
> 
>   (provide/contract [hash-table->generator
>                      (hash-table? . -> . (-> any/c))])
>   (define (hash-table->generator ht)
>     (local
>         ((define ch (make-channel))
>          (define sentinel (cons 'done 'done))
>          (define all-done? #f))
>       (thread (lambda ()
>                 (hash-table-for-each
>                  ht
>                  (lambda (k v)
>                    (channel-put ch k)))
>                 (channel-put ch sentinel)))
>       (lambda ()
>         (cond
>           [all-done? #f]
>           [else
>            (let ([result (channel-get ch)])
>              (cond
>                [(eq? result sentinel)
>                 (set! all-done? #t)
>                 #f]
>                [else
>                 result]))])))))

We have the thread version above.

The call/cc version is:


(define (hash-table->generator ht)
   (let ([continue 'start]
         [return   #f])
     (lambda ()
       (let/cc ret
         (set! return ret)
         (case continue
           [(done)    (return #f)]
           [(start)   (hash-table-for-each
                       ht
                       (lambda (x v)
                         (call/cc
                          (lambda (k)
                            (set! continue k)
                            (return x)))))
                      (set! continue 'done)
                      (return #f)]
           [else      (continue)])))))

And a convert-to-list-first version:

(define (hash-table->generator ht)
   (let ([xs (hash-table->list ht)])
     (lambda ()
       (cond
         [(null? xs) #f]
         [else       (let ([x (car xs)])
                       (set! xs (cdr xs))
                       x)]))))

In my sample application I get:

   Above version:    cpu time: 23594 real time: 25469 gc time: 3389
   Call/cc version:  cpu time: 18125 real time: 18344 gc time: 11515
   List version:     cpu time: 1843 real time: 1843 gc time: 578

The conclusion must therefore be, that you need to
implement hash-table->generator as a primitive, if you want
to avoid Unnecessary allocation.

-- 
Jens Axel Søgaard