Re: Hatables are slow

[Mikael Djurfeldt <mikael@djurfeldt.com>]

[-- Attachment #1: Type: text/plain, Size: 2168 bytes --]

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.itampe@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
>
>
>
>

[-- Attachment #2: Type: text/html, Size: 3203 bytes --]