Hashing on System.Address

Hashing on System.Address

[Duncan Sands]

Does anyone have an efficient portable algorithm for hashing
on a System.Address?

The Ada 2005 package Ada.Containers defines Hash_Type as

	type Hash_Type is mod implementation-defined;

This is the target type I would like for the hash.

Thanks a lot,

Duncan.

Re: Hashing on System.Address

[Mark Lorenzen]

Duncan Sands <baldrick@free.fr> writes:

> Does anyone have an efficient portable algorithm for hashing
> on a System.Address?
> 
> The Ada 2005 package Ada.Containers defines Hash_Type as
> 
> 	type Hash_Type is mod implementation-defined;
> 
> This is the target type I would like for the hash.
> 
> Thanks a lot,
> 
> Duncan.

You can always convert a value of type System.Address to a value of a
signed or modular (implementation-defined) type. That should help when
you want to hash it into a value of type Hash_Type.

- Mark Lorenzen

Re: Hashing on System.Address

[Matthew Heaney]

Duncan Sands wrote:
> Does anyone have an efficient portable algorithm for hashing
> on a System.Address?
>
> The Ada 2005 package Ada.Containers defines Hash_Type as
>
> 	type Hash_Type is mod implementation-defined;
>
> This is the target type I would like for the hash.

Use System.Storage_Elements.To_Integer to convert the address to an
Integer_Address, and then convert that to type Hash_Type.

Re: Hashing on System.Address

[Robert A Duff]

"Matthew Heaney" <mheaney@on2.com> writes:

> Duncan Sands wrote:
> > Does anyone have an efficient portable algorithm for hashing
> > on a System.Address?
> >
> > The Ada 2005 package Ada.Containers defines Hash_Type as
> >
> > 	type Hash_Type is mod implementation-defined;
> >
> > This is the target type I would like for the hash.
> 
> Use System.Storage_Elements.To_Integer to convert the address to an
> Integer_Address, and then convert that to type Hash_Type.

It might be a good idea to divide that by 8, since most addresses have
zeros in the low three bits.

- Bob

Re: Hashing on System.Address

[Matthew Heaney]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> "Matthew Heaney" <mheaney@on2.com> writes:
> > Use System.Storage_Elements.To_Integer to convert the address to an
> > Integer_Address, and then convert that to type Hash_Type.
> 
> It might be a good idea to divide that by 8, since most addresses have
> zeros in the low three bits.

Good idea.  The other thing I haven't really figured out is what to do
if you have a 64-bit address, and Hash_Type is only 32.  Ideally you'd
like to compute a 32-bit hash value that uses all 64 bits of the
address.

Alternatively, you could use the ordered container, since type
System.Address has a less than ("<") relational operator.

Re: Hashing on System.Address

[Duncan Sands]

Hi Matthew,

> Use System.Storage_Elements.To_Integer to convert the address to an
> Integer_Address, and then convert that to type Hash_Type.

that's what I'm doing.  But there's no guarantee that they have the
same size, so it's not portable.  It's easy enough to thunk Integer_Address
to a modular type (which I'll also call Integer_Address here).  If
Integer_Address is smaller than or equal to Hash_Type then there's no
problem.  If it's larger then you can do some bit rotation, but it's surprisingly
awkward to do when you don't know the sizes in advance.  I was hoping
someone knew how to do this in a clean way.

All the best,

Duncan.

Re: Hashing on System.Address

[Duncan Sands]

Hi Mark,

> You can always convert a value of type System.Address to a value of a
> signed or modular (implementation-defined) type. That should help when
> you want to hash it into a value of type Hash_Type.

yes that helps - thanks for the suggestion.  In fact that is what I'm already
doing.  The problem is the next part...  That can be simplified to: I have two
modular types (binary modulus), but I don't know their modulus.  Values of
the first type should be hashed into values of the second type.  This can be
done (I've done it) but somehow the code is much more horrible than I feel
it should be.  One annoying point is that a program with a static expression
that would raise Constraint_Error is illegal, even if you would never get to the
Contraint_Error raising part in run-time.  If you don't understand the relevance
of this remark, try to code this kind of hash thing yourself and you will soon
see :)

Thanks again,

Duncan.

Re: Hashing on System.Address

[Duncan Sands]

> Good idea.  The other thing I haven't really figured out is what to do
> if you have a 64-bit address, and Hash_Type is only 32.  Ideally you'd
> like to compute a 32-bit hash value that uses all 64 bits of the
> address.

Yes, that's the problem.  In fact to be portable the code should work
regardless of which type has the bigger modulus.

> Alternatively, you could use the ordered container, since type
> System.Address has a less than ("<") relational operator.

I considered that, but since I'm sure to want to hash on addresses one
day, it seemed like a good idea to bite the bullet and come up with a
good solution now.

By the way, is there any reason why Ada.Containers doesn't provide some
standard hash functions?  I reckon hashing on strings and on addresses
would be pretty handy.

Ciao,

Duncan.

Re: Hashing on System.Address

[Larry Kilgallen]

In article <wcc3brlrfj5.fsf@shell01.TheWorld.com>, Robert A Duff <bobduff@shell01.TheWorld.com> writes:
> "Matthew Heaney" <mheaney@on2.com> writes:
> 
>> Duncan Sands wrote:
>> > Does anyone have an efficient portable algorithm for hashing
>> > on a System.Address?
>> >
>> > The Ada 2005 package Ada.Containers defines Hash_Type as
>> >
>> > 	type Hash_Type is mod implementation-defined;
>> >
>> > This is the target type I would like for the hash.
>> 
>> Use System.Storage_Elements.To_Integer to convert the address to an
>> Integer_Address, and then convert that to type Hash_Type.
> 
> It might be a good idea to divide that by 8, since most addresses have
> zeros in the low three bits.

Or it might not be, since he said portable.  Looking at addresses of
_instructions_ (which are the closest to that pattern) on the machine
architectures on which VMS runs:

	VAX - No restriction, 1 bit (odd and even) just as likely to be
		one as the other
	Alpha - 4 byte boundary, 4 bit (100) just as likely to be one
		as the other
	Itanium - 8 byte boundary for VLIW instructions, but in software
		the last octet of the address is 0, 1 or 2 depending on
		which instruction in the bundle is addressed.

Re: Hashing on System.Address

[Larry Kilgallen]

In article <u8y1dllt8.fsf@earthlink.net>, Matthew Heaney <matthewjheaney@earthlink.net> writes:
> Robert A Duff <bobduff@shell01.TheWorld.com> writes:
> 
>> "Matthew Heaney" <mheaney@on2.com> writes:
>> > Use System.Storage_Elements.To_Integer to convert the address to an
>> > Integer_Address, and then convert that to type Hash_Type.
>> 
>> It might be a good idea to divide that by 8, since most addresses have
>> zeros in the low three bits.
> 
> Good idea.  The other thing I haven't really figured out is what to do
> if you have a 64-bit address, and Hash_Type is only 32.  Ideally you'd
> like to compute a 32-bit hash value that uses all 64 bits of the
> address.

I think ignoring the high bits is better than ignoring the low bits,
since most data sets are likely to be somewhat localized.

Re: Hashing on System.Address

[Alex R. Mosteo]

Duncan Sands wrote:

> By the way, is there any reason why Ada.Containers doesn't provide some
> standard hash functions?  I reckon hashing on strings and on addresses
> would be pretty handy.

Out of Containers hierarchy: Ada.Strings.Hash

Re: Hashing on System.Address

[Duncan Sands]

> > By the way, is there any reason why Ada.Containers doesn't provide some
> > standard hash functions?  I reckon hashing on strings and on addresses
> > would be pretty handy.
> 
> Out of Containers hierarchy: Ada.Strings.Hash

Thanks a lot - I hadn't spotted that.

Best wishes,

Duncan.

Re: Hashing on System.Address

[Duncan Sands]

> > By the way, is there any reason why Ada.Containers doesn't provide some
> > standard hash functions?  I reckon hashing on strings and on addresses
> > would be pretty handy.
> 
> Out of Containers hierarchy: Ada.Strings.Hash

You know, this implementation advice sounds pretty silly:

Implementation Advice
7/2
     The various Hash functions should be good hash functions, returning a wide spread of values for different string values. It should be unlikely for similar strings to return the same value.

As if any implementor needs to be told that they should use a "good" rather than a "bad"
hash function!

Ciao,

d.

Re: Hashing on System.Address

[Marius Amado Alves]

> ... The other thing I haven't really figured out is what to do
> if you have a 64-bit address, and Hash_Type is only 32...

I gave a general solution to this class of cases before:

<<
Treat both the input and output values as bit strings X (1 .. M) and Y 
(1 .. N) respectively. (Use representation clauses, packed arrays, and 
unchecked conversion for this.) Make N small, say 16. Set Y bits to the 
value of X bits as follows:

if M > N, Y (J) = X (1 + (J - 1) * M / N), for J in 1 .. N

if M = N, Y = X

if M < N, initialize Y to all zeros,
  then let Y (1 + (I - 1) * N / M) = X (I), for I in 1 .. M
 >>

Re: Hashing on System.Address

[Duncan Sands]

On Tuesday 14 June 2005 12:03, Marius Amado Alves wrote:
> > ... The other thing I haven't really figured out is what to do
> > if you have a 64-bit address, and Hash_Type is only 32...
> 
> I gave a general solution to this class of cases before:
> 
> <<
> Treat both the input and output values as bit strings X (1 .. M) and Y 
> (1 .. N) respectively. (Use representation clauses, packed arrays, and 
> unchecked conversion for this.) Make N small, say 16. Set Y bits to the 
> value of X bits as follows:
> 
> if M > N, Y (J) = X (1 + (J - 1) * M / N), for J in 1 .. N
> 
> if M = N, Y = X
> 
> if M < N, initialize Y to all zeros,
>   then let Y (1 + (I - 1) * N / M) = X (I), for I in 1 .. M
>  >>

Hi Marius, thanks for the suggestion.  A few comments though:
if M > N (say M = 2*N) then you're skipping every second bit
in X.  Why not use them - mix them in somehow?  If M < N then
you are trying to spread the bits of X evenly throughout Y.  Are
there any theoretical reasons to think this is a good strategy?
Finally, I'm betting the code produced is kind of yucky.  It would
be nice to have a solution that resulted in a small number of
simple bit operations.

All the best,

Duncan.

Re: Hashing on System.Address

[Marius Amado Alves]

On 14 Jun 2005, at 11:14, Duncan Sands wrote:

> On Tuesday 14 June 2005 12:03, Marius Amado Alves wrote:
>>> ... The other thing I haven't really figured out is what to do
>>> if you have a 64-bit address, and Hash_Type is only 32...
>>
>> I gave a general solution to this class of cases before:
>>
>> <<
>> Treat both the input and output values as bit strings X (1 .. M) and Y
>> (1 .. N) respectively. (Use representation clauses, packed arrays, and
>> unchecked conversion for this.) Make N small, say 16. Set Y bits to 
>> the
>> value of X bits as follows:
>>
>> if M > N, Y (J) = X (1 + (J - 1) * M / N), for J in 1 .. N
>>
>> if M = N, Y = X
>>
>> if M < N, initialize Y to all zeros,
>>   then let Y (1 + (I - 1) * N / M) = X (I), for I in 1 .. M
>>>>
>
> Hi Marius, thanks for the suggestion.  A few comments though:
> if M > N (say M = 2*N) then you're skipping every second bit
> in X.  Why not use them - mix them in somehow?

Yes, I thought of that, namely picking every slice of M / N bits of the 
input and convert it to 1 bit. Example for M = 2 * N: 00 => 0, 01 => 0, 
10 => 1, 11 => 1. But see below.

>   If M < N then
> you are trying to spread the bits of X evenly throughout Y.  Are
> there any theoretical reasons to think this is a good strategy?

Intuition + experimentation. "Guess first, prove later" (Poincaré) I 
tested my function against GNAT's. Dispersion was equivalent. Speed 
also I if I remember correctly. That's proof enough for me. That's why 
I didn't advance to the slice variant just above.

Re: Hashing on System.Address

[Marius Amado Alves]

Now more "theoretically", for my bit-based hash function, output 
dispersion is clearly dependent on input dispersion. I tested it with 
text strings (Latin-1) and it did well. But for skewed domains like 
memory addresses it may not work as good. In these cases it is indeed 
smarter to use whatever knowledge you have of the skewdness e.g. cut 
out invariant bits. Note the two methods can work in tandem: first cut 
out invariant bits, then use my function to zoom in or out to the 
output size.

Re: Hashing on System.Address

[Duncan Sands]

> It might be a good idea to divide that by 8, since most addresses have
> zeros in the low three bits.

Hi Bob, if the number of hash buckets is a prime number (not equal to 2),
so the actual bucket chosen is the hash value mod a prime, then I guess
dividing by 8 won't make any difference...

Ciao,

D.

Re: Hashing on System.Address

[Matthew Heaney]

Duncan Sands wrote:
> > Use System.Storage_Elements.To_Integer to convert the address to an
> > Integer_Address, and then convert that to type Hash_Type.
>
> that's what I'm doing.  But there's no guarantee that they have the
> same size, so it's not portable.

Even if the Integer_Address type is 64 bits, that doesn't necessarily
mean To_Address will return values > 2**32.  The easiest thing is to do
is just throw away the upper 32 bits of of the integer value, and then
convert that to type Hash_Type.

Yes, then means you won't have a perfect hash function, but that's
typical for hash functions anyway.  (The Birthday Paradox applies to
hash functions too, I think.)

You might want to post your question on comp.compilers or one of the OS
newgroups.  This is most probably a solved problem.

-Matt

Re: Hashing on System.Address

[Duncan Sands]

Hi Matthew,

> Even if the Integer_Address type is 64 bits, that doesn't necessarily
> mean To_Address will return values > 2**32.  The easiest thing is to do
> is just throw away the upper 32 bits of of the integer value, and then
> convert that to type Hash_Type.

that's exactly what I did, with some tricks to get around RM4.9.34.
 
> ...You might want to post your question on comp.compilers or one of the OS
> newgroups.  This is most probably a solved problem.

I'm sure it is solved.  I had expected solutions to be well known, but
apparently they are not.

Thanks for your help,

Duncan.

Re: Hashing on System.Address

[Pascal Obry]

Duncan Sands <baldrick@free.fr> writes:

> As if any implementor needs to be told that they should use a "good" rather
> than a "bad" hash function!

It is always good to state things clearly even if evident at some point by
some people :)

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Hashing on System.Address

[Randy Brukardt]

"Duncan Sands" <baldrick@free.fr> wrote in message
news:mailman.25.1118740226.17633.comp.lang.ada@ada-france.org...
> > > By the way, is there any reason why Ada.Containers doesn't provide
some
> > > standard hash functions?  I reckon hashing on strings and on addresses
> > > would be pretty handy.
> >
> > Out of Containers hierarchy: Ada.Strings.Hash
>
> You know, this implementation advice sounds pretty silly:
>
> Implementation Advice
> 7/2
>      The various Hash functions should be good hash functions, returning a
wide spread of values for different string values. It should be unlikely for
similar strings to return the same value.
>
> As if any implementor needs to be told that they should use a "good"
rather than a "bad"
> hash function!

We'd have preferred to say something stronger, and normatively, but there
doesn't seem to be a way to describe what a hash function does, other than
returning a value of Hash_Type that depends of the argument. So we use IA to
describe what the intent is; IA can be informal and use undefined terms like
"good".

Without the IA, the only indication that this is a hash function is the
name. That wouldn't be enough. And if you don't know what a hash function
is, the IA will be helpful.

                                    Randy.

Re: Hashing on System.Address

[Randy Brukardt]

"Duncan Sands" <baldrick@free.fr> wrote in message
news:mailman.22.1118733848.17633.comp.lang.ada@ada-france.org...
> Hi Mark,
>
> > You can always convert a value of type System.Address to a value of a
> > signed or modular (implementation-defined) type. That should help when
> > you want to hash it into a value of type Hash_Type.
>
> yes that helps - thanks for the suggestion.  In fact that is what I'm
already
> doing.  The problem is the next part...  That can be simplified to: I have
two
> modular types (binary modulus), but I don't know their modulus.  Values of
> the first type should be hashed into values of the second type.  This can
be
> done (I've done it) but somehow the code is much more horrible than I feel
> it should be.  One annoying point is that a program with a static
expression
> that would raise Constraint_Error is illegal, even if you would never get
to the
> Contraint_Error raising part in run-time.  If you don't understand the
relevance
> of this remark, try to code this kind of hash thing yourself and you will
soon
> see :)

That's one of the reasons that Ada 2006 adds the "Mod" attribute. You could
use that to discard any extra bits. (If you want to keep them, well, that
gets messier.).

So I'd use something like:

    if Integer_Address'Last < Hash_Type'Modulus then
            return Hash_Type'Mod(Addr);
    elsif Integer_Address'Last / Hash_Type'Modulus < Hash_Type'Modulus then
            return Hash_Type'Mod(Addr) xor Hash_Type'Mod(Addr /
Hash_Type'Modulus);
    else
            raise Program_Error;
    end if;

You could of course continue to handle larger multiples in the same way.

I don't remember if those static expressions are illegal because of typing.
That can be fixed by making sure the entire expression is of type
Universal_Integer:

    if Integer_Address'Pos(Integer_Address'Last) < Hash_Type'Modulus then
            return Hash_Type'Mod(Addr);
    elsif Integer_Address'Pos(Integer_Address'Last) / Hash_Type'Modulus <
Hash_Type'Modulus then
            return Hash_Type'Mod(Addr) xor Hash_Type'Mod(Addr /
Hash_Type'Modulus);
    else
            raise Program_Error;
    end if;

                                   Randy.

Re: Hashing on System.Address

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> We'd have preferred to say something stronger, and normatively, but there
> doesn't seem to be a way to describe what a hash function does, other than
> returning a value of Hash_Type that depends of the argument. So we use IA to
> describe what the intent is; IA can be informal and use undefined terms like
> "good".

Right.  Given any Hash function, I can construct a data set that will
make it "bad".  Therefore, we have to use informal terms in describing
"goodness".

- Bob

Re: Hashing on System.Address

[Duncan Sands]

> >      The various Hash functions should be good hash functions, returning a
> wide spread of values for different string values. It should be unlikely for
> similar strings to return the same value.
> >
> > As if any implementor needs to be told that they should use a "good"
> rather than a "bad"
> > hash function!
> 
> We'd have preferred to say something stronger, and normatively, but there
> doesn't seem to be a way to describe what a hash function does, other than
> returning a value of Hash_Type that depends of the argument. So we use IA to
> describe what the intent is; IA can be informal and use undefined terms like
> "good".
> 
> Without the IA, the only indication that this is a hash function is the
> name. That wouldn't be enough. And if you don't know what a hash function
> is, the IA will be helpful.

How about this then:

"The various Hash functions should return a wide spread of values for different
string values. It should be unlikely for similar strings to return the same value."

Ciao,

D.

Re: Hashing on System.Address

[Duncan Sands]

Hi Randy,

> That's one of the reasons that Ada 2006 adds the "Mod" attribute. You could
> use that to discard any extra bits. (If you want to keep them, well, that
> gets messier.).

I didn't know about 'Mod - it will certainly be useful.  Luckily GNAT seems to have
implemented it.

> So I'd use something like:
...

Interesting suggestion!

Thanks again,

Duncan.