From: Noam Postavsky <npostavs@gmail.com>
To: Michael Heerdegen <michael_heerdegen@web.de>
Cc: Paul Eggert <eggert@cs.ucla.edu>, 37321@debbugs.gnu.org
Subject: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 17 Sep 2019 08:47:46 -0400 [thread overview]
Message-ID: <87d0fz9jil.fsf@gmail.com> (raw)
In-Reply-To: <87r24flrwp.fsf@web.de> (Michael Heerdegen's message of "Tue, 17 Sep 2019 01:53:26 +0200")
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.
next prev parent reply other threads:[~2019-09-17 12:47 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-09-06 13:52 bug#37321: 27.0.50; Excessive gc in a use case (el-search) Michael Heerdegen
2019-09-07 14:23 ` Michael Heerdegen
2019-09-07 15:30 ` Michael Heerdegen
2019-09-08 1:11 ` Paul Eggert
2019-09-08 14:52 ` Michael Heerdegen
2019-09-08 15:25 ` Michael Heerdegen
2019-09-14 8:04 ` Paul Eggert
2019-09-14 8:37 ` Eli Zaretskii
2019-09-14 8:52 ` Paul Eggert
2019-09-14 9:57 ` Eli Zaretskii
2019-09-14 17:57 ` Paul Eggert
2019-09-14 18:16 ` Eli Zaretskii
2019-09-15 4:33 ` Richard Stallman
2019-09-16 23:53 ` Michael Heerdegen
2019-09-17 0:55 ` Paul Eggert
2019-09-21 0:41 ` Michael Heerdegen
2019-09-21 0:46 ` Michael Heerdegen
2019-09-21 6:19 ` Paul Eggert
2019-09-17 12:47 ` Noam Postavsky [this message]
2019-09-21 0:44 ` Michael Heerdegen
2019-09-25 9:42 ` Michael Heerdegen
2019-09-25 20:37 ` Paul Eggert
2019-09-26 11:42 ` Michael Heerdegen
2019-09-26 12:14 ` Eli Zaretskii
2019-09-26 13:03 ` Michael Heerdegen
2019-10-08 8:43 ` Michael Heerdegen
2019-10-08 9:09 ` Eli Zaretskii
2019-10-08 9:11 ` Michael Heerdegen
2019-10-08 9:19 ` Eli Zaretskii
2019-10-08 11:12 ` Michael Heerdegen
2019-10-08 12:11 ` Eli Zaretskii
2019-10-08 12:38 ` Michael Heerdegen
2019-10-08 13:03 ` Eli Zaretskii
2019-10-09 14:47 ` Michael Heerdegen
2019-10-09 15:33 ` Eli Zaretskii
2019-10-09 20:53 ` Paul Eggert
2019-10-10 10:58 ` Michael Heerdegen
2019-10-08 9:22 ` Michael Heerdegen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87d0fz9jil.fsf@gmail.com \
--to=npostavs@gmail.com \
--cc=37321@debbugs.gnu.org \
--cc=eggert@cs.ucla.edu \
--cc=michael_heerdegen@web.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
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).