This is one that is hard for people to really internalize, I think? The SAT solvers many are likely to use today are not at all the same as the ones they would have used 20 years ago. They have made some amazing advances in how to approach those problems.

There are also probably some very poorly conceived models that people use to adapt a problem to some of these solvers.

That is, why couldn't they have done the essentially same trick that you reference for += with reduce?

With hashtables, it was more that it was not guaranteed to be the minimal cost. Just, depending on statistics of the data that you feed to it, it shouldn't be the worst case.

To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in a program. And then decide from there on whether you are worried about some of the more esoteric growth patterns.

I'd love to read a good history of the different development styles. I know we often have a good exploration of the parts of an executable file. I don't recall seeing a good exploration of different compilation/build styles through the years.

That can be a really hard thing for people to realize. We will ask, "why didn't someone use this really compelling framing to get me hooked on something?!" And then move to something like "how come nobody has ever said just walking an hour a day will get you in pretty good physical shape?" Thing is, plenty of people say stuff like that.

And don't mistake this as blaming the listener! The point is messages can often come when you flat out aren't prepared for them.

So, what do we do? We spend time on the rote muscle memory of facts. In the hopes that that will prepare you for the next time a message comes and you are then ready for it.

Ideally, you rinse and repeat this. Constantly. All too often, the cycle gets subverted, though, and you forget to reopen yourself to the messages that came before.