counsel-shell-history slow (freezes emacs) fuzzy matching

[ChoppinBlockParty]

I have the following configuration on my shell-mode

(add-to-list 'display-buffer-alist
             `(,(regexp-quote "*shell") display-buffer-same-window))

(setq comint-prompt-read-only t
      ;;; Remember lots of previous commands in shell-mode
      comint-input-ring-size 1000000
      comint-input-ignoredups t)

(defun my-shell-mode-hook ()
  "A hook to setup shell-mode."
  (setq comint-output-filter-functions
    (remove'ansi-color-process-output comint-output-filter-functions))
  (add-hook 'comint-preoutput-filter-functions 'xterm-color-filter nil t)
  ;;; Removes face inherited from minibuffer
  (face-remap-set-base 'comint-highlight-prompt :inherit nil)
  ;;; You can highlight some text based on regexp (useful to see "OK" or warnings):
  ;; (add-hook 'shell-mode-hook (lambda () (highlight-regexp "\\[OK\\]" "hi-green-b")))
  ;;; Make URLs clickable
  (goto-address-mode)
  ;;; Make file paths clickable
  ;;; Every line representing a path to a file will be colorized and made clickable, so that you can jump to that file and that line, like in compilation-mode (specially useful when compiling a program or running tests):
  (compilation-shell-minor-mode)

  ;;; For some reasons must be in a hook
  (setq comint-input-ring-file-name "~/.config/zsh/.zhistory")
                                    ; Ignore timestamps in history file.  Assumes that zsh
                                    ; EXTENDED_HISTORY option is in use.
  (setq comint-input-ring-separator "\n: \\([0-9]+\\):\\([0-9]+\\);")

  (comint-read-input-ring nil)
  )
(add-hook 'shell-mode-hook 'my-shell-mode-hook)
(define-key shell-mode-map (kbd "C-r") 'counsel-shell-history)

I am using flx fuzzy matcher, it works very well even on sets like 100k. However, on shell history it can completely freeze emacs and burn all 100% CPU even with small input, like 3 chars, and a set of 29k history lines. What can it be? Can it be relevant to comint-input-ring-separator? How can I improve it? I have being using fzf in zsh for the same job for months, never even had a slightest noticable delay.

[abo-abo]

I don't have enough data to debug this. Please dump comint-input-ring to a file and attach it.

[ChoppinBlockParty]

It is possible just to duplicate your history file until you get 30k lines.

[abo-abo]

I think I'm able to reproduce something that's related to this issue.

It only happens when counsel-shell-history is configured to use ivy--regex-fuzzy.

Here are my params related to ~/.bash_history:

(length (ring-elements comint-input-ring))
;; => 1707

(apply 'max (mapcar 'length (ring-elements comint-input-ring)))
;; => 463

The second part is the most important: one of the commands on history is very long, which makes regex matching very slow.
This cannot be mitigated in a good way, I think. Take, for instance:

(setq s1
      (car (reverse
            (cl-sort (ring-elements comint-input-ring) #'<
                     :key #'length))))
(length s1)
;; => 463

(setq r1 (ivy--regex-fuzzy "sandboxls"))
;; => "\\(s\\).*?\\(a\\).*?\\(n\\).*?\\(d\\).*?\\(b\\).*?\\(o\\).*?\\(x\\).*?\\(l\\).*?\\(s\\)"

(benchmark-run 100
  (string-match-p r1 s1))
;; => (5.6352934569999995 0 0.0)

We can imagine how much backtracking has to happen with that regex on a string of length 463. It takes 0.05s just to match that single string once with that input. But we can have many more strings like that on our history, maybe hundreds or thousands.

One work around is to e.g. remove strings with length more than 100 from history:

(defun counsel--browse-history (elements)
  "Use Ivy to navigate through ELEMENTS."
  (setq ivy-completion-beg (point))
  (setq ivy-completion-end (point))
  (let ((cands
         (cl-remove-if (lambda (s) (> (length s) 100))
                       (delete-dups
                        (when (> (ring-size elements) 0)
                          (ring-elements elements))))))
    (ivy-read "Symbol name: " cands
              :action #'ivy-completion-in-region-action
              :caller 'counsel-shell-history)))

Let me know if this results in a speedup for you.