From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Noam Postavsky Newsgroups: gmane.emacs.bugs Subject: bug#37321: 27.0.50; Excessive gc in a use case (el-search) Date: Tue, 17 Sep 2019 08:47:46 -0400 Message-ID: <87d0fz9jil.fsf@gmail.com> References: <87lfv1pm5x.fsf@web.de> <874l1mc01w.fsf@web.de> <87woeidd4g.fsf@web.de> <733d0142-51ee-55df-de0c-cca7c989b370@cs.ucla.edu> <87r24flrwp.fsf@web.de> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="204487"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) Cc: Paul Eggert , 37321@debbugs.gnu.org To: Michael Heerdegen Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Tue Sep 17 14:49:09 2019 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.89) (envelope-from ) id 1iACur-000r4t-LC for geb-bug-gnu-emacs@m.gmane.org; Tue, 17 Sep 2019 14:49:09 +0200 Original-Received: from localhost ([::1]:45758 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iACuq-0006qK-D3 for geb-bug-gnu-emacs@m.gmane.org; Tue, 17 Sep 2019 08:49:08 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:38709) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iACtq-0006AY-6w for bug-gnu-emacs@gnu.org; Tue, 17 Sep 2019 08:48:08 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iACtn-0000yk-JP for bug-gnu-emacs@gnu.org; Tue, 17 Sep 2019 08:48:05 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:43001) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1iACtl-0000ws-V6 for bug-gnu-emacs@gnu.org; Tue, 17 Sep 2019 08:48:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1iACtl-00021n-R0 for bug-gnu-emacs@gnu.org; Tue, 17 Sep 2019 08:48:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Noam Postavsky Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Tue, 17 Sep 2019 12:48:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 37321 X-GNU-PR-Package: emacs Original-Received: via spool by 37321-submit@debbugs.gnu.org id=B37321.15687244787786 (code B ref 37321); Tue, 17 Sep 2019 12:48:01 +0000 Original-Received: (at 37321) by debbugs.gnu.org; 17 Sep 2019 12:47:58 +0000 Original-Received: from localhost ([127.0.0.1]:51822 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1iACti-00021W-A2 for submit@debbugs.gnu.org; Tue, 17 Sep 2019 08:47:58 -0400 Original-Received: from mail-io1-f46.google.com ([209.85.166.46]:37574) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1iACte-00021H-QO for 37321@debbugs.gnu.org; Tue, 17 Sep 2019 08:47:57 -0400 Original-Received: by mail-io1-f46.google.com with SMTP id b19so7277116iob.4 for <37321@debbugs.gnu.org>; Tue, 17 Sep 2019 05:47:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=eyBnTM2thUUf+gNhoaHOMFZ5CZoqN2zC+CFu7nqdwMs=; b=nP6JoIy3JHnvnfivr9vLH3ZNqQOT1oRcCb+uDqX6k+G5IsR+U5Lv2MVyPitP0H6njz gkDwrTyRYeTs2nKbbPkLk3KdqA2wWlKW1wF9B172uRbxJuF0vev/8cKX+/cn66Plt0Nv 65QrmfUI4mB0yoMWFcUghu0W71yO8bLHxNFrNy7486pA0pkYxbUvRiwBioFXgvZBLN+P 2yN9duBOioNhjcwZSWNLsvBzzDolnenpf6UT02eSzGgSnf5VttgPviCACH6gFXSMBHyk YqbEISHeeTq7ca2xaQWG5np1+oux28rosbTno4PiUc46ZOqoM/2MNbnVIEq+bRpGgdwz 7zbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version; bh=eyBnTM2thUUf+gNhoaHOMFZ5CZoqN2zC+CFu7nqdwMs=; b=rSwPOoRlKh4njVCKGGFA8BEEP0z3DegMjWoZlIERiZZHyBK50PeZrdSuEAZkY1A9ku 5OBpJBWKGsWc542quW9XYQlCho9XMm2aSwB8vuUE75REM3GvWXKt7YWtmmneyFoKGGqE 53itiXO77gKJRIVpAXIiXsGTVDdbv+FRB1oC16iZGbUiTkmWCC0AiOze6a2hTDY8nes9 IunJk7HCkEfjCRMRX4Yw7aAG4ty0bk4+jFk1C5iLsBs9iwG19KC2Fnxn3Tk3SmV+kmq6 N5QStp6m5dOmW4yg2OUIQk+gZfc/Glx41zCwsggzNRG4p/i19BEH0b/sKqrfnzqZkFn/ UvUQ== X-Gm-Message-State: APjAAAU5jF2Yp7PjHtx+LrLU7ve2WgUddork7lmdMWLoJVLNP5oZu8Rb l6gfciwXXXzeYJ6AqXpXcVQKxWEf X-Google-Smtp-Source: APXvYqx47by2I/YUWWt6h5MNDN5B0r42OacnVj2Si9C3NwP0fNhNGyuNX/fkBBhsjX340JwG2onxeg== X-Received: by 2002:a5e:8a43:: with SMTP id o3mr3552406iom.296.1568724468782; Tue, 17 Sep 2019 05:47:48 -0700 (PDT) Original-Received: from minid (cbl-45-2-119-34.yyz.frontiernetworks.ca. [45.2.119.34]) by smtp.gmail.com with ESMTPSA id v3sm1952196ioh.51.2019.09.17.05.47.47 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 17 Sep 2019 05:47:47 -0700 (PDT) In-Reply-To: <87r24flrwp.fsf@web.de> (Michael Heerdegen's message of "Tue, 17 Sep 2019 01:53:26 +0200") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 209.51.188.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:166641 Archived-At: Michael Heerdegen 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.