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

Previous Next

Full log

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?

Previous Next

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