Re: OKURI-NASI

[Stefan Monnier]

> Doing some very light profiling here, a lot of the time is taken up by
> skkdic-get-entry, which is just lookup-nested-alist.

Odd: `skkdic-get-entry` didn't even appear in the profile I got (and
`lookup-nested-alist` was dwarfed by other things):

        5412  79% - normal-top-level
        5346  78%  - command-line
        5345  78%   - command-line-1
        5343  78%    - skkdic-convert
        2770  40%     - skkdic-convert-okuri-nasi
        2751  40%      - skkdic-reduced-candidates
        2699  39%       - skkdic-breakup-string
         707  10%        - skkdic-breakup-string
           7   0%         - skkdic-breakup-string
           2   0%          - skkdic-breakup-string
           1   0%             skkdic-breakup-string
        1915  28%     - skkdic-collect-okuri-nasi
          81   1%        skkdic-get-candidate-list
           3   0%        lookup-nested-alist
          47   0%       skkdic-convert-okuri-ari
          36   0%       skkdic-convert-prefix
          34   0%     - save-buffer
          34   0%      - basic-save-buffer
          33   0%       - basic-save-buffer-1
          33   0%        - basic-save-buffer-2
          26   0%         - write-region
          26   0%          - select-safe-coding-system
           1   0%             find-auto-coding
           1   0%           - find-coding-systems-region
           1   0%            - sort-coding-systems
           1   0%               #<compiled -0x6cdb28b2d51a5ea>
           1   0%       - vc-before-save
           1   0%        - vc-backend
           1   0%         - vc-registered
           1   0%          - mapc
           1   0%           - #<compiled 0x1c10f50111ddf347>
           1   0%            - vc-call-backend
           1   0%             - vc-svn-registered
           1   0%              - let
           1   0%               - if
           1   0%                - vc-find-root
           1   0%                   locate-dominating-file
          31   0%     - set-visited-file-name
          26   0%      - set-auto-mode
          25   0%       - set-auto-mode--apply-alist
          25   0%        - set-auto-mode-0
          25   0%         - emacs-lisp-mode
          25   0%          - run-mode-hooks
          19   0%           - hack-local-variables
          19   0%            - hack-local-variables-apply
          19   0%             - hack-one-local-variable
          19   0%              - bug-reference-prog-mode
          18   0%               - jit-lock-register
          18   0%                  jit-lock-mode
           1   0%                 defalias
           6   0%           - run-hooks
           6   0%            - global-font-lock-mode-enable-in-buffers
           6   0%             - turn-on-font-lock-if-desired
           6   0%              - turn-on-font-lock
           6   0%               - font-lock-mode
           6   0%                - font-lock-default-function
           6   0%                 - font-lock-mode-internal
           6   0%                  - font-lock-turn-on-thing-lock
           6   0%                   - jit-lock-register
           6   0%                      jit-lock-mode
           1   0%         hack-local-variables
           5   0%      - hack-local-variables
           5   0%       - hack-local-variables-apply
           4   0%        - hack-one-local-variable
           4   0%         - bug-reference-prog-mode
           4   0%          - jit-lock-register
           4   0%             jit-lock-mode
          10   0%       skkdic-convert-postfix
          65   0%  - startup--honor-delayed-native-compilations
          61   0%   - startup--require-comp-safely
          44   0%    - byte-code
          42   0%     - require
          30   0%      - do-after-load-evaluation
          29   0%       - elisp--font-lock-flush-elisp-buffers
          29   0%          font-lock-flush
           6   0%      - byte-code
           6   0%       - require
           5   0%        - do-after-load-evaluation
           4   0%         - elisp--font-lock-flush-elisp-buffers
           4   0%            font-lock-flush
           1   0%        defalias
           6   0%    - do-after-load-evaluation
           6   0%     - elisp--font-lock-flush-elisp-buffers
           6   0%        font-lock-flush
           1   0%    - native--compile-async
           1   0%     - comp-run-async-workers
           1   0%      - write-region
           1   0%       - select-safe-coding-system
           1   0%          find-auto-coding
           1   0%    #<compiled -0x114e6bbdb5ca73f0>
        1364  20% - ...
        1364  20%    Automatic GC
           8   0% + redisplay_internal (C function)
           6   0% + command-execute

Of that profile I mostly see:

        2770  40%     - skkdic-convert-okuri-nasi
        1915  28%     - skkdic-collect-okuri-nasi
        1364  20%    Automatic GC

and AFAICT there's not much that can be optimized in
`skkdic-collect-okuri-nasi` (assuming my profile is mostly accurate)
since it spends most of its time just converting the source file into
a usable Lisp data structure.  Also, I suspect that most of the GC time
comes from the "convert" part (based on the mem profile which shows it
allocates about 70% vs 30%), so if we factor GC time into it, it's
probably more like

        3770       - skkdic-convert-okuri-nasi
        2279       - skkdic-collect-okuri-nasi

> My guess is that if somebody took a look ja-dic-cnv.el, this algorithm
> could be made substantially more efficient by using other data
> structures than an extremely long nested alist.

I believe those (nested) alists shouldn't be that long (IIUC it's
a trie-like data-structure, a bit like keymaps, so even with many
entries in total, the total depth of the tree should be fairly short and
the length of each list (i.e. the out degree of each node) shouldn't be
very large either).


        Stefan