6 ms·

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). I

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.

rav 5y ago
> 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.
- remram 5y ago
  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).
scottlamb 5y ago
> 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.
deleted 5y ago
[deleted]
nearbuy 5y ago
> 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).

rav 5y ago

> 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.

remram 5y ago
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).

scottlamb 5y ago

> 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.

deleted 5y ago

[deleted]

nearbuy 5y ago

> 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).