Sources of Complexity: Constraints

submited by

Style Pass

2023-01-24 00:30:08

But software is complex for a reason. While people like coming up with grand theories of complexity (Simple Made Easy, No Silver Bullet) there’s very little info out there on the nitty-gritty specific sources of complexity. Without that, all the theories feel to me like the four elements theory. We just don’t have the data needed to come up with something more predictive. 1

A constraint is any measurable quality of the system that you have as a goal. The canonical constraint is performance: if your software runs too slow, you need to fix your software. Anything measurable can be a potential constraint:

Every constraint has variations, depending on what specifically we’re trying to measure. Does performance mean latency or throughput? Worst-case or average-case performance? Single-threaded or parallel performance? Or we could be constraining the variation of a metric, like guaranteeing constant-time operations.

I think this is “obvious”, so much so that it’s hard for me to step out of that mindset and support it from first principles. The best I can do is give an example. Take sorting: Insertion sort is very simple to understand and has a simple implementation that’s easy to prove correct. If you didn’t have any performance constraints, you’d be fine sorting with insertion sort. But it also has O(n²) worst case performance. Mergesort is considerably more complex, but has O(nlogn) performance. You can choose to make your program more complex to better match your performance constraints.