Using SMALL_LIST_LEN_MAX for memq and list_length (was: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...}))

[Alex Gramiak <agrambot@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 412 bytes --]

Paul Eggert <eggert@cs.ucla.edu> writes:

> We could probably speed up the cycle checking somewhat, but that's a different
> topic.

On that topic, I recently tried using SMALL_LIST_LEN_MAX for memq and
list_length similarly to nth/elt. WDYT? For small lists it seems to be
faster, but for longer lists it seems to be slower (maybe that's due to
the branch predictor in my simple benchmark-run-compiled tests).


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: memq --]
[-- Type: text/x-patch, Size: 582 bytes --]

diff --git a/src/fns.c b/src/fns.c
index c3202495da..267bd2c40f 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1557,9 +1557,18 @@ The value is actually the tail of LIST whose car is ELT.  */)
   (Lisp_Object elt, Lisp_Object list)
 {
   Lisp_Object tail = list;
+  for (int i = 0; i < SMALL_LIST_LEN_MAX; ++i, tail = XCDR (tail))
+    {
+      if (!CONSP (tail))
+        goto end;
+      else if (EQ (XCAR (tail), elt))
+        return tail;
+    }
+
   FOR_EACH_TAIL (tail)
     if (EQ (XCAR (tail), elt))
       return tail;
+ end:
   CHECK_LIST_END (tail, list);
   return Qnil;
 }

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: list_length --]
[-- Type: text/x-patch, Size: 383 bytes --]

diff --git a/src/fns.c b/src/fns.c
index c3202495da..b7f25d4cba 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -97,6 +97,11 @@ ptrdiff_t
 list_length (Lisp_Object list)
 {
   intptr_t i = 0;
+  for ( ; i < SMALL_LIST_LEN_MAX && CONSP (list); ++i, list = XCDR (list))
+    ;
+  if (i < SMALL_LIST_LEN_MAX)
+    return i;
+
   FOR_EACH_TAIL (list)
     i++;
   CHECK_LIST_END (list, list);