4 ms·

On a related note, NSArray, the standard array class in Cocoa, is actually implemented as a circular array under the hood, allowing you to unshift/shift just as

On a related note, NSArray, the standard array class in Cocoa, is actually implemented as a circular array under the hood, allowing you to unshift/shift just as efficiently as you can push/pop. The reason it's able to do this is because it doesn't have any API that exposes a pointer to its object storage. Without the need to have a pointer to its storage, there's no need to ensure the objects are actually stored contiguously and in-order, which means using a circular array is a trivial optimization. There are other data structures it could use instead, such as a sequence of fixed-length arrays like (common implementations of) std::deque, but I guess a circular buffer was chosen because it meets all of the complexity guarantees and is still pretty simple. Although I'm also generalizing a bit, because it turns out that NSArray/CFArrayRef actually changes the implementation it uses when the array gets large enough (I don't remember precisely where to find it, but there's a blog post out there with details on the observed performance of NSArray/CFArrayRef as it grows). But in most cases, it's probably a circular array. On that note, I'd think that using a circular array would be an obvious optimization for any JavaScript implementation. JavaScript doesn't have any need to store its values contiguously and in-order (since JavaScript doesn't have pointers so it can't possibly expose a pointer to its storage). I would expect that unshifting arrays (and shifting them) is common enough that this optimization is an obvious win for all engines.

nightcracker 12y ago
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

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.