Cache history functions

[jojojames]

Might be more performant to write a cache for the history compare functions.

Have something like this already but need some benchmark tests to show it's actually an improvement over the previous 'loop over all elements of the list to find a match' version.

(defun fussy-histlen< (c1 c2)
  "Return t if C1 occurred more recently than C2.

Check C1 and C2 in `minibuffer-history-variable'."
  (when (fussy--history-enabled-p)
    (let* ((hist (fussy--history-hash-table))
           (c1-pos (or (gethash c1 hist) 100000000))
           (c2-pos (or (gethash c2 hist) 100000000)))
      (if (= c1-pos c2-pos)
          (fussy-strlen< c1 c2)
        (< c1-pos c2-pos)))))

(defun fussy-histlen->strlen< (c1 c2)
  "Return t if C1 occurs more recently than C2 or is shorter than C2."
  (if (fussy--history-enabled-p)
      (let* ((hist (fussy--history-hash-table))
             (c1-pos (or (gethash c1 hist) 100000000))
             (c2-pos (or (gethash c2 hist) 100000000)))
        (if (= c1-pos c2-pos)
            (fussy-strlen< c1 c2)
          (< c1-pos c2-pos)))
    (fussy-strlen< c1 c2)))

(defvar fussy--history-hash-table nil)
(defun fussy--history-hash-table ()
  "Return hash table representing `minibuffer-history-variable'.

Key is history string and Value is the history position."
  (if fussy--history-hash-table
      fussy--history-hash-table
    (let ((hist (fussy--history-enabled-p)))
      (when hist
        (setf fussy--history-hash-table
              (make-hash-table :test 'equal
                               :size (length hist)))
        (cl-loop for index from 0
                 for item in hist
                 do (puthash item index fussy--history-hash-table))
        fussy--history-hash-table))))

(defun fussy--history-enabled-p ()
  "Return whether or not `minibuffer-history-value' is available.

Return value is the history variable's value."
  (and (not (eq minibuffer-history-variable t))
       (symbol-value minibuffer-history-variable)))

[minad]

You may want to take a look at the Vertico history hashing and the sort functions there https://github.com/minad/vertico/blob/e5935b5bbfc0d820c54ed1ad52e36e8c48248fd7/vertico.el#L182-L241.

[jojojames]

Thanks this looks awesome! @minad

I'll have to pull it out so I can apply in a manner similar to (< CANDIDATE_1 CANDIDATE_2).

[jojojames]

Implemented a simple version of the hash table.