Re: Ann: SWI-Prolog 7.1.0

Hi Jan,

On 07/12/2013, at 09:54, Jan Wielemaker <[email protected]> wrote:

> On 12/06/2013 11:28 PM, Paulo Moura wrote:
>> Hi,
>> 
>> Sorry about the very late reply to this post (on defaulty data
>> structures) but I have some experience here that I want to share.
>> 
>> On 28/11/2013, at 07:10, Richard A. O'Keefe <[email protected]>
>> wrote:
>> 
>>> 
>>> On 28/11/2013, at 7:00 AM, Jan Wielemaker wrote:
>>> 
>>>> Alan,
>>>> 
>>>> Good to point this out!  Yes, if everyone follows the Craft of
>>>> Prolog's rules on this, [] \== '[]' is not needed.  But ..
>>>> 
>>>> - It uses a lot more memory (1 cell for joe and 3 for
>>>> word(joe)).
>>> 
>>> This is seriously misleading.
>>> 
>>> The design rules given in the Craft of Prolog do NOT generate
>>> wrappers except to do one of two things: - to package together two
>>> or more piece of information - to distinguish one case from
>>> another.
>>> 
>>> One of the reasons that I wrote that section of the book was that I
>>> was disturbed by the amount of Prolog code I had seen that 
>>> *over*-used wrappers, so I wanted simple clear guidelines that 
>>> would *only* result in wrappers that paid for themselves.
>>> 
>>> By the way, I used to have a 4MB desktop machine in 1990. It had 1
>>> core and rand about 30 MHz. I now have an 8GB desktop machine,
>>> which has 4 cores, each of them 100 times faster.
>>> 
>>> Using 2 extra words of memory is a GOOD thing IF it pays for itself
>>> by making the program simpler and clearer.
>>> 
>>> As a case in point, when David Warren wrote the Quintus compiler, 
>>> he used defaulty data structures everywhere.
>>> 
>>> I rewrote it to never use defaulty data structures. And it ran 20%
>>> faster. It even took less memory, because the trick was to
>>> carefully design *every* case in the data type. ...
>> 
>> During my sabbatical, when visiting K.U.Leuven, I had the chance to
>> help two researchers there that were using complex Prolog
>> applications to deal with stuff like big data. They were using a fast
>> Prolog system (YAP) but still their applications run for long hours.
>> I offered my help and, thanks to Richard's book on defaulty data
>> representation, I quickly recognized a familiar pattern: cuts
>> everywhere and the Prolog runtime repeatedly  creating choice-points
>> just to cut them some point later while it tried clause after clause
>> after clause. I asked a few questions (I had no familiarity with the
>> code) and rewrote that part of the code. It took me around one hour
>> in each case to avoid the defaulty data representation. The resulting
>> applications speedup was impressive. Around 40% for one of the cases,
>> a bit less for the other.
>> 
>> It's not always easy to avoid using defaulty data structures. But the
>> benefits in both code clarity and performance can be quite
>> significant :-) Specially when the defaulty bits are where the
>> application spends most of its time.
> 
> All true.  Just, Prolog systems can also nicely generate a switch-on-tag
> from code such as
> 
> do(X) :- atom(X), ....
> do(X) :- number(X), ...
> do(X) :- string(X), ...
> 
> etc.  Properly implemented, the above should be faster than code like this
> 
> do(atom(X)) :-
> do(number(X)) :-
> do(string(X)) :-

But there's an important difference here that is not apparent if a switch-on-tag would solve. Often, you have something like:

do(X) :- atom(X), !, ....
do(X) :- number(X), !, ...
do(X) :- string(X), !, ...

Does the approach you mention avoids creating a choice-point for do(X) calls that is then discarded by the cuts? The advantage (I observed) of the alternative solution:

do(atom(X)) :-
do(number(X)) :-
do(string(X)) :-

is that no choice-point is created for calls to do(X) where X is instantiated. Plus, from my readings about Prolog implementations, those that do a switch-on-tag approach do so only when the tests are the standard *built-in* term type predicates, which doesn't help with the also common cases where the tests are calls to user-defined predicates.

> Alas, SWI-Prolog only looks at the clause head.  Possibly YAP does the
> same.  Ideally, Prolog examines the code for unification and type checks
> (and whatever it can understand) that follow the head to support its
> indexing.
> 
> That said, I agree that defaulty data structures can positively influence
> readability and declarative behaviour.

And, in cases such as the ones described, also avoid the performance penalty of repeatedly creating and destroying choice-points, plus looking for the correct clause by trying them one by one instead of jumping straight to it (thanks to indexing of clause heads).

Cheers,

Paulo

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

Email: <mailto:[email protected]>
Web:   <http://logtalk.org/>
-----------------------------------------------------------------