[RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Alex Gramiak]

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

Here are a few procedures that should make using vectors in Elisp a bit
nicer. They are in C since all the Elisp versions I've tried were too
slow for such simple procedures.

I started with just vector-memq, but the other ones should have some
application as well. I took vector-index and vector-partition from SRFI
133 [1].

[1] https://srfi.schemers.org/srfi-133/srfi-133.html


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

From 353dd712d8dc94b17d5382f571c81cb9693887d9 Mon Sep 17 00:00:00 2001
From: Alexander Gramiak <agrambot@gmail.com>
Date: Fri, 19 Apr 2019 13:58:39 -0600
Subject: [PATCH] Add some new vector procedures

* src/eval.c (apply_helper): New helper procedure.
(apply): Move most of body to apply_helper.
(vector-apply): New procedure.

* src/fns.c (vector-memq, vector-member, vector-assq, vector-assoc)
(vector-index, vector-partition, vector-to-string): New procedures.
---
 src/eval.c |  93 +++++++++++++++++++++++++++-----------
 src/fns.c  | 130 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 198 insertions(+), 25 deletions(-)

diff --git a/src/eval.c b/src/eval.c
index c2e996a947..bf8de51bf8 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -2375,32 +2375,16 @@ eval_sub (Lisp_Object form)
 
   return val;
 }
+
 \f
-DEFUN ("apply", Fapply, Sapply, 1, MANY, 0,
-       doc: /* Call FUNCTION with our remaining args, using our last arg as list of args.
-Then return the value FUNCTION returns.
-Thus, (apply \\='+ 1 2 \\='(3 4)) returns 10.
-usage: (apply FUNCTION &rest ARGUMENTS)  */)
-  (ptrdiff_t nargs, Lisp_Object *args)
+static Lisp_Object
+apply_helper (ptrdiff_t nargs, ptrdiff_t numargs, Lisp_Object fun,
+              Lisp_Object spread_arg, Lisp_Object *args)
 {
-  ptrdiff_t i, funcall_nargs;
+  ptrdiff_t funcall_nargs;
   Lisp_Object *funcall_args = NULL;
-  Lisp_Object spread_arg = args[nargs - 1];
-  Lisp_Object fun = args[0];
   USE_SAFE_ALLOCA;
 
-  ptrdiff_t numargs = list_length (spread_arg);
-
-  if (numargs == 0)
-    return Ffuncall (nargs - 1, args);
-  else if (numargs == 1)
-    {
-      args [nargs - 1] = XCAR (spread_arg);
-      return Ffuncall (nargs, args);
-    }
-
-  numargs += nargs - 2;
-
   /* Optimize for no indirection.  */
   if (SYMBOLP (fun) && !NILP (fun)
       && (fun = XSYMBOL (fun)->u.s.function, SYMBOLP (fun)))
@@ -2432,11 +2416,20 @@ usage: (apply FUNCTION &rest ARGUMENTS)  */)
   memcpy (funcall_args, args, nargs * word_size);
   /* Spread the last arg we got.  Its first element goes in
      the slot that it used to occupy, hence this value of I.  */
-  i = nargs - 1;
-  while (!NILP (spread_arg))
+  if (CONSP (spread_arg))
+    {
+      ptrdiff_t i = nargs - 1;
+      while (!NILP (spread_arg))
+        {
+          funcall_args [i++] = XCAR (spread_arg);
+          spread_arg = XCDR (spread_arg);
+        }
+    }
+  else
     {
-      funcall_args [i++] = XCAR (spread_arg);
-      spread_arg = XCDR (spread_arg);
+      memcpy (funcall_args + nargs - 1,
+              XVECTOR (spread_arg)->contents,
+              ASIZE (spread_arg) * word_size);
     }
 
   Lisp_Object retval = Ffuncall (funcall_nargs, funcall_args);
@@ -2444,6 +2437,55 @@ usage: (apply FUNCTION &rest ARGUMENTS)  */)
   SAFE_FREE ();
   return retval;
 }
+
+DEFUN ("apply", Fapply, Sapply, 1, MANY, 0,
+       doc: /* Call FUNCTION with our remaining args, using our last arg as list of args.
+Then return the value FUNCTION returns.
+Thus, (apply #\\='+ 1 2 \\='(3 4)) returns 10.
+usage: (apply FUNCTION &rest ARGUMENTS)  */)
+  (ptrdiff_t nargs, Lisp_Object *args)
+{
+  Lisp_Object spread_arg = args[nargs - 1];
+  Lisp_Object fun = args[0];
+
+  ptrdiff_t numargs = list_length (spread_arg);
+
+  if (numargs == 0)
+    return Ffuncall (nargs - 1, args);
+  else if (numargs == 1)
+    {
+      args [nargs - 1] = XCAR (spread_arg);
+      return Ffuncall (nargs, args);
+    }
+
+  return apply_helper (nargs, numargs + nargs - 2, fun, spread_arg, args);
+}
+
+DEFUN ("vector-apply", Fvector_apply, Svector_apply, 1, MANY, 0,
+       doc: /* Call FUNCTION with our remaining args, using our last arg as a vector of args.
+Then return the value FUNCTION returns.
+Thus, (vector-apply #\\='+ 1 2 [3 4]) returns 10.
+usage: (vector-apply FUNCTION &rest ARGUMENTS)  */)
+  (ptrdiff_t nargs, Lisp_Object *args)
+{
+  Lisp_Object spread_arg = args[nargs - 1];
+  Lisp_Object fun = args[0];
+
+  CHECK_VECTOR (spread_arg);
+
+  ptrdiff_t numargs = ASIZE (spread_arg);
+
+  if (!numargs)
+    return Ffuncall (nargs - 1, args);
+  else if (numargs == 1)
+    {
+      args [nargs - 1] = AREF (spread_arg, 0);
+      return Ffuncall (nargs, args);
+    }
+
+   return apply_helper (nargs, numargs + nargs - 2, fun, spread_arg, args);
+}
+
 \f
 /* Run hook variables in various ways.  */
 
@@ -4236,6 +4278,7 @@ alist of active lexical bindings.  */);
   defsubr (&Sautoload_do_load);
   defsubr (&Seval);
   defsubr (&Sapply);
+  defsubr (&Svector_apply);
   defsubr (&Sfuncall);
   defsubr (&Sfunc_arity);
   defsubr (&Srun_hooks);
diff --git a/src/fns.c b/src/fns.c
index c3202495da..de37240aaa 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2134,6 +2134,129 @@ merge (Lisp_Object org_l1, Lisp_Object org_l2, Lisp_Object pred)
 }
 
 \f
+DEFUN ("vector-memq", Fvector_memq, Svector_memq, 2, 2, 0,
+       doc: /* Return index of ELT in VECTOR.  Comparison done with `eq'.
+The value is nil if ELT is not found in VECTOR.  */)
+  (Lisp_Object elt, Lisp_Object vector)
+{
+  CHECK_VECTOR (vector);
+  const ptrdiff_t len = ASIZE (vector);
+
+  for (ptrdiff_t i = 0; i < len; ++i)
+    if (EQ (elt, AREF (vector, i)))
+      return make_fixnum (i);
+
+  return Qnil;
+}
+
+DEFUN ("vector-member", Fvector_member, Svector_member, 2, 2, 0,
+       doc: /* Return index of ELT in VECTOR.  Comparison done with `equal'.
+The value is nil if ELT is not found in VECTOR.  */)
+  (Lisp_Object elt, Lisp_Object vector)
+{
+  CHECK_VECTOR (vector);
+  const ptrdiff_t len = ASIZE (vector);
+
+  for (ptrdiff_t i = 0; i < len; ++i)
+    if (Fequal (elt, AREF (vector, i)))
+      return make_fixnum (i);
+
+  return Qnil;
+}
+
+DEFUN ("vector-assq", Fvector_assq, Svector_assq, 2, 2, 0,
+       doc: /* Return the index of KEY in the association vector VECTOR.
+Elements of VECTOR that are not vectors are ignored.  */)
+  (Lisp_Object key, Lisp_Object vector)
+{
+  CHECK_VECTOR (vector);
+  const ptrdiff_t len = ASIZE (vector);
+
+  for (ptrdiff_t i = 0; i < len; ++i)
+    if (VECTORP (AREF (vector, i))
+        && EQ (key, AREF (AREF (vector, i), 0)))
+      return make_fixnum (i);
+
+  return Qnil;
+}
+
+DEFUN ("vector-assoc", Fvector_assoc, Svector_assoc, 2, 2, 0,
+       doc: /* Return the index of KEY in the association vector VECTOR.
+Elements of VECTOR that are not vectors are ignored.  */)
+  (Lisp_Object key, Lisp_Object vector)
+{
+  CHECK_VECTOR (vector);
+  const ptrdiff_t len = ASIZE (vector);
+
+  for (ptrdiff_t i = 0; i < len; ++i)
+    if (VECTORP (AREF (vector, i))
+        && Fequal (key, AREF (AREF (vector, i), 0)))
+      return make_fixnum (i);
+
+  return Qnil;
+}
+
+DEFUN ("vector-index", Fvector_index, Svector_index, 2, 2, 0,
+       doc: /* Return the index of the first KEY satisfying (PRED KEY) in the vector VECTOR.  */)
+  (Lisp_Object pred, Lisp_Object vector)
+{
+  CHECK_VECTOR (vector);
+  const ptrdiff_t len = ASIZE (vector);
+
+  for (ptrdiff_t i = 0; i < len; ++i)
+    if (!NILP (call1 (pred, AREF (vector, i))))
+      return make_fixnum (i);
+
+  return Qnil;
+}
+
+DEFUN ("vector-partition", Fvector_partition, Svector_partition, 2, 2, 0,
+       doc: /* Return a vector that partitions the elements of VECTOR by PRED.
+
+The vector contains two vectors that contain elements that satisfy and
+do not satisfy PRED respectively.
+For example: (vector-partition #'fixnump [1 2 3.0 4 5.0])
+  => [[1 2 4] [3.0 5.0]] */)
+  (Lisp_Object pred, Lisp_Object vector)
+{
+  CHECK_VECTOR (vector);
+  const ptrdiff_t len = ASIZE (vector);
+  Lisp_Object *satisfying = NULL;
+  Lisp_Object *failing    = NULL;
+  ptrdiff_t s_count      = 0;
+  ptrdiff_t f_count      = 0;
+  USE_SAFE_ALLOCA;
+
+  SAFE_ALLOCA_LISP (satisfying, len);
+  SAFE_ALLOCA_LISP (failing,    len);
+
+  for (ptrdiff_t i = 0; i < len; ++i)
+    {
+      register Lisp_Object tem = AREF (vector, i);
+      if (!NILP (call1 (pred, tem)))
+        satisfying[s_count++] = tem;
+      else
+        failing[f_count++] = tem;
+    }
+
+  Lisp_Object partitions[2] =
+    { Fvector (s_count, satisfying),
+      Fvector (f_count, failing) };
+  Lisp_Object result = Fvector (2, partitions);
+  SAFE_FREE ();
+  return result;
+}
+
+DEFUN ("vector-to-string", Fvector_to_string, Svector_to_string, 1, 1, 0,
+       doc: /* Return a string containing the elements of VECTOR.  */)
+  (Lisp_Object vector)
+{
+  CHECK_VECTOR (vector);
+
+  return Fstring (ASIZE (vector), XVECTOR (vector)->contents);
+}
+
+\f
 /* This does not check for quits.  That is safe since it must terminate.  */
 
 DEFUN ("plist-get", Fplist_get, Splist_get, 2, 2, 0,
@@ -5417,6 +5540,13 @@ this variable.  */);
   defsubr (&Sdelete);
   defsubr (&Snreverse);
   defsubr (&Sreverse);
+  defsubr (&Svector_memq);
+  defsubr (&Svector_member);
+  defsubr (&Svector_assq);
+  defsubr (&Svector_assoc);
+  defsubr (&Svector_index);
+  defsubr (&Svector_partition);
+  defsubr (&Svector_to_string);
   defsubr (&Ssort);
   defsubr (&Splist_get);
   defsubr (&Sget);
-- 
2.21.0

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Eli Zaretskii]

> From: Alex Gramiak <agrambot@gmail.com>
> Date: Fri, 19 Apr 2019 14:49:39 -0600
> 
> Here are a few procedures that should make using vectors in Elisp a bit
> nicer. They are in C since all the Elisp versions I've tried were too
> slow for such simple procedures.

Doesn't seq.el already provide this functionality?

As for speed, did you have any application where the speed of the Lisp
implementation was inadequate?

Thanks.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Alex Gramiak]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Alex Gramiak <agrambot@gmail.com>
>> Date: Fri, 19 Apr 2019 14:49:39 -0600
>> 
>> Here are a few procedures that should make using vectors in Elisp a bit
>> nicer. They are in C since all the Elisp versions I've tried were too
>> slow for such simple procedures.
>
> Doesn't seq.el already provide this functionality?

Some, but not all. I don't see a vector-partition equivalent
(seq-partition is different), or a vector-index equivalent
(seq-find/cl-find return the element instead of the index, and is ~10x
slower).

I don't see any replacement for vector-apply, but I admit that the worth
of that one might not be worth the change at this point.

Though I just remembered that (concat vec) does the same as
vector-to-string; if vector-to-string is added, then I suppose it should
be a Lisp wrapper around concat just like string-to-vector is around
vconcat.

> As for speed, did you have any application where the speed of the Lisp
> implementation was inadequate?

For vector-memq, the Lisp implementations almost disallow it from being
used over memq/lists. The equivalent in seq.el, seq-position, is ~100x
slower for smaller vectors and ~200x for larger (500 elements) vectors.
A cl-loop implementation is just slightly better than seq-position.

The main two I care about here are vector-memq/vector-member. The other
ones were just ones I thought up while I was at it.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Eli Zaretskii]

> From: Alex Gramiak <agrambot@gmail.com>
> Cc: emacs-devel@gnu.org
> Date: Sat, 20 Apr 2019 10:50:28 -0600
> 
> > Doesn't seq.el already provide this functionality?
> 
> Some, but not all. I don't see a vector-partition equivalent
> (seq-partition is different), or a vector-index equivalent
> (seq-find/cl-find return the element instead of the index, and is ~10x
> slower).

Isn't seq-position the equivalent of vector-index?

Anyway, if some algorithms are missing from seq.el, maybe we should
just add them there instead of starting an entirely new family of
primitives?

> > As for speed, did you have any application where the speed of the Lisp
> > implementation was inadequate?
> 
> For vector-memq, the Lisp implementations almost disallow it from being
> used over memq/lists. The equivalent in seq.el, seq-position, is ~100x
> slower for smaller vectors and ~200x for larger (500 elements) vectors.

The factors don't really answer my question.  The question was whether
some real-life application that uses seq.el is so slow that moving
them to C is necessary.  IOW, the question was about absolute times,
not relative times.  If you can describe such use cases, I'd like to
discuss them with the participation of seq.el's maintainer first.

And if we eventually decide that some special cases do require to be
coded in C, I think we'd prefer calling them from seq.el, not
directly.  Otherwise, why have seq.el at all?

> The main two I care about here are vector-memq/vector-member.

Please tell why in more detail.

Thanks.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Alex Gramiak]

Eli Zaretskii <eliz@gnu.org> writes:

> Isn't seq-position the equivalent of vector-index?

It's quite similar (I forgot that it took an optional predicate), though
seq-position takes a 2-arg procedure that's supposed to check for
equality, while vector-index takes a 1-arg procedure. One can implement
one in terms of the other.

> Anyway, if some algorithms are missing from seq.el, maybe we should
> just add them there instead of starting an entirely new family of
> primitives?

Ideally. Though in the case of vector-partition the size of the 2
partition vectors is not known in advance, so a Lisp implementation
would have to create two extra Lisp vectors as opposed to using
SAFE_ALLOCA. That is, unless Elisp grows a growable/resizeable vector
type (which is something I was thinking about -- would that be denied?).

>> > As for speed, did you have any application where the speed of the Lisp
>> > implementation was inadequate?
>> 
>> For vector-memq, the Lisp implementations almost disallow it from being
>> used over memq/lists. The equivalent in seq.el, seq-position, is ~100x
>> slower for smaller vectors and ~200x for larger (500 elements) vectors.
>
> The factors don't really answer my question.  The question was whether
> some real-life application that uses seq.el is so slow that moving
> them to C is necessary.  IOW, the question was about absolute times,
> not relative times.  If you can describe such use cases, I'd like to
> discuss them with the participation of seq.el's maintainer first.

Currently the only (M)ELPA package I use that depends on seq is
Flycheck, that doesn't seem to use seq with vectors.

>> The main two I care about here are vector-memq/vector-member.
>
> Please tell why in more detail.

Well, it's a stupid itch, but sometimes I see the (memq elt <list
of constants>) and think that using a vector would be faster/better,
mainly since memq has to check for cycles. More generally, there's
currently no way to check existence in a vector nearly as fast as one
can check existence in a list, which is unusual in programming
languages. This unfairly discourages usage of vectors in appropriate
places.

I don't believe that the vector-memq/member procedures would pose a
maintenance burden like some of the others (vector-apply in particular)
would.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Eli Zaretskii]

> From: Alex Gramiak <agrambot@gmail.com>
> Cc: emacs-devel@gnu.org
> Date: Sat, 20 Apr 2019 12:18:01 -0600
> 
> Ideally. Though in the case of vector-partition the size of the 2
> partition vectors is not known in advance, so a Lisp implementation
> would have to create two extra Lisp vectors as opposed to using
> SAFE_ALLOCA. That is, unless Elisp grows a growable/resizeable vector
> type (which is something I was thinking about -- would that be denied?).

What would be the advantage of that vs lists?

> >> > As for speed, did you have any application where the speed of the Lisp
> Well, it's a stupid itch, but sometimes I see the (memq elt <list
> of constants>) and think that using a vector would be faster/better,
> mainly since memq has to check for cycles.

You mean 'member', right?  I don't think 'memq' checks for cycles.

> More generally, there's currently no way to check existence in a
> vector nearly as fast as one can check existence in a list, which is
> unusual in programming languages.

Vectors are used quite rarely in Emacs Lisp, IME.  I think we should
all keep in mind that Emacs Lisp is not a general-purpose language, it
is a language for implementing and extending Emacs.

> I don't believe that the vector-memq/member procedures would pose a
> maintenance burden like some of the others (vector-apply in particular)
> would.

Every additional primitive means a burden.  More importantly, we
should IMO be consistent in how we design and implement families of
functions, which is why I still think we should extend seq.el
(possibly some of that with internal C primitives, if needed), instead
of starting a new family.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Alan Mackenzie]

Hello, Eli.

On Sat, Apr 20, 2019 at 22:11:10 +0300, Eli Zaretskii wrote:

> I think we should all keep in mind that Emacs Lisp is not a
> general-purpose language, it is a language for implementing and
> extending Emacs.

Well said, that man!

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Óscar Fuentes]

Alan Mackenzie <acm@muc.de> writes:

>> I think we should all keep in mind that Emacs Lisp is not a
>> general-purpose language, it is a language for implementing and
>> extending Emacs.
>
> Well said, that man!

OTOH, we try to use Elisp instead of C as much as possible.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Paul Eggert]

>> sometimes I see the (memq elt <list
>> of constants>) and think that using a vector would be faster/better,
>> mainly since memq has to check for cycles.

> You mean 'member', right?  I don't think 'memq' checks for cycles.
No, (memq ELT LIST) checks for cycles in LIST, just as (member ELT LIST) does.

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

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

[Alex Gramiak]

[-- 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);

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Alex Gramiak]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Alex Gramiak <agrambot@gmail.com>
>> Cc: emacs-devel@gnu.org
>> Date: Sat, 20 Apr 2019 12:18:01 -0600
>> 
>> Ideally. Though in the case of vector-partition the size of the 2
>> partition vectors is not known in advance, so a Lisp implementation
>> would have to create two extra Lisp vectors as opposed to using
>> SAFE_ALLOCA. That is, unless Elisp grows a growable/resizeable vector
>> type (which is something I was thinking about -- would that be denied?).
>
> What would be the advantage of that vs lists?

Better space efficiency, less pressure (hopefully) on the GC, and faster
random access. I believe growable vectors would make sense for linear
lists that don't need the insertion/deletion properties of linked lists.

As for vector-partition, it's more so a means of keeping the input and
partition types the same. Not a huge deal.

> Vectors are used quite rarely in Emacs Lisp, IME.

Not enough suitable vector procedures doesn't help, though. Emacs Lisp
is certainly not a general-purpose language, but that doesn't mean that
it has to be missing particular language features/types that improve
efficiency as long as it doesn't add a lot of complexity.

> Every additional primitive means a burden.  More importantly, we
> should IMO be consistent in how we design and implement families of
> functions, which is why I still think we should extend seq.el
> (possibly some of that with internal C primitives, if needed), instead
> of starting a new family.

I'm not sure what you mean here by internal C primitives if it's not
similar to vector-memq/member. Do you just mean expose a single
`sequence-memq' and keep the new type-specific implementations internal?

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Eli Zaretskii]

> From: Alex Gramiak <agrambot@gmail.com>
> Cc: emacs-devel@gnu.org
> Date: Sat, 20 Apr 2019 19:52:36 -0600
> 
> > Vectors are used quite rarely in Emacs Lisp, IME.
> 
> Not enough suitable vector procedures doesn't help, though. Emacs Lisp
> is certainly not a general-purpose language, but that doesn't mean that
> it has to be missing particular language features/types that improve
> efficiency as long as it doesn't add a lot of complexity.

I actually think it means precisely that: we don't need to expand the
language just because some feature is missing, we should do that only
if said feature is important for implementing Emacs features.  The
dynamic nature of Emacs on the one hand, and the efficient
implementation of lists OTOH, are the main reasons why vectors are
rarely used in ELisp programs.  I think most of the uses are for
objects whose structure and size are known in advance, and for objects
that are read-only from the Lisp side.  When we needed a vector-like
object that could change its structure dynamically, we invented
char-tables.

> > Every additional primitive means a burden.  More importantly, we
> > should IMO be consistent in how we design and implement families of
> > functions, which is why I still think we should extend seq.el
> > (possibly some of that with internal C primitives, if needed), instead
> > of starting a new family.
> 
> I'm not sure what you mean here by internal C primitives if it's not
> similar to vector-memq/member. Do you just mean expose a single
> `sequence-memq' and keep the new type-specific implementations internal?

When a C implementation is justified, yes.

Anyway, I think I spoke enough about this.  I will now let Nicolas and
others to chime in.

Thanks.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Stefan Monnier]

> I don't see any replacement for vector-apply, but I admit that the worth
> of that one might not be worth the change at this point.

I'm not sure I like vector-apply, but I am interested in doing something
along these lines for cl-generic: the use of wrappers of the form

    (lambda (x &rest args) ... (apply f x args))

proves to be too costly in some cases (e.g. cl-print).  But the main issue
seems to be the allocation of a new list for `args`, so `vector-apply`
doesn't really help here.

> For vector-memq, the Lisp implementations almost disallow it from being
> used over memq/lists.

I your `vector-memq` significantly faster than `memq`?
My impression is that for small enough "sets", even if a bit faster,
`vector-memq` wouldn't bring much benefit, and for larger sets if
performance is an issue you'd likely prefer using a completely different
structure such as a hash-table.


        Stefan

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Alex Gramiak]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I don't see any replacement for vector-apply, but I admit that the worth
>> of that one might not be worth the change at this point.
>
> I'm not sure I like vector-apply, but I am interested in doing something
> along these lines for cl-generic: the use of wrappers of the form
>
>     (lambda (x &rest args) ... (apply f x args))
>
> proves to be too costly in some cases (e.g. cl-print).  But the main issue
> seems to be the allocation of a new list for `args`, so `vector-apply`
> doesn't really help here.

I'm not sure how one would avoid the allocation lambda does without a
new special form (or byte compiler optimization that checks that you
only give args to apply), but perhaps I'm overlooking something.

There could also be a &rest-vector, but that's likely going too far.

>> For vector-memq, the Lisp implementations almost disallow it from being
>> used over memq/lists.
>
> I your `vector-memq` significantly faster than `memq`?

Not hugely; about 15-25% when vector-memq is made into a 2-byte bytecode
(as in my other thread) for a 5 element collection, and about 50% on a
50-element collection.

> My impression is that for small enough "sets", even if a bit faster,
> `vector-memq` wouldn't bring much benefit, and for larger sets if
> performance is an issue you'd likely prefer using a completely different
> structure such as a hash-table.

Right, I'm not under the impression that it would be a monumental
difference (that's why I called it a stupid itch :). Still, I think
there's a middle ground between lists and hash tables that vectors would
fit into nicely enough.

Re: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})

[Stefan Monnier]

> I'm not sure how one would avoid the allocation lambda does without a
> new special form (or byte compiler optimization that checks that you
> only give args to apply), but perhaps I'm overlooking something.
> There could also be a &rest-vector, but that's likely going too far.

I don't have any good ideas to solve that either, but I figured it was
worth mentioning.

> Right, I'm not under the impression that it would be a monumental
> difference (that's why I called it a stupid itch :). Still, I think
> there's a middle ground between lists and hash tables that vectors would
> fit into nicely enough.

The problem is usually in the construction phase, where it's a lot
easier to construct the list, whereas for vectors you'll likely want to
first construct a list and later convert it to a vector.

Growable vectors would be nice, but they're a different beast (need
a different low-level representation).


        Stefan