Object identity

Object identity

[Lars Brinkhoff]

(Would emacs-devel be a more appropriate list to post this?)

Is there a function, say object-identity, in Emacs Lisp that maps an
object to a unique value (other than the object itself)?  For example,
the value could be an integer, or a list of integers, or a string,
that represents the memory address of the object.

To clarify, this function would have the property that
    (equal (object-identity obj1) (object-identity obj2))
if and only if
    (eq obj1 obj2)
. 

This is my current implementation.  However, my version of Emacs
doesn't implement weak hash tables, so it will make memory leak.
Any ideas about how to deal with that?

    (defvar object-identities (make-hash-table :test 'eq :weakness t))
    
    (defvar identity-counter 0)
    
    (defun object-identity (object)
      (or (gethash object object-identities)
          (setf (gethash object object-identities)
                (incf identity-counter))))

(Yes, I'm aware the counter will eventually wrap around...)

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/

Re: Object identity

[Stefan Monnier]

> (Would emacs-devel be a more appropriate list to post this?)
> Is there a function, say object-identity, in Emacs Lisp that maps an
> object to a unique value (other than the object itself)?  For example,

I don't think there's such a thing, although it'd be easy to add given the
current non-copying GC.  On another hand, I'm wondering what you want it
for.  The only use I know of for such a feature is to implement a hash-table
with a cheap hash function, but obviously, that's not your goal since that
is already provided.


        Stefan

Re: Object identity

[Barry Margolin]

In article <mailman.2049.1066716515.21628.help-gnu-emacs@gnu.org>,
Lars Brinkhoff  <lars@nocrew.org> wrote:
>(Would emacs-devel be a more appropriate list to post this?)
>
>Is there a function, say object-identity, in Emacs Lisp that maps an
>object to a unique value (other than the object itself)?  For example,
>the value could be an integer, or a list of integers, or a string,
>that represents the memory address of the object.
>
>To clarify, this function would have the property that
>    (equal (object-identity obj1) (object-identity obj2))
>if and only if
>    (eq obj1 obj2)
>. 

I'm not sure it's possible to write such a function without significant
overhead.

Suppose it just returns the object's address as an integer.  This satisfies
the requirement

  (eq obj1 obj2) -> (equal id1 id2)

But then the object gets GC'ed, and a new object is allocated at the same
address.  When you ask for the new object's identity, you'll get the same
value as was previously returned for the old object, even though the
objects are not eq.

So let's try augmenting it with additional information, like a timestamp.
This obviously can't be the time that object-identity was called, because
then it will be different every time.  It needs to be something associated
with the object itself, like the time it was created or the time that
object-identity was first invoked on it.  This implies that every object
needs to have a slot to store its creation time.  As a result, the size of
every object will have to grow by at least 4 bytes.  Assuming cons cells
are 8 bytes, this means increasing the space they use by 50%.  Since most
objects in memory will never have object-identity called on them, this
space is mostly wasted.

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Re: Object identity

[Stefan Monnier]

> So let's try augmenting it with additional information, like a timestamp.
> This obviously can't be the time that object-identity was called, because
> then it will be different every time.  It needs to be something associated
> with the object itself, like the time it was created or the time that
> object-identity was first invoked on it.  This implies that every object
> needs to have a slot to store its creation time.  As a result, the size of
> every object will have to grow by at least 4 bytes.  Assuming cons cells
> are 8 bytes, this means increasing the space they use by 50%.  Since most
> objects in memory will never have object-identity called on them, this
> space is mostly wasted.

But since Java has such a function and Java is an attention-grabber, people
have been working on clever ways to implement this efficiently.

I still have no clue what it's useful for, so I tend to find such research
rather pointless.  But I'm probably just missing the point.


        Stefan

Re: Object identity

[Barry Margolin]

In article <jwvekx67ex4.fsf-monnier+gnu.emacs.help@vor.iro.umontreal.ca>,
Stefan Monnier  <monnier@iro.umontreal.ca> wrote:
>I still have no clue what it's useful for, so I tend to find such research
>rather pointless.  But I'm probably just missing the point.

The OP explained what it's useful for: emulating weak hash tables in a
system that doesn't have them built in.  If you use ordinary hash tables,
then using an object as a key will prevent it from ever becoming garbage,
which is like a memory leak.

If implementing an identity function like the one the OP requests results
in every object being larger (due to a design like the one I described),
it's likely that this overhead will be much greater than the memory leak in
his application.  So the net result is that he would be better off letting
the memory leak.

Another possibility is to implement an application-specific object-identity
function.  If all the objects that the application needs to deal with are
implemented as lists or structures, he can add an id-code slot to all of
them.  The object-identity function can maintain a counter, and store the
current value into this slot into the object if it's not filled in yet.
This way, the overhead cost is only paid for the few objects that need it,
rather than every Lisp object.

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Re: Object identity

[Stefan Monnier]

>> I still have no clue what it's useful for, so I tend to find such research
>> rather pointless.  But I'm probably just missing the point.

> The OP explained what it's useful for: emulating weak hash tables in a
> system that doesn't have them built in.

That's not how I understood his article.  He seemed to say that he
currently uses an implementation of object-identity which relies
on a weak hash-table but that his Emacs's doesn't implement weakness.
I.e. he seemed to say he needed weak hash-tables to implement
oject-identity, not the other way around.

Furthermore, all the systems I know of that offer something like
`object-identity' also offer weak hash-tables.  Ah... maybe Java
uses object-identity to implement some of its hash-table libraries,
thus justifying the work done on object-identity?
Still if that's the only use, it seems stupid to work on object-identity
rather than just provide the has-table functionality directly.

> If implementing an identity function like the one the OP requests results
> in every object being larger (due to a design like the one I described),

There are various tricks possible to pay only for objects on which
object-identity was called.  It makes `object-identity' slower, of course.

> it's likely that this overhead will be much greater than the memory leak in
> his application.

If the application is long running a 50% overhead can still be
significantly better than a memory leak.


        Stefan

Re: Object identity

[Stefan Monnier]

> I don't think there's such a thing, although it'd be easy to add given the
> current non-copying GC.  On another hand, I'm wondering what you want it

Actually, easier to add would be an `object<' comparison function
which would be equivalent to
(lambda (o1 o2) (< (object-identity o1) (object-identity o2))


        Stefan

Re: Object identity

[Barry Margolin]

In article <jwv3cdm7d8k.fsf-monnier+gnu.emacs.help@vor.iro.umontreal.ca>,
Stefan Monnier  <monnier@iro.umontreal.ca> wrote:
>>> I still have no clue what it's useful for, so I tend to find such research
>>> rather pointless.  But I'm probably just missing the point.
>
>> The OP explained what it's useful for: emulating weak hash tables in a
>> system that doesn't have them built in.
>
>That's not how I understood his article.  He seemed to say that he
>currently uses an implementation of object-identity which relies
>on a weak hash-table but that his Emacs's doesn't implement weakness.
>I.e. he seemed to say he needed weak hash-tables to implement
>oject-identity, not the other way around.

I just reread it and you're correct.

>> it's likely that this overhead will be much greater than the memory leak in
>> his application.
>
>If the application is long running a 50% overhead can still be
>significantly better than a memory leak.

50% overhead on every object versus leaking something like 1% of objects.
I think I'd prefer the latter.

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Re: Object identity

[Lars Brinkhoff]

Barry Margolin <barry.margolin@level3.com> writes:
> Lars Brinkhoff  <lars@nocrew.org> wrote:
> >Is there a function, say object-identity, in Emacs Lisp that maps an
> >object to a unique value (other than the object itself)?  For example,
> >the value could be an integer, or a list of integers, or a string,
> >that represents the memory address of the object.
> I'm not sure it's possible to write such a function without significant
> overhead.

Right, I didn't consider that garbage collection (in general) can move
things around.

Stefan Monnier <monnier@iro.umontreal.ca> writes:
> > The OP explained what it's useful for: emulating weak hash tables in a
> > system that doesn't have them built in.
> That's not how I understood his article.  He seemed to say that he
> currently uses an implementation of object-identity which relies on
> a weak hash-table but that his Emacs's doesn't implement weakness.

Right, that's what I meant.

> I.e. he seemed to say he needed weak hash-tables to implement
> oject-identity, not the other way around.

Well, either I need weak hash tables, or a different implementation
of object-identity.

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/

Re: Object identity

[Lars Brinkhoff]

Stefan Monnier <monnier@iro.umontreal.ca> writes:
> > Is there a function, say object-identity, in Emacs Lisp that maps an
> > object to a unique value (other than the object itself)?
> I'm wondering what you want it for.

In the implementation of Common Lisp's print-unreadable-object when
:identity t is supplied.

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/

Re: Object identity

[Barry Margolin]

In article <mailman.2095.1066762882.21628.help-gnu-emacs@gnu.org>,
Lars Brinkhoff  <lars@nocrew.org> wrote:
>Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> > Is there a function, say object-identity, in Emacs Lisp that maps an
>> > object to a unique value (other than the object itself)?
>> I'm wondering what you want it for.
>
>In the implementation of Common Lisp's print-unreadable-object when
>:identity t is supplied.

AFAIK, there's no guarantee that the same object will print identically
over time.  Most implementations just display the object's current address;
if the GC moves it, the next time it's printed it will be different.  And
it's also possible for two different objects to display identically; in
between the two PRINT-UNREADABLE-OBJECT calls the GC could copy one of them
into the location that the other one used to occupy.

Anyway, there's a reason why Common Lisp requires that
PRINT-UNREADABLE-OBJECT be built into the implementation.  We didn't want
to expose an interface to getting these not-quite-unique identifiers.
They're not much use for anything other than this one function; if we
provided the API, users would undoubtedly misuse it.

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Re: Object identity

[Lars Brinkhoff]

Barry Margolin <barry.margolin@level3.com> writes:
> In article <mailman.2095.1066762882.21628.help-gnu-emacs@gnu.org>,
> Lars Brinkhoff  <lars@nocrew.org> wrote:
> >Stefan Monnier <monnier@iro.umontreal.ca> writes:
> >> > Is there a function, say object-identity, in Emacs Lisp that maps an
> >> > object to a unique value (other than the object itself)?
> >> I'm wondering what you want it for.
> >In the implementation of Common Lisp's print-unreadable-object when
> >:identity t is supplied.
> AFAIK, there's no guarantee that the same object will print identically
> over time.  Most implementations just display the object's current address;
> if the GC moves it, the next time it's printed it will be different.

Excellent, then the functionality I would need shouldn't that hard to
implement.

> Anyway, there's a reason why Common Lisp requires that
> PRINT-UNREADABLE-OBJECT be built into the implementation.  We didn't
> want to expose an interface to getting these not-quite-unique
> identifiers.  They're not much use for anything other than this one
> function; if we provided the API, users would undoubtedly misuse it.

I have no desire to get the not-quite-unique identifiers in Common
Lisp.  I want to implement PRINT-UNREADABLE-OBJECT in Emacs Lisp.

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/

Re: Object identity

[Barry Margolin]

In article <mailman.2101.1066765792.21628.help-gnu-emacs@gnu.org>,
Lars Brinkhoff  <lars@nocrew.org> wrote:
>Barry Margolin <barry.margolin@level3.com> writes:
>> Anyway, there's a reason why Common Lisp requires that
>> PRINT-UNREADABLE-OBJECT be built into the implementation.  We didn't
>> want to expose an interface to getting these not-quite-unique
>> identifiers.  They're not much use for anything other than this one
>> function; if we provided the API, users would undoubtedly misuse it.
>
>I have no desire to get the not-quite-unique identifiers in Common
>Lisp.  I want to implement PRINT-UNREADABLE-OBJECT in Emacs Lisp.

I understand that.  My point was that just as PRINT-UNREADABLE-OBJECT has
to be part of the implementation in CL, your requested object-identity
function would have to be part of the Emacs Lisp implementation.  I don't
think there's any way to write this function in Emacs Lisp, it needs to be
a primitive in the C code that implements the Lisp interpreter.

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Re: Object identity

[Stefan Monnier]

> Well, either I need weak hash tables, or a different implementation
> of object-identity.

Given your particular situation, you can just flush your hash-table at the
end of print-unreadable-object, so it does not even need to be weak.


        Stefan

Re: Object identity

[Lars Brinkhoff]

Stefan Monnier <monnier@iro.umontreal.ca> writes:
> > Well, either I need weak hash tables, or a different implementation
> > of object-identity.
> Given your particular situation, you can just flush your hash-table at the
> end of print-unreadable-object, so it does not even need to be weak.

Yes, but that would print eq objects differently between two
subsequent calls to print-unreadable-object, which probably would
confuse the user.  I might almost as well print "0" for all object
identities.

Flushing somewhat less often (for some value of "less") would be good
enough, I think.  It's not like all objects are in the hash table, so
the memory overhead isn't large.

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/

Re: Object identity

[Stefan Monnier]

>> > Well, either I need weak hash tables, or a different implementation
>> > of object-identity.
>> Given your particular situation, you can just flush your hash-table at the
>> end of print-unreadable-object, so it does not even need to be weak.
> Yes, but that would print eq objects differently between two
> subsequent calls to print-unreadable-object, which probably would
> confuse the user.

Might be confusing, but after all, it's a behavior that can appear
even with a "real" implementation of print-unreadable-object.

Another possibility is to print a random number, which simulates the
behavior were a copying GC is called everytime and moves everything around
all the time.


        Stefan

Re: Object identity

[Barry Margolin]

In article <jwv7k2y5mpb.fsf-monnier+gnu.emacs.help@vor.iro.umontreal.ca>,
Stefan Monnier  <monnier@iro.umontreal.ca> wrote:
>>> > Well, either I need weak hash tables, or a different implementation
>>> > of object-identity.
>>> Given your particular situation, you can just flush your hash-table at the
>>> end of print-unreadable-object, so it does not even need to be weak.
>> Yes, but that would print eq objects differently between two
>> subsequent calls to print-unreadable-object, which probably would
>> confuse the user.
>
>Might be confusing, but after all, it's a behavior that can appear
>even with a "real" implementation of print-unreadable-object.

The point of the hash table is to remember the ID between calls to
print-unreadable-object, so that the same object will usually be printed
the same way.  If you flush it at the end of each call, it will never
contain anything!

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Re: Object identity

[Lars Brinkhoff]

Barry Margolin <barry.margolin@level3.com> writes:
> Lars Brinkhoff  <lars@nocrew.org> wrote:
> >I have no desire to get the not-quite-unique identifiers in Common
> >Lisp.  I want to implement PRINT-UNREADABLE-OBJECT in Emacs Lisp.
> I understand that.  My point was that just as PRINT-UNREADABLE-OBJECT has
> to be part of the implementation in CL, your requested object-identity
> function would have to be part of the Emacs Lisp implementation.

Well, unless real storage addresses are needed, a weak hash table
could also to a way to implement object-identity, right?

> I don't think there's any way to write this function in Emacs Lisp,
> it needs to be a primitive in the C code that implements the Lisp
> interpreter.

I might try to add such a primitive in the future.

Thanks to you and Stefan Monnier for your thoughtful replies.

-- 
Lars Brinkhoff,         Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting    http://www.brinkhoff.se/

Re: Object identity

[jan]

Lars Brinkhoff <lars@nocrew.org> writes:

> This is my current implementation.  However, my version of Emacs
> doesn't implement weak hash tables, so it will make memory leak.
> Any ideas about how to deal with that?

Have you tried using property lists?

-- 
jan

Re: Object identity

[jan]

jan <janmar@iprimus.com.au> writes:

> > This is my current implementation.  However, my version of Emacs
> > doesn't implement weak hash tables, so it will make memory leak.
> > Any ideas about how to deal with that?
> 
> Have you tried using property lists?

Scrap that idea, it wont work.

Unfortunately, I didn't see the obvious until after I posted. =(

-- 
jan