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

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Ethan Kong <ek.ethan.kong <at> gmail.com>
Subject: bug#73885: closed (Re: bug#73883: [PATCH] Fix 'equal' freezing on
 large cyclic objects)
Date: Sat, 09 Nov 2024 09:03:03 +0000

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

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 73885 <at> debbugs.gnu.org.

-- 
73883: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=73883
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems

[Message part 2 (message/rfc822, inline)]

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.

[Message part 3 (message/rfc822, inline)]

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 21:12:41 +0800

[Message part 4 (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'

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

Previous Next

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