Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!rutgers!cmcl2!arizona!debray
From: debray@arizona.edu (Saumya K. Debray)
Newsgroups: comp.lang.prolog
Subject: declarative vs. efficient code [was Re: Efficiency, O'Keefe]
Summary: declarative need not imply inefficient
Message-ID: <8521@megaron.arizona.edu>
Date: 31 Dec 88 17:25:35 GMT
References: <359@cwjcc.CWRU.Edu>
Organization: U of Arizona CS Dept, Tucson
Lines: 48

In article <359@cwjcc.CWRU.Edu>, Arun Lakhotia writes:

>     It seems to me that to understand optimization issues in Prolog
>     knowing the architecure of WAM helps a lot.  [ ... ]
>     Do people with little or no knowledge of WAM find it a bottleneck
>     in gaining efficiency that is beyond gains achievable due to
>     algorithmic changes or perturbations?

With absolutely no knowledge about the underlying architecture or
implementation, I'd imagine that efficiency would be something of a
hit-or-miss affair.  Still, I'd say that in a great many (most?) cases,
the biggest payoffs come from proper choice of algorithms and data
structures (the "proper" choice of algorithms etc. may, of course, be
influenced by knowledge of architecture, implementation etc., but can
often be separated from such low level details).  For example, in the
code for primality testing posted earlier, I found that tinkering with
choice point creation etc. gave me maybe a 5-10% speedup, but changing
the algorithm to test upto ceil(sqrt(N)), instead of ceil(N/2), gave an
order of magnitude improvement.

>     Could one say, that the invisibility of control in Prolog is good
>     for writing "declarative programs" but not good enough for writing
>     efficient ones?

There seems to be a hidden assumption here that "declarative implies
inefficient".  While this may not be what Arun meant, this is certainly
a common (and unfortunate) misconception.  The more I code in Prolog, the
more I find that declarative code need not be inefficient. There are two
reasons for this.  First, a good programmer can very often write efficient
code without having to resort to blatantly nondeclarative language
features. Second, it's often the case that nondeclarative constructs are
expensive to implement, and so contribute to inefficiency (e.g. people
who are unaware of the fact that an "assert" is about 2 to 3 orders of
magnitude more expensive than a simple unification often try to simulate
global variables and destructive assignment using assert, then wonder why
their programs crawl!).

>     Thanks Saumya for ... pointing out that checking for divisors upto
>     "ceil(sqrt(N) + 1)" is sufficient to test for primeness.
                   ^^^^
My mistake, I was thinking "floor" when I typed in "ceil".  To check that
a number N is prime, it's enough to check that none of the (prime) numbers
between 2 and ceil(sqrt(N)) divide it.
-- 
Saumya Debray		CS Department, University of Arizona, Tucson

     internet:   debray@arizona.edu
     uucp:       arizona!debray