3 ms·

I'm working on a data structure that is double-ended as well as contiguous: https://github.com/orlp/devector https://github.com/orlp/devector

eridius 12y ago
Interesting. I do wonder what pathological performance is like, though. I would imagine that you can design an access scenario that does pushes/pops and shifts/unshifts in the right order to cause it to keep shuffling elements back and forth within the storage (without reallocating) indefinitely even though the number of elements never grows beyond a set amount.
- nightcracker 12y ago
  The pathological case is FIFO. If you store a FIFO queue inside devector, with n elements in the queue, memory usage bounds at 5n/3. This means that the total free space is 2n/3, of which half gets re-used everytime the elements shuffle. This means that after n/3 push_back/pop_front pairs n elements have to be moved. Which is still amortized constant, with an overhead of approximately 1.5 moves per operation. This means that performance, even in the pathological case, is quite good. If you know you're dealing with a FIFO queue you can always replace devector with a specialized queue. But as a general default container devector is never a bad choice.
  - eridius 12y ago
    From looking over your README, when it needs new space on one end, it preserves half of the free space on the other, and requires at least 1/3rd of the size of the vector at the end that's being appended to (assuming >= 16). I didn't check to see how it balances space when the 1/2 free space it harvests from the other end is larger than the 1/3rd size it needs. But my assumption is that when it grows an end, it may end up with more free space at that end than at the other, right? If that's true, then deleting the added elements from that end and switching to appending to the other (until it has to shuffle) would presumably cause it to shuffle more often than a simple FIFO. Is my assumption wrong, would such a pattern of access not actually result in the "other end" having less free space (and therefore switching the ends it appends to would not result in more shuffles)?
    - nightcracker 12y ago
      Actually, you are right, I was wrong about my assumption that FIFO is the worst case, and that 5n/2 is the space bound. Let's first establish that to get the worst case it's always optimal to append to the end with the least free space. Anything else and you're using allocations more efficiently. There's two cases. One where reallocation is needed, and one where it is not. Let's look at both seperately. No reallocation needed: half of the free space "harvested" (as you call it) is enough. End result after shuffling is same free space on both ends, thus it doesn't matter if you switch sides. This is the FIFO case which I analyzed above. Reallocation needed: the side that needed more space _always_ has more space than the side that was harvested from, because if the harvesting alone was enough we'd be in the "no reallocation" case. This means that if you want the worst case, you will always switch sides. Let's say there are n elements, the side you're appending to has a free space, and the other side has b free space, and the total memory usage is s. So the model after x reallocations is: s(x) = 1.5s(x-1) n(x) = n(x-1) + a(x-1) a(x) = b(x-1) / 2 b(x) = s(x) - n(x) - a(x) Forgive me for not being on-point in a quick reply with my exact maths, but entering this model with n(0) = s(0) = 16 using Python and memoization to speed up the recursion reveals that a(x) / n(x) is exactly 1/2. So after n/2 appends n moves are needed, so 2 moves per operation. s(x) / n(x) turns out to be exactly 3, so 3n is the max space bound. --- This means that the memory bound is worse than a ring buffer in the worst case, but the 2 moves per operation isn't even worse than just appending to a regular array, assuming the growth factor is 1.5 for both.
    - nightcracker 12y ago
      Actually, after revisiting my model below, I found that it's completely wrong. In my model below I forgot to account for the mechanism that we sometimes shuffle, rather than reallocate. I've written a new model which can be found here: https://gist.github.com/orlp/439890748c6d55897ba5 https://gist.github.com/orlp/439890748c6d55897ba5 The new model shows that the memory bound is indeed 5n/3, and amortized 3 moves per operation are needed in the worst case, compared to 2 moves per operation in perfect conditions.

eridius 12y ago

Interesting. I do wonder what pathological performance is like, though. I would imagine that you can design an access scenario that does pushes/pops and shifts/unshifts in the right order to cause it to keep shuffling elements back and forth within the storage (without reallocating) indefinitely even though the number of elements never grows beyond a set amount.

nightcracker 12y ago
The pathological case is FIFO. If you store a FIFO queue inside devector, with n elements in the queue, memory usage bounds at 5n/3. This means that the total free space is 2n/3, of which half gets re-used everytime the elements shuffle. This means that after n/3 push_back/pop_front pairs n elements have to be moved. Which is still amortized constant, with an overhead of approximately 1.5 moves per operation. This means that performance, even in the pathological case, is quite good. If you know you're dealing with a FIFO queue you can always replace devector with a specialized queue. But as a general default container devector is never a bad choice.
- eridius 12y ago
  From looking over your README, when it needs new space on one end, it preserves half of the free space on the other, and requires at least 1/3rd of the size of the vector at the end that's being appended to (assuming >= 16). I didn't check to see how it balances space when the 1/2 free space it harvests from the other end is larger than the 1/3rd size it needs. But my assumption is that when it grows an end, it may end up with more free space at that end than at the other, right? If that's true, then deleting the added elements from that end and switching to appending to the other (until it has to shuffle) would presumably cause it to shuffle more often than a simple FIFO. Is my assumption wrong, would such a pattern of access not actually result in the "other end" having less free space (and therefore switching the ends it appends to would not result in more shuffles)?
  - nightcracker 12y ago
    Actually, you are right, I was wrong about my assumption that FIFO is the worst case, and that 5n/2 is the space bound. Let's first establish that to get the worst case it's always optimal to append to the end with the least free space. Anything else and you're using allocations more efficiently. There's two cases. One where reallocation is needed, and one where it is not. Let's look at both seperately. No reallocation needed: half of the free space "harvested" (as you call it) is enough. End result after shuffling is same free space on both ends, thus it doesn't matter if you switch sides. This is the FIFO case which I analyzed above. Reallocation needed: the side that needed more space _always_ has more space than the side that was harvested from, because if the harvesting alone was enough we'd be in the "no reallocation" case. This means that if you want the worst case, you will always switch sides. Let's say there are n elements, the side you're appending to has a free space, and the other side has b free space, and the total memory usage is s. So the model after x reallocations is: s(x) = 1.5s(x-1) n(x) = n(x-1) + a(x-1) a(x) = b(x-1) / 2 b(x) = s(x) - n(x) - a(x) Forgive me for not being on-point in a quick reply with my exact maths, but entering this model with n(0) = s(0) = 16 using Python and memoization to speed up the recursion reveals that a(x) / n(x) is exactly 1/2. So after n/2 appends n moves are needed, so 2 moves per operation. s(x) / n(x) turns out to be exactly 3, so 3n is the max space bound. --- This means that the memory bound is worse than a ring buffer in the worst case, but the 2 moves per operation isn't even worse than just appending to a regular array, assuming the growth factor is 1.5 for both.
  - nightcracker 12y ago
    Actually, after revisiting my model below, I found that it's completely wrong. In my model below I forgot to account for the mechanism that we sometimes shuffle, rather than reallocate. I've written a new model which can be found here: https://gist.github.com/orlp/439890748c6d55897ba5 https://gist.github.com/orlp/439890748c6d55897ba5 The new model shows that the memory bound is indeed 5n/3, and amortized 3 moves per operation are needed in the worst case, compared to 2 moves per operation in perfect conditions.