Re: Hatables are slow

[Mikael Djurfeldt <mikael@djurfeldt.com>]

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

(Note that the resizing means *rehashing* of all elements.)

On Mon, Feb 21, 2022 at 11:17 PM Mikael Djurfeldt <mikael@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.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: 3645 bytes --]