bug#74097: 31.0.50; all-completions is slower on obarrays in emacs-30 than in emacs-29

bug#74097: 31.0.50; all-completions is slower on obarrays in emacs-30 than in emacs-29

[Dmitry Gutov]

X-Debbugs-Cc: Mattias Engdegård <mattiase@acm.org>

This is probably not critical for most uses, but it came up in experiment:

(let* ((my-size 100000)
        (my-obarray
         (let ((ob (obarray-make 1000)))
           (dotimes (i my-size)
             (intern (format "%s" i) ob))
           ob))
        (my-list
         (let (list)
           (dotimes (i my-size)
             (push (format "%s" i) list))
           (nreverse list)))
        (s 0))
   ;; Just to verify.
   (message "lengths obarray: %s list: %s"
            (progn
              (obarray-map (lambda (_) (cl-incf s))
                           my-obarray)
              s)
            (length my-list))
   (message "list %s" (benchmark-run 10 (all-completions "1" my-list)))
   (message "obarray %s" (benchmark-run 10 (all-completions "1" 
my-obarray))))

In emacs-30 and emacs-31 it's 2-4x slower than on a list of strings:

   lengths obarray: 100000 list: 100000
   obarray (0.10444341 1 0.01843060800000007)
   list (0.038867963 1 0.01855441899999999)
      lengths obarray: 100000 list: 100000
   obarray (0.082519579 1 0.017577374000000034)
   list (0.038507061 1 0.017987661999999904)
      lengths obarray: 100000 list: 100000
   obarray (0.09489151100000001 1 0.017720256000000045)
   list (0.039559388 1 0.01808564800000001)

And in emacs-29 the performance is closer to a list (1.5x difference maybe):

   lengths obarray: 100000 list: 100000
   obarray (0.04566377 1 0.014927433999999629)
   list (0.034239810999999995 1 0.015311175000000787)
      lengths obarray: 100000 list: 100000
   obarray (0.048750494 1 0.015651392999999736)
   list (0.034873387 1 0.015080243999999965)

In GNU Emacs 31.0.50 (build 41, x86_64-pc-linux-gnu, GTK+ Version
  3.24.41, cairo version 1.18.0) of 2024-10-29 built on potemkin
Repository revision: fb5915665522f747daa8dfa11e91dc406d18edb7
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12302006
System Description: Ubuntu 24.04.1 LTS