bug#41200: Displaying a tooltip with x-show-tip gets very slow as more faces are defined

[Eli Zaretskii <eliz@gnu.org>]

> Resent-From: Clément Pit-Claudel <cpitclaudel@gmail.com>
> Original-Sender: "Debbugs-submit" <debbugs-submit-bounces@debbugs.gnu.org>
> Resent-CC: bug-gnu-emacs@gnu.org
> Resent-Sender: help-debbugs@gnu.org
> From: Clément Pit-Claudel <cpitclaudel@gmail.com>
> Date: Tue, 12 May 2020 00:30:23 -0400
> 
> 
> [1:text/plain Hide]
> 
> Hi all,
> 
>   (defun my-def-many-faces (nfaces)
>     (dotimes (i nfaces)
>       (custom-declare-face
>        (intern (format "my-face-%d" i))
>        '((t)) "A face."
>        :group 'basic-faces)))
> 
>   (defun my-bench-x-tip (nfaces)
>     (setq x-gtk-use-system-tooltips nil)
>     (my-def-many-faces nfaces)
>     (benchmark-run 1 (x-show-tip "Test" (selected-frame) nil 5 nil nil)))
> 
>   (my-bench-x-tip 100) ;; ⇒ (0.035934318 1 0.015908304000000012)
>   (my-bench-x-tip 200) ;; ⇒ (0.049593474 1 0.01508625500000002)
>   (my-bench-x-tip 300) ;; ⇒ (0.094929297 2 0.03376510099999999)
>   (my-bench-x-tip 400) ;; ⇒ (0.094900665 2 0.03254889999999999)
>   (my-bench-x-tip 500) ;; ⇒ (0.118183442 2 0.03218763600000002)
>   (my-bench-x-tip 600) ;; ⇒ (0.154759438 3 0.04923829399999996)
>   (my-bench-x-tip 700) ;; ⇒ (0.183241646 3 0.04901039700000004)
>   (my-bench-x-tip 800) ;; ⇒ (0.212218872 3 0.050182316999999976)
>   (my-bench-x-tip 900) ;; ⇒ (0.248743542 3 0.04915146899999995)
>   (my-bench-x-tip 1000) ;; ⇒ (0.29221963 3 0.04943874300000006)
>   (my-bench-x-tip 1100) ;; ⇒ (0.334084605 3 0.05403986499999991)
>   (my-bench-x-tip 1200) ;; ⇒ (0.397292289 4 0.06869684599999992)
>   (my-bench-x-tip 1300) ;; ⇒ (0.442873256 4 0.06865671799999995)
>   (my-bench-x-tip 1400) ;; ⇒ (0.492474982 4 0.06888139900000001)
>   (my-bench-x-tip 1500) ;; ⇒ (0.579180262 5 0.08583425400000011)
>   (my-bench-x-tip 1600) ;; ⇒ (0.63504114 5 0.08973981699999989)
>   (my-bench-x-tip 1700) ;; ⇒ (0.723722857 5 0.09094433899999999)
>   (my-bench-x-tip 1800) ;; ⇒ (0.791952279 5 0.08777533800000015)
>   (my-bench-x-tip 1900) ;; ⇒ (0.902377982 6 0.10768666300000018)
>   (my-bench-x-tip 2000) ;; ⇒ (0.998815784 6 0.11384837999999986)
> 
> Be sure to run it in emacs -q, not emacs -Q, because emacs -Q ignores X resources and hence skips the body of make-face-x-resource-internal, which contributes greatly to the issue.
> For some reasons the effects are a bit worse in my config — roughly a factor 3 to 5 (I have 600 faces defined, and each tooltip takes .5s to display).  The profiles below suggest that face-spec-set-2 is called in my config, but not in my repro, which could explain part of the difference.
> 
> This is what the profile in emacs -q looks like:
> 
> - command-execute                                                1742  97%
>  - call-interactively                                            1742  97%
>   - funcall-interactively                                        1720  96%
>    - eval-defun                                                  1711  95%
>     - elisp--eval-defun                                          1711  95%
>      - eval-region                                               1711  95%
>       - let                                                      1711  95%
>        - list                                                    1711  95%
>         - let                                                    1711  95%
>          - x-show-tip                                            1708  95%
>           - face-set-after-frame-default                         1708  95%
>            - face-spec-recalc                                    1654  92%
>             - make-face-x-resource-internal                      1414  78%
>              - set-face-attributes-from-resources                1413  78%
>               - set-face-attribute-from-resource                 1394  77%
>                - face-name                                       1353  75%
>                 - check-face                                     1348  75%
>                    facep                                         1344  75%

If you look at internal-lisp-face-p, which is the workhorse of facep,
you will see that it does the moral equivalent of

  (assq FACE (frame-face-alist))

(The code is actually in a subroutine called by internal-lisp-face-p.)
Which means face-set-after-frame-default, which loops over all of the
faces, runs with O(n²) complexity in the number of faces.

So I think if we want to support such large amounts of faces, we
should not store them in alists, but in a more efficient data
structure.

> Configured using:
>  'configure -C'
> 
> Configured features:
> XPM JPEG TIFF GIF PNG RSVG CAIRO SOUND GPM DBUS GSETTINGS GLIB NOTIFY
> INOTIFY ACL LIBSELINUX GNUTLS LIBXML2 FREETYPE HARFBUZZ M17N_FLT LIBOTF
> ZLIB TOOLKIT_SCROLL_BARS GTK3 X11 XDBE XIM MODULES THREADS LIBSYSTEMD
> JSON PDUMPER LCMS2 GMP

No Emacs version information?