arun@dsrgsun.ces.cwru.edu (Arun Lakhotia) (12/29/88)
Thanks Saumya for pointing out some inefficiency in the code I had
posted. And also for pointing out that checking for divisors upto
"ceil(sqrt(N) + 1)" is sufficient to test for primeness.
This property gives a better foundation to the latter code that
I'd posted, where I was checking for divisor between I .. N//I+1,
(should have read I .. ceil(N//I+1) I think the recursion
terminates at ceil(sqrt(N)+1).
And regarding my remark on O'K: It was a pun and not a sigh of
relief. I have explicitly communicated my appreciation for his
taking the time to comment on various issues including coding
style in a very early posting, and also to him in person.
And I also appreciate Saumya's comments. In particular the
insights regarding choice point creation and the possibility of
writing code that may enable compilers utilize architecture
specific features.
Now an offshoot thought.
It seems to me that to understand optimization issues in Prolog
knowing the architecure of WAM helps a lot. Besides choice point
creation things like indexing on the first argument, bypassing the
need to shuffle arguments by maintaining the same order for
arguments in calls to other subprocedures, etc become clear only
after one knows how Prolog is compiled to WAM. (Assuming WAM as
the defacto standard abstract machine).
To me these issues became clear after reading Gabriel et. al's
tutorial on WAM, and Warren's tutorial in Seattle. With the
working knowledge of WAM that I have gathered, I can appreciate
Saumya's comments.
Now some queries:
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?
Could one say, that the invisibility of control in Prolog is good
for writing "declarative programs" but not good enough for writing
efficient ones?
In contrast, does the visibility of control in other programming
languages like Pascal, C, etc help one write efficient programs?
How long would it be when the issues like optimizing choice-points
can be taken care of by the compiler itself? and at what
cost/restriction to the programmer, if any?
Arun Lakhotiadebray@arizona.edu (Saumya K. Debray) (01/01/89)
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