News for hackers. Stuff that matters.
Re:I had to give a wrong answer to get the job (2017) by pavpanchekha on Monday July 19, 2021 @01:11PM (#27884977)
Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not—

Keep two arrays, of size n and 2n. Initially the first has capacity c = n/2 and the second has capacity 0. Reads go to the first array. When you append, append one element to the first array, and copy two elements to the second array. By the time the first array is full, it has been entirely copied to the second array—so discard the first array, move the second array to be first, and allocate a new "next" array.

The same trick can be applied to many amortized data structures (but it gets very complicated when you have many operations).

Re:I had to give a wrong answer to get the job (2017) by pierrebai on Monday July 19, 2021 @03:11PM (#27886222)
This is dangerous, but if well documented and understood it might be okay. Some data might contain unique things (for argument's sake, say a std::unique_ptr). It can get tricky since you need to know the implementation details of everything that gets inserted and it's ownership behavior, since elements can be kept at two places. (A copy in array n and one in 2n.)

Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.

As for the original interview question, there are systems where an occasional longer pause is not OK. Personally, I think that sticking to your gun must have come across as being stubborn and unyielding and maybe not ready to admit errors. As an interviewer, and for having worked with people who always think they're right and inflexible, it would have been a red flag.

Re:I had to give a wrong answer to get the job (2017) by rav on Monday July 19, 2021 @03:31PM (#27886430)
> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.

> As for the original interview question, there are systems where an occasional longer pause is not OK.

As you say, it's a tradeoff between worst-case operation cost and average operation cost: If you allow any worst-case operation cost, you can get really efficient on average. If you want really efficient worst-case operation cost, you can't get it down to exactly the average operation cost you could've otherwise gotten.

I wouldn't be surprised if this tradeoff is inherent to many de-amortization problems. But since the difference between the amortized and de-amortized solution is usually only a constant factor (as it is in this case), you have to be very specific about the model of computation if you want to prove anything mathematically.

Re:I had to give a wrong answer to get the job (2017) by remram on Friday July 23, 2021 @03:02PM (#27934398)
To be clear, there is no tradeoff in the number of operations. You are doing the exact same number on average (or total or amortized), while improving the worst-case.

You do lose the ability to do a no-copy realloc() though, and increase the average memory use (not peak).

Re:I had to give a wrong answer to get the job (2017) by nearbuy on Monday July 19, 2021 @09:26PM (#27889203)
> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.

This is the exact same average cost per element, just spread out evenly. Consider that each element still gets copied to the array of twice the size once whether you use this technique or the classic amortized version. Same average performance without the hitches (although copying a larger block of memory at once would likely be a bit faster).

Re:I had to give a wrong answer to get the job (2017) by scottlamb on Monday July 19, 2021 @05:07PM (#27887266)
> This is dangerous, but if well documented and understood it might be okay.

I agree in principle. I think even something like std::unique_ptr could work; the concern would be self-referential types. Notably Rust doesn't allow those anyway, so I think any Rust type would be fine, not just Copy types.

> Then there is the fact that you basically make every insertion 3x as costly. You better have a good reason to need this given the additional complexity and caveats.

Still might be a lot better than a linked list for small types (due to less RAM spent on pointers and better cache locality because it's contiguous). With the exception of intrusive linked lists of stuff that is separately allocated anyway, I really hate linked lists.

Re:I had to give a wrong answer to get the job (2017) by vladf on Monday July 19, 2021 @01:28PM (#27885142)
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?
Re:I had to give a wrong answer to get the job (2017) by mjevans on Monday July 19, 2021 @02:53PM (#27886052)
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.

Re:I had to give a wrong answer to get the job (2017) by Dylan16807 on Monday July 19, 2021 @11:13PM (#27889706)
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.
Re:I had to give a wrong answer to get the job (2017) by vladf on Tuesday July 20, 2021 @01:35AM (#27890412)
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.
Re:I had to give a wrong answer to get the job (2017) by Dylan16807 on Tuesday July 20, 2021 @02:35AM (#27890696)
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.

Re:I had to give a wrong answer to get the job (2017) by vladf on Tuesday July 20, 2021 @04:24PM (#27898819)
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

Re:I had to give a wrong answer to get the job (2017) by Dylan16807 on Tuesday July 20, 2021 @04:46PM (#27899091)
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.

Re:I had to give a wrong answer to get the job (2017) by vladf on Tuesday July 20, 2021 @05:48PM (#27899833)
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.

Re:I had to give a wrong answer to get the job (2017) by Dylan16807 on Tuesday July 20, 2021 @06:47PM (#27900271)
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]

Re:I had to give a wrong answer to get the job (2017) by vecter on Monday July 19, 2021 @02:39PM (#27885915)
IIUC, this is assuming that memory allocation is O(1)?
Re:I had to give a wrong answer to get the job (2017) by hawk_ on Monday July 19, 2021 @05:00PM (#27887203)
yes it's rare to not assume that.
Re:I had to give a wrong answer to get the job (2017) by mhh__ on Tuesday July 20, 2021 @01:22AM (#27890346)
The coefficient can and will bite your head off, however.
Re:I had to give a wrong answer to get the job (2017) by steelframe on Monday July 19, 2021 @05:00PM (#27887204)
The primary thing I like about this approach vs. stopping to copy the entire array on expanding its capacity is cache hotness.
Re:I had to give a wrong answer to get the job (2017) by mhh__ on Tuesday July 20, 2021 @01:24AM (#27890357)
Evidence?