Perhaps the common approach to performance testing is wrong (forget for a moment that most shops don't think about it at all; let's just consider quality developers/companies). Instead of just monitoring whether the product is fast enough for minimal/typical/peak expected usage, maybe it would be good to focus on determining a boundary. E.g. how much data does it take for the program to run 60 seconds? Or, in general, 10x longer than the maximum you'd consider acceptable? How much data does it take for it to run out of memory?

These determinations can be made with few tests each. Start with some reasonable amount of data, keep doubling it until the test fails. Continue binary-searching between last success and last failure.

The results may come out surprising. Performance does not scale linearly - just because your program takes 1 second for 1 unit of data, and 2 seconds for 2 units of data, doesn't mean it'll take 20 seconds for 20 units of data. It may as well take an hour. Picking a threshold far above what's acceptable, and continuously monitoring how much load is required to reach it, will quickly identify when something is working much slower than it should.