bug#37321: 27.0.50; Excessive gc in a use case (el-search)

[Noam Postavsky]

Michael Heerdegen <michael_heerdegen@web.de> writes:
>
> Question: why didn't it help to switch to hash tables?  My use case is
> like this: very frequently I need to collect N (N is variable with an
> order of magnitude of roughly 0 < N < 100.000 or so) objects in a
> structure and later perform member tests whether a given element is
> equal to one of the N.  I used to use a list and `member' to implement
> this.  When I use a hash-table that associates the N elements with t
> instead, and use gethash as member test, do I produce less garbage?
> That would be good but when using this it didn't lower the amount of
> time spent in gc.

I would expect it to produce more garbage.  A list of length N has to
contain 2N slots (2 for each cons = car+cdr).  A hash table with N
items, needs at least 2N as well: N keys + N values.  And since it
stores these in vectors/arrays, as you add items it has to reallocate
them to resize (and the final size will likely be a bit higher than N),
producing more garbage (this can be avoided if you can pass :size N up
front).

gethash as a member test should be faster than lists for large N though.