Subject: bug#73883: closed (Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects)

From: [email-masked] (GNU bug Tracking System)
Date: Sat, 09 Nov 2024 09:03:02 +0000

Your bug report

#73883: [PATCH] Fix internal_equal so that it uses at most one hash table

which was filed against the emacs package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
73883: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=73883
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects
From: Eli Zaretskii <[email-masked]>
To: Ethan Kong <[email-masked]>
Cc: [email-masked], [email-masked]
Date: Sat, 09 Nov 2024 11:01:54 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

> Cc: [email-masked]
> Date: Sat, 9 Nov 2024 11:36:56 +0800
> From: Ethan Kong <[email-masked]>
> 
> 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.

Subject: [PATCH] Fix internal_equal so that it uses at most one hash table
From: Ethan Kong <[email-masked]>
To: [email-masked]
Date: Sat, 19 Oct 2024 18:53:40 +0800
List-Id: <debbugs-submit.debbugs.gnu.org>

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'