Re: in praise of tabling

Nick Wedd wrote:
> I wish I could find a
> simple, Clocksin & Mellish-level, tutorial on how tabling works and
how
> to use it.

Well, tabling is, to a first order approximation, Prolog-speak for
memoization. I think the Mercury Reference Manual section on it
says all you need to get the gist in a few paragraphs:
http://www.mercury.cs.mu.oz.au/information/doc-latest/mercury_ref/Tabled-evaluation.html

In a nutshell, a tabled predicate is associated with a hash table of
some kind. Whenever a new result for the predicate is computed, the
result is recorded in the hash table. When the predicate is invoked
the hash table is first consulted to see if the answer(s) is (are)
already known; if so, they can be returned immediately. Otherwise,
if there is no entry in the hash table then the predicate proper must
be evaluated to obtain a result.

The decision as to whether a predicate should be tabled or not depends
upon whether the cost of recomputation outweighs the cost of checking
the hash table and the cost of having the hash table in memory.

-- Ralph

.

Relevant Pages

  • Re: Suggestions for double-hashing scheme
    ... >> managing the hash table is very low. ... > Irrelevant to the point about the relative costs of comparing, hashing, ... the cost of these sorts. ... > if 75% of the lookups hit on the first try. ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... >>> Once you sufficiently optimize a hash table, the big cost in hashing ... >>> by computing of the hash function). ... Irrelevant to the point about the relative costs of comparing, hashing, ...
    (comp.programming)
  • Re: maintenance of hash tables.
    ... than masks, typically they are not a significant portion of the overall ... will be a significant cost associated with the hash function. ... various other costs (checking if the spot is free, ...
    (comp.programming)
  • Re: maintenance of hash tables.
    ... typically they are not a significant portion of the overall ... will be a significant cost associated with the hash function. ... I observe a much smaller ratio between TRUNCATE and + ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... >> Once you sufficiently optimize a hash table, the big cost in hashing ... >> by computing of the hash function). ... any good hash function basically always has a minimal ... >> What you want is for each of these entries to have a different reprobe ...
    (comp.programming)