From: Mark H Weaver <mhw@netris.org>
To: David Kastrup <dak@gnu.org>
Cc: 17049@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 [thread overview]
Message-ID: <87zjk6m9ap.fsf@yeeloong.lan> (raw)
In-Reply-To: <1395421018-29987-1-git-send-email-dak@gnu.org> (David Kastrup's message of "Fri, 21 Mar 2014 17:56:58 +0100")
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@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@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
next prev parent reply other threads:[~2014-03-31 19:56 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-03-20 11:23 bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST David Kastrup
2014-03-20 11:38 ` bug#17049: PostScriptum: David Kastrup
2014-03-20 14:19 ` bug#17049: [PATCH] Make reverse! forego the cost of SCM_VALIDATE_LIST David Kastrup
2014-03-20 20:50 ` Andy Wingo
2014-03-20 21:27 ` David Kastrup
2014-03-21 4:38 ` Mark H Weaver
2014-03-21 16:56 ` David Kastrup
2014-03-31 19:56 ` Mark H Weaver [this message]
2014-04-01 10:26 ` bug#17049: [PATCH v2] " David Kastrup
2014-04-01 10:40 ` David Kastrup
2014-04-01 14:09 ` Mark H Weaver
2014-04-01 14:24 ` bug#17049: [PATCH v3] " David Kastrup
2014-04-01 16:35 ` Mark H Weaver
2014-03-21 17:44 ` bug#17049: [PATCH] " David Kastrup
2014-03-30 16:36 ` bug#17049: Further change ideas David Kastrup
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87zjk6m9ap.fsf@yeeloong.lan \
--to=mhw@netris.org \
--cc=17049@debbugs.gnu.org \
--cc=dak@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).