Re: faster deep copies?
Re: faster deep copies?
- Subject: Re: faster deep copies?
- From: "Gerriet M. Denkmann" <email@hidden>
- Date: Fri, 15 Feb 2013 09:59:49 +0700
On 15 Feb 2013, at 01:25, Ken Thomases <email@hidden> wrote:
>
>
> On Feb 14, 2013, at 8:30 AM, Uli Kusterer wrote:
>
>> On Feb 14, 2013, at 3:57 AM, Ken Thomases <email@hidden> wrote:
>>> Your question prompted me to try to design an analog of NSKeyedArchiver, NSCode, and NSCoding that would generate the new object graph on the fly as it went instead of producing a data object. The idea is that the copier (the analog of the archiver/coder) would know which objects had already been copied and so would avoid over-duplicating them in the new graph. However, that ends up being hard because each object has to copy its related object before it's complete enough to be registered with the copier. So, it isn't successful in avoiding the potential for infinite recursion.
>>
>> What NSKeyedArchiver probably does is have a dictionary that maps the original object pointer values to the copied objects. So instead of just straight-out copying an object, it does:
>>
>> NSString* theKey = [NSString stringWithFormat: @"%p", theOriginal];
>> id theCopy = [objectCopies objectForKey: theKey];
>> if( !theCopy )
>> {
>> theCopy = [theOriginal copy];
>> [objectCopies setObject: theCopy forKey: theKey];
>> }
>>
>> That way, every object only gets copied once, and the copy re-used in other spots. That may be part of why it is slower. (NB - you could probably use an NSValue +valueWithUnretainedPointer: or whatever as the key, I just quickly typed this untested code into the e-mail)
>
> That's what I considered but it doesn't work. You can't add the copy into the archiver's database of already-copied objects until it's complete. But, for the case where the graph has cycles, making the complete copy will try to make copies of all its related objects first. When the cycle loops back to the same original, that original still does not have a copy in the database, so it tries to make another copy. Infinite recursion.
Why not keep a mutable dictionary M and on encountering an object (in the scanning phase) do:
if object not in mutable dictionary M then
add to M: key = address of object, value = NSNull
continue walking the object tree
else
do nothing
endif
And in the second (copy) phase do:
if value of object = NSNull then copy it and set the value in M to the copied object
else just store a link to the already copied object.
Should work with cycles. Might not be faster than NSArchive.
Kind regards,
Gerriet.
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden