GNU bug report logs - #17049
[PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 17049 in the body.
You can then email your comments to 17049 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: bug-guile <at> gnu.org
Cc: David Kastrup <dak <at> gnu.org>
Subject: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Thu, 20 Mar 2014 12:23:02 +0100

Since reverse! is often used during list creation in C, an unvalidating
version could improve efficiency.

However, a validating version without the cost of validation also speeds
up existing code and does not require tradeoffs.

In contrast to most list operations, reverse! cannot get stuck in an
infinite loop but arrives back at the start when given an eventually or
fully circular list.  Because of that, one can save the cost of an
upfront proper list check at the price of having to do a double reversal
in the error case.

Signed-off-by: David Kastrup <dak <at> gnu.org>
---
 libguile/list.c | 45 ++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 38 insertions(+), 7 deletions(-)

diff --git a/libguile/list.c b/libguile/list.c
index 1f44ad0..8cbdfcf 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
 	    "@code{reverse!}")
 #define FUNC_NAME s_scm_reverse_x
 {
-  SCM_VALIDATE_LIST (1, lst);
+  SCM oldlst = lst;
+  SCM tail = SCM_BOOL_F;
+
   if (SCM_UNBNDP (new_tail))
     new_tail = SCM_EOL;
 
-  while (!SCM_NULL_OR_NIL_P (lst))
+  if (SCM_NULL_OR_NIL_P (lst))
+    return new_tail;
+
+  SCM_VALIDATE_CONS (1, lst);
+
+  /* SCM_VALIDATE_LIST would run through the whole list to make sure it
+     is not eventually circular.  In contrast to most list operations,
+     reverse! cannot get stuck in an infinite loop but arrives back at
+     the start when given an eventually or fully circular list.  Because
+     of that, we can save the cost of an upfront proper list check at
+     the price of having to do a double reversal in the error case.
+  */
+
+  do {
+    SCM old_tail = SCM_CDR (lst);
+    SCM_SETCDR (lst, tail);
+    tail = lst;
+    lst = old_tail;
+  } while (scm_is_pair (lst));
+
+  if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
     {
-      SCM old_tail = SCM_CDR (lst);
-      SCM_SETCDR (lst, new_tail);
-      new_tail = lst;
-      lst = old_tail;
+      SCM_SETCDR (oldlst, new_tail);
+      return tail;
     }
-  return new_tail;
+
+  /* We did not start with a proper list.  Undo the reversal. */
+
+  do {
+    SCM old_tail = SCM_CDR (tail);
+    SCM_SETCDR (tail, lst);
+    lst = tail;
+    tail = old_tail;
+  } while (scm_is_pair (tail));
+
+  scm_wrong_type_arg (FUNC_NAME, 1, lst);
+  return oldlst;
 }
 #undef FUNC_NAME
 
-- 
1.9.1

Message #8 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Subject: PostScriptum:
Date: Thu, 20 Mar 2014 12:38:44 +0100

The final return statement cannot actually be reached, it is basically
there for silencing compilers.

If it is left in place, it should probably rather "return" the
equivalent `lst' in order to keep the function from retaining `oldlst'
unnecessarily.

Holler if you want a patch amended accordingly.

-- 
David Kastrup

Message #11 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Cc: David Kastrup <dak <at> gnu.org>
Subject: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Thu, 20 Mar 2014 15:19:09 +0100

Since reverse! is often used during list creation in C, an unvalidating
version could improve efficiency.

However, a validating version without the cost of validation also speeds
up existing code and does not require tradeoffs.

In contrast to most list operations, reverse! cannot get stuck in an
infinite loop but arrives back at the start when given an eventually or
fully circular list.  Because of that, one can save the cost of an
upfront proper list check at the price of having to do a double reversal
in the error case.

Signed-off-by: David Kastrup <dak <at> gnu.org>
---
As opposed to the previous patch, there is just a single error path,
making for a slightly nicer flow.

 libguile/list.c | 43 ++++++++++++++++++++++++++++++++++++-------
 1 file changed, 36 insertions(+), 7 deletions(-)

diff --git a/libguile/list.c b/libguile/list.c
index 1f44ad0..da99c8e 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -374,18 +374,47 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
 	    "@code{reverse!}")
 #define FUNC_NAME s_scm_reverse_x
 {
-  SCM_VALIDATE_LIST (1, lst);
+  SCM oldlst = lst;
+  SCM tail = SCM_BOOL_F;
+
   if (SCM_UNBNDP (new_tail))
     new_tail = SCM_EOL;
 
-  while (!SCM_NULL_OR_NIL_P (lst))
+  if (SCM_NULL_OR_NIL_P (lst))
+    return new_tail;
+
+  /* SCM_VALIDATE_LIST would run through the whole list to make sure it
+     is not eventually circular.  In contrast to most list operations,
+     reverse! cannot get stuck in an infinite loop but arrives back at
+     the start when given an eventually or fully circular list.  Because
+     of that, we can save the cost of an upfront proper list check at
+     the price of having to do a double reversal in the error case.
+  */
+
+  while (scm_is_pair (lst)) {
+    SCM old_tail = SCM_CDR (lst);
+    SCM_SETCDR (lst, tail);
+    tail = lst;
+    lst = old_tail;
+  };
+
+  if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
     {
-      SCM old_tail = SCM_CDR (lst);
-      SCM_SETCDR (lst, new_tail);
-      new_tail = lst;
-      lst = old_tail;
+      SCM_SETCDR (oldlst, new_tail);
+      return tail;
     }
-  return new_tail;
+
+  /* We did not start with a proper list.  Undo the reversal. */
+
+  while (scm_is_pair (tail)) {
+    SCM old_tail = SCM_CDR (tail);
+    SCM_SETCDR (tail, lst);
+    lst = tail;
+    tail = old_tail;
+  };
+
+  scm_wrong_type_arg (FUNC_NAME, 1, lst);
+  return lst;
 }
 #undef FUNC_NAME
 
-- 
1.9.1

Message #14 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: Andy Wingo <wingo <at> pobox.com>
To: David Kastrup <dak <at> gnu.org>
Cc: 17049 <at> debbugs.gnu.org
Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of
 SCM_VALIDATE_LIST
Date: Thu, 20 Mar 2014 21:50:11 +0100

Hi,

Thanks for the patch.  What is its performance impact for your use case?

On Thu 20 Mar 2014 12:23, David Kastrup <dak <at> gnu.org> writes:

> +  /* We did not start with a proper list.  Undo the reversal. */

I'm hesitant.  This is visible to other threads.  (Granted there has to
be significant wrongness if we get here...)

Andy
-- 
http://wingolog.org/

Message #17 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: Andy Wingo <wingo <at> pobox.com>
Cc: 17049 <at> debbugs.gnu.org
Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of
 SCM_VALIDATE_LIST
Date: Thu, 20 Mar 2014 22:27:28 +0100

Andy Wingo <wingo <at> pobox.com> writes:

> Thanks for the patch.  What is its performance impact for your use
> case?

Use case is a bit hard to benchmark from scratch as it's basically
consing a list together and then reversing it.  Of course, in a fresh
session the consing is dominating the run time, while in a real-life
session cons cells are usually available from a free list.

Of course, one can just call scm_reverse_x in a loop without any consing
at all, but that's probably a bit too much of a best use case.  I could
do this in order to give an upper limit to what improvement may be
expected.

In that case, if we are talking about large lists, I'd expect a factor
of about 7:4 since the reversal takes 2 read-modify-writes per 2
elements, and tortoise and hare take 1 and 2 read cycles per 2 elements.
The loops should be tight enough to fit into registers and executing
cache, so those memory accesses should by far dominate the timing. And
with a large list, all of those data accesses need to get their cache
line at a different time.

> On Thu 20 Mar 2014 12:23, David Kastrup <dak <at> gnu.org> writes:
>
>> +  /* We did not start with a proper list.  Undo the reversal. */
>
> I'm hesitant.  This is visible to other threads.  (Granted there has to
> be significant wrongness if we get here...)

Uh, what of it?  The other threads have to deal with the reversal in the
non-error case, and it does not have well-defined multithread semantics.
So what you are saying is that you want to have multithread-safe
semantics for the error case exclusively if I understand correctly.

But the tortoise-hare algorithm used in SCM_VALIDATE_LIST is not
multithread-robust either as far as I can see.

At any rate, this additional reversal only happens in the error case.
Tortoise-hare is read-only, so it will be quite faster than a double
reversal (which dirties the cache of the chain twice, and if we are
talking about a circular list, the cache of the non-circular part even
four times).  So if we want to have an efficient error behavior, this
change is not going to be an improvement.

It seems pointless to add an extra unvalidated reversal when it would be
just as fast as _this_ validated reversal.

-- 
David Kastrup

Message #20 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Andy Wingo <wingo <at> pobox.com>
Cc: David Kastrup <dak <at> gnu.org>, 17049 <at> debbugs.gnu.org
Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of
 SCM_VALIDATE_LIST
Date: Fri, 21 Mar 2014 00:38:46 -0400

Andy Wingo <wingo <at> pobox.com> writes:

> On Thu 20 Mar 2014 12:23, David Kastrup <dak <at> gnu.org> writes:
>
>> +  /* We did not start with a proper list.  Undo the reversal. */
>
> I'm hesitant.  This is visible to other threads.  (Granted there has to
> be significant wrongness if we get here...)

If one thread attempts to access a list that's being destructively
reversed by another thread, the behavior is undefined.  Incidentally,
that's also the reason that your recent changes to 'for-each' are
defensible, Andy.  Therefore, I strongly believe this to be a non-issue.

I have yet to review this patch properly (except to notice that it does
not follow the GNU coding standards w.r.t. bracket placement, which
needs to be fixed), but based on the high-level description, it sounds
good to me, and also quite clever.

    Regards,
      Mark

Message #23 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Cc: David Kastrup <dak <at> gnu.org>
Subject: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Fri, 21 Mar 2014 17:56:58 +0100

Since reverse! is often used during list creation in C, an unvalidating
version could improve efficiency.

However, a validating version without the cost of validation also speeds
up existing code and does not require tradeoffs.

In contrast to most list operations, reverse! cannot get stuck in an
infinite loop but arrives back at the start when given an eventually or
fully circular list.  Because of that, one can save the cost of an
upfront proper list check at the price of having to do a double reversal
in the error case.

Signed-off-by: David Kastrup <dak <at> gnu.org>
---

Formatting changes.  Also renamed oldlst to old_lst to match the
existing variable name style better.

libguile/list.c | 41 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 36 insertions(+), 5 deletions(-)

diff --git a/libguile/list.c b/libguile/list.c
index 1f44ad0..9b2a0d7 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
 	    "@code{reverse!}")
 #define FUNC_NAME s_scm_reverse_x
 {
-  SCM_VALIDATE_LIST (1, lst);
+  SCM old_lst = lst;
+  SCM tail = SCM_BOOL_F;
+
   if (SCM_UNBNDP (new_tail))
     new_tail = SCM_EOL;
 
-  while (!SCM_NULL_OR_NIL_P (lst))
+  if (SCM_NULL_OR_NIL_P (lst))
+    return new_tail;
+
+  /* SCM_VALIDATE_LIST would run through the whole list to make sure it
+     is not eventually circular.  In contrast to most list operations,
+     reverse! cannot get stuck in an infinite loop but arrives back at
+     the start when given an eventually or fully circular list.  Because
+     of that, we can save the cost of an upfront proper list check at
+     the price of having to do a double reversal in the error case.
+  */
+
+  while (scm_is_pair (lst))
     {
       SCM old_tail = SCM_CDR (lst);
-      SCM_SETCDR (lst, new_tail);
-      new_tail = lst;
+      SCM_SETCDR (lst, tail);
+      tail = lst;
       lst = old_tail;
     }
-  return new_tail;
+
+  if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
+    {
+      SCM_SETCDR (old_lst, new_tail);
+      return tail;
+    }
+
+  /* We did not start with a proper list.  Undo the reversal. */
+
+  while (scm_is_pair (tail))
+    {
+      SCM old_tail = SCM_CDR (tail);
+      SCM_SETCDR (tail, lst);
+      lst = tail;
+      tail = old_tail;
+    }
+
+  scm_wrong_type_arg (FUNC_NAME, 1, lst);
+  return lst;
 }
 #undef FUNC_NAME
 
-- 
1.9.1

Message #26 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: Andy Wingo <wingo <at> pobox.com>
Cc: 17049 <at> debbugs.gnu.org
Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of
 SCM_VALIDATE_LIST
Date: Fri, 21 Mar 2014 18:44:07 +0100

[Message part 1 (text/plain, inline)]

Andy Wingo <wingo <at> pobox.com> writes:

> Hi,
>
> Thanks for the patch.  What is its performance impact for your use case?

Here is an artificial use case (I make care to get my list scattered
over memory, assuming that sort! keeps the cells around).

[zoppo.scm (application/octet-stream, attachment)]

[Message part 3 (text/plain, inline)]

The output for my version first and the default version afterwards is

#<time type: time-duration nanosecond: 449629000 second: 8>dak <at> lola:/usr/local/tmp/guile$ meta/guile /tmp/zoppo.scm 
#<time type: time-duration nanosecond: 898802000 second: 15>dak <at> lola:/usr/local/tmp/guile$ 

So it's a bit better than my 7:4 estimate (rather a factor of 1.88),
probably because I forgot that the CPU does not have to wait for the
write cycle to complete for continuing.

Now that's a somewhat artificial benchmark, but still: almost a factor
of 2 for the operation itself is pretty good.

-- 
David Kastrup

Message #29 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Subject: Further change ideas.
Date: Sun, 30 Mar 2014 18:36:20 +0200

While it does not appear like this patch proposal is going anywhere for
some reason, there is a further opportunity for change.

One thing is to note that scm_srfi1_append_reverse_x does essentially
the same thing but has a different doc string, the second argument
non-optional and a different implementation that creates nonsense on
some arguments and hangs on others:

scheme@(guile-user)> (use-modules (srfi srfi-1))
scheme@(guile-user)> (append-reverse! (circular-list 1 2) '(3 4))
$2 = (4 3 1 2 . #-1#)
scheme@(guile-user)> (append-reverse! (circular-list 1) (circular-list 2))
[hangs uninterruptibly...]

It can also show somewhat inventive error messages:

scheme@(guile-user)> (append-reverse! '(1 2 3 . 4) 5)
ERROR: In procedure append-reverse!:
ERROR: In procedure append-reverse!: Wrong type argument in position 1 (expecting list): 4

or even
scheme@(guile-user)> (append-reverse! (circular-list 1 2 3) 5)
ERROR: In procedure append-reverse!:
ERROR: In procedure append-reverse!: Wrong type argument in position 1 (expecting list): 5


It is an obvious candidate to rerouting to reverse!.  However, there is
another difference apart from append-reverse! not really being all too
robust against errors:

scheme@(guile-user) [2]> (reverse! (circular-list 1 2 3) 5)
ERROR: In procedure reverse!:
ERROR: In procedure reverse!: Wrong type argument in position 1: (1 2 3 . #-2#)

Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.

Note that with reverse! the "(expecting list)" in the error message is
absent because scm_wrong_type_arg instead of scm_wrong_type_arg_msg is
employed in scm_reverse_x (directly after the patch, indirectly through
SCM_VALIDATE_LIST before the patch).

So if one wants to have identical error behavior, it would likely make
sense to move to the somewhat more specific scm_wrong_type_arg_msg,
possibly even for the whole of SCM_VALIDATE_LIST.

Of course all this is water under the drawbridge if not even the
original patch is going anywhere.

-- 
David Kastrup

Message #32 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17049 <at> debbugs.gnu.org
Subject: Re: bug#17049: [PATCH] Make reverse! forego the cost of
 SCM_VALIDATE_LIST
Date: Mon, 31 Mar 2014 15:56:30 -0400

Hi David,

This latest patch looks good to me, and Andy has agreed.  Could you add
a GNU ChangeLog-style commit log, according to our conventions, and send
it in the format produced by "git format-patch"?

    Regards,
      Mark


David Kastrup <dak <at> gnu.org> writes:

> Since reverse! is often used during list creation in C, an unvalidating
> version could improve efficiency.
>
> However, a validating version without the cost of validation also speeds
> up existing code and does not require tradeoffs.
>
> In contrast to most list operations, reverse! cannot get stuck in an
> infinite loop but arrives back at the start when given an eventually or
> fully circular list.  Because of that, one can save the cost of an
> upfront proper list check at the price of having to do a double reversal
> in the error case.
>
> Signed-off-by: David Kastrup <dak <at> gnu.org>
> ---
>
> Formatting changes.  Also renamed oldlst to old_lst to match the
> existing variable name style better.
>
> libguile/list.c | 41 ++++++++++++++++++++++++++++++++++++-----
>  1 file changed, 36 insertions(+), 5 deletions(-)
>
> diff --git a/libguile/list.c b/libguile/list.c
> index 1f44ad0..9b2a0d7 100644
> --- a/libguile/list.c
> +++ b/libguile/list.c
> @@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
>  	    "@code{reverse!}")
>  #define FUNC_NAME s_scm_reverse_x
>  {
> -  SCM_VALIDATE_LIST (1, lst);
> +  SCM old_lst = lst;
> +  SCM tail = SCM_BOOL_F;
> +
>    if (SCM_UNBNDP (new_tail))
>      new_tail = SCM_EOL;
>  
> -  while (!SCM_NULL_OR_NIL_P (lst))
> +  if (SCM_NULL_OR_NIL_P (lst))
> +    return new_tail;
> +
> +  /* SCM_VALIDATE_LIST would run through the whole list to make sure it
> +     is not eventually circular.  In contrast to most list operations,
> +     reverse! cannot get stuck in an infinite loop but arrives back at
> +     the start when given an eventually or fully circular list.  Because
> +     of that, we can save the cost of an upfront proper list check at
> +     the price of having to do a double reversal in the error case.
> +  */
> +
> +  while (scm_is_pair (lst))
>      {
>        SCM old_tail = SCM_CDR (lst);
> -      SCM_SETCDR (lst, new_tail);
> -      new_tail = lst;
> +      SCM_SETCDR (lst, tail);
> +      tail = lst;
>        lst = old_tail;
>      }
> -  return new_tail;
> +
> +  if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
> +    {
> +      SCM_SETCDR (old_lst, new_tail);
> +      return tail;
> +    }
> +
> +  /* We did not start with a proper list.  Undo the reversal. */
> +
> +  while (scm_is_pair (tail))
> +    {
> +      SCM old_tail = SCM_CDR (tail);
> +      SCM_SETCDR (tail, lst);
> +      lst = tail;
> +      tail = old_tail;
> +    }
> +
> +  scm_wrong_type_arg (FUNC_NAME, 1, lst);
> +  return lst;
>  }
>  #undef FUNC_NAME

Message #35 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Cc: Mark H Weaver <mhw <at> netris.org>, David Kastrup <dak <at> gnu.org>
Subject: [PATCH v2] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Tue,  1 Apr 2014 12:26:59 +0200

* libguile/list.c (scm_reverse_x): Do not check first argument to
  reverse! to be a proper list in advance.  This provides the
  performance of a version without validation (tests show a speedup by a
  factor of 1.8) except for the error case.

Signed-off-by: David Kastrup <dak <at> gnu.org>
---
 libguile/list.c | 41 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 36 insertions(+), 5 deletions(-)

diff --git a/libguile/list.c b/libguile/list.c
index 1f44ad0..9b2a0d7 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
 	    "@code{reverse!}")
 #define FUNC_NAME s_scm_reverse_x
 {
-  SCM_VALIDATE_LIST (1, lst);
+  SCM old_lst = lst;
+  SCM tail = SCM_BOOL_F;
+
   if (SCM_UNBNDP (new_tail))
     new_tail = SCM_EOL;
 
-  while (!SCM_NULL_OR_NIL_P (lst))
+  if (SCM_NULL_OR_NIL_P (lst))
+    return new_tail;
+
+  /* SCM_VALIDATE_LIST would run through the whole list to make sure it
+     is not eventually circular.  In contrast to most list operations,
+     reverse! cannot get stuck in an infinite loop but arrives back at
+     the start when given an eventually or fully circular list.  Because
+     of that, we can save the cost of an upfront proper list check at
+     the price of having to do a double reversal in the error case.
+  */
+
+  while (scm_is_pair (lst))
     {
       SCM old_tail = SCM_CDR (lst);
-      SCM_SETCDR (lst, new_tail);
-      new_tail = lst;
+      SCM_SETCDR (lst, tail);
+      tail = lst;
       lst = old_tail;
     }
-  return new_tail;
+
+  if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
+    {
+      SCM_SETCDR (old_lst, new_tail);
+      return tail;
+    }
+
+  /* We did not start with a proper list.  Undo the reversal. */
+
+  while (scm_is_pair (tail))
+    {
+      SCM old_tail = SCM_CDR (tail);
+      SCM_SETCDR (tail, lst);
+      lst = tail;
+      tail = old_tail;
+    }
+
+  scm_wrong_type_arg (FUNC_NAME, 1, lst);
+  return lst;
 }
 #undef FUNC_NAME
 
-- 
1.9.1

Message #38 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Cc: Mark H Weaver <mhw <at> netris.org>
Subject: Re: [PATCH v2] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Tue, 01 Apr 2014 12:40:53 +0200

Sigh.  In case you are committing this, there might be one minor change
worth doing to match the coding style:

> +  scm_wrong_type_arg (FUNC_NAME, 1, lst);

This should likely be

     SCM_WRONG_TYPE_ARG (1, lst);

for consistency with other usage in list.c.  I can reroll if you prefer
this over fixing it yourself.

-- 
David Kastrup

Message #41 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17049 <at> debbugs.gnu.org
Subject: Re: [PATCH v2] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Tue, 01 Apr 2014 10:09:32 -0400

David Kastrup <dak <at> gnu.org> writes:

> Sigh.  In case you are committing this, there might be one minor change
> worth doing to match the coding style:
>
>> +  scm_wrong_type_arg (FUNC_NAME, 1, lst);
>
> This should likely be
>
>      SCM_WRONG_TYPE_ARG (1, lst);
>
> for consistency with other usage in list.c.  I can reroll if you prefer
> this over fixing it yourself.

Please reroll, since there's also make a change to the commit log I'd
like.  You wrote:

> * libguile/list.c (scm_reverse_x): Do not check first argument to
> reverse! to be a proper list in advance.  This provides the
> performance of a version without validation (tests show a speedup by a
> factor of 1.8) except for the error case.

As the GNU coding standards suggest, we prefer for change log entries to
contain only a brief description of what changes were made, and to leave
rationales and other explanations in the code comments.

Therefore, I think you should remove the second sentence above, and also
add a brief mention about undoing the reversal if the argument turned
out to be improper.

     Thanks!
       Mark

Message #44 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: David Kastrup <dak <at> gnu.org>
To: 17049 <at> debbugs.gnu.org
Cc: Mark H Weaver <mhw <at> netris.org>, David Kastrup <dak <at> gnu.org>
Subject: [PATCH v3] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Tue,  1 Apr 2014 16:24:29 +0200

* libguile/list.c (scm_reverse_x): Do not validate first argument to
  reverse! in advance.  Instead undo reversal in error case.

Signed-off-by: David Kastrup <dak <at> gnu.org>
---
 libguile/list.c | 41 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 36 insertions(+), 5 deletions(-)

diff --git a/libguile/list.c b/libguile/list.c
index 1f44ad0..41cc937 100644
--- a/libguile/list.c
+++ b/libguile/list.c
@@ -374,18 +374,49 @@ SCM_DEFINE (scm_reverse_x, "reverse!", 1, 1, 0,
 	    "@code{reverse!}")
 #define FUNC_NAME s_scm_reverse_x
 {
-  SCM_VALIDATE_LIST (1, lst);
+  SCM old_lst = lst;
+  SCM tail = SCM_BOOL_F;
+
   if (SCM_UNBNDP (new_tail))
     new_tail = SCM_EOL;
 
-  while (!SCM_NULL_OR_NIL_P (lst))
+  if (SCM_NULL_OR_NIL_P (lst))
+    return new_tail;
+
+  /* SCM_VALIDATE_LIST would run through the whole list to make sure it
+     is not eventually circular.  In contrast to most list operations,
+     reverse! cannot get stuck in an infinite loop but arrives back at
+     the start when given an eventually or fully circular list.  Because
+     of that, we can save the cost of an upfront proper list check at
+     the price of having to do a double reversal in the error case.
+  */
+
+  while (scm_is_pair (lst))
     {
       SCM old_tail = SCM_CDR (lst);
-      SCM_SETCDR (lst, new_tail);
-      new_tail = lst;
+      SCM_SETCDR (lst, tail);
+      tail = lst;
       lst = old_tail;
     }
-  return new_tail;
+
+  if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
+    {
+      SCM_SETCDR (old_lst, new_tail);
+      return tail;
+    }
+
+  /* We did not start with a proper list.  Undo the reversal. */
+
+  while (scm_is_pair (tail))
+    {
+      SCM old_tail = SCM_CDR (tail);
+      SCM_SETCDR (tail, lst);
+      lst = tail;
+      tail = old_tail;
+    }
+
+  SCM_WRONG_TYPE_ARG (1, lst);
+  return lst;
 }
 #undef FUNC_NAME
 
-- 
1.9.1

Message #47 received at 17049 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: request <at> debbugs.gnu.org, 17049 <at> debbugs.gnu.org
Subject: Re: [PATCH v3] Make reverse! forego the cost of SCM_VALIDATE_LIST
Date: Tue, 01 Apr 2014 12:35:48 -0400

tags 17049 notabug
severity 17049 wishlist
close 17049
thanks

David Kastrup <dak <at> gnu.org> writes:

> * libguile/list.c (scm_reverse_x): Do not validate first argument to
>   reverse! in advance.  Instead undo reversal in error case.

Pushed to stable-2.0, commit 0ece4850c5423d53db3245f57681053486327aa3.
I'm closing this bug now.

   Thanks!
     Mark

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.