[m-dev.] For review: hash table implementation

[Ralph Becket]

>From Fergus Henderson on 05/02/2001 12:18:45
> On 05-Feb-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> > > > int_hash_pred =
> > > >     ( pred(N::in, H1::out, H2::out) is det :-
> > > >         H1 = N * N,
> > > >         H2 = N `xor` (N + N)
> > > >     ).
> > > 
> > > Why not just `H1 = N'?
> > 
> > I perceived (through highly unscientific testing) that this gave a
> > better spread where N is small.  It's a weak justification, so I'll
> > change it back if it offends people :)
> 
> No, that's probably better as is.
> But adding a comment or two here might be nice.

There is in fact a genuine reason for it that I just remembered: the
two hash functions should be independent in the sense that one should
not be a function of the other w.r.t. machine integer arithmetic.
Squaring fits the bill whereas identity doesn't.

> That won't work:
> 
> (1) there's no array__foldl in the current standard library.

I've just added it - I thought I'd put it up for review (although our
e-mail has been in a mess recently).  I'll repost it.

> (2) dynamic cast only works for casting to ground types,
>     not for pattern matching with partially instantiated
>     type patterns, e.g. `array(T)'.  Probably the compiler
>     issued a warning for this.  Read the compiler warnings.
>     Compile again with `-E' and read them again.

Rats.  I recall there's a solution to this problem; I'll dig it up
and apply it.

> >                 HA = munge(munge_factor_a, HA0, HUA),
> >                 HB = munge(munge_factor_b, HB0, HUB)
> 
> The two lines above are duplicated several times; it would be
> nicer to extract the commonality out into a separate predicate
> or function.

Done.

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------