Ann: SWI-Prolog 5.6.54

[Jan Wielemaker]

Hi,

I've replaced 5.6.53 with 5.6.54.  There are just two changes:

        * Portability to big-endian machines (PPC, SPARC, many RISC processors)
        * Fixed CHR, which relied on undocumented `features' of
        previous hash_term/2.

        Enjoy --- Jan

P.s. Hash values are now platform independent.  Both 32/64 bit and
        big/little endian.  String hashing on little-endian machines is
        a lot (2x) faster though.  Fortunately there are not that many programs
        where string hashing takes a significant part of the CPU time.

P.s. Tom, you can of course get the old behaviour using

                hash(Term, Hash) :-
                        (   integer(Term)
                        ->  Hash = Term
                        ;   hash_term(Term, Hash)
                        ).

        I think the new implementation is better as it guarantees proper
        distribution when hashing integers that have some pattern.

P.s. I think hash_term/2 should be called term_hash/2.  Cf. term_variables
        and argument order.  I'm a bit reluctant to change it though.


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Tom Schrijvers-2]

> P.s. Tom, you can of course get the old behaviour using
>
> hash(Term, Hash) :-
> (   integer(Term)
> ->  Hash = Term
> ;   hash_term(Term, Hash)
> ).
>
> I think the new implementation is better as it guarantees proper
> distribution when hashing integers that have some pattern.

Good point. I should do some measurements to see which is faster on
average. Hashing is a bottleneck in CHR. Exploiting the property that
integers hash to themselves made a big difference.

I expect the new hash_term/2 implementation is slower than before?

> P.s. I think hash_term/2 should be called term_hash/2.  Cf. term_variables
> and argument order.  I'm a bit reluctant to change it though.

Yes, that does make more sense.

Tom

--
Tom Schrijvers

Department of Computer Science
K.U. Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium

tel: [phone]
e-mail: tom.schrijvers@...
url: http://www.cs.kuleuven.be/~toms/

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Jan Wielemaker]

On Wednesday 16 April 2008 15:41, Tom Schrijvers wrote:

> > P.s. Tom, you can of course get the old behaviour using
> >
> > hash(Term, Hash) :-
> > (   integer(Term)
> > ->  Hash = Term
> > ;   hash_term(Term, Hash)
> > ).
> >
> > I think the new implementation is better as it guarantees proper
> > distribution when hashing integers that have some pattern.
>
> Good point. I should do some measurements to see which is faster on
> average. Hashing is a bottleneck in CHR. Exploiting the property that
> integers hash to themselves made a big difference.
>
> I expect the new hash_term/2 implementation is slower than before?

In some places it should be a bit faster, in others slower, but the
difference is very marginal:

SWI-Prolog 5.6.50
1 ?- time(forall(between(1, 10000000, X), hash_term(X, Hash))).
% 10,000,002 inferences, 1.89 CPU in 1.90 seconds (100% CPU, 5291006 Lips)

SWI-Prolog 5.6.54
1 ?- time(forall(between(1, 10000000, X), hash_term(X, Hash))).
% 10,000,002 inferences, 1.97 CPU in 1.97 seconds (100% CPU, 5076143 Lips)

This mostly measures the loop overhead :-)

> > P.s. I think hash_term/2 should be called term_hash/2.  Cf.
> > term_variables and argument order.  I'm a bit reluctant to change it
> > though.
>
> Yes, that does make more sense.

If nobody is going to object with good arguments I'll change that and
move hash_term/2 to library(backcomp).

        --- Jan


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Richard A. O'Keefe]

Concerning the hashing of integers,
There is a great new book by Andres Valloud,
called "Hashing in Smalltalk: Theory and Practice."

Anyone concerned with hashing should read this book.
Its relevance here is that there are excellent reasons
for letting the hash of fixnums be themselves.

Someone, was it Jan, said:
>> I think the new implementation is better as it guarantees proper
>> distribution when hashing integers that have some pattern.

It can't.  No hashing method can possibly do that.


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Jan Wielemaker]

On Thursday 17 April 2008 02:48:24 Richard A. O'Keefe wrote:

> Concerning the hashing of integers,
> There is a great new book by Andres Valloud,
> called "Hashing in Smalltalk: Theory and Practice."
>
> Anyone concerned with hashing should read this book.
> Its relevance here is that there are excellent reasons
> for letting the hash of fixnums be themselves.
>
> Someone, was it Jan, said:
> >> I think the new implementation is better as it guarantees proper
> >> distribution when hashing integers that have some pattern.
>
> It can't.  No hashing method can possibly do that.

I guess `guarantees' is a bit too strong. Using a cryptographic hash in
the bits of the integer however would come very close to a `guarantee'.

        Cheers --- Jan

P.s. I'd suspect you to have an opinion on hash_term <-> term_hash ...


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Alan Baljeu]

> P.s.    I'd suspect you to have an opinion on hash_term <-> term_hash ...


I do!  hash_term(+Hash, -Term) doesn't make sense, so I prefer term_hash(+Term, -Hash).




      __________________________________________________________________
Connect with friends from any web browser - no download required. Try the new Yahoo! Canada Messenger for the Web BETA at http://ca.messenger.yahoo.com/webmessengerpromo.php

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Richard A. O'Keefe]

I agree that term_hash(+Term, -Hash) makes the most sense.
What's more, that's the name that SICStus Prolog uses:

term_hash(?Term, ?Hash)
term_hash(?Term, +Depth, +Range, ?Hash)

(found in SICStus 3 and SICStus 4 documentation; see library(terms)).

It would be nice if term_hash/4 were supported as well as term_hash/2.
To the best of my belief, I invented these predicates, inspired by the
Lisp SXHASH function.  The Depth argument was to do something useful
with sufficiently-instantiated but non-ground terms.  The Range argument
was to do modular computations internally.

Why it ended up as hash_term/2 in the Quintus manual is something I can
no longer recall; it might well be my fault.


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Jan Wielemaker]

On Friday 18 April 2008 05:13, Richard A. O'Keefe wrote:

> I agree that term_hash(+Term, -Hash) makes the most sense.
> What's more, that's the name that SICStus Prolog uses:
>
> term_hash(?Term, ?Hash)
> term_hash(?Term, +Depth, +Range, ?Hash)
>
> (found in SICStus 3 and SICStus 4 documentation; see library(terms)).
>
> It would be nice if term_hash/4 were supported as well as term_hash/2.
> To the best of my belief, I invented these predicates, inspired by the
> Lisp SXHASH function.  The Depth argument was to do something useful
> with sufficiently-instantiated but non-ground terms.  The Range argument
> was to do modular computations internally.

They are now in the latest GIT version.

        Enjoy --- Jan



------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Chris Lamb-3]

Jan Wielemaker wrote:

> I've replaced 5.6.53 with 5.6.54.  There are just two changes:
>
> * Portability to big-endian machines (PPC, SPARC, many RISC
> processors)

Seems to be working ([0] [1]). Why the regression, out of interest?


/Lamby

[0] http://tinyurl.com/47v44e (5.6.53)
[1] http://tinyurl.com/3lykb8 (5.6.54)

--
Chris Lamb, UK                                       chris@...
                                                            GPG: 0x634F9A20

[Jan Wielemaker]

On Monday 21 April 2008 05:24:29 Chris Lamb wrote:
> Jan Wielemaker wrote:
> > I've replaced 5.6.53 with 5.6.54.  There are just two changes:
> >
> > * Portability to big-endian machines (PPC, SPARC, many RISC
> > processors)
>
> Seems to be working ([0] [1]). Why the regression, out of interest?

I replaced the string hash function. Murmurhash 2.0 is really fast, but
on big-endian machine the hash code of a string depends on the alignment
of the string :-(

I don't have access to a big-endian machine continuously, so often I I
just run the regression tests on Linux and Windows.  99% of the issues
are portable, so it is generally not a big issue.

        --- Jan



------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...