[devector] optimum growing/insertion policy
Hi, Much an worthy discussion has taken place with respect to growing and insertion policies of boost::double_ended::devector. I think I can justify what the optimum policy is when the overall goal is to minimize number of element movements. What follows is *not* a formal optimality proof, though it's my hunch one could be provided relatively easily. Assumptions * The cost of allocating new memory is negligible when compared to the cost of moving elements around (either intra-buffer or when migrating to a new buffer); so, the growing/insertion policy should focus on minimizing number of elements moved. This implies fully occupying free space before reallocation is *not* the primary goal of the growing/insertion policy. * For the purposes of our discussion, we consider an ever-growing devector without intervening erasures --erasures can be accomodated later as we will see. * Element insertion is modelled as a process where each new insertion happens at a random position within the current devector. The minimal characterization (i.e. its 1st moment in stochastic process theory terminology) is just the percentage R of insertions that happen within the right half of the devector --we call these *right insertions*; left insertions happen then with a frequency L=1-R. push_back is a right insertion, push_front a left insertion. Facts * When a right insertion arrives, if there's free back capacity the optimum insertion policy is to shift elements to the right, as this involves fewer movements than the other way around. The symmetrical applies for left insertions. * If a right insertion at position N arrives and there's no free back capacity (but there is free front capacity), we have only two options: A. Reallocate to get back free capacity. B. Shift elements to the left. The key observation here is that A is cheaper in the long run: as the scenario is one of an ever-growing sequence, reallocation will happen eventually and we can just amortize it in our analysis, so reallocating early saves us the extra movements incurred when left shifting on a right insertion, namely N - (size()-N) = 2*N - size() movements. In fact, we save more than that as insertion is done simultaneously with reallocation, hence no shifting occurs additionally to the (amortized) reallocation cost. All this analysis applies symmetrically to left insertions, of course. * The optimum growing policy is that which maximizes the probability that *both* front and back free capacities get exhausted at the same time. With our 1st moment characterization of the insertion random process, this implies that when reallocating a percentage R of the new space should be devoted to the right side, and a percentage L to the left side. Description of resulting policy * Fix the growing factor to G (this can be 1.5 or 2 or anything greater than one, the actual figure is orthogonal to the discussion). * Maintain a counter right_ of right insertions that gets incremented when a right insertion occurs and *decremented* when an erasure is issued past the middle of the devector. * Right insertions trigger right shifting except when there's no back free capacity, in which case a reallocation is performed. * Left insertions trigger left shifting except when there's no front free capacity, in which case a reallocation is performed. * Reallocation reserves space for G*size() elements: of the resulting G*size()-size() free space, a fraction right_/size() is devoted to back free capacity, the rest to front free capacity. In practice, we may want to keep some minimum space at each end as determined by some empirical threshold. And that's it. Comments welcome. Joaquín M López Muñoz
hi Joaquin, Thanks for this. Some comments below. Assumptions * The cost of allocating new memory is negligible when compared to the cost of moving elements around (either intra-buffer or when migrating to a new buffer); so, the growing/insertion policy should focus on minimizing number of elements moved. This implies fully occupying free space before reallocation is *not* the primary goal of the growing/insertion policy. ——- But in the real world allocations (+ the implied deallocation ) is not that cheap, especially not with non trivial destructors. For small containers, typical for flat containers, I’m not sure this is a good assumption. Facts * When a right insertion arrives, if there's free back capacity the optimum insertion policy is to shift elements to the right, as this involves fewer movements than the other way around. The symmetrical applies for left insertions. * If a right insertion at position N arrives and there's no free back capacity (but there is free front capacity), we have only two options: A. Reallocate to get back free capacity. B. Shift elements to the left. The key observation here is that A is cheaper in the long run: as the scenario is one of an ever-growing sequence, reallocation will happen eventually and we can just amortize it in our analysis, so reallocating early saves us the extra movements incurred when left shifting on a right insertion, namely N - (size()-N) = 2*N - size() —— How do you get that number ? I would say we save Incur 1/2 * size movements on average for shifting to the end with free space. Description of resulting policy * Fix the growing factor to G (this can be 1.5 or 2 or anything greater than one, the actual figure is orthogonal to the discussion). * Maintain a counter right_ of right insertions that gets incremented when a right insertion occurs and *decremented* when an erasure is issued past the middle of the devector. * Right insertions trigger right shifting except when there's no back free capacity, in which case a reallocation is performed. * Left insertions trigger left shifting except when there's no front free capacity, in which case a reallocation is performed. * Reallocation reserves space for G*size() elements: of the resulting G*size()-size() free space, a fraction right_/size() is devoted to back free capacity, the rest to front free capacity. In practice, we may want to keep some minimum space at each end as determined by some empirical threshold. And that's it. Comments welcome. —-____ Interesting analysis. Thanks. I agree if the sequence is ever growing, it’s better to allocate when one end is full. The idea of keeping track of left right insertions also interesting. It does assume additionally that the insert pattern in the future is the same as in the past, right? I think in the case where the user has called reserve, it’s a little problematic that insert may allocate anyway. That is, for many uses there is no infinitely growing sequence . The right_ member can become larger than size if elects are added to the right and removed from the left, not sure what to do about that. It will also make operations slower, but that can be tested. Kind regards Thorsten -- Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html
El 15/10/2017 a las 15:50, thorsten.ottosen via Boost escribió:
hi Joaquin,
Thanks for this. Some comments below.
Assumptions
* The cost of allocating new memory is negligible when compared to the cost of moving elements around (either intra-buffer or when migrating to a new buffer); so, the growing/insertion policy should focus on minimizing number of elements moved. This implies fully occupying free space before reallocation is *not* the primary goal of the growing/insertion policy. — But in the real world allocations (+ the implied deallocation ) is not that cheap, especially not with non trivial destructors. For small containers, typical for flat containers, I’m not sure this is a good assumption.
The assumption is of an ever growing sequence. That said, I recorgnize there are scenarios not falling under this, most notably FIFO queues. I've given the policy a little more thought and think we can twist it to also accommodate non-growing scenarios, please keep on reading.
Facts
[...] * If a right insertion at position N arrives and there's no free back capacity (but there is free front capacity), we have only two options: A. Reallocate to get back free capacity. B. Shift elements to the left. The key observation here is that A is cheaper in the long run: as the scenario is one of an ever-growing sequence, reallocation will happen eventually and we can just amortize it in our analysis, so reallocating early saves us the extra movements incurred when left shifting on a right insertion, namely N - (size()-N) = 2*N - size()
— How do you get that number ? I would say we save Incur 1/2 * size movements on average for shifting to the end with free space.
The number follows from: assume right insertion is at position N, that means that under normal conditions (there's back free capacity) we need to make size()-N movements to the right. If instead of that we shift to the left the resulting number of movements is N, so the penalty for taking the "wrong" decision is the difference N - (size()-N) = 2*N - size(). Did I explain myself now? The worst case is when N is right at the end of the sequence (N=size()) and there's no free space at the back, the penalty is then N - (size()-N) = size(), that is, we have to shift the entire sequence to the left (in which case it's clear that reallocating would have been a better decision).
Description of resulting policy
[...]
—
Interesting analysis. Thanks. I agree if the sequence is ever growing, it’s better to allocate when one end is full.
The idea of keeping track of left right insertions also interesting. It does assume additionally that the insert pattern in the future is the same as in the past, right?
I think in the case where the user has called reserve, it’s a little problematic that insert may allocate anyway. That is, for many uses there is no infinitely growing sequence .
The right_ member can become larger than size if elects are added to the right and removed from the left, not sure what to do about that.
Yes, you're right. right_ becoming greater thatn size() can't happen under the ever- growing assumtion, but it certainly can in the real world. Let's slightly adjust the policy as follows. I think this copes with the ever-growing and fixed-size scenarios equally well. Let us remember that the goal when reserving new free space at both front and back is to make it so that both ends get exhausted at the same time --if they ever are. * Fix the growing factor to G. * The right balancing factor B is defined as the ratio between back free capacity and total free capacity. Let's say this is 50% at the start, that is, we have front_free_capacity()= back_free_capacity(). * Right insertions and left insertions shift to the right and left, respectively (as before). * When reallocation is needed, calculate the new balance factor as a function of front and back space consumption just prior to reallocation. Pseudocode follows: struct free_space { std::size_t back,front }; free_space new_space(free_space original,free_space remaining) { float balance=(float)std::max(original.back-remaining.back,0)/ (original.back+original.front-remaining.back-remaining.front); // denominator can't be 0 std::size_t new_space=std::max(size()*G,size()+remaining.back+remaining.front), new_free_space=new_space-size(); return {balance*new_free_space,(1-balance)*new_free_space}; } This has the effect that if no insertions happened at one end (more precisely, more erasures than insertions took place at that end) then the new reserved space for that end will be zero. Safe guards may be applied. * When reallocation results in the same total space being reserved (this happens when the size at reallocation time is equal or less than the size() at the last reallocation), there is no need to request memory and we can simply shift the sequence so that back and front free capacity are adjusted according to new_space calculations. This nicely handles the FIFO scenario, for instance: when the growing side meets its end, reallocaton resolves to shifting the entire sequence within the current buffer so that space is kept at that end: this keeps cycling forever with no memory allocation and minimal element shifting. Thougths? Joaquín M López Muñoz
El 15/10/2017 a las 17:59, Joaquin M López Muñoz escribió:
[...]
float balance=(float)std::max(original.back-remaining.back,0)/ (original.back+original.front-remaining.back-remaining.front); // denominator can't be 0
This should be float balance=(float)std::max(original.back-remaining.back,0)/ (std::max(original.back-remaining.back,0)+std::max(original.front-remaining.front,0); Joaquín M López Muñoz
On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
The assumption is of an ever growing sequence. That said, I recorgnize there are scenarios not falling under this, most notably FIFO queues. I've given the policy a little more thought and think we can twist it to also accommodate non-growing scenarios, please keep on reading.
Thougths?
I think that the default (we could have other policies) should be simple and similar to vector/string/stable_vector/etc.... In this sense, capacity() and reserve(), if provided, should make sense. If we reallocate depending on the free capacity of one side, then capacity() and reserve() make no sense to the user I think the user expects capacity() as the maximum number of insertions, in any position, that will be accepted before reallocating. Making free_capacity = capacity() - size(), less than, say, back_free_capacity() will be really hard to understand by users. I propose a simple strategy: Definitions: --------- capacity() = the size of the buffer free_capacity() = capacity() - size() xxx_free_capacity() = the number of unconstructed items in the xxx (xxx = left or right) side of the buffer. N = the number of items to be inserted GF = growth factor Strategy: --------- 1) devector is initialized with equal free capacity for both ends. 2) If a xxx (xxx = left or right) insertion is needed and xxx_free_capacity >= the number of items to be inserted, a xxx insertion is done (minimizes moves). 3) Otherwise if a xxx (xxx = left or right) insertion is needed and xxx_free_capacity < N, the sequence containing new plus old elements should be placed in the middle of the buffer. (Note: This step should be limited if amortized constant time is desired for push_xxx insertions) 4) Otherwise if the allocator supports in-place expansion, the buffer is expanded for max(size()+N, capacity()*GF) and if successful, steps 2 or 3 are performed depending on the new xxx_free_capacity value. 5) Otherwise a new buffer is allocated and the new sequence containing new plus old elements should be placed in the middle of the buffer. For uniformly distributed random insertions on both ends, very few extra movements will be done. This means it's amortized constant time, just like vector. Worst case: for a repeated one-side insertion, when N/2 insertions are performed, the first relocation step will take place. In general, log(N/2) relocation steps (each one with a increasing number of moves) will be performed before reallocating a new buffer. I don't think it's amortized constant time, but amortized logarithmic time (but see below). Extra moves can be reduced by imposing a capacity() that is a factor (say reallocation factor, RF) of the buffer size, forcing to reallocation when the load factor is high. This means that if size() is capacity() = RF*internal_buffer_size, even if there is room for the left/right insertions a reallocation will be performed. This means that capacity() = RF*internal buffer is known and means something to the user. Memory usage will grow, but data movement will be minimized. RF could be a policy-based parameter. I think the RF factor obtains an amortized constant time for one side insertion if that property is considered useful. It's equivalent to reduce the number of relocations to a to a fixed number of steps, so the average movement to insert N elements in a devector of capacity C = N/RF is proportional to N. For a quick example (number might be wrong, but you get the idea) of a repeated push_back: If relocation steps are limited to 3, which happens with RF = 15/16, we need N = 15/16 C moves to insert new elements, plus C/2 + 3/4*C + 7/8*C moves to move already inserted elements. This means something like N + 17/8*C = N + 17/8*N/RF = 49/15*N = 3,26*N moves. A fast choice would be to allow just two relocations, a RF of 7/8 = (0,87) which would mean aprox. 2,6*N moves to push_back N elements. A RF of 3/4 (0.75, single relocation step) would mean 1,33*N moves to push_back N elements. Statistics based policies seem more complex, and I don't know how well they will adapt to pattern changes thorough the lifetime of the container, plus they impose a size cost to the container. I wouldn't make the the default choice, as the average user should easily understand the default policy. For a FIFO, I think a deque that reuses free segment capacity on one side and transfers it to the other side before allocating new memory would be the best choice. Currently boost::container::deque does not do this, but pull requests are welcome ;-) Best, Ion
Den 16-10-2017 kl. 01:45 skrev Ion Gaztañaga via Boost:
On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
The assumption is of an ever growing sequence. That said, I recorgnize there are scenarios not falling under this, most notably FIFO queues. I've given the policy a little more thought and think we can twist it to also accommodate non-growing scenarios, please keep on reading.
Thougths?
I think that the default (we could have other policies) should be simple and similar to vector/string/stable_vector/etc....
Yes, let's keep it simple.
I propose a simple strategy:
Definitions: ---------
capacity() = the size of the buffer free_capacity() = capacity() - size() xxx_free_capacity() = the number of unconstructed items in the xxx (xxx = left or right) side of the buffer. N = the number of items to be inserted GF = growth factor
Strategy: ---------
1) devector is initialized with equal free capacity for both ends.
I assume that implies reserve() does the very same?
2) If a xxx (xxx = left or right) insertion is needed and xxx_free_capacity >= the number of items to be inserted, a xxx insertion is done (minimizes moves). 3) Otherwise if a xxx (xxx = left or right) insertion is needed and xxx_free_capacity < N, the sequence containing new plus old elements should be placed in the middle of the buffer. (Note: This step should be limited if amortized constant time is desired for push_xxx insertions)
There might be some corner cases here. Suppose we have front_free_capacity() == 3, back_free_capacity() == 0 and is about to insert to the right half. Does it then make sense to place elements in the middle? If we shift by one element position we pay (on average) size * 3/4 moves If we move to the middle, we have to move everything and pay size * moves We now have two (average) insertions to gain the lost moves before we allocate. One will be in the left side, so has no impact. The other insertion will now take size * 1/4 moves if we placed in the middle and size * 3/4 moves if we shifted. So shifting leads to size * 6/4 moves and moving to the middle leads to size * 5/4 moves. So I agree, we should probably always move to the middle if the free space >= 3 (at the other end). This applies to situations where reallocating is not desired.
Worst case: for a repeated one-side insertion, when N/2 insertions are performed, the first relocation step will take place. In general, log(N/2) relocation steps (each one with a increasing number of moves) will be performed before reallocating a new buffer. I don't think it's amortized constant time, but amortized logarithmic time (but see below).
Extra moves can be reduced by imposing a capacity() that is a factor (say reallocation factor, RF) of the buffer size, forcing to reallocation when the load factor is high. This means that if size() is capacity() = RF*internal_buffer_size, even if there is room for the left/right insertions a reallocation will be performed. This means that capacity() = RF*internal buffer is known and means something to the user. Memory usage will grow, but data movement will be minimized. RF could be a policy-based parameter.
I think the RF factor obtains an amortized constant time for one side insertion if that property is considered useful.
I think that is a must.
A fast choice would be to allow just two relocations, a RF of 7/8 = (0,87) which would mean aprox. 2,6*N moves to push_back N elements. A RF of 3/4 (0.75, single relocation step) would mean 1,33*N moves to push_back N elements.
I like low numbers here.
For a FIFO, I think a deque that reuses free segment capacity on one side and transfers it to the other side before allocating new memory would be the best choice. Currently boost::container::deque does not do this, but pull requests are welcome ;-)
Or maybe just boost::circular_buffer (is this not the optimal way to handle that case?). No one is saying that devector has to solve every problem. I do want to focus on simple properties from a user's perspective. Some cases to consider: # case 1: push_back from empty state ------------------------------------ vector<int> v; v.reserve( N ); This guarantees N pushes without exceptions and without reallocation. # case 2: push_back from unknown state -------------------------------------- vector<int> v; ... v.reserve( v.size() + N ); This guarantees N pushes without exceptions and without reallocation. # case 3: insert from empty state --------------------------------- vector<int> v; v.reserve( N ); This guarantees N inserts without exceptions and without reallocation. # case 4: insert from unknown state ----------------------------------- vector<int> v; ... v.reserve( v.size() + N ); This guarantees N inserts without exceptions and without reallocation. How do these properties work for a devector? If I understand your strategy, we get the following: # case 1: push_back from empty state ------------------------------------ devector<int> v; v.reserve( N ); This does not guarantee N pushes without exceptions or without reallocation. To get that guarantee we have to write devector<int> v; v.reserve_back( N ); # case 2: push_back from unknown state -------------------------------------- Same as for case 1: no guarantees unless reserve_back is called. # case 3: insert from empty state --------------------------------- devector<int> v; v.reserve( N ); This does not guarantees N inserts without exceptions or without reallocation. Using reserve_back or reserve_front doesn't help either. The only thing that works is if insert defers all reallocation till it is absolutely needed. # case 4: insert from unknown state ----------------------------------- Same as for case 3: no guarantees unless insert exhaust memory. There are various ways to fix that: either the user replaces v.reserve( N ) v.reserve( v.size() + N ) with v.reserve( N * 2 ) v.reserve( v.size() + N * 2 ) or reserve() automatically acquires double the extra memory requested. The latter will also make generic code work as expected. Using the double amount of requested memory automatically guarantees the optimal insertion performance: no move to the middle is ever required and on average devector performs half the moves of vector. If the user wants less memory waste for push_front/push_back, he can use reserve_front/reserve_back. If the user wants full capacity usage for insert, he can only get that if we exhaust memory for insert by moving to the middle and make reserve allocate exactly what he asks for. Even so, devector should perform no worse than vector, and likely somewhat better. Unfortunately, the is no scheme that is 100% compatible with vector if reserve() for devector produces front_free_capacity() == back_free_capacity(). For that to work, reserve() must act as reserve_back(). Would that be undesirable for insert of reserve() is modeled after the vector? What would happen is that the first time an element falls in the front half, the elements are moved to the middle. This is probably acceptable compared to removing reserve() altogether because its semantics are ambiguous. How do we get the optimal performance for flat containers? We can still call reserve( 2 * N ) and then only pay one move to the middle operation. This is not 100% optimal, granted. For that to happen flat containers would need to forward additional arguments for reserve(). (and possibly clear() as well) How bad is it to waste 50% memory for optimal flat containers. If the container is local in a function, it is probably of no concern at all. Otherwise one may use trim_to_fit() if that applies. At any rate, it would be the user that decides. kind regards Thorsten
Den 16-10-2017 kl. 19:18 skrev Thorsten Ottosen via Boost:
I do want to focus on simple properties from a user's perspective. Some cases to consider:
# case 1: push_back from empty state ------------------------------------
vector<int> v; v.reserve( N );
This guarantees N pushes without exceptions and without reallocation.
# case 2: push_back from unknown state --------------------------------------
vector<int> v; ... v.reserve( v.size() + N );
This guarantees N pushes without exceptions and without reallocation.
A note: this is why I absolutely loathe reserve() compared to a function called v.anticipate( N ) which would work equally well in both cases. -Thorsten
On 16/10/2017 19:18, Thorsten Ottosen via Boost wrote:
1) devector is initialized with equal free capacity for both ends.
I assume that implies reserve() does the very same?
Yes.
2) If a xxx (xxx = left or right) insertion is needed and xxx_free_capacity >= the number of items to be inserted, a xxx insertion is done (minimizes moves). 3) Otherwise if a xxx (xxx = left or right) insertion is needed and xxx_free_capacity < N, the sequence containing new plus old elements should be placed in the middle of the buffer. (Note: This step should be limited if amortized constant time is desired for push_xxx insertions)
There might be some corner cases here. Suppose we have front_free_capacity() == 3, back_free_capacity() == 0 and is about to insert to the right half. Does it then make sense to place elements in the middle?
We are optimizing the general case, we don't know where the user is going to insert the next element. Putting data in the middle seems the choice that minimizes worst-case scenarios. What if the next insertion is in the left half (say, via flat_map)? In any case if we want some kind of cache, we could just move new elements to the side where free elements were available in the old buffer with some kind of logic, like moving data more to left if right free capacity was exhausted.
I think the RF factor obtains an amortized constant time for one side insertion if that property is considered useful.
I think that is a must.
Ok. That's what's used in the alternative implementation in: http://larshagencpp.github.io/blog/2016/05/22/devector using a reallocation factor of 0.8. push_back benchmarks seem quite inline with vector and deque. But it uses some statistics based approach to relocate the buffer so that the push_back case is optimized instead of a random insertion scenario.
For a FIFO, I think a deque that reuses free segment capacity on one side and transfers it to the other side before allocating new memory would be the best choice. Currently boost::container::deque does not do this, but pull requests are welcome ;-)
Or maybe just boost::circular_buffer (is this not the optimal way to handle that case?). No one is saying that devector has to solve every problem.
You are right, circular_buffer should be container to use.
I do want to focus on simple properties from a user's perspective. Some cases to consider:
# case 1: push_back from empty state # case 2: push_back from unknown state # case 3: insert from empty state # case 4: insert from unknown state
How do these properties work for a devector? If I understand your strategy, we get the following:
I think all of them work.
# case 1: push_back from empty state ------------------------------------
devector<int> v; v.reserve( N );
This does not guarantee N pushes without exceptions or without reallocation. To get that guarantee we have to write
If I'm not mistaken, you get the same guarantee. The difference is that elements are "relocated" (moved), but there is no "reallocation" (new buffer allocation). They are first moved when N/2 elements are push_backed and left/right_free_capacity() is zero, then after push_backing additional N/2 elements, etc (the number of relocations (moves) steps depend on the "relocation factor"). Since push_back requires nothrow move constructible to avoid exceptions, moving elements is not a problem, because all of them will be noexcept. If I understand it correctly, it's more or less the same strategy used in: http://larshagencpp.github.io/blog/2016/05/22/devector Best, Ion
Den 16-10-2017 kl. 22:57 skrev Ion Gaztañaga via Boost:
On 16/10/2017 19:18, Thorsten Ottosen via Boost wrote:
2) If a xxx (xxx = left or right) insertion is needed and xxx_free_capacity >= the number of items to be inserted, a xxx insertion is done (minimizes moves). 3) Otherwise if a xxx (xxx = left or right) insertion is needed and xxx_free_capacity < N, the sequence containing new plus old elements should be placed in the middle of the buffer. (Note: This step should be limited if amortized constant time is desired for push_xxx insertions)
There might be some corner cases here. Suppose we have front_free_capacity() == 3, back_free_capacity() == 0 and is about to insert to the right half. Does it then make sense to place elements in the middle?
We are optimizing the general case, we don't know where the user is going to insert the next element. Putting data in the middle seems the choice that minimizes worst-case scenarios. What if the next insertion is in the left half (say, via flat_map)? In any case if we want some kind of cache, we could just move new elements to the side where free elements were available in the old buffer with some kind of logic, like moving data more to left if right free capacity was exhausted.
Right. My point was simply that it pays (in the average case) to move to the middle even when there is only a free space of 3 on the other side.
I think the RF factor obtains an amortized constant time for one side insertion if that property is considered useful.
I think that is a must.
Ok. That's what's used in the alternative implementation in:
http://larshagencpp.github.io/blog/2016/05/22/devector
using a reallocation factor of 0.8. push_back benchmarks seem quite inline with vector and deque. But it uses some statistics based approach to relocate the buffer so that the push_back case is optimized instead of a random insertion scenario.
Yeah, I'm not too happy about push_back/push_front doing movements except in few cases. I think such ideas belong in advanced use of the resize policy.
I do want to focus on simple properties from a user's perspective. Some cases to consider:
# case 1: push_back from empty state # case 2: push_back from unknown state # case 3: insert from empty state # case 4: insert from unknown state
How do these properties work for a devector? If I understand your strategy, we get the following:
I think all of them work.
# case 1: push_back from empty state ------------------------------------
devector<int> v; v.reserve( N );
This does not guarantee N pushes without exceptions or without reallocation. To get that guarantee we have to write
If I'm not mistaken, you get the same guarantee. The difference is that elements are "relocated" (moved), but there is no "reallocation" (new buffer allocation). They are first moved when N/2 elements are push_backed and left/right_free_capacity() is zero, then after push_backing additional N/2 elements, etc (the number of relocations (moves) steps depend on the "relocation factor").
Well, we don't get an O(1) push_back in that case, right? And if we do, we have to reallocate. How about about this: we use Joaquin's idea that if the requested new buffer is smaller/equal to capacity, push_back shifts the whole sequence to the leftmost position (and wise versa for push_front). Then we just make sure that the allocated buffer size is always even, so if the user asks for 5, we allocate 6. Then when the the right hand side is full, we ask for size()*GF (GF should be two) and this is exactly the the capacity. This could work when we start with an empty container, but still leaves devector<int> v; ... v.reserve( v.size() + N ); as a potential problem, doesn't it (unless we allocate twice as much as requested)? I think there is no prefect solution, only it is clear that optimal vector usage and optimal flat container usage requires slightly different behavior of reserve() & clear(). Do we then A. make reserve() & clear() behave like in vector while providing versions that balance around the middle, e.g. reserve( int front, int back ); clear( int front_capacity ); B. make reserve() & clear() behave unlike vector, with balance around the middle. vector code can be made optimal by using reserve_back( int capacity ); clear_back(); C. Don't define reserve() and clear() for devector. kind regards Thorsten
El 16/10/2017 a las 1:45, Ion Gaztañaga via Boost escribió:
On 15/10/2017 17:59, Joaquin M López Muñoz via Boost wrote:
The assumption is of an ever growing sequence. That said, I recorgnize there are scenarios not falling under this, most notably FIFO queues. I've given the policy a little more thought and think we can twist it to also accommodate non-growing scenarios, please keep on reading.
Thougths?
I think that the default (we could have other policies) should be simple and similar to vector/string/stable_vector/etc.... In this sense, capacity() and reserve(), if provided, should make sense. If we reallocate depending on the free capacity of one side, then capacity() and reserve() make no sense to the user
I think the user expects capacity() as the maximum number of insertions, in any position, that will be accepted before reallocating. Making free_capacity = capacity() - size(), less than, say, back_free_capacity() will be really hard to understand by users.
I think providig capacity() will lead to confusion no matter the growing/insertion policy. For instance, users of vector/string/... expect capacity()-size() to be the number of push_back()'s accepted without iterator invalidation. Your policy below does break this expectation --as any policy other than the pathological case where front is given no free space ever.
I propose a simple strategy:
[...]
For any policy, there's a tradeoff between number of movements and wasted space --i.e. space not used before reallocation. Yours prioritizes the latter, mine the former.
Statistics based policies seem more complex, and I don't know how well they will adapt to pattern changes thorough the lifetime of the container, plus they impose a size cost to the container. I wouldn't make the the default choice, as the average user should easily understand the default policy.
Any policy can in principle be implemented behind the following interface: struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n); used like this (pseudocode): auto new_free_space=query_for_insertion(pos,n); if(new_free_space.back+new_free_space.front>free_capacity()){ // allocate or request in-place extension // move and insert appropriately so that back_free_capacity()==new_free_space.back // and front_free_capacity()==new_free_space.front } else{ // free space rebalance assert(new_free_space.back+new_free_space.front==free_capacity()); // move and insert appropriately so that back_free_capacity()==new_free_space.back // and front_free_capacity()==new_free_space.front } Why don't we equip devector with such a customization point and test the different alternatives for real?
For a FIFO, I think a deque that reuses free segment capacity on one side and transfers it to the other side before allocating new memory would be the best choice. Currently boost::container::deque does not do this, but pull requests are welcome ;-)
Or a circular buffer, but devector is the only structure that would additionally guarantee memory contiguity. Joaquín M López Muñoz
On 17 October 2017 at 15:08, Joaquin M López Muñoz via Boost < boost@lists.boost.org> wrote:
Any policy can in principle be implemented behind the following interface:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n);
used like this (pseudocode):
auto new_free_space=query_for_insertion(pos,n); if(new_free_space.back+new_free_space.front>free_capacity()){ // allocate or request in-place extension // move and insert appropriately so that back_free_capacity()==new_free _space.back // and front_free_capacity()==new_free_space.front } else{ // free space rebalance assert(new_free_space.back+new_free_space.front==free_capacity()); // move and insert appropriately so that back_free_capacity()==new_free _space.back // and front_free_capacity()==new_free_space.front }
Why don't we equip devector with such a customization point and test the different alternatives for real?
I've been saying that for a while now... I wrote (from yesterday): All of the above builds on the assumption of free_front equals free_back on relocation. I think, since we are starting to talk about a *very* performant vector-type implementation, that it would be appropriate to provide a free_allocation_ratio_policy<F, B> of sorts, i.e. generalise the 1:1 and make it std::ratio<F, B>, with a default of std::ratio<1, 1> (so not everybody needs to read the small print). On small devectors this has rounding issues. std::ratio<1000, 999> could denote that, this would mean roughly a policy of 1:1, but to 'round towards the front'. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
Den 17-10-2017 kl. 14:08 skrev Joaquin M López Muñoz via Boost:
Any policy can in principle be implemented behind the following interface:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n);
n is the current size of the container or the capacity?
used like this (pseudocode):
auto new_free_space=query_for_insertion(pos,n); if(new_free_space.back+new_free_space.front>free_capacity()){ // allocate or request in-place extension // move and insert appropriately so that back_free_capacity()==new_free_space.back // and front_free_capacity()==new_free_space.front } else{ // free space rebalance assert(new_free_space.back+new_free_space.front==free_capacity()); // move and insert appropriately so that back_free_capacity()==new_free_space.back // and front_free_capacity()==new_free_space.front }
Why don't we equip devector with such a customization point and test the different alternatives for real?
I can try that, but won't be until next week. In the mean time, people can post their favorite policy and answer what it does in the following situations (so it is easier to follow): A. what is the front_free_capacity/back_free_capacity after reserve() on an empty devector? B. what is the front_free_capacity/back_free_capacity after clear() C. what is the front_free_capacity/back_free_capacity after push_back on an empty devector? D. what is the front_free_capacity/back_free_capacity after push_front on an empty devector? E. what is the front_free_capacity/back_free_capacity after insert on an empty devector? F. what is the front_free_capacity/back_free_capacity after reserve on a non-empty empty devector?
For a FIFO, I think a deque that reuses free segment capacity on one side and transfers it to the other side before allocating new memory would be the best choice. Currently boost::container::deque does not do this, but pull requests are welcome ;-)
Or a circular buffer, but devector is the only structure that would additionally guarantee memory contiguity.
Right. So it may be worth considering. Note as we have discussed previously, that if we shift all the way to the front, a subsequent push_front shifts all the way to the back, and a subsequent push_back shifts all the way to the front. This can in principle go on until the size is again larger than the threshold used for shifting. kind regards Thorsten
El 18/10/2017 a las 10:36, Thorsten Ottosen via Boost escribió:
Den 17-10-2017 kl. 14:08 skrev Joaquin M López Muñoz via Boost:
Any policy can in principle be implemented behind the following interface:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n);
n is the current size of the container or the capacity?
n is meant to indicate the number of elements being inserted at once.
[...]
For a FIFO, I think a deque that reuses free segment capacity on one side and transfers it to the other side before allocating new memory would be the best choice. Currently boost::container::deque does not do this, but pull requests are welcome ;-)
Or a circular buffer, but devector is the only structure that would additionally guarantee memory contiguity.
Right. So it may be worth considering. Note as we have discussed previously, that if we shift all the way to the front, a subsequent push_front shifts all the way to the back, and a subsequent push_back shifts all the way to the front. This can in principle go on until the size is again larger than the threshold used for shifting.
Right, ths is why I suggest rebalance includes some safeguards (minimum free space on each side) to avoid thrashing. Joaquín M López Muñoz
Den 18-10-2017 kl. 11:26 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 10:36, Thorsten Ottosen via Boost escribió:
Den 17-10-2017 kl. 14:08 skrev Joaquin M López Muñoz via Boost:
Any policy can in principle be implemented behind the following interface:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n);
n is the current size of the container or the capacity?
n is meant to indicate the number of elements being inserted at once.
Of course :-) We need an additional interface function for handling clear, don't we? -Thorsten
El 18/10/2017 a las 13:52, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 11:26 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 10:36, Thorsten Ottosen via Boost escribió:
Den 17-10-2017 kl. 14:08 skrev Joaquin M López Muñoz via Boost:
Any policy can in principle be implemented behind the following interface:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n);
[...]
We need an additional interface function for handling clear, don't we?
Umm... yes, we need something for clear(), right. In the rest of erasure scenarios there's an obvious way to give free space back to both ends. Joaquín M López Muñoz
Den 18-10-2017 kl. 15:07 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 13:52, Thorsten Ottosen via Boost escribió:
We need an additional interface function for handling clear, don't we?
Umm... yes, we need something for clear(), right. In the rest of erasure scenarios there's an obvious way to give free space back to both ends.
Obvious as in "erase never moves elements within the buffer"? or did you mean, leave front_free_capacity and back_free_capacity as they would for any call to erase? If we erase the last element, do we then guarantee the same capacities as clear()? -Thorsten
El 18/10/2017 a las 15:21, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 15:07 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 13:52, Thorsten Ottosen via Boost escribió:
We need an additional interface function for handling clear, don't we?
Umm... yes, we need something for clear(), right. In the rest of erasure scenarios there's an obvious way to give free space back to both ends.
Obvious as in "erase never moves elements within the buffer"? or did you mean, leave front_free_capacity and back_free_capacity as they would for any call to erase?
Ummm... I wrote too fast, the answer is not obvious :-) Say our devector looks like FF···FMM···MBB···B and we want to erase MM···M. We have these three options: 1. Move BB...B right after FF···F, so that only back free capacity grows. 2. Move FF···F right before BB···B, so that only front free capacity grows. 3. Make FF···F meet BB···B at a middle position within the buffer so that the ratio between back and front free capacity is kept. In my opinion, the best option is to do 1 or 2 depending on which of the two subsequences BB···B and FF···F is smaller (respectively), which minimizes the number of movements. This is consistent with the expected behavior for push_[back|front]. 3 always implies more movements. Joaquín M López Muñoz
El 18/10/2017 a las 16:28, Joaquin M López Muñoz escribió:
Ummm... I wrote too fast, the answer is not obvious :-) Say our devector looks like
FF···FMM···MBB···B
and we want to erase MM···M. We have these three options:
1. Move BB...B right after FF···F, so that only back free capacity grows. 2. Move FF···F right before BB···B, so that only front free capacity grows. 3. Make FF···F meet BB···B at a middle position within the buffer so that the ratio between back and front free capacity is kept.
In my opinion, the best option is to do 1 or 2 depending on which of the two subsequences BB···B and FF···F is smaller (respectively), which minimizes the number of movements. This is consistent with the expected behavior for push_[back|front]. 3 always implies more movements.
Writing this has led me to realize that a generic growing/insertion policy also needs a member function to indicate what to do on erasure: struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n); free_space query_for_erasure(std::size_t pos,std::size_t n); (clear would be the case where erasure happens at begin() and n==size()). Joaquín M López Muñoz
Den 18-10-2017 kl. 16:37 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 16:28, Joaquin M López Muñoz escribió:
Ummm... I wrote too fast, the answer is not obvious :-) Say our devector looks like
FF···FMM···MBB···B
and we want to erase MM···M. We have these three options:
1. Move BB...B right after FF···F, so that only back free capacity grows. 2. Move FF···F right before BB···B, so that only front free capacity grows. 3. Make FF···F meet BB···B at a middle position within the buffer so that the ratio between back and front free capacity is kept.
In my opinion, the best option is to do 1 or 2 depending on which of the two subsequences BB···B and FF···F is smaller (respectively), which minimizes the number of movements. This is consistent with the expected behavior for push_[back|front]. 3 always implies more movements.
Agreed, in a move-minimizing policy, one would want erase to do the least work.
Writing this has led me to realize that a generic growing/insertion policy also needs a member function to indicate what to do on erasure:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n); free_space query_for_erasure(std::size_t pos,std::size_t n);
(clear would be the case where erasure happens at begin() and n==size()).
But the policy does not know size() unless we pass it that too. kind regards Thorsten
El 26/10/2017 a las 17:08, Thorsten Ottosen escribió:
Den 18-10-2017 kl. 16:37 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 16:28, Joaquin M López Muñoz escribió: Writing this has led me to realize that a generic growing/insertion policy also needs a member function to indicate what to do on erasure:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n); free_space query_for_erasure(std::size_t pos,std::size_t n);
(clear would be the case where erasure happens at begin() and n==size()).
But the policy does not know size() unless we pass it that too.
Yes, it need access the size and front and back capacity. If the policy is used via CRTP (which is what I have in mind but admittedly didn't make clear) then this info can be retrived by the policy through devector's public interface. Other designs would require that the info be passed as additional arguments to the member functions. Joaquín M López Muñoz
Den 26-10-2017 kl. 19:59 skrev Joaquin M López Muñoz via Boost:
El 26/10/2017 a las 17:08, Thorsten Ottosen escribió:
But the policy does not know size() unless we pass it that too.
Yes, it need access the size and front and back capacity. If the policy is used via CRTP (which is what I have in mind but admittedly didn't make clear) then this info can be retrived by the policy through devector's public interface. Other designs would require that the info be passed as additional arguments to the member functions.
Regardless, We also need to see what to test. I have tried to improve the test measurements, see attached code. It tests insertion without buffer expansion. Do we want one that doesn't reserve memory too, inserting at a random position? And? kind regards Thorsten
El 01/11/2017 a las 20:21, Thorsten Ottosen escribió:
Den 26-10-2017 kl. 19:59 skrev Joaquin M López Muñoz via Boost:
El 26/10/2017 a las 17:08, Thorsten Ottosen escribió:
But the policy does not know size() unless we pass it that too.
Yes, it need access the size and front and back capacity. If the policy is used via CRTP (which is what I have in mind but admittedly didn't make clear) then this info can be retrived by the policy through devector's public interface. Other designs would require that the info be passed as additional arguments to the member functions.
Regardless,
We also need to see what to test. I have tried to improve the test measurements, see attached code. It tests insertion without buffer expansion.
May I suggest we use something like the following framework: template<typename T> struct default_factory { using value_type=T; static value_type get(){return T{};} }; template<typename Factory> struct random_process { using factory_type=Factory; random_process( double wib,double wif,double wim, double web,double wef,double wem, const Factory& f=Factory{}): rnd{{wib,wif,wim,web,wef,wem}},f{f}{} template<typename Devector> void operator()(Devector& d){ using uniform=std::uniform_int_distribution<typename Devector::size_type>; switch(rnd(gen)){ case 0: d.push_back(f.get());break; case 1: d.push_front(f.get());break; case 2: d.insert(d.begin()+uniform{0,d.size()}(gen),f.get());break; case 3: if(d.size()>0)d.pop_back();break; case 4: if(d.size()>0)d.pop_front();break; case 5: if(d.size()>0)d.erase(d.begin()+uniform{0,d.size()-1}(gen));break; } } std::mt19937 gen{92748}; // some arbitrary random seed std::discrete_distribution<> rnd; Factory f; }; template<typename RandomProcess> void run(RandomProcess p,int n) { boost::double_ended::devector< typename RandomProcess::factory_type::value_type> d; for(int i=0;i<n;++i)p(d); } random_process models a, well, random process that, each time it is invoked, can do the following: 1. push_back 2. push_front 3. insert at a random position within the devector 4. pop_back 5. pop_front 6. erase at a random position within the devector where each action is chosen with probabilistic weights wib, wif, wim, web, wef and wem, respectively. We can then easily model different usage patterns: * (1,0,0,0,0,0) --> growing on back * (1,1,0,0,0,0) --> growing both ends * (1,0,0,0,1,0) --> FIFO (average size = 0) * (2,0,0,0,1,0) --> growing FIFO * (0,0,1,0,0,0) --> growing, no end bias * (0,0,2,0,0,1) --> growing with some deletions, no end bias Etc. Joaquín M López Muñoz
Den 26-10-2017 kl. 17:08 skrev Thorsten Ottosen via Boost:
Den 18-10-2017 kl. 16:37 skrev Joaquin M López Muñoz via Boost:
In my opinion, the best option is to do 1 or 2 depending on which of the two subsequences BB···B and FF···F is smaller (respectively), which minimizes the number of movements. This is consistent with the expected behavior for push_[back|front]. 3 always implies more movements.
Agreed, in a move-minimizing policy, one would want erase to do the least work.
There is one thing which might affect things for trivially copyable types I expect move() to be faster than move_backwards(). Just guessing though. -T
Den 18-10-2017 kl. 16:37 skrev Joaquin M López Muñoz via Boost:
Writing this has led me to realize that a generic growing/insertion policy also needs a member function to indicate what to do on erasure:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n); free_space query_for_erasure(std::size_t pos,std::size_t n);
I don't get how we know if we have a push_back or push_front. So I think we should use free_space query_for_middle_insertion(std::size_t pos,std::size_t n); free_space query_for_back_insertion(std::size_t pos,std::size_t n); free_space query_for_front_insertion(std::size_t pos,std::size_t n); so we have clear control over inserts/push to either end. kind regards -Thorsten
El 02/11/2017 a las 19:10, Thorsten Ottosen escribió:
Den 18-10-2017 kl. 16:37 skrev Joaquin M López Muñoz via Boost:
Writing this has led me to realize that a generic growing/insertion policy also needs a member function to indicate what to do on erasure:
struct free_space{std::size_t back,front;}; free_space query_for_insertion(std::size_t pos,std::size_t n); free_space query_for_erasure(std::size_t pos,std::size_t n);
I don't get how we know if we have a push_back or push_front. So I think we should use
free_space query_for_middle_insertion(std::size_t pos,std::size_t n); free_space query_for_back_insertion(std::size_t pos,std::size_t n); free_space query_for_front_insertion(std::size_t pos,std::size_t n);
so we have clear control over inserts/push to either end.
push_back is query_for_insertion(size(),1), push_front is query_for_insertion(0,1); I don't think we need specialized member functions for those, don't you think? Joaquín M López Muñoz
Den 03-11-2017 kl. 10:26 skrev Joaquin M López Muñoz via Boost:
El 02/11/2017 a las 19:10, Thorsten Ottosen escribió:
Den 18-10-2017 kl. 16:37 skrev Joaquin M López Muñoz via Boost: so we have clear control over inserts/push to either end.
push_back is query_for_insertion(size(),1), push_front is query_for_insertion(0,1); I don't think we need specialized member functions for those, don't you think?
Perhaps not. I'm playing with an implementation, and it's not trivial to get ones head around all corner cases, so I started with the push_back case to keep things simple -- if its trivial simplify afterwards, we can do that. There is also the thing about a policy that do different things if push_back is called or if insert is called. Say you only want to leave free space on the right when push_back is called on an empty container, but if insert is called on an empty container, you want to balance the free space. I don't see how we can do that without knowing the nature of the call, i.e., was it push_back, push_front or an insert. kind regards -Thorsten
Den 15-10-2017 kl. 17:59 skrev Joaquin M López Muñoz via Boost:
El 15/10/2017 a las 15:50, thorsten.ottosen via Boost escribió:
hi Joaquin,
Thanks for this. Some comments below.
Facts
— How do you get that number ? I would say we save Incur 1/2 * size movements on average for shifting to the end with free space.
The number follows from: assume right insertion is at position N, that means that under normal conditions (there's back free capacity) we need to make size()-N movements to the right. If instead of that we shift to the left the resulting number of movements is N, so the penalty for taking the "wrong" decision is the difference N - (size()-N) = 2*N - size(). Did I explain myself now?
yes, I somehow got confused.
Description of resulting policy
The idea of keeping track of left right insertions also interesting. It does assume additionally that the insert pattern in the future is the same as in the past, right?
Did you see this question?
I think in the case where the user has called reserve, it’s a little problematic that insert may allocate anyway. That is, for many uses there is no infinitely growing sequence .
And this one? I'm still not sure we want to allocate on insert before the buffer is full.
The right_ member can become larger than size if elects are added to the right and removed from the left, not sure what to do about that.
Yes, you're right. right_ becoming greater thatn size() can't happen under the ever- growing assumtion, but it certainly can in the real world.
minor remark: If one goes with this approach, I think the member should be left_ so as to not penalize normal push_back.
Let's slightly adjust the policy as follows. I think this copes with the ever-growing and fixed-size scenarios equally well. Let us remember that the goal when reserving new free space at both front and back is to make it so that both ends get exhausted at the same time --if they ever are.
This has the effect that if no insertions happened at one end (more precisely, more erasures than insertions took place at that end) then the new reserved space for that end will be zero. Safe guards may be applied. * When reallocation results in the same total space being reserved (this happens when the size at reallocation time is equal or less than the size() at the last reallocation), there is no need to request memory and we can simply shift the sequence so that back and front free capacity are adjusted according to new_space calculations. This nicely handles the FIFO scenario, for instance: when the growing side meets its end, reallocaton resolves to shifting the entire sequence within the current buffer so that space is kept at that end: this keeps cycling forever with no memory allocation and minimal element shifting.
So if no elements are added to the left but only to the right, the live elements are shifted all the way to the left? That would certainly be optimal, and letting the user decide the initial memory consumption let him control how often the shifting is needed. kind regards Thorsten
I can only say that I fully agree with the approach taken in this thread. All of the above builds on the assumption of free_front equals free_back on relocation. I think, since we are starting to talk about a *very* performant vector-type implementation, that it would be appropriate to provide a free_allocation_ratio_policy<F, B> of sorts, i.e. generalise the 1:1 and make it std::ratio<F, B>, with a default of std::ratio<1, 1> (so not everybody needs to read the small print). On small devectors this has rounding issues. std::ratio<1000, 999> could denote that, this would mean roughly a policy of 1:1, but to 'round towards the front'. One could imagine a de::devector_tuner, deriving from de::devector, to trace and be queried over how front and back pushed/emplacements are split, so one can apply the optimal free_allocation_ratio_policy<F, B> after a/some test runs in a live situation (adaptive is possible as well, that that might be a high price to pay). Another thought (off thread!) is that de::devector should provide void unordered_erase ( iterator & it_ ) noexcept;, often when one uses a vector-like structure, one does not care about order. So I imagine a member function, conceptually like the below, providing O1 erase: void unordered_erase ( iterator & it_ ) noexcept { *it_ = back ( ); resize ( size ( ) - 1 ); } degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
El 16/10/2017 a las 10:45, Thorsten Ottosen via Boost escribió:
Den 15-10-2017 kl. 17:59 skrev Joaquin M López Muñoz via Boost:
El 15/10/2017 a las 15:50, thorsten.ottosen via Boost escribió:
The idea of keeping track of left right insertions also interesting. It does assume additionally that the insert pattern in the future is the same as in the past, right?
Did you see this question?
Sorry, I missed that one. Yes, we use the insertion pattern after the last reallocation to estimate the new one. If the insertion pattern changes over time the policy will adapt with a delay of one reallocation.
I think in the case where the user has called reserve, it’s a little problematic that insert may allocate anyway. That is, for many uses there is no infinitely growing sequence .
And this one? I'm still not sure we want to allocate on insert before the buffer is full.
If we must guarantee that the buffer is full before reallocation, the resulting policy won't be optimal wrt number of movements. This is the tradeoff. I guess your reservation stems from the desire that capacity()-size() indicates the number of insertions before reallocation, to that I just answered Ion in another post. My (current) opinion is that capacity() should not be provided.
The right_ member can become larger than size if elects are added to the right and removed from the left, not sure what to do about that.
Yes, you're right. right_ becoming greater thatn size() can't happen under the ever- growing assumtion, but it certainly can in the real world.
minor remark: If one goes with this approach, I think the member should be left_ so as to not penalize normal push_back.
This is superseded by the alternative formulation I described above.
Let's slightly adjust the policy as follows. I think this copes with the ever-growing and fixed-size scenarios equally well. Let us remember that the goal when reserving new free space at both front and back is to make it so that both ends get exhausted at the same time --if they ever are.
This has the effect that if no insertions happened at one end (more precisely, more erasures than insertions took place at that end) then the new reserved space for that end will be zero. Safe guards may be applied. * When reallocation results in the same total space being reserved (this happens when the size at reallocation time is equal or less than the size() at the last reallocation), there is no need to request memory and we can simply shift the sequence so that back and front free capacity are adjusted according to new_space calculations. This nicely handles the FIFO scenario, for instance: when the growing side meets its end, reallocaton resolves to shifting the entire sequence within the current buffer so that space is kept at that end: this keeps cycling forever with no memory allocation and minimal element shifting.
So if no elements are added to the left but only to the right, the live elements are shifted all the way to the left? That would certainly be optimal, and letting the user decide the initial memory consumption let him control how often the shifting is needed.
Much as I think capacity() should not be provided, reserve would probably better replaced by reserve_front_free/reserve_back_free or something similar. Joaquín M López Muñoz
Den 17-10-2017 kl. 14:23 skrev Joaquin M López Muñoz via Boost:
El 16/10/2017 a las 10:45, Thorsten Ottosen via Boost escribió:
I think in the case where the user has called reserve, it’s a little problematic that insert may allocate anyway. That is, for many uses there is no infinitely growing sequence .
And this one? I'm still not sure we want to allocate on insert before the buffer is full.
If we must guarantee that the buffer is full before reallocation, the resulting policy won't be optimal wrt number of movements.
Correct. If you want that for insert, you would need to allocate twice the needed space.
This is the tradeoff. I guess your reservation stems from the desire that capacity()-size() indicates the number of insertions before reallocation, to that I just answered Ion in another post. My (current) opinion is that capacity() should not be provided.
My reservation is not really with capacity(), but with the cost of allocation for small flat containers. Last I checked, you could copy hundreds of objects for the price of one allocation (and the deallocation that is implied). kind regards Thorsten
El 17/10/2017 a las 15:25, Thorsten Ottosen via Boost escribió:
Den 17-10-2017 kl. 14:23 skrev Joaquin M López Muñoz via Boost:
This is the tradeoff. I guess your reservation stems from the desire that capacity()-size() indicates the number of insertions before reallocation, to that I just answered Ion in another post. My (current) opinion is that capacity() should not be provided.
My reservation is not really with capacity(), but with the cost of allocation for small flat containers. Last I checked, you could copy hundreds of objects for the price of one allocation (and the deallocation that is implied).
If your concern is allocation cost and you do not worry that much about wasted space, you can increase the growing factor G to lower that (amortized) cost down at the expense of increasing the average free space not used on on one of both sides when the other side gets exhausted. Joaquín M López Muñoz
Den 15-10-2017 kl. 14:09 skrev Joaquin M López Muñoz via Boost:
Hi,
* Maintain a counter right_ of right insertions that gets incremented when a right insertion occurs and *decremented* when an erasure is issued past the middle of the devector.
So to implement this with a custom Resizing policy, the policy would need be stored via compressed_pair as a member and additionally provide a hook: right_event( int elements ) where elements can be both positive and negative and which is called from push_back and insert as needed. By default this could be an empty function.
* Right insertions trigger right shifting except when there's no back free capacity, in which case a reallocation is performed. * Left insertions trigger left shifting except when there's no front free capacity, in which case a reallocation is performed. * Reallocation reserves space for G*size() elements: of the resulting G*size()-size() free space, a fraction right_/size() is devoted to back free capacity,
Maybe this is lost to me in the details, but given code that works for vector: vector<int> v; ... v.reserve( v.size() + N ); which guarantees no exceptions and no reallocations, how would that work with your policy? Is it going to depend on no left insertions ever to have been made for v? kind regards -Thorsten
El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
Den 15-10-2017 kl. 14:09 skrev Joaquin M López Muñoz via Boost:
Hi,
* Maintain a counter right_ of right insertions that gets incremented when a right insertion occurs and *decremented* when an erasure is issued past the middle of the devector.
So to implement this with a custom Resizing policy, the policy would need be stored via compressed_pair as a member and additionally provide a hook:
right_event( int elements )
where elements can be both positive and negative and which is called from push_back and insert as needed. By default this could be an empty function.
In another post I'm proposing an alternative policy interface which can in principle accommodate any policy --AFAICS.
* Right insertions trigger right shifting except when there's no back free capacity, in which case a reallocation is performed. * Left insertions trigger left shifting except when there's no front free capacity, in which case a reallocation is performed. * Reallocation reserves space for G*size() elements: of the resulting G*size()-size() free space, a fraction right_/size() is devoted to back free capacity,
Maybe this is lost to me in the details, but given code that works for vector:
vector<int> v; ... v.reserve( v.size() + N );
which guarantees no exceptions and no reallocations, how would that work with your policy?
Sorry, now it's me who's lost :-) std::vector::reserve can both throw and reallocate, right? Joaquín M López Muñoz
Den 18-10-2017 kl. 11:36 skrev Joaquin M López Muñoz via Boost:
El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
Maybe this is lost to me in the details, but given code that works for vector:
vector<int> v; ... v.reserve( v.size() + N );
which guarantees no exceptions and no reallocations, how would that work with your policy?
Sorry, now it's me who's lost :-) std::vector::reserve can both throw and reallocate, right?
Yes, sorry for being unclear, I'm talking about the guarantee given to push_back() and insert() of N elements after the call to reserve(). -Thorsten
El 18/10/2017 a las 13:48, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 11:36 skrev Joaquin M López Muñoz via Boost:
El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
Maybe this is lost to me in the details, but given code that works for vector:
vector<int> v; ... v.reserve( v.size() + N );
which guarantees no exceptions and no reallocations, how would that work with your policy?
Sorry, now it's me who's lost :-) std::vector::reserve can both throw and reallocate, right?
Yes, sorry for being unclear, I'm talking about the guarantee given to push_back() and insert() of N elements after the call to reserve().
OK, now I get it. Well, my position is that reserve should be replaced by some mechanism for explicitly controlling free space at each end. Then the user can rely on the guarantee that she can do as many as [back|front]_free_capacity() push_[back|front] ops without rellocation. Joaquín M López Muñoz
Den 18-10-2017 kl. 15:10 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 13:48, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 11:36 skrev Joaquin M López Muñoz via Boost:
El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
Maybe this is lost to me in the details, but given code that works for vector:
vector<int> v; ... v.reserve( v.size() + N );
which guarantees no exceptions and no reallocations, how would that work with your policy?
Yes, sorry for being unclear, I'm talking about the guarantee given to push_back() and insert() of N elements after the call to reserve().
OK, now I get it. Well, my position is that reserve should be replaced by some mechanism for explicitly controlling free space at each end. Then the user can rely on the guarantee that she can do as many as [back|front]_free_capacity() push_[back|front] ops without rellocation.
and what about insert()? Do we then say if you want to avoid reallocations, you must allocate twice the needed memory? For vector we do not reallocate on insert(). (I'm not saying that is the wrong answer, I would just like to know that the answer is). -Thorsten
El 18/10/2017 a las 15:18, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 15:10 skrev Joaquin M López Muñoz via Boost:
El 18/10/2017 a las 13:48, Thorsten Ottosen via Boost escribió:
Den 18-10-2017 kl. 11:36 skrev Joaquin M López Muñoz via Boost:
El 16/10/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
Maybe this is lost to me in the details, but given code that works for vector:
vector<int> v; ... v.reserve( v.size() + N );
which guarantees no exceptions and no reallocations, how would that work with your policy?
Yes, sorry for being unclear, I'm talking about the guarantee given to push_back() and insert() of N elements after the call to reserve().
OK, now I get it. Well, my position is that reserve should be replaced by some mechanism for explicitly controlling free space at each end. Then the user can rely on the guarantee that she can do as many as [back|front]_free_capacity() push_[back|front] ops without rellocation.
and what about insert()? Do we then say if you want to avoid reallocations, you must allocate twice the needed memory?
For vector we do not reallocate on insert().
(I'm not saying that is the wrong answer, I would just like to know that the answer is).
My proposed policy consumes back free capacity if we have a right insertion (past the middle of the devector) and front free capacity in the case of a left insertion (before the middle of the devector). If you want to guarantee N no-reallocation insertions at any position so, yes, both front and back free capacity has to be >=N. For the benefit of the readers, allow me to paste here the policy description: * Fix the growing factor to G. * The right balancing factor B is defined as the ratio between back free capacity and total free capacity. Let's say this is 50% at the start, that is, we have front_free_capacity()= back_free_capacity(). * Right insertions and left insertions shift to the right and left, respectively (as before). * When reallocation is needed, calculate the new balance factor as a function of front and back space consumption just prior to reallocation. Pseudocode follows: struct free_space { std::size_t back,front }; free_space new_space(free_space original,free_space remaining) { float balance=(float)std::max(original.back-remaining.back,0)/ (std::max(original.back-remaining.back,0)+std::max(original.front-remaining.front,0)); std::size_t new_space=std::max(size()*G,size()+remaining.back+remaining.front), new_free_space=new_space-size(); return {balance*new_free_space,(1-balance)*new_free_space}; } Joaquín M López Muñoz
OK, now I get it. Well, my position is that reserve should be replaced by some mechanism for explicitly controlling free space at each end. Then the user can rely on the guarantee that she can do as many as [back|front]_free_capacity() push_[back|front] ops without rellocation.
So, reserve_front(), reserve_back()? I mostly get your growth/reallocation strategy as-described but I think at this point you have to start to question the purpose. With a deque-like segmented structure you could allocate multiple blocks using reserve and then assign them to the back or front depending as needed. Looking at the performance of GCC's deque implementation, you're not going to lose significant iteration performance if this is done right, asides from for large types (http://www.plflib.org/benchmarks_haswell_gcc.htm#rawperformance).
participants (6)
-
degski -
Ion Gaztañaga -
Joaquin M López Muñoz -
Soul Studios -
Thorsten Ottosen -
thorsten.ottosen