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

Previous Next

Full log

View this message in rfc822 format

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17049 <at> debbugs.gnu.org
Subject: 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

Previous Next

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