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

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 37321 in the body.
You can then email your comments to 37321 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: bug-gnu-emacs <at> gnu.org
Subject: 27.0.50; Excessive gc in a use case (el-search)
Date: Fri, 06 Sep 2019 15:52:10 +0200

Hi,

apparently due to the latest changes in gc (I noticed the problem today,
after doing a make bootstrap yesterday), el-searching is slowed down by
a factor of 10000 or so.  Profiling shows that nearly all of the time is
spent in gc.

To reproduce from emacs -Q:

M-x list-packages
Install el-search
M-x el-search-emacs-elisp-sources 'pcase M-RET

This will start an el-occur for the symbol 'pcase in the Emacs Elisp
sources.  This normally takes around 10 seconds but is now just
unusable.

(If you want me to bisect, do I have to make bootstrap, or does a simple
make suffice?)

Hope someone can help.

TIA,

Michael.





In GNU Emacs 27.0.50 (build 2, x86_64-pc-linux-gnu, GTK+ Version 3.24.10)
 of 2019-09-06 built on drachen
Repository revision: 459b416e5f950c6127f10c9eca68d65bdab688d4
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12004000
System Description: Debian GNU/Linux bullseye/sid

Message #8 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 07 Sep 2019 16:23:42 +0200

Michael Heerdegen <michael_heerdegen <at> web.de> writes:

> M-x el-search-emacs-elisp-sources 'pcase M-RET

I found the culprit.  It's this simple function:

#+begin_src emacs-lisp
(defun el-search--flatten-tree (tree)
  "Return a list of `el-search--atomic-p' objects in TREE."
  (let ((elements ())
        (walked-objects ;to avoid infinite recursion for circular TREEs
         (make-hash-table :test #'eq))
         (gc-cons-percentage 0.8)
        ) ;Why is binding it here more effective than binding it more top-level?
    (cl-labels ((walker (object)
                        (if (el-search--atomic-p object)
                            (push object elements)
                          (unless (gethash object walked-objects)
                            (puthash object t walked-objects)
                            (if (consp object)
                                (progn
                                  (while (consp object)
                                    (walker (car object))
                                    (setq object (cdr object))
                                    (if (gethash object walked-objects)
                                        (setq object nil)
                                      (puthash object t walked-objects)))
                                  (when object ;dotted list
                                    (walker object)))
                              (cl-loop for elt being the elements of object do (walker elt)))))))
      (walker tree)
      elements)))
#+end_src

I've put a lot of work in optimizing el-searching speed.  It now mainly
depends of effectiveness of gc, mostly in the above function.  When I
wrote it I noticed that it worked best when binding gc-cons-percentage
to a value of 0.8 (inside the function, see the code).  But now this
binding slows the thing down as hell.  When I remove the binding,
searching is fast again, but it still takes twice as long as in the past
when 0.8 worked.

I've no clue about how gc works and how the above function can be
optimized, and if gc is expected to be that slow now with the
gc-cons-percentage binding in effect.  Advice appreciated.

TIA,

Michael.

Message #11 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 07 Sep 2019 17:30:57 +0200

Michael Heerdegen <michael_heerdegen <at> web.de> writes:

> #+begin_src emacs-lisp
> (defun el-search--flatten-tree (tree)
>   "Return a list of `el-search--atomic-p' objects in TREE."
>   (let ((elements ())
>         (walked-objects ;to avoid infinite recursion for circular TREEs
>          (make-hash-table :test #'eq))
>          (gc-cons-percentage 0.8)
>         ) ;Why is binding it here more effective than binding it more top-level?
>     (cl-labels ((walker (object)
>                         (if (el-search--atomic-p object)
>                             (push object elements)
>                           (unless (gethash object walked-objects)
>                             (puthash object t walked-objects)
>                             (if (consp object)
>                                 (progn
>                                   (while (consp object)
>                                     (walker (car object))
>                                     (setq object (cdr object))
>                                     (if (gethash object walked-objects)
>                                         (setq object nil)
>                                       (puthash object t walked-objects)))
>                                   (when object ;dotted list
>                                     (walker object)))
>                               (cl-loop for elt being the elements of object do (walker elt)))))))
>       (walker tree)
>       elements)))
> #+end_src

It doesn't seem to be related to the hash table usage - if I remove the
hash table test based infloop check part of the function, the behavior
wrt gc doesn't change.  So I wonder what in this function does it make
so much depend on gc behavior?

Michael.

Message #14 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 7 Sep 2019 18:11:53 -0700

[Message part 1 (text/plain, inline)]

Thanks for reporting the bug. I installed the attached patch; please give it a try.

[0001-Fix-bug-when-gc-cons-percentage-is-bumped-to-0.8.patch (text/x-patch, attachment)]

Message #17 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sun, 08 Sep 2019 16:52:43 +0200

Paul Eggert <eggert <at> cs.ucla.edu> writes:

> Thanks for reporting the bug. I installed the attached patch; please
> give it a try.

Thank you, that fixes the issue for me.

FWIW, in the end, the search is still slower as before, by a factor of 5
or so.  But I had found .8 only by trying - if the gc implementation has
been changed, maybe some other value works better now.

I think I'll rewrite my use case to use hash tables instead, that should
be more efficient (less garbage).


Thanks,

Michael.

Message #20 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sun, 08 Sep 2019 17:25:03 +0200

Michael Heerdegen <michael_heerdegen <at> web.de> writes:

> I think I'll rewrite my use case to use hash tables instead, that should
> be more efficient (less garbage).

Unfortunately this doesn't make a difference :-(

Garbage collection takes ~ 50% of the search time.  I don't think I
produce unnaturally amounts of garbage.  But my Emacs seems to have
become slower independently from gc.  There is still a slow down of
searching by a factor of at least 3 or so that doesn't seem to be
related to gc.

Michael.

Message #23 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 14 Sep 2019 01:04:07 -0700

[Message part 1 (text/plain, inline)]

On 9/8/19 8:25 AM, Michael Heerdegen wrote:
> my Emacs seems to have
> become slower independently from gc.  There is still a slow down of
> searching by a factor of at least 3 or so that doesn't seem to be
> related to gc.

Have you tried turning on profiling to see what the problem might be?

I looked into it a bit, and I think the problem is related to this line in 
el-search--flatten-tree:

        (gc-cons-percentage 0.8)) ;Why is binding it here more effective than 
binding it more top-level?

That binding is not effective in general, because it causes Emacs to do most of 
its computation with gc-cons-percentage equal to 0.8, but a small amount of it 
with gc-cons-percentage equal to 0.1 (the default value). This is in an attempt 
to disable most GC. However, the attempt fails in master because when 
gc-cons-percentage drops to 0.1 Emacs does a garbage collection pretty much 
right away. (In Emacs 26, the code lucks out because Emacs happens to not look 
at gc-cons-percentage during the brief time that it is 0.1, so it doesn't GC.)

Proposed ELPA fix attached; it should help performance in Emacs master (where I 
checked in some changes recently to help master work a bit better on this 
example). The abovementioned line shouldn't be needed in Emacs master.

There may be other places in el-search that would benefit from a change similar 
to the attached patch, but I didn't investigate this.

[0001-Port-GC-tuning-to-Emacs-27-alpha.patch (text/x-patch, attachment)]

Message #26 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: michael_heerdegen <at> web.de, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 14 Sep 2019 11:37:37 +0300

> From: Paul Eggert <eggert <at> cs.ucla.edu>
> Date: Sat, 14 Sep 2019 01:04:07 -0700
> Cc: 37321 <at> debbugs.gnu.org
> 
>          (gc-cons-percentage 0.8)) ;Why is binding it here more effective than 
> binding it more top-level?
> 
> That binding is not effective in general, because it causes Emacs to do most of 
> its computation with gc-cons-percentage equal to 0.8, but a small amount of it 
> with gc-cons-percentage equal to 0.1 (the default value). This is in an attempt 
> to disable most GC. However, the attempt fails in master because when 
> gc-cons-percentage drops to 0.1 Emacs does a garbage collection pretty much 
> right away. (In Emacs 26, the code lucks out because Emacs happens to not look 
> at gc-cons-percentage during the brief time that it is 0.1, so it doesn't GC.)

Maybe we should have something in NEWS describing the Lisp-visible
effects of the GC changes, perhaps with a couple of practical do's and
dont's regarding GC?

I'm not sure if you are reading Reddit, but it turns out a lot of
Emacs users have GC-related tricks in their init files, and some
unbundled packages even do that as part of their operation, like the
one in question here.  IMNSHO, a large part of this proliferation is
based on blind copying from others without really understanding what
this does, and it reached epidemic proportions.  It might be a good
idea to give users who do care some inside information to allow them
to tune their GC tricks to these changes -- it could lower the number
of bug reports that I'm afraid will follow.

Thanks.

Message #29 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: michael_heerdegen <at> web.de, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 14 Sep 2019 01:52:27 -0700

On 9/14/19 1:37 AM, Eli Zaretskii wrote:
> It might be a good
> idea to give users who do care some inside information to allow them
> to tune their GC tricks to these changes -- it could lower the number
> of bug reports that I'm afraid will follow.

I could add something to NEWS along the lines of "The heuristics for when to 
garbage collect have been tweaked, in an attempt to make Emacs perform a bit 
better and follow its documentation a bit more closely." Dunno how much that 
would help, though. It'd be hard to be much more specific.

Message #32 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: michael_heerdegen <at> web.de, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 14 Sep 2019 12:57:49 +0300

> Cc: michael_heerdegen <at> web.de, 37321 <at> debbugs.gnu.org
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> Date: Sat, 14 Sep 2019 01:52:27 -0700
> 
> On 9/14/19 1:37 AM, Eli Zaretskii wrote:
> > It might be a good
> > idea to give users who do care some inside information to allow them
> > to tune their GC tricks to these changes -- it could lower the number
> > of bug reports that I'm afraid will follow.
> 
> I could add something to NEWS along the lines of "The heuristics for when to 
> garbage collect have been tweaked, in an attempt to make Emacs perform a bit 
> better and follow its documentation a bit more closely." Dunno how much that 
> would help, though. It'd be hard to be much more specific.

If we cannot give any specifics, I think at least telling users to
re-tune their GC tricks would help.

Thanks.

Message #35 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: michael_heerdegen <at> web.de, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 14 Sep 2019 10:57:35 -0700

[Message part 1 (text/plain, inline)]

On 9/14/19 2:57 AM, Eli Zaretskii wrote:
> If we cannot give any specifics, I think at least telling users to
> re-tune their GC tricks would help.

I installed the attached to try to do that.

[0001-Improve-doc-of-GC-thresholds.patch (text/x-patch, attachment)]

Message #38 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: michael_heerdegen <at> web.de, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 14 Sep 2019 21:16:12 +0300

> Cc: michael_heerdegen <at> web.de, 37321 <at> debbugs.gnu.org
> From: Paul Eggert <eggert <at> cs.ucla.edu>
> Date: Sat, 14 Sep 2019 10:57:35 -0700
> 
> On 9/14/19 2:57 AM, Eli Zaretskii wrote:
> > If we cannot give any specifics, I think at least telling users to
> > re-tune their GC tricks would help.
> 
> I installed the attached to try to do that.

Thanks.

Message #41 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Richard Stallman <rms <at> gnu.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: michael_heerdegen <at> web.de, eliz <at> gnu.org, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sun, 15 Sep 2019 00:33:02 -0400

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > I could add something to NEWS along the lines of "The heuristics for when to 
  > garbage collect have been tweaked, in an attempt to make Emacs perform a bit 
  > better and follow its documentation a bit more closely." Dunno how much that 
  > would help, though. It'd be hard to be much more specific.

That is so general that I am not sure it is worth mentioning in NEWS.
Users don't need to read about it to get the benefit of it.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Message #44 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 17 Sep 2019 01:53:26 +0200

Paul Eggert <eggert <at> cs.ucla.edu> writes:

> > my Emacs seems to have become slower independently from gc.  There
> > is still a slow down of searching by a factor of at least 3 or so
> > that doesn't seem to be related to gc.
>
> Have you tried turning on profiling to see what the problem might be?

For el-searches, yes, I did.  But the amounts of time spent were
distributed quite evenly between different things, I could not identify
a culprit.  It looked more like everything got proportionally slower.

> I looked into it a bit, and I think the problem is related to this
> line in el-search--flatten-tree:
>
>         (gc-cons-percentage 0.8)) ;Why is binding it here more
>         effective than binding it more top-level?
>
> That binding is not effective in general, because it causes Emacs to
> do most of its computation with gc-cons-percentage equal to 0.8, but a
> small amount of it with gc-cons-percentage equal to 0.1 (the default
> value).

Yeah.  Funnily enough I had experimented a lot with where to put this
binding.  I also had tried what you suggest in your patch.  What I
currently use looks weird and I don't understand why but in the past it
produced the most efficient result - even more efficient than with a
more durable binding.  Seems this is not true any more.

> This is in an attempt to disable most GC. However, the attempt
> fails in master because when gc-cons-percentage drops to 0.1 Emacs
> does a garbage collection pretty much right away. (In Emacs 26, the
> code lucks out because Emacs happens to not look at gc-cons-percentage
> during the brief time that it is 0.1, so it doesn't GC.)

Ah, ok.

> There may be other places in el-search that would benefit from a
> change similar to the attached patch, but I didn't investigate this.

Yes, I think so.

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.

Thanks,

Michael.

Message #47 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Mon, 16 Sep 2019 17:55:56 -0700

On 9/16/19 4:53 PM, Michael Heerdegen wrote:

> For el-searches, yes, I did.  But the amounts of time spent were
> distributed quite evenly between different things, I could not identify
> a culprit.  It looked more like everything got proportionally slower.

That doesn't sound good. Can you identify which commit did that, if any?

> 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?

Hard to say, but you can use (memory-use-counts) to estimate how much 
garbage you're creating, since it counts all uses whereas 
(garbage-collect) counts only live uses. There's also memory profiling, 
as opposed to CPU profiling.

Message #50 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Noam Postavsky <npostavs <at> gmail.com>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: Paul Eggert <eggert <at> cs.ucla.edu>, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 17 Sep 2019 08:47:46 -0400

Michael Heerdegen <michael_heerdegen <at> 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.

Message #53 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 21 Sep 2019 02:41:55 +0200

Paul Eggert <eggert <at> cs.ucla.edu> writes:

> > For el-searches, yes, I did.  But the amounts of time spent were
> > distributed quite evenly between different things, I could not identify
> > a culprit.  It looked more like everything got proportionally slower.
>
> That doesn't sound good. Can you identify which commit did that, if any?

I made the gc related change to el-search now and search times don't
look that bad any more.  I still have a slow down of 2 or so, but I
think that can at least partly be explained by changes I made to
el-search in the meantime.  I'll keep an eye on it, but I guess
everything is good.

Michael.

Message #56 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Noam Postavsky <npostavs <at> gmail.com>
Cc: Paul Eggert <eggert <at> cs.ucla.edu>, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 21 Sep 2019 02:44:11 +0200

Noam Postavsky <npostavs <at> gmail.com> writes:

> 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).

Makes sense, thanks.  So in the case I had in mind switching to hash
tables offers no advantages.

Michael.

Message #59 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Sat, 21 Sep 2019 02:46:28 +0200

Michael Heerdegen <michael_heerdegen <at> web.de> writes:

> I made the gc related change to el-search now and search times don't
> look that bad any more.  I still have a slow down of 2 or so, but I
> think that can at least partly be explained by changes I made to
> el-search in the meantime.  I'll keep an eye on it, but I guess
> everything is good.

After reading all messages again, seems we are all happy and everything
is done.  Can we close?

Michael.

Message #64 received at 37321-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: 37321-done <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Fri, 20 Sep 2019 23:19:59 -0700

On 9/20/19 5:46 PM, Michael Heerdegen wrote:

> After reading all messages again, seems we are all happy and everything
> is done.  Can we close?

Sure, closing. Thanks for checking things out.

Message #67 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Wed, 25 Sep 2019 11:42:39 +0200

Paul Eggert <eggert <at> cs.ucla.edu> writes:

> That binding is not effective in general, because it causes Emacs to
> do most of its computation with gc-cons-percentage equal to 0.8, but a
> small amount of it with gc-cons-percentage equal to 0.1 (the default
> value). [...]
> Proposed ELPA fix attached [...]
>
> There may be other places in el-search that would benefit from a
> change similar to the attached patch, but I didn't investigate this.

That would actually mean that I would have to add the gc-cons-percentage
binding to nearly every single command, which are quite a lot.  Isn't
there a better way?

Thanks,

Michael.

Message #70 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Wed, 25 Sep 2019 13:37:09 -0700

On 9/25/19 2:42 AM, Michael Heerdegen wrote:
> That would actually mean that I would have to add the gc-cons-percentage
> binding to nearly every single command, which are quite a lot.  Isn't
> there a better way?

I don't see one offhand, sorry. Except for the obvious way, which 
depends on a larger question: what's different about el-search? That is, 
if you are observing significantly better performance with 
gc-cons-percentage set to 0.8, shouldn't we set it to be that value by 
default in Emacs?

Message #73 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Thu, 26 Sep 2019 13:42:02 +0200

Paul Eggert <eggert <at> cs.ucla.edu> writes:

> I don't see one offhand, sorry. Except for the obvious way, which
> depends on a larger question: what's different about el-search?

El-searching produces a lot of garbage on the way, since I must
continuously `read'.  Not a very special thing, though.

> That is, if you are observing significantly better performance with
> gc-cons-percentage set to 0.8, shouldn't we set it to be that value by
> default in Emacs?

Good question.  Could it have downsides (I guess garbage collection
would happen less often but take longer then so one could get noticeable
interrupts)?


Regards,

Michael

Message #76 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Thu, 26 Sep 2019 15:14:35 +0300

> From: Michael Heerdegen <michael_heerdegen <at> web.de>
> Date: Thu, 26 Sep 2019 13:42:02 +0200
> Cc: 37321 <at> debbugs.gnu.org
> 
> > That is, if you are observing significantly better performance with
> > gc-cons-percentage set to 0.8, shouldn't we set it to be that value by
> > default in Emacs?
> 
> Good question.  Could it have downsides (I guess garbage collection
> would happen less often but take longer then so one could get noticeable
> interrupts)?

Using 0.8 means we won't GC before we cons 80% of the heap, which
sounds too high.

Btw, any reason why you enlarge gc-cons-percentage instead of
gc-cons-threshold?  The former is less determinate because it depends
on the size of the heap, which you cannot control.

Message #79 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Thu, 26 Sep 2019 15:03:55 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> Btw, any reason why you enlarge gc-cons-percentage instead of
> gc-cons-threshold?  The former is less determinate because it depends
> on the size of the heap, which you cannot control.

I don't recall.  Just ignorance I guess.

Michael.

Message #82 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 10:43:06 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> > From: Michael Heerdegen <michael_heerdegen <at> web.de>
> > Date: Thu, 26 Sep 2019 13:42:02 +0200
> > Cc: 37321 <at> debbugs.gnu.org
> >
> > > That is, if you are observing significantly better performance with
> > > gc-cons-percentage set to 0.8, shouldn't we set it to be that value by
> > > default in Emacs?
> >
> > Good question.  Could it have downsides (I guess garbage collection
> > would happen less often but take longer then so one could get noticeable
> > interrupts)?
>
> Using 0.8 means we won't GC before we cons 80% of the heap, which
> sounds too high.

I've now had it set to 0.8 in my init file all the time and Emacs
behaved ok afaict.  So, do you want to try to increase some gc value in
Emacs master now?

Regards,

Michael.

Message #85 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 12:09:31 +0300

> From: Michael Heerdegen <michael_heerdegen <at> web.de>
> Cc: eggert <at> cs.ucla.edu,  37321 <at> debbugs.gnu.org
> Date: Tue, 08 Oct 2019 10:43:06 +0200
> 
> Eli Zaretskii <eliz <at> gnu.org> writes:
> 
> > Using 0.8 means we won't GC before we cons 80% of the heap, which
> > sounds too high.
> 
> I've now had it set to 0.8 in my init file all the time and Emacs
> behaved ok afaict.  So, do you want to try to increase some gc value in
> Emacs master now?

No, I think it's too high for being the default (you can, of course,
do that locally).  Can you instead increase gc-cons-threshold, leaving
the percentage at its default value, and see if you can get the same
good results?  It is much easier for us to bump gc-cons-threshold
(assuming the higher value is still reasonable), because that is an
absolute number, so it is independent of the heap size.

Message #88 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 11:11:56 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> No, I think it's too high for being the default (you can, of course,
> do that locally).  Can you instead increase gc-cons-threshold, leaving
> the percentage at its default value, and see if you can get the same
> good results?  It is much easier for us to bump gc-cons-threshold
> (assuming the higher value is still reasonable), because that is an
> absolute number, so it is independent of the heap size.

Sure.  Which value would you suggest?

Michael.

Message #91 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 12:19:48 +0300

> From: Michael Heerdegen <michael_heerdegen <at> web.de>
> Cc: eggert <at> cs.ucla.edu,  37321 <at> debbugs.gnu.org
> Date: Tue, 08 Oct 2019 11:11:56 +0200
> 
> Eli Zaretskii <eliz <at> gnu.org> writes:
> 
> > No, I think it's too high for being the default (you can, of course,
> > do that locally).  Can you instead increase gc-cons-threshold, leaving
> > the percentage at its default value, and see if you can get the same
> > good results?  It is much easier for us to bump gc-cons-threshold
> > (assuming the higher value is still reasonable), because that is an
> > absolute number, so it is independent of the heap size.
> 
> Sure.  Which value would you suggest?

Start with 4 times the default.  If that's not enough, double the
value until you are satisfied, and tell what was the final value.

Thanks.

Message #94 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 11:22:39 +0200

Michael Heerdegen <michael_heerdegen <at> web.de> writes:

> Sure.  Which value would you suggest?

BTW, as a guidance: an el-search for the symbol pcase in my complete
load-path (and with the .8 setting) currently behaves like this:

Elapsed time: 52.331413s (7.141519s in 20 GCs)

Conses: 4.32514e+07
Floats: 152079
Vector-Cells: 2.735e+08
Symbols: 163489
String-Chars: 8.00088e+07
Intervals: 28094
Strings: 2.7693e+06

(the last values are the printed vector difference of the return value
of `memory-use-counts' from before and after command invocation).

Michael.

Message #97 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 13:12:29 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> Start with 4 times the default.  If that's not enough, double the
> value until you are satisfied, and tell what was the final value.

I leave it to you to interpret the result (can we expect that other use
cases have a similar optimum?):



My current setup (setq gc-cons-percentage .8)

52.331413s (7.141519s in 20 GCs)


Default: (setq gc-cons-threshold 800000)

87.626289s (41.526705s in 269 GCs)


(setq gc-cons-threshold (* 800000 2))

86.213154s (40.132441s in 267 GCs)


(setq gc-cons-threshold (* 800000 4))

87.422085s (40.967298s in 267 GCs)


(setq gc-cons-threshold (* 800000 8))

84.519948s (38.535352s in 245 GCs)


(setq gc-cons-threshold (* 800000 16))

81.596529s (34.603730s in 193 GCs)


(setq gc-cons-threshold (* 800000 32))

70.866717s (24.850518s in 123 GCs)


(setq gc-cons-threshold (* 800000 64))

61.893515s (14.088496s in 63 GCs)


(setq gc-cons-threshold (* 800000 128))

56.277259s (8.122554s in 32 GCs)


(setq gc-cons-threshold (* 800000 256))

55.173263s (6.067774s in 17 GCs)


(setq gc-cons-threshold (* 800000 512))

56.116736s (8.825274s in 9 GCs)


(setq gc-cons-threshold (* 800000 1024))

70.832969s (19.474471s in 5 GCs)



Regards,

Michael.

Message #100 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 15:11:23 +0300

> From: Michael Heerdegen <michael_heerdegen <at> web.de>
> Cc: eggert <at> cs.ucla.edu,  37321 <at> debbugs.gnu.org
> Date: Tue, 08 Oct 2019 13:12:29 +0200
> 
> Eli Zaretskii <eliz <at> gnu.org> writes:
> 
> > Start with 4 times the default.  If that's not enough, double the
> > value until you are satisfied, and tell what was the final value.
> 
> I leave it to you to interpret the result (can we expect that other use
> cases have a similar optimum?):
> [...]
> 61.893515s (14.088496s in 63 GCs)
> 
> 
> (setq gc-cons-threshold (* 800000 128))
> 
> 56.277259s (8.122554s in 32 GCs)
> 
> (setq gc-cons-threshold (* 800000 256))
> 
> 55.173263s (6.067774s in 17 GCs)
> 
> (setq gc-cons-threshold (* 800000 512))
> 
> 56.116736s (8.825274s in 9 GCs)
> 
> (setq gc-cons-threshold (* 800000 1024))
> 
> 70.832969s (19.474471s in 5 GCs)

IMO, this suggests that your code produces a lot of garbage, so it is
not a good basis for setting the default values.  I would be OK with
bumping up the default gc-cons-threshold 8-fold, or even 16-fold, but
increasing it by a factor of 256 is too much, IMO: it would mean we
only GC after consing ~200MB of data, which is about half the heap
size of my current Emacs session, which has been up and running for 28
days, and has 360 live buffers.

Thanks.

Message #103 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 14:38:57 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> IMO, this suggests that your code produces a lot of garbage

Yes, mostly unavoidable afaik.

>, so it is not a good basis for setting the default values.  I would be
>OK with bumping up the default gc-cons-threshold 8-fold, or even
>16-fold, but increasing it by a factor of 256 is too much, IMO: it
>would mean we only GC after consing ~200MB of data, which is about half
>the heap size of my current Emacs session, which has been up and
>running for 28 days, and has 360 live buffers.

Ok, then I'll increase gc-cons-threshold in el-search as it had been
suggested.  Unless you have a better idea of how to handle the garbage
in a way that gc doesn't lower the speed that much (I wish I could
explicitly free the many garbage objects).


Thanks,

Michael.

Message #106 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Tue, 08 Oct 2019 16:03:58 +0300

> From: Michael Heerdegen <michael_heerdegen <at> web.de>
> Cc: eggert <at> cs.ucla.edu,  37321 <at> debbugs.gnu.org
> Date: Tue, 08 Oct 2019 14:38:57 +0200
> 
> Ok, then I'll increase gc-cons-threshold in el-search as it had been
> suggested.  Unless you have a better idea of how to handle the garbage
> in a way that gc doesn't lower the speed that much

AFAIK, the latter can only be done by changing your algorithms to
produce less garbage.

Message #109 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Wed, 09 Oct 2019 16:47:58 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> > in a way that gc doesn't lower the speed that much
>
> AFAIK, the latter can only be done by changing your algorithms to
> produce less garbage.

I tried to find out what code produces the most garbage.  It turned out
that ca. 50% of garbage was generated by code that prevents infinite
recursion when recursing into nested structures.  I use hash tables to
collect visited objects, and the hash tables cause the garbage.  I tried
to reuse hash tables and clear them after each use, but this makes the
code much slower than what I win from gc.

But 99,9% of el-searched code isn't cyclic, so the effort is for nothing
most of the time.  Is there an efficient way to find out if a given
object is cyclic?

For now I try with this:

(lambda ()
  (save-excursion)
  (goto-char (point-min))
  (search-forward-regexp "#[0-9+]=[^\"]" nil t))

(all treated objects are read from a buffer, so I can inspect the
contents) and get good results but it feels a bit hackish.


Thanks,

Michael.

Message #112 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Wed, 09 Oct 2019 18:33:12 +0300

> From: Michael Heerdegen <michael_heerdegen <at> web.de>
> Cc: eggert <at> cs.ucla.edu,  37321 <at> debbugs.gnu.org
> Date: Wed, 09 Oct 2019 16:47:58 +0200
> 
> > AFAIK, the latter can only be done by changing your algorithms to
> > produce less garbage.
> 
> I tried to find out what code produces the most garbage.  It turned out
> that ca. 50% of garbage was generated by code that prevents infinite
> recursion when recursing into nested structures.  I use hash tables to
> collect visited objects, and the hash tables cause the garbage.  I tried
> to reuse hash tables and clear them after each use, but this makes the
> code much slower than what I win from gc.
> 
> But 99,9% of el-searched code isn't cyclic, so the effort is for nothing
> most of the time.  Is there an efficient way to find out if a given
> object is cyclic?

The hare/tortoise method we use in data.c?

Or maybe you could make your search non-recursive by using an
internal queue of requests (like in BFS vs DFS)?

(I wrote that based on 5 sec of thought, so maybe it makes no sense at
all.)

Message #115 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Eli Zaretskii <eliz <at> gnu.org>, Michael Heerdegen <michael_heerdegen <at> web.de>
Cc: 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Wed, 9 Oct 2019 13:53:07 -0700

On 10/9/19 8:33 AM, Eli Zaretskii wrote:
> The hare/tortoise method we use in data.c?

Yes, that's a good suggestion, as Brent's teleporting tortoise-hare 
algorithm (see citation in lisp.h) is quite good at lessening the 
overhead of checking for this rare situation. Perhaps there's a way we 
could "export" that algorithm from the C code, so that Elisp code could 
use the algorithm without having to reinvent it.

Message #118 received at 37321 <at> debbugs.gnu.org (full text, mbox):

From: Michael Heerdegen <michael_heerdegen <at> web.de>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: eggert <at> cs.ucla.edu, 37321 <at> debbugs.gnu.org
Subject: Re: bug#37321: 27.0.50; Excessive gc in a use case (el-search)
Date: Thu, 10 Oct 2019 12:58:07 +0200

Eli Zaretskii <eliz <at> gnu.org> writes:

> The hare/tortoise method we use in data.c?

I didn't know that one.  Nice!  Thanks for the suggestions,

Michael.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.