Re: Simple copy-on-write framework
Ulrich Eckhardt wrote:
Joe Seigh wrote:
You probably get not a few comments to check out String implementations
that use COW with reference counting.
IIRC, COW std::strings mostly suffer from the fact that operator[] returns
a mutable C++ reference which is obviously totally ignorant of the COW
schemes behind it, so making it provably correct requires more copying
than it usually would. Or is it even impossible considering the required
interface? I don't remember.
I just thought I'd mention them if you weren't aware of them but you seem
to be.
However, my idea is rather geared to a Java-like design (I think, I'm
rather ignorant of Java otherwise) where you have immutable strings and,
when you need to modify one, a stringbuffer. Java of course uses GC
instead of refcounting, but that shouldn't make a difference.
Probably not relevant here.
A totally different issue is of course that the locking overhead of the
refcounter might be bigger than the gains in avoiding copies. [1]
illustrates the issue quite well. However, in my case the objects are
large, and containing several sub-objects that also use dynamically
allocated memory (containers, strings).
Yes or no depending on how you do it.
[snip various questions which hopefully get answered below]
Some examples to illustrate (this is pseudocode, doesn't follow
all the C++ conventions used here, probably won't compile, and
not all methods are shown).
template<typename T> class COWObj {
private:
atomic_ptr<T> handle;
Mutex mutex;
public:
sometype read() {
local_ptr<T> lpObj;
sometype temp;
lpObj = handle; // get current instance (1 interlocked instruction)
temp = lpObj->read(); // execute non threadsafe read on immutable instance
of object
lpObj = 0; // optional, dtor will drop ref also (1 interlocked
instruction.
}
void update() {
T * newInstance;
mutex.lock();
newInstance = handle->clone();
newInstance->update(); // non threadsafe update on private instance
handle = new atomic_ptr<T>(newInstance); // replace *current* instance,
lock guarantees this
mutex.unlock();
}
// lock-free update using compare and swap (not compatible w/ locked
version)
void update2() {
T * newInstance;
atomic_ptr<T> xchg = 0; // CAS exchange pointer
local_ptr<T> cmp = 0; // CAS compare pointer
do {
cmp = handle; // current instance
newInstance = cmp->clone();
newInstance->update(); // non threadsafe update on private instance
xchg = new atomic_ptr<T>(newInstance);
}
while (!handle.cas(cmp, xchg)); // attempt to replace if current instance
hasn't changed
}
};
If you use shared_ptr you have to use locking on every copy of a shared
shared_ptr.
atomic_ptr doesn't require this. For instance, the read method using shared
pointer
will need at least 3 interlocked instructions, 1 for the lock (assuming
unlock
is a simple store w/ membar) and 2 for the increment and decrement of
refcount.
local_ptr only requires 2 for the refcount "increment" and "decrement".
Plus
it won't block unless the base dtor blocks.
There are other PDR (PCOW Deferred Reclaimation) schemes which don't use any
interlocked instructions at all.
Re atomic_ptr, Sun is patenting it AFAIK, so if you want to use it you will
have to wait and see what they do with it.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]