unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
* Hatables are slow
@ 2022-02-21 13:18 Stefan Israelsson Tampe
  2022-02-21 22:17 ` Mikael Djurfeldt
  2022-02-23  7:40 ` Linus Björnstam
  0 siblings, 2 replies; 6+ messages in thread
From: Stefan Israelsson Tampe @ 2022-02-21 13:18 UTC (permalink / raw)
  To: guile-devel

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

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: 2125 bytes --]

^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2022-02-23 13:46 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-02-21 13:18 Hatables are slow Stefan Israelsson Tampe
2022-02-21 22:17 ` Mikael Djurfeldt
2022-02-21 22:18   ` Mikael Djurfeldt
2022-02-23  7:40 ` Linus Björnstam
2022-02-23  8:02   ` Stefan Israelsson Tampe
2022-02-23 13:46   ` Mikael Djurfeldt

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).