[VM] [XEMACS PATCH] Be lazy about calling marker_position() in bytecode_arithcompare()

[Aidan Kehoe]

PATCH 21.5

This change improves performance for VM with large folder a little, though
it’s not a complete solution. In particular, when hitting q in a modified
folder with index files turned on and non-ASCII bytes in the buffer,
#'vm-sort-compare-physical-order is called about 5 N times for N messages,
giving 10 N calls to marker-position, which is expensive.

This shows up as char-byte conversion in XEmacs profiling, and my below
change improves this, such that the majority of the time in the described
context is now in #'write-file-internal, not char-byte conversion.

diff -r 4e69b24a2301 src/bytecode.c
--- a/src/bytecode.c    Mon Oct 28 16:03:53 2013 +0100
+++ b/src/bytecode.c    Sun Dec 01 11:16:59 2013 +0000
@@ -287,7 +287,7 @@
 bytecode_arithcompare (Lisp_Object obj1, Lisp_Object obj2)
 {
 #ifdef WITH_NUMBER_TYPES
-  switch (promote_args (&obj1, &obj2))
+  switch (promote_args_lazy (&obj1, &obj2))
     {
     case FIXNUM_T:
       {
@@ -306,6 +306,13 @@
     case BIGFLOAT_T:
       return bigfloat_cmp (XBIGFLOAT_DATA (obj1), XBIGFLOAT_DATA (obj2));
 #endif
+    case MARKER_T:
+      {
+       Bytebpos ival1 = byte_marker_position (obj1);
+       Bytebpos ival2 = byte_marker_position (obj2);
+       return ival1 < ival2 ? -1 : ival1 > ival2 ? 1 : 0;
+      }
+
     default: /* FLOAT_T */
       {
        double dval1 = XFLOAT_DATA (obj1), dval2 = XFLOAT_DATA (obj2);
@@ -320,7 +327,19 @@
 
     if      (FIXNUMP    (obj1)) ival1 = XFIXNUM  (obj1);
     else if (CHARP   (obj1)) ival1 = XCHAR (obj1);
-    else if (MARKERP (obj1)) ival1 = marker_position (obj1);
+    else if (MARKERP (obj1))
+      {
+       /* Handle markers specially, since #'marker-position can be O(N): */
+       if (MARKERP (obj2)
+           && (XMARKER (obj1)->buffer == XMARKER (obj2)->buffer))
+         {
+           Bytebpos ival1 = byte_marker_position (obj1);
+           Bytebpos ival2 = byte_marker_position (obj2);
+           return ival1 < ival2 ? -1 : ival1 > ival2 ? 1 : 0;
+         }
+
+       ival1 = marker_position (obj1);
+      }
     else goto arithcompare_float;
 
     if      (FIXNUMP    (obj2)) ival2 = XFIXNUM  (obj2);
diff -r 4e69b24a2301 src/data.c
--- a/src/data.c        Mon Oct 28 16:03:53 2013 +0100
+++ b/src/data.c        Sun Dec 01 11:16:59 2013 +0000
@@ -936,10 +936,10 @@
     {                                                          \
       obj1 = args[i - 1];                                      \
       obj2 = args[i];                                          \
-      switch (promote_args (&obj1, &obj2))                     \
+      switch (promote_args_lazy (&obj1, &obj2))                        \
        {                                                       \
        case FIXNUM_T:                                          \
-         if (!(XREALFIXNUM (obj1) c_op XREALFIXNUM (obj2)))            \
+         if (!(XREALFIXNUM (obj1) c_op XREALFIXNUM (obj2)))    \
            return Qnil;                                        \
          break;                                                \
        BIGNUM_CASE (op)                                        \
@@ -949,11 +949,20 @@
            return Qnil;                                        \
          break;                                                \
        BIGFLOAT_CASE (op)                                      \
+        case MARKER_T:                                          \
+          if (!(byte_marker_position (obj1) c_op                \
+                byte_marker_position (obj2)))                   \
+            return Qnil;                                        \
+          break;                                                \
        }                                                       \
     }                                                          \
   return Qt;                                                   \
 }
 #else /* !WITH_NUMBER_TYPES */
+/* We don't convert markers lazily here, although we could. It's more
+   important that we do this lazily in bytecode, which is the case; see
+   bytecode_arithcompare().
+   */
 #define ARITHCOMPARE_MANY(c_op,op)                             \
 {                                                              \
   int_or_double iod1, iod2, *p = &iod1, *q = &iod2;            \
diff -r 4e69b24a2301 src/number.h
--- a/src/number.h      Mon Oct 28 16:03:53 2013 +0100
+++ b/src/number.h      Sun Dec 01 11:16:59 2013 +0000
@@ -373,11 +373,40 @@
 
 EXFUN (Fcanonicalize_number, 1);
 
-enum number_type {FIXNUM_T, BIGNUM_T, RATIO_T, FLOAT_T, BIGFLOAT_T};
+#define NUMBER_TYPES(prefix) prefix##FIXNUM_T, prefix##BIGNUM_T, \
+    prefix##RATIO_T, prefix##FLOAT_T, prefix##BIGFLOAT_T
+
+enum number_type { NUMBER_TYPES() };
+enum lazy_number_type { NUMBER_TYPES(LAZY_), MARKER_T };
 
 extern enum number_type get_number_type (Lisp_Object);
 extern enum number_type promote_args (Lisp_Object *, Lisp_Object *);
 
+/* promote_args() *always* converts a marker argument to an integer.
+
+   Unfortunately, for a marker with byte position N, getting the (character)
+   marker position is O(N). Getting the character position isn't necessary
+   for bytecode_arithcompare() if two markers being compared are in the same
+   buffer, comparing the byte position is enough.
+
+   It is necessary for those operations implemented by bytecode_arithop(),
+   though, with the exception that Bmax and Bmin could be changed to call
+   marker-position once rather than twice. */
+DECLARE_INLINE_HEADER (
+enum lazy_number_type
+promote_args_lazy (Lisp_Object *obj1, Lisp_Object *obj2))
+{
+  if (MARKERP (*obj1) && MARKERP (*obj2) &&
+      XMARKER (*obj1)->buffer == XMARKER (*obj2)->buffer)
+    {
+      return MARKER_T;
+    }
+
+  return (enum lazy_number_type) promote_args (obj1, obj2);
+}
+
+#undef NUMBER_TYPES
+
 #ifdef WITH_NUMBER_TYPES
 DECLARE_INLINE_HEADER (
 int


-- 
‘Liston operated so fast that he once accidentally amputated an assistant’s
fingers along with a patient’s leg, […] The patient and the assistant both
died of sepsis, and a spectator reportedly died of shock, resulting in the
only known procedure with a 300% mortality.’ (Atul Gawande, NEJM, 2012)