How to bind a graph structure?

[Erwan Loisant]

Hello.

I am still in my binding thing; actually the structure I want to bind
is an oriented graph structure (a Galois' Lattice to be precise). So I
have 2 class (as well in C as in Ruby): GaloisNode and GaloisLattice.
Each GaloisNode structure contains links to neighbors.

For now, I wrap my C GaloisLattice structure, and I have observer
methods to look at my nodes. Basically I have a "nodes" methods
returning the list of nodes. And this is the problem.

I just wrap each node into a ruby GaloisNode and return an array
containing all the nodes. Note that since these C objects are used by
the lattice I don't want Ruby to delete them, so I pass "0" as the
argument for the "free" function.

The problem is that if I do that:

myLattice = GaloisLattice.new
[ Adding elements, building a big lattice... ]
allNodes = GaloisLattice.nodes
[ Modifying the lattice, including deleting nodes ]
allNodes

....Then allNodes will contain GaloisNode wrapping a NULL element, which
is bad. Next time I try to access it I get a segfault for sure.

I think that the problem is that my library is written in pure C (and I
would like it to remain an independant C library) and in this library I
create, delete elements and add, remove references; Ruby's garbage
collector doesn't know about these modifications and can not know about
that.

What could be a better design? I there a way to design my C library
better so I can tell Ruby's garbage collector about references without
introducing a Ruby dependency in my library's source code ?

I have thought about returning a copy of node elements instead of
wrapping them, but since each nodes contains references to neighbors I
would have to duplicate the whole graph (which is supposed to grow
big).

 

[Markus]

What could be a better design? I there a way to design my C library
better so I can tell Ruby's garbage collector about references without
introducing a Ruby dependency in my library's source code ?

I'm not sure that this is logically possible to do in a clean way.
You may be able to find a way to do it with no _explicit_ dependencies
on Ruby in your source code (though I don't see how), but only by
introducing some _implicit_ dependencies, e.g. relying on side effects
of the interaction between your code & ruby's to do what you want. This
would be very brittle.

One idea might be to give ruby "handles" of some sort that were
only usable/meaningful via calls to your library. As far as ruby's GC
was concerned, they would just be integers. You would then be able to
manage your storage as you saw fit, and ruby would be able to do
likewise.

-- Markus

 

[Robert Klemme]

I'm not sure that this is logically possible to do in a clean way.
You may be able to find a way to do it with no _explicit_ dependencies
on Ruby in your source code (though I don't see how), but only by
introducing some _implicit_ dependencies, e.g. relying on side effects
of the interaction between your code & ruby's to do what you want. This
would be very brittle.

IMHO this is the typical situation of layering object models: the Ruby
object model (the wrapper instances) sits on top of the C object model and
each Ruby model instance refers to at most one C model instance. The hard
part with this scenario is, as both of you noticed, to deal with object
construction and even more so object destruction.

One idea might be to give ruby "handles" of some sort that were
only usable/meaningful via calls to your library. As far as ruby's GC
was concerned, they would just be integers. You would then be able to
manage your storage as you saw fit, and ruby would be able to do
likewise.

IMHO this is probably the most reasonable approach. Additionally Erwan
should then have some mechanism of verifying the handle stored in a
wrapper object to be able to detect the situation that you have a wrapper
whose corresponding C model instance is gone. Unfortunately you would
have to check the validity in every method that needs the C model instance
or even in *every* method. Alternatively you need some kind of observer
mechanism so your Ruby model instances get to know that their C model
counterparts are gone. But even then you still some other object might
reference the Ruby model instance...

Another issue is aliasing: depending on the application it might be
crucial that you have at most one Ruby model instance per C model
instance, i.e., you want the same representant on the higher level. This
is typically the case when you store additional state in the wrapper
instance. You can handle this with some sort of mapping - but you'll have
to be careful with respect to GC in order to not fix wrapper instances in
mem: You might need a Hash where values are WeakReferences to the wrapping
instances.

This is all not very nice and personally I haven't found a clean, nice and
efficient solution to this issue...

Kind regards

robert

 

[Markus]

IMHO this is probably the most reasonable approach. Additionally Erwan
should then have some mechanism of verifying the handle stored in a
wrapper object to be able to detect the situation that you have a wrapper
whose corresponding C model instance is gone. Unfortunately you would
have to check the validity in every method that needs the C model instance
or even in *every* method. Alternatively you need some kind of observer
mechanism so your Ruby model instances get to know that their C model
counterparts are gone. But even then you still some other object might
reference the Ruby model instance...

Another issue is aliasing: depending on the application it might be
crucial that you have at most one Ruby model instance per C model
instance, i.e., you want the same representant on the higher level. This
is typically the case when you store additional state in the wrapper
instance. You can handle this with some sort of mapping - but you'll have
to be careful with respect to GC in order to not fix wrapper instances in
mem: You might need a Hash where values are WeakReferences to the wrapping
instances.

This is all not very nice and personally I haven't found a clean, nice and
efficient solution to this issue...

If he wants to be truly independent of ruby (so that his library
can be used elsewhere) I would suggest the following:

* Assign each C object a handle (int) on creation.
* Store the handle in the object
* Maintain an index mapping handle --> C object
* Only talk to outsiders in terms of handles
* When an outsider tries to talk to you about a C object, first
check that the handle is valid (via the index)


There are several operations that would need to be implemented in
the library:

* Assigning a handle
* Adding a handle=>object to the index
* Looking up an object given a handle
* Cleaning up the index when an object is deleted
* Detecting if an object is valid

All of them admit to rather simple, time & space efficient
solutions, provided you know what sort of load (lots of lookups, few
creations, or visa versa, etc.) to expect. For example, if deletions
were going to be rare or done all at the end, the index could be a
hierarchical array and:

* Assigning a handle-- this_handle = (next_handle++)
* Adding a handle=>object to the index --
index[this_handle] = this_object
* Looking up an object given a handle -- index[handle]
* Cleaning up the index when an object is deleted --
index[this_handle] = NULL
* Detecting if an object is valid -- index[handle]


If there was going to be more turnover, you could use a hash for
the index, or store an additional id with the object (and in the index)
to detect recycled handles. In effect, the handle becomes a
(slot,version) pair. The later may be a tad faster but a hash is less
ad hoc and might be easier to maintain.

-- Markus

 

[Robert Klemme]

IMHO this is probably the most reasonable approach. Additionally Erwan
should then have some mechanism of verifying the handle stored in a
wrapper object to be able to detect the situation that you have a wrapper
whose corresponding C model instance is gone. Unfortunately you would
have to check the validity in every method that needs the C model
instance
or even in *every* method. Alternatively you need some kind of observer
mechanism so your Ruby model instances get to know that their C model
counterparts are gone. But even then you still some other object might
reference the Ruby model instance...

Another issue is aliasing: depending on the application it might be
crucial that you have at most one Ruby model instance per C model
instance, i.e., you want the same representant on the higher level. This
is typically the case when you store additional state in the wrapper
instance. You can handle this with some sort of mapping - but you'll
have
to be careful with respect to GC in order to not fix wrapper instances in
mem: You might need a Hash where values are WeakReferences to the
wrapping
instances.

This is all not very nice and personally I haven't found a clean, nice
and
efficient solution to this issue...

If he wants to be truly independent of ruby (so that his library
can be used elsewhere) I would suggest the following:

* Assign each C object a handle (int) on creation.
* Store the handle in the object
* Maintain an index mapping handle --> C object
* Only talk to outsiders in terms of handles
* When an outsider tries to talk to you about a C object, first
check that the handle is valid (via the index)


There are several operations that would need to be implemented in
the library:

* Assigning a handle
* Adding a handle=>object to the index
* Looking up an object given a handle
* Cleaning up the index when an object is deleted
* Detecting if an object is valid

All of them admit to rather simple, time & space efficient
solutions, provided you know what sort of load (lots of lookups, few
creations, or visa versa, etc.) to expect. For example, if deletions
were going to be rare or done all at the end, the index could be a
hierarchical array and:

* Assigning a handle-- this_handle = (next_handle++)
* Adding a handle=>object to the index --
index[this_handle] = this_object
* Looking up an object given a handle -- index[handle]
* Cleaning up the index when an object is deleted --
index[this_handle] = NULL
* Detecting if an object is valid -- index[handle]


If there was going to be more turnover, you could use a hash for
the index, or store an additional id with the object (and in the index)
to detect recycled handles. In effect, the handle becomes a
(slot,version) pair. The later may be a tad faster but a hash is less
ad hoc and might be easier to maintain.

Completely ACK! Still, these solutions do not get rid of the problem of
orphaned handles, which renders them somehow ugly. But the ugliness is in
the problem, not in the solution. *sigh*

Kind regards

robert

 

[markus]

On Tue, 2004-10-26 at 02:14, Erwan Loisant wrote:
What could be a better design? I there a way to design my C library
better so I can tell Ruby's garbage collector about references
without
introducing a Ruby dependency in my library's source code ?

One idea might be to give ruby "handles" of some sort that were
only usable/meaningful via calls to your library. As far as ruby's GC
was concerned, they would just be integers. You would then be able to
manage your storage as you saw fit, and ruby would be able to do
likewise.

IMHO this is probably the most reasonable approach. Additionally Erwan
should then have some mechanism of verifying the handle stored in a
wrapper object to be able to detect the situation that you have a wrapper
whose corresponding C model instance is gone. Unfortunately you would
have to check the validity in every method that needs the C model
instance
or even in *every* method. Alternatively you need some kind of observer
mechanism so your Ruby model instances get to know that their C model
counterparts are gone. But even then you still some other object might
reference the Ruby model instance...

Another issue is aliasing: depending on the application it might be
crucial that you have at most one Ruby model instance per C model
instance, i.e., you want the same representant on the higher level. This
is typically the case when you store additional state in the wrapper
instance. You can handle this with some sort of mapping - but you'll
have
to be careful with respect to GC in order to not fix wrapper instances in
mem: You might need a Hash where values are WeakReferences to the
wrapping
instances.

This is all not very nice and personally I haven't found a clean, nice
and
efficient solution to this issue...

If he wants to be truly independent of ruby (so that his library
can be used elsewhere) I would suggest the following:

* Assign each C object a handle (int) on creation.
* Store the handle in the object
* Maintain an index mapping handle --> C object
* Only talk to outsiders in terms of handles
* When an outsider tries to talk to you about a C object, first
check that the handle is valid (via the index)


There are several operations that would need to be implemented in
the library:

* Assigning a handle
* Adding a handle=>object to the index
* Looking up an object given a handle
* Cleaning up the index when an object is deleted
* Detecting if an object is valid

All of them admit to rather simple, time & space efficient
solutions, provided you know what sort of load (lots of lookups, few
creations, or visa versa, etc.) to expect. For example, if deletions
were going to be rare or done all at the end, the index could be a
hierarchical array and:

* Assigning a handle-- this_handle = (next_handle++)
* Adding a handle=>object to the index --
index[this_handle] = this_object
* Looking up an object given a handle -- index[handle]
* Cleaning up the index when an object is deleted --
index[this_handle] = NULL
* Detecting if an object is valid -- index[handle]


If there was going to be more turnover, you could use a hash for
the index, or store an additional id with the object (and in the index)
to detect recycled handles. In effect, the handle becomes a
(slot,version) pair. The later may be a tad faster but a hash is less
ad hoc and might be easier to maintain.

Completely ACK! Still, these solutions do not get rid of the problem of
orphaned handles, which renders them somehow ugly. But the ugliness is in
the problem, not in the solution. *sigh*

Kind regards

robert

Why ACK? This is a pretty standard solution, it works, it's clean
and fast to implement, and does what is needed...and the semantics are a
direct extention of the usual pointer semantics, adding only what is
needed to solve the problem at hand.

Specifically, a pointer is just an integer that (by convention) tells
you how to find the object you want (e.g. that it is so many bytes from
the start of your memory. These handles are just integer that (by the
proposed convention) tell you how to find the object that you want, but
the details of their dereferencing (which can and should be hidden from
the "user") are somewhat different. Why is one more ugly than the other?

As for the orphaned handles, that is the whole point. He wants to
decouple the library from the use of the library in a way that does not
require the library to know anything about ruby's internals. Which means
that it will be possible to have orphaned handles. So a means of
detecting them is needed.

If I write something like:

g = A_graph.new
points.each { |p| g.add_node(p) }
lines.each { |p1,p2| g.add_node(p1,p2) }
x = g.random_unconnected_node
if x
while p = g.random_unconnected_node
g.delete_node(p)
end
end
print x.inspect

I would _expect_ some sort of error in the final print statement, since x
should have been deleted in the while loop, just as I would expect an
error if I tried to cat a file after I deleted it, even if I had written
its name down.

-- Markus

 

[Robert Klemme]

Why ACK?

Um, why not? Is there a problem with my agreement to what you wrote? I
just wanted to add some remarks about the inherent difficulties of this
problem and solution since you didn't mention them explicitely and I
wanted to make sure the OP is aware of them.

Cheers

robert

 

[Sam Roberts]

Quoteing (e-mail address removed), on Wed, Oct 27, 2004 at 05:04:07PM +0900:

Um, why not? Is there a problem with my agreement to what you wrote? I
just wanted to add some remarks about the inherent difficulties of this
problem and solution since you didn't mention them explicitely and I
wanted to make sure the OP is aware of them.

If somebody isn't familiar with this as a protocol element
(ACKnowledged) it sounds like you're puking something up...

It might be a very english-speaking-hacker usage.

Cheers,
Sam

 

[Markus]

Quoteing (e-mail address removed), on Wed, Oct 27, 2004 at 05:04:07PM +0900:

If somebody isn't familiar with this as a protocol element
(ACKnowledged) it sounds like you're puking something up...

It might be a very english-speaking-hacker usage.

Thank you! I was even more puzzled by the response, until I saw
this. Now all is light.

ACK /ak/ interj.

1. [common; from the ASCII mnemonic for 0000110] Acknowledge.
Used to register one's presence (compare mainstream _Yo!_). An
appropriate response to ping or ENQ.

2. [from the comic strip "Bloom County"] An exclamation of
surprised disgust, esp. in "Ack pffft!" Semi-humorous. Generally
this sense is not spelled in caps (ACK) and is distinguished by
a following exclamation point.

3. Used to politely interrupt someone to tell them you
understand their point (see NAK). Thus, for example, you might
cut off an overly long explanation with "Ack. Ack. Ack. I get it
now".

4. An affirmative. "Think we ought to ditch that damn NT server
for a Linux box?" "ACK!"

He was meaning 3) or 4) but I was hearing 2). Thanks.

-- Markus

 

[Robert Klemme]

Sam, thanks for clearing that up!

It might be a very english-speaking-hacker usage.

Thank you! I was even more puzzled by the response, until I saw
this. Now all is light.

ACK /ak/ interj.

1. [common; from the ASCII mnemonic for 0000110] Acknowledge.
Used to register one's presence (compare mainstream _Yo!_). An
appropriate response to ping or ENQ.

2. [from the comic strip "Bloom County"] An exclamation of
surprised disgust, esp. in "Ack pffft!" Semi-humorous. Generally
this sense is not spelled in caps (ACK) and is distinguished by
a following exclamation point.

3. Used to politely interrupt someone to tell them you
understand their point (see NAK). Thus, for example, you might
cut off an overly long explanation with "Ack. Ack. Ack. I get it
now".

4. An affirmative. "Think we ought to ditch that damn NT server
for a Linux box?" "ACK!"

He was meaning 3) or 4) but I was hearing 2). Thanks.

ACK, err, yep, I meant 4. I wasn't aware that it could be misunderstood
as 2 in this context as I thought it's so widely used among IT folks as
short for "ackknowledge".

Btw, do you know "Bloom County"? IMHO a great piece of cartoon artwork.
Too sad, it's not continued. But then again, it's probably quite 80ies and
doesn't fit so well today. Although I'd guess Berke Breathed would have to
say some things about the current US government...

Kind regards

robert

 

[Erwan Loisant]

Thank you for your answers!
I will try to implement this simple garbage collection system.

 

[Joel VanderWerf]

Btw, do you know "Bloom County"? IMHO a great piece of cartoon artwork.
Too sad, it's not continued. But then again, it's probably quite 80ies
and doesn't fit so well today. Although I'd guess Berke Breathed would
have to say some things about the current US government...

Opus lives! At least in the SF Chron, on Sundays. Here's one from B.B.'s
site (last Sunday's was better, but not online, unfortunately):

http://www.berkeleybreathed.com/Images/hamster-GRAB_1.jpg

 

[Robert Klemme]

Opus lives! At least in the SF Chron, on Sundays. Here's one from B.B.'s
site (last Sunday's was better, but not online, unfortunately):

http://www.berkeleybreathed.com/Images/hamster-GRAB_1.jpg

Ah, he's back in business:

http://www.washingtonpost.com/ac2/wp-dyn/A45450-2003Sep8

Welcome back Berke!

robert