CoW and reference counting in the STL
in [C++]
|
From: Francis Glassborow on 21 Apr 2010 22:08 �� Tiib wrote: > What are you suggesting then? We can either share or we can make > personal copy for everyone who needs one. The fact if they need one > may be expensive to figure out. When it is not about cheap cases like > string then copying may be expensive. The issues are not solved on > generic case (C++ does not even have threads in established standard). > Throwing CoW out of string is good, but throwing it away as generally > obsolete concept feels slightly premature. Basically, if you may need to change the object you need your own one and the cost of delaying the copying is more than most people think (and gets worse with concurrency). If you do not need to change the object and do not mind if someone else does (or know that no one will) then you do not need to copy. So the choices are: Have a single shared but immutable object. Have a single shared object that can be changed but all users need to see the changes Have separate objects (copies) CoW tries to delay the decision but that delay is not cost free. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Seungbeom Kim on 20 Apr 2010 16:59 On 2010-04-20 12:42, �� Tiib wrote: > On Apr 20, 5:37 pm, Mathias Gaunard<loufo...(a)gmail.com> wrote: >> On 18 avr, 23:02, Tiib<oot...(a)hot.ee> wrote: >> >>> For example POSIX fork() >>> implementations are usually cheap thanks to CoW. >> >> Rather, the fork+execvp pattern requires COW with delayed allocation >> (overcommit) to be efficient in both speed and memory usage. And >> overcommit is obviously a serious problem that completely breaks the C >> and C++ languages. > > Interesting. How it breaks C and C++ completely? By pretending that every dynamic allocation (malloc, new and new[]) succeeds by returning a non-NULL pointer even if the system is out of memory, and then crashing the program if the address is used later. That is, by not letting the program to deal with out-of-memory properly. -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Öö Tiib on 22 Apr 2010 13:53 On 22 apr, 16:08, Francis Glassborow <francis.glassbo...(a)btinternet.com> wrote: > �� Tiib wrote: > > What are you suggesting then? We can either share or we can make > > personal copy for everyone who needs one. The fact if they need one > > may be expensive to figure out. When it is not about cheap cases like > > string then copying may be expensive. The issues are not solved on > > generic case (C++ does not even have threads in established standard). > > Throwing CoW out of string is good, but throwing it away as generally > > obsolete concept feels slightly premature. > > Basically, if you may need to change the object you need your own one > and the cost of delaying the copying is more than most people think (and > gets worse with concurrency). Everything costs. What is cheapest is context-dependent. There are no universal ways to share. There are so lot of different already established models of multiprocessing: 1) Intel Threading Building Blocks. Work stealing. 2) OpenMP. Paralleling loops. 3) Thread pool. Short term worker rental. 4) Dedicated threads. Long term background workers and sleeping specialists. Nothing is perfect. It is easy to indicate limitations of each. So there are lot of things to think about and also to measure on each case and in each context. > If you do not need to change the object > and do not mind if someone else does (or know that no one will) then you > do not need to copy. You should be aware when someone else changes that object even if it is read-only for you. Reading locks also hinder things. If it is shared with CoW then that is one way to guarantee that no one can change it. > So the choices are: > > Have a single shared but immutable object. That is corner case of very few inflexible objects that are immutable for everybody. If it is about "temporarily frozen" then you need to put that state onto object. CoW has exactly such state there. > Have a single shared object that can be changed but all users need to > see the changes That does not scale at all. Getting rid of such objects often gains performance in orders of magnitude. > Have separate objects (copies) It means "do not share". Certainly, majority of objects should be like that. Not shared at all. If possible. Not always possible. The threads still share same computer and resources in it. You can not copy whole database for each thread because they may want to write into it. > CoW tries to delay the decision but that delay is not cost free. Nothing is free. CoW does not try anything. It does what it does successfully. CoW writes onto object "this is shared immutable object; if you want to write into such object make a copy". If the flaw is that CoW does it too behind scenes, so the costs are not transparent (like that you may fail the copy with out of memory) then that feature needs to be polished and put up front. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Martin B. on 23 Apr 2010 08:29 Maxim Yegorushkin wrote: > On 20/04/10 15:37, Mathias Gaunard wrote: >> On 18 avr, 23:02, Öö Tiib<oot...(a)hot.ee> wrote: >> >>> For example POSIX fork() >>> implementations are usually cheap thanks to CoW. >> >> Rather, the fork+execvp pattern requires COW with delayed allocation >> (overcommit) to be efficient in both speed and memory usage. And >> overcommit is obviously a serious problem that completely breaks the C >> and C++ languages. > > Interesting that you would mention overcommit as a serious problem. It > is a tunable feature and can be turned on and off. Can't remember though > if I ever needed to turn it off. > When I first heard about overcommit I thought it must be a joke. Now I'm pretty much convinced it is an aberration. I mean - it not even kills the application that caused the OOM to trigger, it just chooses a random process! With regard to C/C++ and overcommit I have one question though: Say we have a process that tries to allocate a 500MB buffer on a 32 bit system. If the address-space of the process is sufficiently fragmented then this can never succeed. Will malloc return 0 in this case, or will it also return a 'valid' address that will just crash the machine if accessed? cheers, Martin -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Öö Tiib on 21 Apr 2010 04:37
On Apr 21, 10:14 am, Mathias Gaunard <loufo...(a)gmail.com> wrote: > On 20 avr, 20:42, �� Tiib <oot...(a)hot.ee> wrote: > > > Interesting. How it breaks C and C++ completely? > > By having malloc or new return a pointer to some memory that has not > yet been allocated, and thus accessing it later may result in a crash, > instead of returning null or throwing an exception. > > > On the other hand trying to achieve same > > effect on Windows using CreateProcess is very inefficent and resource- > > consuming. > > Huh? > On the contrary, CreateProcess is more efficient, it's just that the > function needs to have a lot of parameters to do as many things. Copying all the data of current process is often desirable effect of fork() that is too expensive with CreateProcess(). -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |