Interesting problem. I bet this is why the erlang folks decided to use mutation-less, copy-everything, so that they didn't have to carefully think through every possible case. Maybe you could write your vm to automatically copy everything, and then have a means of coding exceptions. So, if you find that a certain specific case can share, you can add that to the list of exceptions. Otherwise, it copies, so you don't have to worry about unexpected errors.
And you should probably allow the user to require copying if they need to, so that there aren't any surprises.
As an aside, you mentioned a O(M log N) search to determine whether to share or not. Now maybe I don't understand, but you could use a Bloom filter to determine if the object is present on the other process. The only shortcoming is the false positives, which mean you would copy unnecessarily, but they happen so infrequently that it probably isn't an issue. I believe bloom filters were mentioned on Hacker News yesterday. The link on wikipedia is: http://en.wikipedia.org/wiki/Bloom_filter
Using a bloom filter, you'd be able to in constant time, low memory usage, determine if an item is in a set. In this case the items are shared objects and the set is the objects owned by the target process. Now, maybe I don't understand what you're trying to do, but you can clarify that shortly.
How much are you implementing on the c++ side? Couldn't you get a few basic necessities built first, and then just abstract towards usability in arc? I don't know exactly what you're doing, but I don't see why you have to make everything at once.
