4 ms·

One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?

by vladf 5y ago

mjevans 5y ago
It depends on how strictly the structure of each array is defined, the answer can be yes but I don't know what effect this has on modern superscaler CPUs. The source array might be considered to have even offsets (0, 2, 4, etc, index left shift 1 bit) relative to the double-sized array. Addition operations past the halfway value of the smaller array have a relation to values in the second by (Index << 1) % n + 1 ; that is they pair with the values from the start of the smaller array. When a removal operation, like pop(), selects a victim in the source array the corresponding operations must also apply in sync to the values in the larger array.
Dylan16807 5y ago
Easily! You can just make pop do the opposite of push. For example, if push copies two elements to the bigger array, make pop copy two elements to the smaller array.
- vladf 5y ago
  I challenge you to try to implement it this way and test that (1) an arbitrary sequence of push/pop is valid and (2) doesn’t use more than linear space.
  - Dylan16807 5y ago
    It's pretty easy to make sure an arbitrary sequence is valid if you make push and pop be almost exact opposites of each other. Let me walk through a simple version based on the description above, ignoring that it's rather inefficient: Start with an array of size 64, with 32 elements. Our first action is either a push or a pop. I'll split those up. * * * If the first action is a push: From here, call the existing array Small and make a new 128 element array called Big. For the first push, store it in Small[32]. Then copy Small[0] and Small[1] to Big[0] and Big[1]. For the second push, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Then for a pop, just remove the element in Small[33]. Then pushing again, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Notice how this is exactly the same as the previous push. And if you undid two pushes, then did two more pushes, both of them would be the same as they were before. So, analyzing this, once we push once, any arbitrary sequence of pushes and pops is going to do one of the following: * Pushes is always more than pops, but the difference is always under 32. This bounces around forever, undoing and redoing pushes. This is valid, and always uses the same amount of space for 33-63 elements, so that's clearly linear too. * Eventually pops catches up to pushes. This means we're back to 32 elements, right where we started. Throw out the 'Big' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pushes minus pops reaches 32. So now our Small array is completely full, and our Big array is half full, and they contain exactly the same data. Throw out the Small array. Now we're back where we started, except with twice as many elements in an array twice as big. Use all the same logic as before, but with 2x numbers. This is valid and uses linear space. * * * If the first action is a pop: From here, call the existing array Big and make a new 32 element array called Small. For the first pop, copy Big[0] to Small[0]. Then delete and return Big[31]. For the second pop, copy Big[1] to Small[1]. Then delete and return Big[30]. If we get a push, put it in Big[30]. If there's another pop, copy Big[1] to Small[1]. Then delete and return Big[30]. Notice how this is exactly the same as the previous pop. And if you undid two pops, then did two more pops, both of them would be the same as they were before. So, analyzing this, once we pop once, any arbitrary sequence of pops and pushes is going to do one of the following: * Pops are always more than pushes, but the difference is always under 16. This bounces around forever, undoing and redoing pops. This is valid, and always uses the same amount of space for 17-31 elements, so that's clearly linear too. * Eventually pushes catch up to pops. This means we're back to 32 elements, right where we started. Throw out the 'Small' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pops minus pushes reaches 16. So now our Small array is half full, and our Big array is one quarter full, and they contain exactly the same data. Throw out the Big array. Now we're back where we started, except with half as many elements in an array half as big. Use all the same logic as before, but with numbers cut by 2x. This is valid and uses linear space. There. Now, there are easy optimizations that could be done on top of that to cut the memory use in half, or combine pushing and popping into the same logic, or all sorts of other improvements. And you want to have a special case if the size gets too small to stop shrinking. But that should be a perfectly good basic explanation of an algorithm that's very straightforward and has no wiggle room for anything to go wrong.
    - vladf 5y ago
      Ah, I was in a rust/c++ frame of mind here—it seems you deeply rely on a copy operation being available, but unless you use indirection and weak pointers it might not be. I think with copy available this certainly works
      - Dylan16807 5y ago
        I used copy mostly because the earlier post used it, but we can easily use moves instead. The access operator will just have to use some arithmetic to calculate which array an element is in. Moves also make it easier to have less memory overhead. If moves aren't available then a resizable array was doomed from the start.
        vladf 5y ago
        Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) Thought maybe in principle there’s yet another “amortization process“ which can be layered on top of what you already described that tries to keep the proportion of placeholders in both small and big arrays equal.
        Dylan16807 5y ago
        You don't need placeholders. Can you explain why you're thinking about placeholders? For using move, the most straightforward way is: pushes and pops go directly to the big array. For every push you also move one element from small to big. For every pop you also move one element from big to small. This is slightly different from the algorithm above, but basically equivalent. Let's say you start with 32 elements in one array. If you grow into a bigger array, then by the time you add 32 more all your elements will be in the big array. If you shrink into a smaller array, then by the time you remove 16 all your elements will be in the small array. > (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) So let's say after the pushes we have 60/64 elements in the 64 array, almost full. There are also 2/32 in the smaller array. Then we do 10 pops. Now there are 40/64 in the bigger array, and 12/32 in the smaller array. Seems problem-free to me. If we keep doing pops we end up with 0/64 in the bigger array and 32/32 in the smaller array. At this point we could push again, or we could promote the 32 array to 'big' if we need to pop. When the arrays are size 32 and 64, the logic to access an element looks like this: n = total number of elements x = the key of element being accessed if ((x % 32) < (n - 32)) return big[x] else return small[x]

One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?

by vladf 5y ago

One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?

mjevans 5y ago

It depends on how strictly the structure of each array is defined, the answer can be yes but I don't know what effect this has on modern superscaler CPUs. The source array might be considered to have even offsets (0, 2, 4, etc, index left shift 1 bit) relative to the double-sized array. Addition operations past the halfway value of the smaller array have a relation to values in the second by (Index << 1) % n + 1 ; that is they pair with the values from the start of the smaller array. When a removal operation, like pop(), selects a victim in the source array the corresponding operations must also apply in sync to the values in the larger array.

Dylan16807 5y ago

Easily! You can just make pop do the opposite of push. For example, if push copies two elements to the bigger array, make pop copy two elements to the smaller array.

vladf 5y ago
I challenge you to try to implement it this way and test that (1) an arbitrary sequence of push/pop is valid and (2) doesn’t use more than linear space.
- Dylan16807 5y ago
  It's pretty easy to make sure an arbitrary sequence is valid if you make push and pop be almost exact opposites of each other. Let me walk through a simple version based on the description above, ignoring that it's rather inefficient: Start with an array of size 64, with 32 elements. Our first action is either a push or a pop. I'll split those up. * * * If the first action is a push: From here, call the existing array Small and make a new 128 element array called Big. For the first push, store it in Small[32]. Then copy Small[0] and Small[1] to Big[0] and Big[1]. For the second push, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Then for a pop, just remove the element in Small[33]. Then pushing again, store it in Small[33]. Then copy Small[2] and Small[3] to Big[2] and Big[3]. Notice how this is exactly the same as the previous push. And if you undid two pushes, then did two more pushes, both of them would be the same as they were before. So, analyzing this, once we push once, any arbitrary sequence of pushes and pops is going to do one of the following: * Pushes is always more than pops, but the difference is always under 32. This bounces around forever, undoing and redoing pushes. This is valid, and always uses the same amount of space for 33-63 elements, so that's clearly linear too. * Eventually pops catches up to pushes. This means we're back to 32 elements, right where we started. Throw out the 'Big' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pushes minus pops reaches 32. So now our Small array is completely full, and our Big array is half full, and they contain exactly the same data. Throw out the Small array. Now we're back where we started, except with twice as many elements in an array twice as big. Use all the same logic as before, but with 2x numbers. This is valid and uses linear space. * * * If the first action is a pop: From here, call the existing array Big and make a new 32 element array called Small. For the first pop, copy Big[0] to Small[0]. Then delete and return Big[31]. For the second pop, copy Big[1] to Small[1]. Then delete and return Big[30]. If we get a push, put it in Big[30]. If there's another pop, copy Big[1] to Small[1]. Then delete and return Big[30]. Notice how this is exactly the same as the previous pop. And if you undid two pops, then did two more pops, both of them would be the same as they were before. So, analyzing this, once we pop once, any arbitrary sequence of pops and pushes is going to do one of the following: * Pops are always more than pushes, but the difference is always under 16. This bounces around forever, undoing and redoing pops. This is valid, and always uses the same amount of space for 17-31 elements, so that's clearly linear too. * Eventually pushes catch up to pops. This means we're back to 32 elements, right where we started. Throw out the 'Small' array too. Going back where we started is valid and uses linear space. If the next action is a push, go to the start of the push instructions. If it's a pop, go to the start of the pop instructions. * Eventually pops minus pushes reaches 16. So now our Small array is half full, and our Big array is one quarter full, and they contain exactly the same data. Throw out the Big array. Now we're back where we started, except with half as many elements in an array half as big. Use all the same logic as before, but with numbers cut by 2x. This is valid and uses linear space. There. Now, there are easy optimizations that could be done on top of that to cut the memory use in half, or combine pushing and popping into the same logic, or all sorts of other improvements. And you want to have a special case if the size gets too small to stop shrinking. But that should be a perfectly good basic explanation of an algorithm that's very straightforward and has no wiggle room for anything to go wrong.
  - vladf 5y ago
    Ah, I was in a rust/c++ frame of mind here—it seems you deeply rely on a copy operation being available, but unless you use indirection and weak pointers it might not be. I think with copy available this certainly works
    - Dylan16807 5y ago
      I used copy mostly because the earlier post used it, but we can easily use moves instead. The access operator will just have to use some arithmetic to calculate which array an element is in. Moves also make it easier to have less memory overhead. If moves aren't available then a resizable array was doomed from the start.
      - vladf 5y ago
        Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) Thought maybe in principle there’s yet another “amortization process“ which can be layered on top of what you already described that tries to keep the proportion of placeholders in both small and big arrays equal.
        Dylan16807 5y ago
        You don't need placeholders. Can you explain why you're thinking about placeholders? For using move, the most straightforward way is: pushes and pops go directly to the big array. For every push you also move one element from small to big. For every pop you also move one element from big to small. This is slightly different from the algorithm above, but basically equivalent. Let's say you start with 32 elements in one array. If you grow into a bigger array, then by the time you add 32 more all your elements will be in the big array. If you shrink into a smaller array, then by the time you remove 16 all your elements will be in the small array. > (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back) So let's say after the pushes we have 60/64 elements in the 64 array, almost full. There are also 2/32 in the smaller array. Then we do 10 pops. Now there are 40/64 in the bigger array, and 12/32 in the smaller array. Seems problem-free to me. If we keep doing pops we end up with 0/64 in the bigger array and 32/32 in the smaller array. At this point we could push again, or we could promote the 32 array to 'big' if we need to pop. When the arrays are size 32 and 64, the logic to access an element looks like this: n = total number of elements x = the key of element being accessed if ((x % 32) < (n - 32)) return big[x] else return small[x]