3 ms·

You can't justify this one with the "no true scotsman" fallacy. If you do a test that shows that X is faster than Y, you're allowed to say "X proved faster tha

You can't justify this one with the "no true scotsman" fallacy. If you do a test that shows that X is faster than Y, you're allowed to say "X proved faster than Y". You're equally allowed to say "merge sort is proven to sort any list with an upper bound of n log n comparisons" after you write up a mathematical proof of that. (But welcome to the sadness of the real world, where the running time of a sort might not be slow because of the number of comparisons, but "real world" annoyances like cache hit rate.) HN is largely software engineering practitioners. Practice is one level of complexity above the mathematics; among the mathematically optimal solutions to a problem, you have to find the one that's actually fastest on some sort of computer you can buy. Otherwise the math is just an interesting fact to throw out at parties. Testing in the real world is really the only way to find the solution that is fastest in the real world, but of course, mathematics dramatically limits the search space for the ideal algorithm. Basically, farmers aren't interested in how much milk a spherical cow can produce. There are no spherical cows.

junon 4y ago
It's not proven. You've demonstrated it was faster on your machine. That's the end of it. From a CS perspective, you've not proven anything at all. You've also completely misrepresented my point. It's not a "no true Scotsman" fallacy, at all. Not sure what spherical cows have anything to do with anything.
- nick__m 4y ago
  Do you know that a word can have a different meaning in a different context? You describe a formal proof but the Collin dictionary define proof that way : Proof is a fact, argument, or *piece of evidence* which shows that something is definitely true or definitely exists. That demonstration is a piece of evidence that shows that an algorithm is truly faster on that computer with that specific input, sure it's not a formal generalizable CS proof but it a valid usage of the word proven nonetheless.
  - junon 4y ago
    Yes, clearly I'm aware of that. In the context of computer science, it is not proven.
judofyr 4y ago
This is a quite interesting discussion actually! Some thoughts: First of all: Theoretical results are actually quite important for real-life performance. It’s possible to write an implementation of bubble sort, have a bunch of benchmarks which shows great performance and 100% test coverage. Yet there are cases where you’ll hit the n^2. The theoretical proof (especially the worst case) are quite important to not get bitten by this. You can search for “accidental quadratic” for plenty of cases where this happens in practice: people have implemented algorithms which works well in practice for small n, but fails (unnecessary) for larger n. A theoretical analysis would have caught this (although probably not worth the engineering effort). Secondly: “proving” isn’t exclusive to theoretical analysis. I’d argue you can “prove” that a method call in Ruby is slower than a function call in C. You can look at the machine code which gets executed and see that there’s no way for a CPU (regardless of cache, pipelining etc) to execute the Ruby variant faster. There will of course be plenty of assumptions (as there is in theoretical proofs as well!), but in my option it’s a proof nonetheless. However, to claim that “Kermem is provably 10x faster than FlatBuffers”, I’d say that you need more than a few benchmarks. You’d have to argue that every operational is (at worst) 10x faster.
kortex 4y ago
> If you do a test that shows that X is faster than Y, you're allowed to say "X proved faster than Y". No, you have the hypothesis X is faster than Y, and some evidence to back it up. It's no different than a scientist treating cancer cells with unobtainium, and claiming it "proves unobtanium cures cancer". You need a lot more rigor to prove benchmarks. Notably absent is some independent verification and peer review. It's possible to write benchmarks in ways that bias the outcome. If you have multiple different benchmarks written by independent authors and counter-reviewed, all showing 10x speedup, sure, call it "proven". A few benchmarks on 3 arches, no, use the word "shown" or similar.

junon 4y ago

It's not proven. You've demonstrated it was faster on your machine. That's the end of it. From a CS perspective, you've not proven anything at all. You've also completely misrepresented my point. It's not a "no true Scotsman" fallacy, at all. Not sure what spherical cows have anything to do with anything.

nick__m 4y ago
Do you know that a word can have a different meaning in a different context? You describe a formal proof but the Collin dictionary define proof that way : Proof is a fact, argument, or *piece of evidence* which shows that something is definitely true or definitely exists. That demonstration is a piece of evidence that shows that an algorithm is truly faster on that computer with that specific input, sure it's not a formal generalizable CS proof but it a valid usage of the word proven nonetheless.
- junon 4y ago
  Yes, clearly I'm aware of that. In the context of computer science, it is not proven.

judofyr 4y ago

This is a quite interesting discussion actually! Some thoughts: First of all: Theoretical results are actually quite important for real-life performance. It’s possible to write an implementation of bubble sort, have a bunch of benchmarks which shows great performance and 100% test coverage. Yet there are cases where you’ll hit the n^2. The theoretical proof (especially the worst case) are quite important to not get bitten by this. You can search for “accidental quadratic” for plenty of cases where this happens in practice: people have implemented algorithms which works well in practice for small n, but fails (unnecessary) for larger n. A theoretical analysis would have caught this (although probably not worth the engineering effort). Secondly: “proving” isn’t exclusive to theoretical analysis. I’d argue you can “prove” that a method call in Ruby is slower than a function call in C. You can look at the machine code which gets executed and see that there’s no way for a CPU (regardless of cache, pipelining etc) to execute the Ruby variant faster. There will of course be plenty of assumptions (as there is in theoretical proofs as well!), but in my option it’s a proof nonetheless. However, to claim that “Kermem is provably 10x faster than FlatBuffers”, I’d say that you need more than a few benchmarks. You’d have to argue that every operational is (at worst) 10x faster.

kortex 4y ago

> If you do a test that shows that X is faster than Y, you're allowed to say "X proved faster than Y". No, you have the hypothesis X is faster than Y, and some evidence to back it up. It's no different than a scientist treating cancer cells with unobtainium, and claiming it "proves unobtanium cures cancer". You need a lot more rigor to prove benchmarks. Notably absent is some independent verification and peer review. It's possible to write benchmarks in ways that bias the outcome. If you have multiple different benchmarks written by independent authors and counter-reviewed, all showing 10x speedup, sure, call it "proven". A few benchmarks on 3 arches, no, use the word "shown" or similar.