[boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase, response to Bjorn Reese about copy-on-write

Date: Fri, 04 Apr 2014 19:24:53 +0200 From: Bjorn Reese To: boost@lists.boost.org Subject: Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase (Glen Fernandes) Message-ID: <533EEAE5.2040304@mail1.stofanet.dk> Content-Type: text/plain; charset=ISO-8859-1; format=flowed

On 04/04/2014 02:10 PM, Lars Viklund wrote:

...

As for the Copy-on-Write semantics, isn't the general consensus that CoW is a horrible horrible thing and is very hard to get right+fast in the modern world with concurrency?

Yes:

http://www.gotw.ca/publications/optimizations.htm

Hi, Bjorn, 1) Proposed Copy-on-Write (CoW) optimization will be only option. Developer will chose, which container he or she wants: a) without CoW, b) with CoW with internal locks, c) with CoW without internal locks (very dangerous). Option "a" will be the first choise. Option "c" is used either in single-threaded apps or if he/she knows that all shallow copies are maintained in the single thtread or behind single semaphore which protects all shallow copies. 2) The article states mostly that there are ineffective optimizations of CoW. CoW by itself is not that bad. Citation: Plain 1726ms Plain_FastAlloc 642ms COW_Unsafe 1629ms COW_AtomicInt 1949ms COW_CritSec 10660ms COW_Mutex 33298ms e.g., the AtomicInt is 10-15% slower than plain, while Mutex 33 times. 3) There are situations where it's worth. Firstly, mobile/embedded devices are memory greedy. Secondly, small changes in very large arrays, such as text editors. Thirdly, no need to implement "undo" command in text editors, that reduces development time. But I see that community does not appreciate this feature so I do it in the end of my priority list. Best regards, A.K.