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

Subject: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase, response to Bjorn Reese about copy-on-write
From: Alexander Kuprijanov (alexkupri_at_[hidden])
Date: 2014-04-06 07:44:52

> Date: Fri, 04 Apr 2014 19:24:53 +0200
> From: Bjorn Reese <breese_at_[hidden]>
> To: boost_at_[hidden]
> Subject: Re: [boost] Proposal: Vector-like container, which takes
> 	O(log(N)) for insert/erase (Glen Fernandes)
> Message-ID: <533EEAE5.2040304_at_[hidden]>
> 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.