From http://www.digitalmars.com/d/garbage.html

"Using pointer values to compute a hash function. A copying garbage collector can arbitrarily move objects around in memory, thus invalidating the computed hash value."

Why then does Object's toHash() method default implementation do exactly that?

uint toHash()
{
return (uint)(void *)this;
}

I was relying on the default toHash() for the value of a key in an associative array.  I guess I should provide my own hash function then?

Thanks!
Brian

Brian Hammond <d at brianhammond dot com> wrote:

<snip>
> Why then does Object's toHash() method default implementation do exactly that?
<snip>
> I was relying on the default toHash() for the value of a key in an associative
> array.  I guess I should provide my own hash function then?

Always a good idea.  Especially if your class has a sense of equality over and above that of being the very same object.

But you're right, Object.toHash is being a bit naughty there.  But is there a better idea?

Maybe it's only meant to be a makeshift, but still....

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

Brian Hammond wrote:

> From http://www.digitalmars.com/d/garbage.html
> 
> "Using pointer values to compute a hash function. A copying garbage collector can arbitrarily move objects around in memory, thus invalidating the computed hash value."

B.t.w: is this "moving around" described more clearly anywhere in the documentation? What exactly happens if the GC moves an object that was allocated by a call to "new"? Does it adjust all references pointing anywhere into that object?

I would assume that this takes quite a bit of intelligence, definitely more than the Boehm GC has. Is there actually any GC out there, that does move objects for defragmentation or some other purpose?

On Tue, 18 May 2004 16:53:43 +0200, Norbert Nemec <Norbert.Nemec@gmx.de> wrote:

> B.t.w: is this "moving around" described more clearly anywhere in the
> documentation?

The current GC implementation doesn't support it.

> What exactly happens if the GC moves an object that was
> allocated by a call to "new"? Does it adjust all references pointing
> anywhere into that object?

Yes, that's how it works.

> I would assume that this takes quite a bit of intelligence, definitely more than the Boehm GC has. Is there actually any GC out there, that does move
> objects for defragmentation or some other purpose?

Walter, once mentioned that he had written such a GC. I don't know how he did it, maybe using something like a dictornary, or a special reference memory pool, so you know where to start the scan to adjust addresses. Maybe the MMU could be used to help too. Just wild guessing...

-- 
Robert M. Münch
Management & IT Freelancer
http://www.robertmuench.de

>> I was relying on the default toHash() for the value of a key in an associative array.  I guess I should provide my own hash function then?
>
>Always a good idea.  Especially if your class has a sense of equality over and above that of being the very same object.

In my case no.. I was simply using Object's toHash() as a convenient way to have
fast lookups (via an associative array) for collections of basic object types
like a delegate.

A contrived example: a class that allows delegates to be registered/unregistered as observers.

alias void delegate(subject) obs_dg;

class subject
{
void register(obs_dg dg) { observers_[dg.toHash()] = dg; }
void unregister(obs_dg dg) { delete observers_[dg.toHash()]; }
//...
private obs_dg[uint] observers_;
}

The key can change due to the GC however so I'll have to use something else like a straight array and have O(n) lookups.  For small n, who cares really.

Thanks,
Brian

>But you're right, Object.toHash is being a bit naughty there.  But is there a better idea?
>
>Maybe it's only meant to be a makeshift, but still....
>
>Stewart.
>
>-- 
>My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

"Brian Hammond" <d at brianhammond dot comBrian_member@pathlink.com> wrote in message news:c8b56i$pro$1@digitaldaemon.com...
> From http://www.digitalmars.com/d/garbage.html
>
> "Using pointer values to compute a hash function. A copying garbage
collector
> can arbitrarily move objects around in memory, thus invalidating the
computed
> hash value."
>
> Why then does Object's toHash() method default implementation do exactly
that?
>
> uint toHash()
> {
> return (uint)(void *)this;
> }
>
> I was relying on the default toHash() for the value of a key in an
associative
> array.  I guess I should provide my own hash function then?

You're right, Object.toHash() is fundamentally broken, and this break will show up if and when a D implementation gets a copying garbage collector.

"Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:c8d81o$12m4$1@digitaldaemon.com...
> B.t.w: is this "moving around" described more clearly anywhere in the
> documentation? What exactly happens if the GC moves an object that was
> allocated by a call to "new"?
> Does it adjust all references pointing
> anywhere into that object?

Yes.

> I would assume that this takes quite a bit of intelligence, definitely
more
> than the Boehm GC has. Is there actually any GC out there, that does move objects for defragmentation or some other purpose?

I've seen a lot of material saying this cannot be done with a language that manipulates pointers like C, C++ and D do, but there is a way to do it.

Walter wrote:

> 
> "Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:c8d81o$12m4$1@digitaldaemon.com...
>> B.t.w: is this "moving around" described more clearly anywhere in the
>> documentation? What exactly happens if the GC moves an object that was
>> allocated by a call to "new"?
>> Does it adjust all references pointing
>> anywhere into that object?
> 
> Yes.
> 
>> I would assume that this takes quite a bit of intelligence, definitely
> more
>> than the Boehm GC has. Is there actually any GC out there, that does move objects for defragmentation or some other purpose?
> 
> I've seen a lot of material saying this cannot be done with a language that manipulates pointers like C, C++ and D do, but there is a way to do it.

What's the core idea behind it? I don't doubt that it can be done somehow, but I wonder how it efficient it would be. Of course, if the GC knows exactly what data is a pointer, it can go through the complete memory and readjust every pointer referencing the memory that has to be moved. Going through the whole memory should not even be the problem in efficiency, but how should the GC know what is a pointer and what is some other data that by chance has the same binary value as a valid pointer? For a plain GC, this is no problem, since misinterpreting random data as pointers will at worst keep alive some data that actually is dead.

Norbert Nemec wrote:

> Walter wrote:
> 
>> 
>> "Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:c8d81o$12m4$1@digitaldaemon.com...
>>> B.t.w: is this "moving around" described more clearly anywhere in the
>>> documentation? What exactly happens if the GC moves an object that was
>>> allocated by a call to "new"?
>>> Does it adjust all references pointing
>>> anywhere into that object?
>> 
>> Yes.
>> 
>>> I would assume that this takes quite a bit of intelligence, definitely
>> more
>>> than the Boehm GC has. Is there actually any GC out there, that does move objects for defragmentation or some other purpose?
>> 
>> I've seen a lot of material saying this cannot be done with a language that manipulates pointers like C, C++ and D do, but there is a way to do it.
> 
> What's the core idea behind it? I don't doubt that it can be done somehow, but I wonder how it efficient it would be. Of course, if the GC knows exactly what data is a pointer, it can go through the complete memory and readjust every pointer referencing the memory that has to be moved. Going through the whole memory should not even be the problem in efficiency, but how should the GC know what is a pointer and what is some other data that by chance has the same binary value as a valid pointer? For a plain GC, this is no problem, since misinterpreting random data as pointers will at worst keep alive some data that actually is dead.

Here's my guess:
if the GC can tell what is an object reference (for example by allocating
from special heaps that store only objects) then it can get at the class
info and the class info can store a mask that tells the GC which fields can
be updated if the referant is moved.

That would mean dynamic arrays don't get moved and pointers to structs (well, actually, pointers in general) don't get moved.

-Ben

So Walter, if I understand correctly, the current Object.toHash() implementation
is valid with the current garbage collector but would be broken using a new,
copying collector.  If and when the GC impl. is updated, will Object.toHash() be
updated as well?  I'd imagine yes, Object.toHash() will always work correctly
else it should be abstract :)

Just wondering if I need to rewrite code now, when the GC impl. changes, or never.  Thanks.

Brian

In article <c8r874$2tvd$1@digitaldaemon.com>, Ben Hinkle says...
>
>Norbert Nemec wrote:
>
>> Walter wrote:
>> 
>>> 
>>> "Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:c8d81o$12m4$1@digitaldaemon.com...
>>>> B.t.w: is this "moving around" described more clearly anywhere in the
>>>> documentation? What exactly happens if the GC moves an object that was
>>>> allocated by a call to "new"?
>>>> Does it adjust all references pointing
>>>> anywhere into that object?
>>> 
>>> Yes.
>>> 
>>>> I would assume that this takes quite a bit of intelligence, definitely
>>> more
>>>> than the Boehm GC has. Is there actually any GC out there, that does move objects for defragmentation or some other purpose?
>>> 
>>> I've seen a lot of material saying this cannot be done with a language that manipulates pointers like C, C++ and D do, but there is a way to do it.
>> 
>> What's the core idea behind it? I don't doubt that it can be done somehow, but I wonder how it efficient it would be. Of course, if the GC knows exactly what data is a pointer, it can go through the complete memory and readjust every pointer referencing the memory that has to be moved. Going through the whole memory should not even be the problem in efficiency, but how should the GC know what is a pointer and what is some other data that by chance has the same binary value as a valid pointer? For a plain GC, this is no problem, since misinterpreting random data as pointers will at worst keep alive some data that actually is dead.
>
>Here's my guess:
>if the GC can tell what is an object reference (for example by allocating
>from special heaps that store only objects) then it can get at the class
>info and the class info can store a mask that tells the GC which fields can
>be updated if the referant is moved.
>
>That would mean dynamic arrays don't get moved and pointers to structs (well, actually, pointers in general) don't get moved.
>
>-Ben