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?
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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk