Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!arizona!debray
From: debray@arizona.edu (Saumya Debray)
Newsgroups: comp.lang.prolog
Subject: optimizing append/nrev [was Re: Standard of Prolog code]
Message-ID: <2431@megaron.arizona.edu>
Date: Sat, 17-Oct-87 11:51:17 EDT
Article-I.D.: megaron.2431
Posted: Sat Oct 17 11:51:17 1987
Date-Received: Sun, 18-Oct-87 11:30:59 EDT
References: <2265@mulga.oz> <5005@utah-cs.UUCP> <2217@megaron.arizona.edu> <1528@sics.se>
Organization: U of Arizona CS Dept, Tucson
Lines: 31
Summary: optimizing append, nrev

In article <1528@sics.se>, lhe@sics.se (Lars-Henrik Eriksson) writes:

> In at least one "high-powered commercial Prolog system" naive reverse
> suffers a 35% slowdown (on a SUN) when you change append/3 to ...
> Apparently poor handling of inline predicates isn't the only thing that's
> going on...

Hmmm ... I wonder if changing the name of the predicate from "append"
to "foo" results in a significant slowdown! :-)

As long as we're trying to optimize the hell out of append, it's
interesting to note that entering the loop at the bottom instead of
the top, i.e. generating the instruction sequence

  [...], getlist 1, unify, unify, getlist 3, unify, unify, switchonterm

instead of

  switchonterm, [...], getlist 1, unify, unify, getlist 3, unify, unify,
                       execute append/3

can give a 7-10% improvement in naive-reverse LIPS numbers (not to be
sneezed at entirely, since we could only get about a 5-7% speedup using
special unification instructions based on i/o modes).  (Besides, this
technique applies to other tail-recursive predicates as well, so one
needn't be embarrassed about using it to improve nrev.)
-- 
Saumya Debray		CS Department, University of Arizona, Tucson

     internet:   debray@arizona.edu
     uucp:       {allegra, cmcl2, ihnp4} !arizona!debray