GNU bug report logs - #73883
[PATCH] Fix internal_equal so that it uses at most one hash table

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 73883 in the body.
You can then email your comments to 73883 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: Ethan Kong <ek.ethan.kong <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: [PATCH] Fix internal_equal so that it uses at most one hash table
Date: Sat, 19 Oct 2024 18:53:40 +0800

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

Tags: patch

Hi,

When I use 'equal' on large, cyclic objects, emacs freezes.

Reproduce:

    ;; emacs -Q
    (require 'org-element)

    ;; get two identical `org-element' trees of this file
    ;;
https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org
    (let ((file (expand-file-name "doc/misc/modus-themes.org"
                                  source-directory)))
      (with-current-buffer (find-file-noselect file)
        (setq org-o1 (org-element-parse-buffer))
        (org-element-cache-reset)
        (setq org-o2 (org-element-parse-buffer))))

    ;; the test
    (equal org-o1 org-o2)

This equal call freezes emacs. And the memory usage of emacs grows
quickly, until I quit. Reproduced with emacs 29.4 and the master branch.


The cause:

Current code on the master branch:

    static bool
    internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind
equal_kind,
                    int depth, Lisp_Object ht)
    {
     tail_recurse:
      if (depth > 10)
        {
          // ...
          if (NILP (ht))
            ht = CALLN (Fmake_hash_table, QCtest, Qeq);
          // ...
        }
      // ...
            if (! internal_equal (XCAR (o1), XCAR (o2),
                                  equal_kind, depth + 1, ht))
              return false;
            // ...
    }

When internal_equal calls itself, it passes the hash table argument 'ht'
by value. As a result, each internal_equal(depth=11) call initializes
its own hash table, separately recording the objects it encounters in
further recursive calls. This leads to excessive 'hash_put' and
significant memory allocation.


Fix:

Make internal_equal pass the hash table by pointer (see the patch).

With this patch, the test above returns quickly:

    (benchmark-run 100 (equal org-o1 org-o2))

(2.562444 20 0.30933900000000014)

This will also improve the performance for smaller cyclic objects:

    ;; emacs -Q
    (defun make-cyclic (n m)
      (let* ((l1 (make-list n 1))
             (l2 (make-list m 2)))
        (setf (nth (1- m) l2) l1)
        (setf (nth (1- n) l1) l2)
        l1))

    (let ((a (make-cyclic 100 7))
          (b (make-cyclic 100 7)))
      (cl-assert (equal a b))
      (benchmark-run 10000 (equal a b)))

Current:
(0.530081 32 0.49294199999999977)

With the patch:
(0.036401 1 0.0173350000000001)

And it passes all the tests in 'make fns-tests'.


P.S. Could I get the copyright assignment paperwork please?

Best,
Ethan Kong


In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on
 AVALON
Windowing system distributor 'Microsoft Corp.', version 10.0.22631
System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317)

Configured using:
 'configure --with-modules --without-dbus --with-native-compilation=aot
 --without-compress-install --with-sqlite3 --with-tree-sitter
 CFLAGS=-O2'

[Message part 2 (text/html, inline)]

[0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch (application/octet-stream, attachment)]

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

From: Stefan Kangas <stefankangas <at> gmail.com>
To: Ethan Kong <ek.ethan.kong <at> gmail.com>, 73883 <at> debbugs.gnu.org
Subject: Re: bug#73883: [PATCH] Fix internal_equal so that it uses at most one
 hash table
Date: Sun, 20 Oct 2024 04:55:55 -0700

Ethan Kong <ek.ethan.kong <at> gmail.com> writes:

> P.S. Could I get the copyright assignment paperwork please?

Form sent off-list.

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

From: Ethan Kong <ek.ethan.kong <at> gmail.com>
To: 73883 <at> debbugs.gnu.org
Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects
Date: Sun, 20 Oct 2024 19:47:41 +0800

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

I realize the previous title might have been misleading, so I'm replying 
with a
more suitable one. The summary line of the patch is also updated.

On 2024/10/19 18:53, Ethan Kong wrote:
> Tags: patch
>
> Hi,
>
> When I use 'equal' on large, cyclic objects, emacs freezes.
>
> Reproduce:
>
>     ;; emacs -Q
>     (require 'org-element)
>
>     ;; get two identical `org-element' trees of this file
>     ;; 
> https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org
>     (let ((file (expand-file-name "doc/misc/modus-themes.org 
> <http://modus-themes.org>"
>                                   source-directory)))
>       (with-current-buffer (find-file-noselect file)
>         (setq org-o1 (org-element-parse-buffer))
>         (org-element-cache-reset)
>         (setq org-o2 (org-element-parse-buffer))))
>
>     ;; the test
>     (equal org-o1 org-o2)
>
> This equal call freezes emacs. And the memory usage of emacs grows
> quickly, until I quit. Reproduced with emacs 29.4 and the master branch.
>
>
> The cause:
>
> Current code on the master branch:
>
>     static bool
>     internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind 
> equal_kind,
>                     int depth, Lisp_Object ht)
>     {
>      tail_recurse:
>       if (depth > 10)
>         {
>           // ...
>           if (NILP (ht))
>             ht = CALLN (Fmake_hash_table, QCtest, Qeq);
>           // ...
>         }
>       // ...
>             if (! internal_equal (XCAR (o1), XCAR (o2),
>                                   equal_kind, depth + 1, ht))
>               return false;
>             // ...
>     }
>
> When internal_equal calls itself, it passes the hash table argument 'ht'
> by value. As a result, each internal_equal(depth=11) call initializes
> its own hash table, separately recording the objects it encounters in
> further recursive calls. This leads to excessive 'hash_put' and
> significant memory allocation.
>
>
> Fix:
>
> Make internal_equal pass the hash table by pointer (see the patch).
>
> With this patch, the test above returns quickly:
>
>     (benchmark-run 100 (equal org-o1 org-o2))
>
> (2.562444 20 0.30933900000000014)
>
> This will also improve the performance for smaller cyclic objects:
>
>     ;; emacs -Q
>     (defun make-cyclic (n m)
>       (let* ((l1 (make-list n 1))
>              (l2 (make-list m 2)))
>         (setf (nth (1- m) l2) l1)
>         (setf (nth (1- n) l1) l2)
>         l1))
>
>     (let ((a (make-cyclic 100 7))
>           (b (make-cyclic 100 7)))
>       (cl-assert (equal a b))
>       (benchmark-run 10000 (equal a b)))
>
> Current:
> (0.530081 32 0.49294199999999977)
>
> With the patch:
> (0.036401 1 0.0173350000000001)
>
> And it passes all the tests in 'make fns-tests'.
>
>
> P.S. Could I get the copyright assignment paperwork please?
>
> Best,
> Ethan Kong
>
>
> In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on
>  AVALON
> Windowing system distributor 'Microsoft Corp.', version 10.0.22631
> System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317)
>
> Configured using:
>  'configure --with-modules --without-dbus --with-native-compilation=aot
>  --without-compress-install --with-sqlite3 --with-tree-sitter
>  CFLAGS=-O2'

[Message part 2 (text/html, inline)]

[0001-Fix-equal-freezing-on-large-cyclic-objects.patch (text/plain, attachment)]

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Ethan Kong <ek.ethan.kong <at> gmail.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>,
 Mattias Engdegård <mattiase <at> acm.org>
Cc: 73883 <at> debbugs.gnu.org
Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects
Date: Sat, 02 Nov 2024 13:41:42 +0200

> Date: Sun, 20 Oct 2024 19:47:41 +0800
> From: Ethan Kong <ek.ethan.kong <at> gmail.com>
> 
> I realize the previous title might have been misleading, so I'm replying with a
> more suitable one. The summary line of the patch is also updated.
> 
> On 2024/10/19 18:53, Ethan Kong wrote:
> 
>  Tags: patch
> 
>  Hi,
> 
>  When I use 'equal' on large, cyclic objects, emacs freezes.
> 
>  Reproduce:
> 
>      ;; emacs -Q
>      (require 'org-element)
> 
>      ;; get two identical `org-element' trees of this file
>      ;; https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org
>      (let ((file (expand-file-name "doc/misc/modus-themes.org"
>                                    source-directory)))
>        (with-current-buffer (find-file-noselect file)
>          (setq org-o1 (org-element-parse-buffer))
>          (org-element-cache-reset)
>          (setq org-o2 (org-element-parse-buffer))))
> 
>      ;; the test
>      (equal org-o1 org-o2)
> 
>  This equal call freezes emacs. And the memory usage of emacs grows
>  quickly, until I quit. Reproduced with emacs 29.4 and the master branch.
> 
>  The cause:
> 
>  Current code on the master branch:
> 
>      static bool
>      internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
>                      int depth, Lisp_Object ht)
>      {
>       tail_recurse:
>        if (depth > 10)
>          {
>            // ...
>            if (NILP (ht))
>              ht = CALLN (Fmake_hash_table, QCtest, Qeq);
>            // ...
>          }
>        // ...
>              if (! internal_equal (XCAR (o1), XCAR (o2),
>                                    equal_kind, depth + 1, ht))
>                return false;
>              // ...
>      }
> 
>  When internal_equal calls itself, it passes the hash table argument 'ht'
>  by value. As a result, each internal_equal(depth=11) call initializes
>  its own hash table, separately recording the objects it encounters in
>  further recursive calls. This leads to excessive 'hash_put' and
>  significant memory allocation.
> 
>  Fix:
> 
>  Make internal_equal pass the hash table by pointer (see the patch).
> 
>  With this patch, the test above returns quickly:
> 
>      (benchmark-run 100 (equal org-o1 org-o2))
> 
>  (2.562444 20 0.30933900000000014)
> 
>  This will also improve the performance for smaller cyclic objects:
> 
>      ;; emacs -Q
>      (defun make-cyclic (n m)
>        (let* ((l1 (make-list n 1))
>               (l2 (make-list m 2)))
>          (setf (nth (1- m) l2) l1)
>          (setf (nth (1- n) l1) l2)
>          l1))
> 
>      (let ((a (make-cyclic 100 7))
>            (b (make-cyclic 100 7)))
>        (cl-assert (equal a b))
>        (benchmark-run 10000 (equal a b)))
> 
>  Current:
>  (0.530081 32 0.49294199999999977)
> 
>  With the patch:
>  (0.036401 1 0.0173350000000001)
> 
>  And it passes all the tests in 'make fns-tests'.
> 
>  P.S. Could I get the copyright assignment paperwork please?
> 
>  Best,
>  Ethan Kong
> 
>  In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on
>   AVALON
>  Windowing system distributor 'Microsoft Corp.', version 10.0.22631
>  System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317)
> 
>  Configured using:
>   'configure --with-modules --without-dbus --with-native-compilation=aot
>   --without-compress-install --with-sqlite3 --with-tree-sitter
>   CFLAGS=-O2'

Stefan and Mattias, any comments or suggestions?

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

From: Ethan Kong <ek.ethan.kong <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>, Stefan Monnier <monnier <at> iro.umontreal.ca>,
 Mattias Engdegård <mattiase <at> acm.org>,
 Stefan Kangas <stefankangas <at> gmail.com>
Cc: 73883 <at> debbugs.gnu.org
Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects
Date: Fri, 8 Nov 2024 21:37:27 +0800

Hi,

On 24/10/20 19:55, Stefan Kangas wrote:
> Ethan Kong <ek.ethan.kong <at> gmail.com> writes:
>
>> P.S. Could I get the copyright assignment paperwork please?
> Form sent off-list.

Just to let you know that my FSF Copyright Assignment process is
complete.

Best,
Ethan Kong

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: Mattias Engdegård
 <mattiase <at> acm.org>, Ethan Kong <ek.ethan.kong <at> gmail.com>,
 73883 <at> debbugs.gnu.org
Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects
Date: Fri, 08 Nov 2024 13:57:59 -0500

>> I realize the previous title might have been misleading, so I'm
>> replying with a more suitable one. The summary line of the patch is
>> also updated.

While the new title is arguably better for a bug report, the old one was
better at describing your patch.  🙂

> Stefan and Mattias, any comments or suggestions?

Looks good to me,


        Stefan

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

From: Ethan Kong <ek.ethan.kong <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 73883 <at> debbugs.gnu.org
Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects
Date: Sat, 9 Nov 2024 11:36:56 +0800

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

On 24/11/09 02:57, Stefan Monnier wrote:
> While the new title is arguably better for a bug report, the old one was
> better at describing your patch.  🙂

I see. Here is the patch with the old summary line.

[0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch (text/plain, attachment)]

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Ethan Kong <ek.ethan.kong <at> gmail.com>
Cc: monnier <at> iro.umontreal.ca, 73883-done <at> debbugs.gnu.org
Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects
Date: Sat, 09 Nov 2024 11:01:54 +0200

> Cc: 73883 <at> debbugs.gnu.org
> Date: Sat, 9 Nov 2024 11:36:56 +0800
> From: Ethan Kong <ek.ethan.kong <at> gmail.com>
> 
> On 24/11/09 02:57, Stefan Monnier wrote:
> > While the new title is arguably better for a bug report, the old one was
> > better at describing your patch.  🙂
> 
> I see. Here is the patch with the old summary line.

Thanks, installed on the master branch, and closing the bug.

Previous Next

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