Subject: Re: bug#67536: 29.1; Calc mode's math-read-preprocess-string conses unnecessarily

From: Raffael Stocker <[email-masked]>
Date: Tue, 05 Dec 2023 19:14:36 +0100

Mattias Engdegård <[email-masked]> writes:

> Here's a new patch.
> A lot less pretty this time.
>
> In any case, make sure to include unit tests in your final patch.

Ok, here it comes.

I have constructed two org tables for the test (see test-input.org) that
are reasonably long and contain a few not too unreasonable formulas.
The nature of the formulas is not too important for the tests, I just
took them from my original "offending" table.

I also added unit tests for the function, as requested.

One of the tables has no special characters, so
‘math-read-preprocess-string’ just has to walk through without doing any
real work (arguably the most common case).  The other table is full of
replaceable stuff.  I used these two tables to compare the original with
the new version of ‘math-read-preprocess-string’.  The results are in
test-results.org.

As before, I compared ‘gcs-done’ and ‘gc-elapsed’ (with standard
settings for ‘gc-cons-threshold’ and ‘gc-cons-percentage’) with both
versions and tables.  I also instrumented ‘org-table-recalculate’ and
‘math-read-preprocess-string’ using elp.  Then I set ‘gc-cons-threshold’
to a large value and ran the same tests again.  For the latter test, I
only report ‘elp-results’ (as no GC was triggered).

I recalculated every table three times per reported elp result, as it
takes three evaluations for the calculation to converge.

Some interesting results are:

- time spent in GC reduces from 2.11 s to  0.78 s for the second table
  (with replacements)
- elp report of average time decreases from 4.6316224e-3 s to
  3.0294569e-4 s for the second table
- with GC prevented, elp reports avg. time 3.4286452e-4 s vs. 4.9444e-5 s
- elp report of elapsed time for ‘org-table-recalculate’ for three evaluations
  (what the user sees) decreases from 8.36 s to 4.11 s (with standard GC
  settings again)

This is a real win especially for large tables.  Needless to say, I am
very excited about this optimization.

(Just for completeness, I quickly compared my version to Mattias'
version, the latter is about a factor of two faster according to elp.)

Regards,
Raffael

>From c5bd32ef197d2236928d2d6764bfcab5cef0ea6d Mon Sep 17 00:00:00 2001
From: Raffael Stocker <[email-masked]>
Date: Tue, 5 Dec 2023 20:06:36 +0100
Subject: [PATCH] * lisp/calc/calc-aent.el (math-read-preprocess-string):
 optimize (bug#67536)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This is an optimized version of ‘math-read-preprocess-string’ by
Mattias Engdegård <[email-masked]>, with unit tests.

This function is called by calc-eval, which in turn is called
repeatedly when re-calculating org-mode tables.  It was one of the
main bottlenecks there and this optimization addresses this by not
repeatedly allocating new strings while iterating through the
replacement list, but instead working through the argument string only
once, using a "flattened" and cached regexp and only one call to
‘replace-regexp-in-string’.
---
 lisp/calc/calc-aent.el       | 43 +++++++++++++++++++++++++-----------
 test/lisp/calc/calc-tests.el | 27 ++++++++++++++++++++++
 2 files changed, 57 insertions(+), 13 deletions(-)

diff --git a/lisp/calc/calc-aent.el b/lisp/calc/calc-aent.el
index 66ede3295ae..131f31afff7 100644
--- a/lisp/calc/calc-aent.el
+++ b/lisp/calc/calc-aent.el
@@ -547,22 +547,39 @@ math-read-subscripts
   "₀₁₂₃₄₅₆₇₈₉₊₋₍₎" ; 0123456789+-()
   "A string consisting of the subscripts allowed by Calc.")
 
+(defvar math--read-preprocess-re-cache nil
+  "Cached regexp and tag: (REGEXP REPLACEMENTS SUPERSCRIPTS SUBSCRIPTS)")
+
 ;;;###autoload
 (defun math-read-preprocess-string (str)
   "Replace some substrings of STR by Calc equivalents."
-  (setq str
-        (replace-regexp-in-string (concat "[" math-read-superscripts "]+")
-                                  "^(\\&)" str))
-  (setq str
-        (replace-regexp-in-string (concat "[" math-read-subscripts "]+")
-                                  "_(\\&)" str))
-  (let ((rep-list math-read-replacement-list))
-    (while rep-list
-      (setq str
-            (replace-regexp-in-string (nth 0 (car rep-list))
-                                      (nth 1 (car rep-list)) str))
-      (setq rep-list (cdr rep-list))))
-  str)
+  (unless (and (eq (nth 1 math--read-preprocess-re-cache)
+                   math-read-replacement-list)
+               (eq (nth 2 math--read-preprocess-re-cache)
+                   math-read-superscripts)
+               (eq (nth 3 math--read-preprocess-re-cache)
+                   math-read-subscripts))
+    ;; Cache invalid, recompute.
+    (setq math--read-preprocess-re-cache
+          (list (rx-to-string
+                 `(or (group (+ (in ,math-read-superscripts)))
+                      (group (+ (in ,math-read-subscripts)))
+                      (group (or ,@(mapcar #'car math-read-replacement-list))))
+                 t)
+                math-read-replacement-list
+                math-read-superscripts
+                math-read-subscripts)))
+  (replace-regexp-in-string
+   (nth 0 math--read-preprocess-re-cache)
+   (lambda (s)
+     (let ((r (mapconcat (lambda (c)
+                           (cadr (assoc (char-to-string c)
+                                        math-read-replacement-list)))
+                         s)))
+       (cond ((match-beginning 1) (concat "^(" r ")"))
+             ((match-beginning 2) (concat "_(" r ")"))
+             (t r))))
+   str t))
 
 ;; The next few variables are local to math-read-exprs (and math-read-expr
 ;; in calc-ext.el), but are set in functions they call.
diff --git a/test/lisp/calc/calc-tests.el b/test/lisp/calc/calc-tests.el
index 5b11dd950ba..08b5f5575db 100644
--- a/test/lisp/calc/calc-tests.el
+++ b/test/lisp/calc/calc-tests.el
@@ -816,5 +816,32 @@ calc-nth-root
          (x (calc-tests--calc-to-number (math-pow 8 '(frac 1 6)))))
     (should (< (abs (- x (sqrt 2.0))) 1.0e-10))))
 
+(ert-deftest calc-math-read-preprocess-string ()
+  "Test replacement of allowed special Unicode symbols."
+  ;; ... doesn't change an empty string
+  (should (string= "" (math-read-preprocess-string "")))
+  ;; ... doesn't change a string without characters from
+  ;; ‘math-read-replacement-list’
+  (let ((str "don't replace here"))
+    (should (string= str (math-read-preprocess-string str))))
+  ;; ... replaces irrespective of position in input string
+  (should (string= "^(1)" (math-read-preprocess-string "¹")))
+  (should (string= "some^(1)" (math-read-preprocess-string "some¹")))
+  (should (string= "^(1)time" (math-read-preprocess-string "¹time")))
+  (should (string= "some^(1)else" (math-read-preprocess-string "some¹else")))
+  ;; ... replaces every element of ‘math-read-replacement-list’ correctly,
+  ;; in particular combining consecutive super-/subscripts into one
+  ;; exponent/subscript
+  (should (string= (concat "+/-*:-/*inf<=>=<=>=μ(1:4)(1:2)(3:4)(1:3)(2:3)"
+                           "(1:5)(2:5)(3:5)(4:5)(1:6)(5:6)"
+                           "(1:8)(3:8)(5:8)(7:8)1:^(0123456789+-()ni)"
+                           "_(0123456789+-())")
+                   (math-read-preprocess-string (mapconcat #'car
+                                                           math-read-replacement-list
+                                                           ""))))
+  ;; ... signals an error if the argument is not a string
+  (should-error (math-read-preprocess-string nil))
+  (should-error (math-read-preprocess-string 42)))
+
 (provide 'calc-tests)
 ;;; calc-tests.el ends here
-- 
2.43.0