A datastructure I fancy is hash tables. But I found out that hashtables in guile are really slow, How? First of all we make a hash table
(define h (make-hash-table))
Then add values
(for-each (lambda (i) (hash-set! h i i)) (iota 20000000))
Then the following operation cost say 5s
(hash-fold (lambda (k v s) (+ k v s)) 0 h)
It is possible with the foreign interface to speedt this up to 2s using guiles internal interface. But this is slow for such a simple application. Now let's change focus. Assume the in stead an assoc,
(define l (map (lambda (i) (cons i i)) (iota 20000000)))
Then
ime (let lp ((l ll) (s 0)) (if (pair? l) (lp (cdr l) (+ s (caar l))) s))
$5 = 199999990000000
;; 0.114530s real time, 0.114391s run time. 0.000000s spent in GC.
That's 20X faster. What have happened?, Well hashmaps has terrible memory layout for scanning. So essentially keeping a list of the created values consed on a list not only get you an ordered hashmap, you also have 20X increase in speed, you sacrifice memory, say about 25-50% extra. The problem actually more that when you remove elements updating the ordered list is very expensive. In python-on-guile I have solved this by moving to a doubly linked list when people start's to delete single elements. For small hashmap things are different.
I suggest that guile should have a proper faster standard hashmap implemention of such kind in scheme.
Stefan