News for hackers. Stuff that matters.
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).