Stored Hashes for Dogelog Player

Dogelog Player is a Prolog system for the JavaScript, Python and Java target with libraries mostly written in 100% Prolog. Among the libraries we find tree maps library(util/tree) and hash maps library(util/hash). To speed up hash maps for frozen compounds we introduced precomputed hashes.

Function Pointers

The library adopts a unique design to work around a problem, that our Prolog system is not object oriented. If our Prolog system were object oriented we could adopt the Java contract consisting of .hashCode() and .equals() methods and would have Logtalk style definition:

:- protocol(hashable).

% hash predicate: returns an integer hash for a term
 :- public(hashCode/2).

% equality predicate: succeeds if two terms are equal
 :- public(equals/2).

:- end_protocol.

Our design is such that we drop the Grady Booch classic OO mantra object = state + behaviour. And use the fact that ISO core standard Prolog offers call/n, i.e. higher order logic programming via term closures. So the default constructor hash_new/1 of our hash table reads as follows:

% hash_new(-Hash)
hash_new(R) :-
   hash_new(R, term_hash, ==).

The secondary constructor hash_new/3 accepts two closures, one closure for .hashCode() and one closure for .equals(). The hash table routines are then 100% implemented in Prolog, using the Dogelog Player extension change_arg/3 to provide a destructive version as well.

Stored Hashes

Precomputed hashes can be realized by changing the implementation of the frozen compound data structure. Like the new Dogelog Player specific built-in change_arg/3 for non-frozen compounds, this is an native intervention, for the internal frozen compounds data type:

class Frozen(Structure):
    def __init__(self, functor, args):
        super().__init__(functor, args)
        self.hash = object_hash_code(functor)
        i = 0
        while i < len(args):
            obj = args[i]
            if is_frozen(obj):
                self.hash = int32(self.hash*31 + obj.hash)
            else:
                self.hash = int32(self.hash*31 + object_hash_code(obj))
            i += 1

One might ask whether the additional field .hash is justified or not. From the viewpoint of sharing, it is expected that the field .hash will not occupy much space, since frozen compounds are not copied. Their number is limited by the dynamic database size where frozen compounds live.

def equals(first, second):

    if first is second:
        return True
    if (is_frozen(first) and is_frozen(second) and
          first.hash != second.hash):
        return False

The above code shows a main benefit of the .hash field. One might be familiar with the positive pointer equivalence test, but the new .hash can now be used as a negative test for equality before testing the functor of a compound and entering the arguments of a compound.

term_hash/2 Performance

The challenge here is to make no mistakes. In the end the statically pre-computed hashes have to agree with the dynamically computed hashes by the built-in term_hash/2, since a frozen compound might still be syntactically equivalent to a non-frozen compound. We benchmarked:

/* retrieval+hash */
test3(N) :-
   between(1,1000,_),
   data(N, X),
   term_hash(X, _),
   fail.
test3(_).

Interestingly Python beats JavaScript, we have no explanation. Also SWI-Prolog seems to be extremly slow, again we have no explanation, but it throws light we we only tested lists X of size 5, 10, 15 and 20. We find that SWI-Prolog is linear whereas Dogelog Player is constant time.

The constant time for a frozen compound can be explained since .hash is precomputed. Further for a small Prolog non-frozen compounds that are composed from a constant number of frozen compounds the computation of term_hash/2 is designed so that it will be constant time again.

Distinct Problem

Both Dogelog Player and SWI-Prolog offer a sequence libary that provides a predicate distinct/1. This is a meta predicate that uses a state across Prolog calls to filter solutions that are equal modulo (=@=)/2. While Dogelog Player opted to use hash table, SWI Prolog uses its trie data structure.

To perform the testing we created random dumps with basic arithmetic expressions. The data generation can be coded in Prolog itself with a little help of random/1 built-in. In total we created 100000 rows for a dynamic predicate dump/1. The data and test looks as follows.

?- random_dump.
true.
?- dump(X).
X = 4+(2+((6–0)*(6-(2+2*(8*4))-4)-9))+5*((2-(0+6))*9*7);
X = (0+(0*(1–4)-7)+3*3)*1;
X = 3–2+2+8
Etc..

The test is then to cycle through all the data and an run all solutions through distinct/1. Fetching the data itself might incure some cost, which is mittigated in Dogelog Player since it provides program sharing (PS). Like in our previous testing, we subtracted retrieval timing:

/* retrieval+distinct */
test2 :-
   distinct(dump(_)),
   fail.
test2.

The retrieval itself is only a small time component, we find for the conducted test that program sharing (PS) in Dogelog Player occupies more or less the same time as SWI-Prolog. But the program sharing (PS) has repercussions for copy_term/2 in our distinct/1 realization:

In the above we see the additional benefit of .hash as it will be part of the upcoming release of version 2.1.6 of Dogelog Player. We tested against version 2.1.5 of Dogelog for Java and against SWI-Prolog 10.1.11. It shows that the new stored .hash give us a 2x times speed-up.

Conclusions

Stored .hash values are popular through the Java .hashCode() contract. Prolog systems shy away because of additional memory or in favor of other data structures. We show that they can be also beneficial for frozen compounds and demonstrate a 2x times speed-up for distinct/1.