Re: Hokay, I officially give up...

On Fri, 22 May 2009, Brian Hurt wrote:

> There's a middle ground short of writing mathematical proofs about your
> code.  But that's a different rant.

This is a good occasion, because I'm curious about how different the rant 
could be.

> The problem is that it doesn't matter how often you test the code, you
> might not find the bug.  The proof of this is easy.  Assume the following:
> you have M threads, each of which is doing N atomic operations in order.
> How many different permutations of different atomic operation orderings do
> you have to deal with?  It's easy to figure out that the formula is:
> 	(M*N)!/(M*(N!))
> which gets large quick.  For example, if you have 10 threads, each
> performing 4 atomic actions, you have more than 10^45 possible sequences
> of actions.  If one of them causes a bug, you have a problem.  But it
> doesn't matter if you test 10^3, 10^6, 10^9, even 10^12 different
> sequences, you're only testing a tiny fraction.

Fortunately, bugs that can only explained using long sequences of atomic 
operations are quite rare and their likelihood decreases as N increases.
I'd be more worried about what we forget to look at: the code appears to 
work when you check the result, but the check is incomplete, or there are 
things that aren't part of the result and shouldn't change and have been 
changed (corruption). All those hidden variables can create situations 
that look like you have long chains of atomic operations that fail the 
test while any shorter chain passes it, but the solution to the bug is to 
figure out hidden failures in short tests, that eventually explain 
incomprehensible failures in long tests.

> If performance matters *at all*, then threading will matter.

I would rather not see it in this way. It's not like performance matters 
or not, for solving a problem, it's whether you have enough computing 
power for the task. Performance always matters in a program, you just have 
to find a sufficiently slow computer for that to manifest itself, but 
that's why hardware requirements get stated in the first place.

> Even if my code is 1/10th the speed of yours on a single processor, if I 
> make use of the 1024 cores available...

... then your code will run 102,4 times faster than mine, which is why it 
will have to artificially slow itself down by a factor of 102,4 so that it 
becomes as real-time as the user wants it to be. Yet, performance of this 
same app may be a serious issue on much slower machines.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec