(Note that the resizing means *rehashing* of all elements.) On Mon, Feb 21, 2022 at 11:17 PM Mikael Djurfeldt <mik...@djurfeldt.com> wrote:
> The hash table in Guile is rather standard (at least according to what was > standard in the old ages :). (I *have* some vague memory that I might have > implemented a simpler/faster table at some point, but that is not in the > code base now.) > > The structure is a vector of alists. It's of course important that the > alists don't get too long, so there's some resizing going on. If you call > (make-hash-table), the size of the table starts out at 31, so in your use > case, there will be several resizing steps. > > What happens with speed if you do (make-hash-table 5000000) instead? > > Best regards, > Mikael > > On Mon, Feb 21, 2022 at 2:55 PM Stefan Israelsson Tampe < > stefan.ita...@gmail.com> wrote: > >> 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 >> >> >> >>
