Binary Search Tree and Treap Functions bst-assq and treap-put

Binary Search Tree and Treap Functions bst-assq and treap-put

[Andy Sonnenburg]

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

I have implemented standard binary search tree lookup and hash-ordered
treap insertion using XLI comparison for lookup and XLI comparison and
FNV-1a hashing of the XLI result for insertion (using the XLI result as the
hash value would result in the worst case for balancing).  I have the
changes available in a local branch and am uncertain what to do with them
now.  I intend to use these functions to make lexically-scoped variable
lookup average case O(log(n)) instead of the current O(n).

Thanks,

Andy Sonnenburg

[-- Attachment #2: Type: text/html, Size: 606 bytes --]

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Stefan Monnier]

> now.  I intend to use these functions to make lexically-scoped variable
> lookup average case O(log(n)) instead of the current O(n).

AFAIK it's O(1) currently (for byte-compiled code only, but performance
of non-byte-compiled code should be of no importance).


        Stefan

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Andy Sonnenburg]

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

That's too bad (I mean, its good for performance, but unfortunate one of
the use cases doesn't exist).  However, the treap functions may still be of
general use.  Let me know if there is any interest.  They are documented
and tested.  They fill a gap between alists (persistent, linear lookup) and
hash tables (ephemeral, constant lookup) by being persistent while
providing average case logarithmic lookup.

On Dec 3, 2016 11:34 PM, "Stefan Monnier" <monnier@iro.umontreal.ca> wrote:

> now.  I intend to use these functions to make lexically-scoped variable
> lookup average case O(log(n)) instead of the current O(n).

AFAIK it's O(1) currently (for byte-compiled code only, but performance
of non-byte-compiled code should be of no importance).


        Stefan

[-- Attachment #2: Type: text/html, Size: 1186 bytes --]

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Stefan Monnier]

> That's too bad (I mean, its good for performance, but unfortunate one of
> the use cases doesn't exist).  However, the treap functions may still be of
> general use.  Let me know if there is any interest.  They are documented
> and tested.  They fill a gap between alists (persistent, linear lookup) and
> hash tables (ephemeral, constant lookup) by being persistent while
> providing average case logarithmic lookup.

Is it written in C or Elisp?  If it's Elisp, then we definitely would
welcome it into GNU ELPA (there is already an avl-tree implementation in
Emacs itself at lisp/emacs-lisp/avl-tree.el, but the more the merrier).
If it's written C, I'll let others decide whether we want to include it.


        Stefan

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Andy Sonnenburg]

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

It is written in C.  The only real reason C was used was performance
concerns, real or imagined.  I can post a diff of the changes - it isn't
that many lines.

On Dec 4, 2016 12:04 PM, "Stefan Monnier" <monnier@iro.umontreal.ca> wrote:

> > That's too bad (I mean, its good for performance, but unfortunate one of
> > the use cases doesn't exist).  However, the treap functions may still be
> of
> > general use.  Let me know if there is any interest.  They are documented
> > and tested.  They fill a gap between alists (persistent, linear lookup)
> and
> > hash tables (ephemeral, constant lookup) by being persistent while
> > providing average case logarithmic lookup.
>
> Is it written in C or Elisp?  If it's Elisp, then we definitely would
> welcome it into GNU ELPA (there is already an avl-tree implementation in
> Emacs itself at lisp/emacs-lisp/avl-tree.el, but the more the merrier).
> If it's written C, I'll let others decide whether we want to include it.
>
>
>         Stefan
>

[-- Attachment #2: Type: text/html, Size: 1369 bytes --]

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Andy Sonnenburg]

[-- Attachment #1.1: Type: text/plain, Size: 7602 bytes --]

I've attached the patch file and reproduced the diff below (I'm not sure
which form is preferred).

diff --git src/fns.c src/fns.c
index dfc7842..5f3cacc 100644
--- src/fns.c
+++ src/fns.c
@@ -21,6 +21,7 @@ along with GNU Emacs.  If not, see <
http://www.gnu.org/licenses/>.  */
 #include <config.h>

 #include <stdlib.h>
+#include <string.h>
 #include <unistd.h>
 #include <filevercmp.h>
 #include <intprops.h>
@@ -4751,7 +4752,181 @@ returns nil, then (funcall TEST x1 x2) also returns
nil.  */)
   return Fput (name, Qhash_table_test, list2 (test, hash));
 }

+#define EMACS_CAT_I(a, b) a ## b
+#define EMACS_CAT(a, b) EMACS_CAT_I(a, b)
+#define EMACS_LT(x, y) (XLI (x) < XLI (y))
+#define EMACS_BST_VECTOR_SIZE 4
+#define EMACS_FNV_PRIME 1099511628211
+#define EMACS_FNV_OFFSET_BASIS 14695981039346656037
+
+DEFUN ("bst-assq", Fbst_assq, Sbst_assq,
+       2, 2, 0,
+       doc: /* Return the value whose key is `eq' to KEY in BST.
+BST is either a vector whose first element is a key, second element is a
value,
+and third and fourth elements are left and right children; or a
non-vector.  The
+left child's key must be less than BST's key.  The right child's key must
be
+greater than BST's key.  Non-vector descendants of BST are ignored.  */)
+  (Lisp_Object new_key, Lisp_Object bst)
+{
+  const struct Lisp_Vector *vector;
+  const Lisp_Object *contents;
+  Lisp_Object key;
+  for (;;)
+    {
+      if (!VECTORP (bst))
+        {
+          return Qnil;
+        }
+      vector = XVECTOR (bst);
+      if (vector->header.size != EMACS_BST_VECTOR_SIZE)
+        {
+          args_out_of_range_3  (bst,
+                                make_number (0),
+                                make_number (EMACS_BST_VECTOR_SIZE));
+        }
+      contents = vector->contents;
+      key = contents[0];
+      if (EQ (key, new_key))
+        {
+          return contents[1];
+        }
+      bst = contents[2 + EMACS_LT (key, new_key)];
+    }
+}
+
+static uint64_t
+fnv_1a_hash (const void *first, const void *last)
+{
+  const unsigned char *i;
+  uint64_t hash;
+  hash = (uint64_t) EMACS_CAT(EMACS_FNV_OFFSET_BASIS, ull);
+  for (i = (const unsigned char *) first; i != last; ++i)
+    {
+      hash ^= *i;
+      hash *= (uint64_t) EMACS_CAT(EMACS_FNV_PRIME, ull);
+    }
+  return hash;
+}
+
+static Lisp_Object
+treap_singleton (Lisp_Object key, Lisp_Object value, Lisp_Object nil)
+{
+  Lisp_Object result, *contents;
+  result = make_uninit_vector (EMACS_BST_VECTOR_SIZE);
+  contents = XVECTOR (result)->contents;
+  contents[0] = key;
+  contents[1] = value;
+  contents[2] = nil;
+  contents[3] = nil;
+  return result;
+}
+
+static void
+rotate (Lisp_Object *a, Lisp_Object *b, Lisp_Object *c)
+{
+  Lisp_Object d;
+  d = *a;
+  *a = *b;
+  *b = *c;
+  *c = d;
+}
+
+static void
+tree_rotate (Lisp_Object *root, int rotation_index, int opposite_index)
+{
+  Lisp_Object *opposite, *rotation;
+  opposite = XVECTOR (*root)->contents + opposite_index;
+  rotation = XVECTOR (*opposite)->contents + rotation_index;
+  rotate (opposite, rotation, root);
+}
+
+static Lisp_Object
+make_lisp_vector (struct Lisp_Vector *vector)
+{
+  return XIL (TAG_PTR (Lisp_Vectorlike, vector));
+}
+
+static uint64_t
+treap_hash (Lisp_Object object)
+{
+  EMACS_INT i;
+  i = XLI (object);
+  return fnv_1a_hash (&i, &i + 1);
+}
+
+static Lisp_Object
+treap_put (Lisp_Object, uint64_t, Lisp_Object, Lisp_Object);
+
+static Lisp_Object
+treap_vector_put (Lisp_Object new_key,
+                  uint64_t new_hash,
+                  Lisp_Object new_value,
+                  struct Lisp_Vector *vector)
+{
+  const Lisp_Object *contents;
+  Lisp_Object key, value, new_treap, *new_contents;
+  int i, j;
+  if (vector->header.size != EMACS_BST_VECTOR_SIZE)
+    {
+      args_out_of_range_3 (make_lisp_vector (vector),
+                           make_number (0),
+                           make_number (EMACS_BST_VECTOR_SIZE));
+    }
+  contents = vector->contents;
+  key = contents[0];
+  value = contents[1];
+  new_treap = make_uninit_vector (EMACS_BST_VECTOR_SIZE);
+  new_contents = XVECTOR (new_treap)->contents;
+  new_contents[0] = key;
+  if (EQ (key, new_key))
+    {
+      new_contents[1] = new_value;
+      memcpy (new_contents + 2, contents + 2, 2 * sizeof *new_contents);
+      return new_treap;
+    }
+  new_contents[1] = value;
+  i = 2 + EMACS_LT (key, new_key);
+  j = EMACS_BST_VECTOR_SIZE + 1 - i;
+  new_contents[i] = treap_put (new_key, new_hash, new_value, contents[i]);
+  new_contents[j] = contents[j];
+  if (treap_hash (key) < new_hash)
+    {
+      tree_rotate (&new_treap, j, i);
+    }
+  return new_treap;
+}
+
+static Lisp_Object
+treap_put (Lisp_Object key, uint64_t hash, Lisp_Object value, Lisp_Object
treap)
+{
+  if (VECTORP (treap))
+    {
+      return treap_vector_put (key, hash, value, XVECTOR (treap));
+    }
+  return treap_singleton (key, value, treap);
+}
+
+DEFUN ("treap-put", Ftreap_put, Streap_put,
+       3, 3, 0,
+       doc: /* Associate KEY with VALUE in a treap derived from TREAP.
+If KEY is already present in TREAP, return a treap with VALUE replacing the
+existing value.  TREAP will not be modified, though sharing of structure
between
+the result treap and TREAP may occur.  */)
+  (Lisp_Object key, Lisp_Object value, Lisp_Object treap)
+{
+  if (VECTORP (treap))
+    {
+      return treap_vector_put (key, treap_hash (key), value, XVECTOR
(treap));
+    }
+  return treap_singleton (key, value, treap);
+}

+#undef EMACS_FNV_OFFSET_BASIS
+#undef EMACS_FNV_PRIME
+#undef EMACS_BST_VECTOR_SIZE
+#undef EMACS_LT
+#undef EMACS_CAT
+#undef EMACS_CAT_I

 /************************************************************************
  MD5, SHA-1, and SHA-2
@@ -5232,4 +5407,6 @@ this variable.  */);
   defsubr (&Ssecure_hash);
   defsubr (&Sbuffer_hash);
   defsubr (&Slocale_info);
+  defsubr (&Sbst_assq);
+  defsubr (&Streap_put);
 }
diff --git test/src/fns-tests.el test/src/fns-tests.el
index c533bad..1ef393e 100644
--- test/src/fns-tests.el
+++ test/src/fns-tests.el
@@ -245,3 +245,11 @@
   (let ((data '((foo) (bar))))
     (should (equal (mapcan #'identity data) '(foo bar)))
     (should (equal data                     '((foo bar) (bar))))))
+
+(ert-deftest fns-tests-treap-put ()
+  (let ((n 64)
+        (treap nil))
+    (dotimes (i n)
+      (dotimes (j i) (should (equal (bst-assq j treap) j)))
+      (dotimes (j (- n i)) (should (equal (bst-assq (+ i j) treap) nil)))
+      (setq treap (treap-put i i treap)))))


On Sun, Dec 4, 2016 at 12:13 PM, Andy Sonnenburg <andy22286@gmail.com>
wrote:

> It is written in C.  The only real reason C was used was performance
> concerns, real or imagined.  I can post a diff of the changes - it isn't
> that many lines.
>
> On Dec 4, 2016 12:04 PM, "Stefan Monnier" <monnier@iro.umontreal.ca>
> wrote:
>
>> > That's too bad (I mean, its good for performance, but unfortunate one of
>> > the use cases doesn't exist).  However, the treap functions may still
>> be of
>> > general use.  Let me know if there is any interest.  They are documented
>> > and tested.  They fill a gap between alists (persistent, linear lookup)
>> and
>> > hash tables (ephemeral, constant lookup) by being persistent while
>> > providing average case logarithmic lookup.
>>
>> Is it written in C or Elisp?  If it's Elisp, then we definitely would
>> welcome it into GNU ELPA (there is already an avl-tree implementation in
>> Emacs itself at lisp/emacs-lisp/avl-tree.el, but the more the merrier).
>> If it's written C, I'll let others decide whether we want to include it.
>>
>>
>>         Stefan
>>
>

[-- Attachment #1.2: Type: text/html, Size: 11130 bytes --]

[-- Attachment #2: treap.patch --]
[-- Type: text/x-patch, Size: 6402 bytes --]

diff --git src/fns.c src/fns.c
index dfc7842..5f3cacc 100644
--- src/fns.c
+++ src/fns.c
@@ -21,6 +21,7 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
 #include <config.h>
 
 #include <stdlib.h>
+#include <string.h>
 #include <unistd.h>
 #include <filevercmp.h>
 #include <intprops.h>
@@ -4751,7 +4752,181 @@ returns nil, then (funcall TEST x1 x2) also returns nil.  */)
   return Fput (name, Qhash_table_test, list2 (test, hash));
 }
 
+#define EMACS_CAT_I(a, b) a ## b
+#define EMACS_CAT(a, b) EMACS_CAT_I(a, b)
+#define EMACS_LT(x, y) (XLI (x) < XLI (y))
+#define EMACS_BST_VECTOR_SIZE 4
+#define EMACS_FNV_PRIME 1099511628211
+#define EMACS_FNV_OFFSET_BASIS 14695981039346656037
+
+DEFUN ("bst-assq", Fbst_assq, Sbst_assq,
+       2, 2, 0,
+       doc: /* Return the value whose key is `eq' to KEY in BST.
+BST is either a vector whose first element is a key, second element is a value,
+and third and fourth elements are left and right children; or a non-vector.  The
+left child's key must be less than BST's key.  The right child's key must be
+greater than BST's key.  Non-vector descendants of BST are ignored.  */)
+  (Lisp_Object new_key, Lisp_Object bst)
+{
+  const struct Lisp_Vector *vector;
+  const Lisp_Object *contents;
+  Lisp_Object key;
+  for (;;)
+    {
+      if (!VECTORP (bst))
+        {
+          return Qnil;
+        }
+      vector = XVECTOR (bst);
+      if (vector->header.size != EMACS_BST_VECTOR_SIZE)
+        {
+          args_out_of_range_3  (bst,
+                                make_number (0),
+                                make_number (EMACS_BST_VECTOR_SIZE));
+        }
+      contents = vector->contents;
+      key = contents[0];
+      if (EQ (key, new_key))
+        {
+          return contents[1];
+        }
+      bst = contents[2 + EMACS_LT (key, new_key)];
+    }
+}
+
+static uint64_t
+fnv_1a_hash (const void *first, const void *last)
+{
+  const unsigned char *i;
+  uint64_t hash;
+  hash = (uint64_t) EMACS_CAT(EMACS_FNV_OFFSET_BASIS, ull);
+  for (i = (const unsigned char *) first; i != last; ++i)
+    {
+      hash ^= *i;
+      hash *= (uint64_t) EMACS_CAT(EMACS_FNV_PRIME, ull);
+    }
+  return hash;
+}
+
+static Lisp_Object
+treap_singleton (Lisp_Object key, Lisp_Object value, Lisp_Object nil)
+{
+  Lisp_Object result, *contents;
+  result = make_uninit_vector (EMACS_BST_VECTOR_SIZE);
+  contents = XVECTOR (result)->contents;
+  contents[0] = key;
+  contents[1] = value;
+  contents[2] = nil;
+  contents[3] = nil;
+  return result;
+}
+
+static void
+rotate (Lisp_Object *a, Lisp_Object *b, Lisp_Object *c)
+{
+  Lisp_Object d;
+  d = *a;
+  *a = *b;
+  *b = *c;
+  *c = d;
+}
+
+static void
+tree_rotate (Lisp_Object *root, int rotation_index, int opposite_index)
+{
+  Lisp_Object *opposite, *rotation;
+  opposite = XVECTOR (*root)->contents + opposite_index;
+  rotation = XVECTOR (*opposite)->contents + rotation_index;
+  rotate (opposite, rotation, root);
+}
+
+static Lisp_Object
+make_lisp_vector (struct Lisp_Vector *vector)
+{
+  return XIL (TAG_PTR (Lisp_Vectorlike, vector));
+}
+
+static uint64_t
+treap_hash (Lisp_Object object)
+{
+  EMACS_INT i;
+  i = XLI (object);
+  return fnv_1a_hash (&i, &i + 1);
+}
+
+static Lisp_Object
+treap_put (Lisp_Object, uint64_t, Lisp_Object, Lisp_Object);
+
+static Lisp_Object
+treap_vector_put (Lisp_Object new_key,
+                  uint64_t new_hash,
+                  Lisp_Object new_value,
+                  struct Lisp_Vector *vector)
+{
+  const Lisp_Object *contents;
+  Lisp_Object key, value, new_treap, *new_contents;
+  int i, j;
+  if (vector->header.size != EMACS_BST_VECTOR_SIZE)
+    {
+      args_out_of_range_3 (make_lisp_vector (vector),
+                           make_number (0),
+                           make_number (EMACS_BST_VECTOR_SIZE));
+    }
+  contents = vector->contents;
+  key = contents[0];
+  value = contents[1];
+  new_treap = make_uninit_vector (EMACS_BST_VECTOR_SIZE);
+  new_contents = XVECTOR (new_treap)->contents;
+  new_contents[0] = key;
+  if (EQ (key, new_key))
+    {
+      new_contents[1] = new_value;
+      memcpy (new_contents + 2, contents + 2, 2 * sizeof *new_contents);
+      return new_treap;
+    }
+  new_contents[1] = value;
+  i = 2 + EMACS_LT (key, new_key);
+  j = EMACS_BST_VECTOR_SIZE + 1 - i;
+  new_contents[i] = treap_put (new_key, new_hash, new_value, contents[i]);
+  new_contents[j] = contents[j];
+  if (treap_hash (key) < new_hash)
+    {
+      tree_rotate (&new_treap, j, i);
+    }
+  return new_treap;
+}
+
+static Lisp_Object
+treap_put (Lisp_Object key, uint64_t hash, Lisp_Object value, Lisp_Object treap)
+{
+  if (VECTORP (treap))
+    {
+      return treap_vector_put (key, hash, value, XVECTOR (treap));
+    }
+  return treap_singleton (key, value, treap);
+}
+
+DEFUN ("treap-put", Ftreap_put, Streap_put,
+       3, 3, 0,
+       doc: /* Associate KEY with VALUE in a treap derived from TREAP.
+If KEY is already present in TREAP, return a treap with VALUE replacing the
+existing value.  TREAP will not be modified, though sharing of structure between
+the result treap and TREAP may occur.  */)
+  (Lisp_Object key, Lisp_Object value, Lisp_Object treap)
+{
+  if (VECTORP (treap))
+    {
+      return treap_vector_put (key, treap_hash (key), value, XVECTOR (treap));
+    }
+  return treap_singleton (key, value, treap);
+}
 
+#undef EMACS_FNV_OFFSET_BASIS
+#undef EMACS_FNV_PRIME
+#undef EMACS_BST_VECTOR_SIZE
+#undef EMACS_LT
+#undef EMACS_CAT
+#undef EMACS_CAT_I
 \f
 /************************************************************************
 			MD5, SHA-1, and SHA-2
@@ -5232,4 +5407,6 @@ this variable.  */);
   defsubr (&Ssecure_hash);
   defsubr (&Sbuffer_hash);
   defsubr (&Slocale_info);
+  defsubr (&Sbst_assq);
+  defsubr (&Streap_put);
 }
diff --git test/src/fns-tests.el test/src/fns-tests.el
index c533bad..1ef393e 100644
--- test/src/fns-tests.el
+++ test/src/fns-tests.el
@@ -245,3 +245,11 @@
   (let ((data '((foo) (bar))))
     (should (equal (mapcan #'identity data) '(foo bar)))
     (should (equal data                     '((foo bar) (bar))))))
+
+(ert-deftest fns-tests-treap-put ()
+  (let ((n 64)
+        (treap nil))
+    (dotimes (i n)
+      (dotimes (j i) (should (equal (bst-assq j treap) j)))
+      (dotimes (j (- n i)) (should (equal (bst-assq (+ i j) treap) nil)))
+      (setq treap (treap-put i i treap)))))

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Eli Zaretskii]

> From: Andy Sonnenburg <andy22286@gmail.com>
> Date: Sun, 4 Dec 2016 12:13:21 -0500
> Cc: emacs-devel@gnu.org
> 
> It is written in C. The only real reason C was used was performance concerns, real or imagined. I can post a
> diff of the changes - it isn't that many lines.

Please do.  I suggest to post to the bug tracker, using
"M-x report-emacs-bug", though, so that the discussion about it is
tracked.

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[John Wiegley]

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

SM> Is it written in C or Elisp? If it's Elisp, then we definitely would
SM> welcome it into GNU ELPA (there is already an avl-tree implementation in
SM> Emacs itself at lisp/emacs-lisp/avl-tree.el, but the more the merrier). If
SM> it's written C, I'll let others decide whether we want to include it.

Or, we could find a satisfying way to install Modules through ELPA, in which
case C code could live there too.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Stefan Monnier]

SM> Is it written in C or Elisp? If it's Elisp, then we definitely would
SM> welcome it into GNU ELPA (there is already an avl-tree implementation in
SM> Emacs itself at lisp/emacs-lisp/avl-tree.el, but the more the merrier). If
SM> it's written C, I'll let others decide whether we want to include it.
> Or, we could find a satisfying way to install Modules through ELPA, in which
> case C code could live there too.

Oh, yes, of course, that's something we want to do as well.  We could
start with an unsatisfying solution first, and then see how to improve it.


        Stefan

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[John Wiegley]

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

SM> Oh, yes, of course, that's something we want to do as well. We could start
SM> with an unsatisfying solution first, and then see how to improve it.

Sounds reasonable. Any ideas how to start? Should we assume the presence of a
Makefile, or something higher-level, like an Emacs Lisp file that declares how
to build the modules, with options for various platforms?

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Stefan Monnier]

SM> Oh, yes, of course, that's something we want to do as well. We could start
SM> with an unsatisfying solution first, and then see how to improve it.
> Sounds reasonable. Any ideas how to start? Should we assume the presence of a
> Makefile, or something higher-level, like an Emacs Lisp file that declares how
> to build the modules, with options for various platforms?

You can put a

   (eval-when-compile <run-the-C-compiler>)

in the <pkg>.el file, so that the C code gets compiled when the Elisp
file is byte-compiled.


        Stefan

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[John Wiegley]

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

SM> You can put a
SM>    (eval-when-compile <run-the-C-compiler>)
SM> in the <pkg>.el file, so that the C code gets compiled when the Elisp file
SM> is byte-compiled.

Except that <run-the-C-compiler> may vary greatly, depending on platform and
dependencies.  How "universal" does an entry in ELPA need to be?  How many
platforms should it build for?

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Stefan Monnier]

SM> You can put a
SM> (eval-when-compile <run-the-C-compiler>)
SM> in the <pkg>.el file, so that the C code gets compiled when the Elisp file
SM> is byte-compiled.

> Except that <run-the-C-compiler> may vary greatly,

Oh yes, but that's part of the problem we have to solve in general for
C modules in ELPA, regardless of the above sample code.

One solution is to instantiate "<run-the-C-compiler>" with something
akin to "./configure; make".

My point was simply that this can be done "right now with no changes to
package.el or to ELPA infrastructure".  Once we get that working, we'll
probably want to revisit this choice and introduce specific support in
package.el and ELPA infrastructure.


        Stefan

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Noam Postavsky]

On Sat, Dec 3, 2016 at 11:33 PM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>> now.  I intend to use these functions to make lexically-scoped variable
>> lookup average case O(log(n)) instead of the current O(n).
>
> AFAIK it's O(1) currently (for byte-compiled code only, but performance
> of non-byte-compiled code should be of no importance).

There is one case where interpreted code performance matters: during boostrap.

I wonder if bootstrap-emacs could load these functions as a module to
make bootstrapping with .el files go faster...

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Andreas Schwab]

On Okt 22 2017, Noam Postavsky <npostavs@users.sourceforge.net> wrote:

> I wonder if bootstrap-emacs could load these functions as a module to
> make bootstrapping with .el files go faster...

You can arrange them to get byte-compiled first, like we do with the
byte-compiler itself.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Stefan Monnier]

>> AFAIK it's O(1) currently (for byte-compiled code only, but performance
>> of non-byte-compiled code should be of no importance).
> There is one case where interpreted code performance matters: during boostrap.

Which doesn't affect users, so it's reasonably low on the priority list.
Also, I'm far from convinced that an O(log N) lookup of lexical
variables will help very much there (profiling would clearly be needed
to determine the main performance culprit, but I wouldn't be surprised
if it's completely elsewhere as in macro-expansion, for instance).

> I wonder if bootstrap-emacs could load these functions as a module to
> make bootstrapping with .el files go faster...

If we want to speed up bootstrapping, maybe we should aim to bootstrap
without interpreting Elisp code: keep a set of precompiled .elc files,
with which we build bootstrap-emacs.


        Stefan

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Noam Postavsky]

On Sun, Oct 22, 2017 at 12:44 PM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:

> Also, I'm far from convinced that an O(log N) lookup of lexical
> variables will help very much there (profiling would clearly be needed
> to determine the main performance culprit, but I wouldn't be surprised
> if it's completely elsewhere as in macro-expansion, for instance).

I will admit it was idle speculation on my part.

> If we want to speed up bootstrapping, maybe we should aim to bootstrap
> without interpreting Elisp code: keep a set of precompiled .elc files,
> with which we build bootstrap-emacs.

Most of the time we do have the .elc files from the previous run
anyway, but I had hit a situation where they were all of out of date
(due to jumping around in git, I think?) so I was watching a slow
source bootstrap.

Re: Binary Search Tree and Treap Functions bst-assq and treap-put

[Stefan Monnier]

>> If we want to speed up bootstrapping, maybe we should aim to bootstrap
>> without interpreting Elisp code: keep a set of precompiled .elc files,
>> with which we build bootstrap-emacs.
> Most of the time we do have the .elc files from the previous run
> anyway,

If we do, it's not a "bootstrap".  Indeed, I almost never bootstrap
(most of my machines date back to the 2006 era, so bootstrapping takes
very long time and I'm willing to go through a fair bit of trouble to
avoid it), but some people do it more often, and there are circumstances
(such as automated regression testing) where it's almost indispensable.


        Stefan