About performance, hash-tables and garbage collection

About performance, hash-tables and garbage collection

[Oliver Scholz]

I am currently writing a library in which the main function has an
inner loop that may run several thousand times. So I care a bit about
the performance of this inner loop.

1. I have read that hash-tables have a little overhead and that
   association lists are a little bit faster, when they contain not
   more than about a dozen of key-value pairs. It is _possible_ that I
   have to maintain several hundreds or thousand of key/value pairs,
   but in most cases it will be only a dozen or so. So my question is:
   how much overhead has a hashtable? Makes it sense to add a
   condition, like this:

   (if (> ncolours 15) 
       (gethash colour colour-map) 
     (cdr (assoc (colour colour-map))))   

2. I noticed that the garbage collector hits in a little bit too
   often, though I do not know why. I have a lot of `setq'-statements
   like `(setq pointer (1+ pointer))'. Is it possible that they are
   the cause? If so, what could I do?

    -- Oliver

-- 
Jour de la Raison de l'Année 210 de la Révolution
Liberté, Egalité, Fraternité!

Re: About performance, hash-tables and garbage collection

[Stefan Monnier <foo@acm.com>]

> 1. I have read that hash-tables have a little overhead and that
>    association lists are a little bit faster, when they contain not
>    more than about a dozen of key-value pairs. It is _possible_ that I
>    have to maintain several hundreds or thousand of key/value pairs,
>    but in most cases it will be only a dozen or so. So my question is:
>    how much overhead has a hashtable? Makes it sense to add a
>    condition, like this:
>    (if (> ncolours 15)
>        (gethash colour colour-map)
>      (cdr (assoc (colour colour-map))))

The `if' overhead will probably dwarf the difference, so I'd say,
just use the hash-table.  Most likely any performance problem you'll have
won't come from that anyway.

> 2. I noticed that the garbage collector hits in a little bit too often,

What's too often ?  Why do you care ?
Does it use a significant percentage of the running time ?
If yes, look for things like `append' and things like that to see where
you do most allocation.

>    though I do not know why. I have a lot of `setq'-statements
>    like `(setq pointer (1+ pointer))'. Is it possible that they are
>    the cause?

If the code is interpreted, maybe, tho I don't think so.

>  If so, what could I do?

If you've byte-compiled your code, then an increment (as shown above) will
not allocate any memory and will thus have no influence on GC.


        Stefan

Re: About performance, hash-tables and garbage collection

[Oliver Scholz]

"Stefan Monnier <foo@acm.com>" <monnier+gnu.emacs.help/news/@flint.cs.yale.edu> writes:

>> 1. I have read that hash-tables have a little overhead and that
>>    association lists are a little bit faster, when they contain not
>>    more than about a dozen of key-value pairs. It is _possible_ that I
>>    have to maintain several hundreds or thousand of key/value pairs,
>>    but in most cases it will be only a dozen or so. So my question is:
>>    how much overhead has a hashtable? Makes it sense to add a
>>    condition, like this:
>>    (if (> ncolours 15)
>>        (gethash colour colour-map)
>>      (cdr (assoc (colour colour-map))))
>
> The `if' overhead will probably dwarf the difference, so I'd say,
> just use the hash-table.  Most likely any performance problem you'll have
> won't come from that anyway.

Thank you. That helps.

>> 2. I noticed that the garbage collector hits in a little bit too often,
>
> What's too often ?  Why do you care ?
[...]

Well, I changed my mind. The ugliness/performance ratio of any attempt
to squeeze a little bit more out of that inner loop is very likely too
bad. So I do not care about a few garbage collections anymore.

    -- Oliver

-- 
Jour des Récompenses de l'Année 210 de la Révolution
Liberté, Egalité, Fraternité!