However, there may be some clever trick to implement COW efficiently. Sounds like a Ph.D. thesis to me... :-)
-Urs
I sent a message about NewtonScript and copy-on-write on the 12th, but it doesn't look like it got through :(.
How about a blend of indirect access and the pointer redirection. Only use indirect access for objects that use copy-on-write (i.e. objects that still inherit some slots from a prototype). Once an object's slots are all copied, you redirect the pointers once to the new object.
For example, make a stub object with an inheriting slot to the COW object. This object inherits from the prototype and grows new slots as needed. You guarantee that the only pointer to the COW object is the stub, this way, you don't need to use addSlotsIfAbsent:, you can just make a new object, copy the old slots, and reassign the stub's pointer to the new object. When the COW object copies the last slot, you do a define: to make the stub effectively become the COW object.
This gives you the benefit of COW objects when you need them, at the expense of indirect access.
-- Bill Burdick burdick@ars.rtp.nc.us
However, there may be some clever trick to implement COW efficiently. Sounds like a Ph.D. thesis to me... :-)
-Urs
To which Bill Burdick (burdick@ars.rtp.nc.us) writes:
I sent a message about NewtonScript and copy-on-write on the 12th, but it doesn't look like it got through :(.
I also wonder whether my original message got through (other than to Urs) - all replies so far have been to Urs' reply to it.
How about a blend of indirect access and the pointer redirection. Only use indirect access for objects that use copy-on-write (i.e. objects that still inherit some slots from a prototype). Once an object's slots are all copied, you redirect the pointers once to the new object.
This is essentially a sub-case of the "form factoring" I suggested, except the factoring (ie. reduction of duplicate forms) is only done against the form of the prototype object, and not the entire tree of derivatives. At first this suggests a possible speedup - the form need be compared only if the number of slots == that of the parent. The actual slot identities still need to be checked since some of the slots making up the total count could have been explicitly added to the object, and of course the comparison is still not linear-time because even if no new slots are defined the order of automatic slot addition might be different than the order in which they were defined in the prototype. But I think the cases where *all* deferred slots get ultimately defined will be far fewer than those for which only a subset get defined, and that factoring should happen at every slot addition.
I hope I haven't confused the issue by getting my terminology wrong (my copies of the Self Report are packed and inaccessible at present): By "form" I mean the underlying "pseudo-classes" that SELF maintains to factor out the structure of multiple objects' data slots from their individual slot values. Please correct me if I mis-remembered the term!
For example, make a stub object with an inheriting slot to the COW object. This object inherits from the prototype and grows new slots as needed. You guarantee that the only pointer to the COW object is the stub, this way, you don't need to use addSlotsIfAbsent:, you can just make a new object, copy the old slots, and reassign the stub's pointer to the new object. When the COW object copies the last slot, you do a define: to make the stub effectively become the COW object.
I don't see the need for the stub object; addSlotsIfAbsent: takes care of copying the remainder of the slots while preserving object identity. Or perhaps I'm misunderstanding your example.
This gives you the benefit of COW objects when you need them, at the expense of indirect access.
If slot-cacheing is performed, the expense should be small, no?
- JJ Larrea (jjl@panix.com)
I don't see the need for the stub object; addSlotsIfAbsent: takes care of copying the remainder of the slots while preserving object identity. Or perhaps I'm misunderstanding your example.
[...]
- JJ Larrea (jjl@panix.com)
My understanding of addSlotsIfAbsent: is that it first creates a copy of the object with the additional slots added and then walks through all of memory to reassign the pointers from the old one to the new one. I think Urs was referring to this point when he said:
The problem with COW is that there's no straightforward efficient implementation. For example, if an assignment grows an object, the implementation has to make up a new object and redirect all pointers to the old object. That's only fast if you use indirect pointers (i.e., an object table), which is acceptable for an interpreter but slows down a compiled system quite a bit.
However, there may be some clever trick to implement COW efficiently. Sounds like a Ph.D. thesis to me... :-)
So my solution (a stub object until you're finished growing, then an addSlotsIfAbsent) was a blend of the indirect and the direct methods.
Later, Dave said:
A Lieberman-style system (with copy-on-write) avoids the non-concrete traits problem but makes it harder to express shared state-- how do you know when NOT to copy-on-write?
If you want per slot selection of COW, then you can do this by using stubs with only selected slots added to them. The other are implicitly copied over. One possible definition (my Self is VERY rusty, so this may have errors):
[assume that there is a primitive called 'smash: a And: b' that concatenates a and b into a third object -- maybe there already is such a primitive...]
stub objects have an assignable inheriting slot called 'cow' to hold the new slots and a slot called slotsLeft, which holds the number of slots left to copy, so that we know when to convert the stub to the real object.
traits for cow objects:
(| copySlot: aSlot = ( cow: smash: cow And: aSlot. checkGrowth. ). checkGrowth = ( (slotsLeft: slotsLeft - 1) isZero ifTrue: [Define: cow]. ). |)
prototype for a brick:
(| color = red. color: aValue = (copySlot: (| color <- aValue. |)). weight = 1. weight: aValue = (copySlot: (| weight <- aValue. |)). |)
--------------
I think this should do the trick. I'm pretty sure that inheritence will 'do the right thing' with this setup, too..
-- Bill Burdick burdick@ars.rtp.nc.us
self-interest@lists.selflanguage.org
-
Bill Burdick -
J.J. Larrea