Boost logo

Boost :

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:
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.
              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,

Boost list run by bdawes at, gregod at, cpdaniel at, john at