From -3610927215815863201 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,25827c9ceb81badc X-Google-Attributes: gidf78e5,public From: herbs@cntc.com (Herb Sutter) Subject: Re: string/cow/algorithm Date: 1998/09/02 Message-ID: <35ee5ff3.1150564574@nr1.toronto.istar.net>#1/1 X-Deja-AN: 387003764 Content-Transfer-Encoding: 7bit Approved: Fergus Henderson References: <35D9AE1C.7553@pratique.fr> <35e47ac7.633205050@nr1.toronto.istar.net> <6s7ejv$q3h$1@shell7.ba.best.com> <35e84662.881936868@nr1.toronto.istar.net> <6selg2$64j$1@shell7.ba.best.com> X-Original-Date: Tue, 01 Sep 1998 22:10:12 GMT Content-Type: text/plain; charset=us-ascii Organization: iSTAR internet Incorporated X-Auth: PGPMoose V1.1 PGP comp.std.c++ iQBFAgUANey64uEDnX0m9pzZAQGTCQF/ecbxiQnAMbZBcvKrlPeJGDV5i0xsUNcs 5MEDHIhkrACHEkiJlXMlPp1zpIzD2vB/ =oYUA Mime-Version: 1.0 Newsgroups: comp.std.c++ Mea culpa. To borrow a phrase, Sutter hates it when he's wrong. The following two replies clearly point out the flaw in my reasoning: phalpern@truffle.ma.ultranet.com (Pablo Halpern) wrote: >If the reference count indicates that the buffer is not shared, >the only way it can be incremented is by copying the only string that >references it. If one thread is trying to read (or copy) the string >while another is modifying it, you have a BUG IN THE PROGRAM, not a bug >in the string class. If two threads access a shared string, they should >use a mutex lock EXTERNAL TO THE STRING ITSELF. ncm@nospam.cantrip.org (Nathan Myers) wrote: >Remember we were comparing CoW against always-deep-copy. Clearly >if two threads are operating on the same visible string object, >you have a conflict, but that is the same for either implementation >strategy. [...] >It is the responsibility of users to manage access to visible objects. >It is the responsibility of the string implementation to make sure >that is sufficient. (This is the same for either strategy.) Thank you. I had one misapprehension, and this disabuses me of it. Specifically: 'If the reference count is one, there are no thread issues and you can go on to mutate the string at will.' The imaginary problem that I thought I saw was that, after the reference count was checked but before the mutation was complete, a copy ctor or assignment could run on another thread and take a copy, which would share the representation and cause nasty problems. Although this is true, the key observation is simply that the other thread could not do so without referring to the same visible string object, in which case it's the calling code's own lookout "to manage access to visible objects" whether COW is used or not. (If thread A is changing string s1, and at the same time thread B tries to execute something like "s2 = s1;", then clearly the calling code must serialize those operations as usual.) Having been thus enlightened, I am now of the opinion that for COW objects in a MT environment where getting and setting the reference count is atomic: 1. Read-only operations NEVER need to consider the reference count. (This relies completely on #3.) 2. If the reference count is 1, possibly-mutating operations NEVER need a lock. 3. If the reference count is greater than 1, possibly-mutating operations need to take their own copy, and then drop into case #2. I see two possible implementations of "if refs > 1, take your own copy": a) Always lock the copying operation. (This always incurs the expense of a lock, but never performs an unnecessary copy.) if( refs > 1 ) { lock.acquire(); if( refs > 1 ) { // do the work of taking a copy --refs; } lock.release(); } b) Never lock the "take a copy" operation. (This allows race conditions whereby two strings sharing a buffer may both take a copy at the same time, causing one unnecessary copy and requiring cleanup of the now-unreferenced original buffer.) if( refs > 1 ) { // do the work of taking a copy if( --refs < 1 ) { // delete original buffer } } Whether (a) or (b) would be more efficient would depend entirely on the likelihood of the race condition succeeding. This requires no additional locks beyond the availability of "atomic get" and "atomic set" operations on the reference count integer. I believe that only 3(b) would additionally require an "atomic set-and-get". If getting and setting the reference count cannot be done atomically, then locks will still be needed for every possibly mutating operation, as I originally pointed out. Better? Followup question (I will do my own research, but comments are welcome): How efficient is a built-in "integer atomic get/set" operation compared to a Win32 critical section (NOT a mutex, those are more expensive)? My observation is that you still need to read the reference count in EVERY possibly-mutating operation, hence there would still be a MT performance penalty for every possibly-mutating operation after all if the "atomic read" isn't highly efficient. Herb --- Herb Sutter (mailto:herbs@cntc.com) Current Network Technologies Corp 2695 North Sheridan Way, Suite 150 www.cntc.com www.peerdirect.com Mississauga Ontario Canada L5K 2N6 --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html ]