So just what does synchronized do? 58

Posted by Brett Schuchert Fri, 04 Jan 2008 03:27:00 GMT

Synopsis

Using synchronized turns a huge state space into a comparatively small one.

Normally, the light from a star radiates out in all directions. But what happens when a star collapses? There are several possibilities depending on the mass of the star. Our sun will turn into a red giant and then later turn into a white dwarf, giving out light from its accumulated heat for many years after living on Earth has become unbearable; mostly because of all the traffic.

If the mass of the star is around 10x our star, its destiny is just a bit different. It will begin to collapse. Along the way, it will probably have some temporary reprieves from its ultimate fate, to become a Neutron star, by consuming other heavier elements such as carbon and helium . However, the writing is on the wall. The center of star, already an extreme environment, becomes even more so; eventually, the pressure from the collapsing of material into the center of the star results in a massive explosion known as a nova or super nova – depending on the mass of the star. What is left is a neutron star. A neutron star is the heart of a pulsar, able to spin at amazing rates without pulling itself apart.

Another option is a black hole. A black hole is an often used metaphor for either the effort expended on support/fixing/updating a big ball of mud or what the development effort appears to be in most of the time. Either way, it is not considered a good thing if you’re anywhere in the vicinity.

I’m a pessimist by nature. I see a project in decline, sucking in other resources, like a black holes eating neighboring galaxies, snuffing the light out of stars, just like projects can suck the life force out of individuals.

However, energy can escape from a black hole, eventually leading to the demise of the black hole. Energy can escape along the axis of rotation in either direction. In a sense, if we see the expansion of the black hole as a bad thing, anything that diminishes a black hole is a good thing. Stephen Hawking theorized that at the event horizon of black holes, fluctuations in the space can cause the spontaneous creations of pairs of particles and their anti particles. This is another way it can appear that a black hole is losing energy since it gives off particles while the opposite particle goes into the black hole.

Now I’m off track. I wanted to talk about how synchronized give a similar effect as the massive gravity of black hole. But instead of curving space-time, they invert the possible state space of code in the presence of threads. Let’s take a look.

Here’s a simple class:

public class X {
   int value;

   public synchronized void incrementValue() {
        ++value;
    }
}
Let’s say, for the sake of argument, two threads are trying to execute the single method in this class. If the method is written like this:

   public synchronized void incrementValue() {
        ++value;
    }

Then there are only two orderings, Thread 1/Thread 2, or Thread 2/Thread 1. All of those paragraphs at the top were to make this analogy.

OK, so if we use synchronized that that’s the black hole. The number of possible paths through the code for N threads is N!. What’s the opposite? What happens if we take off the keyword and then run two threads through it? In how many ways can that single line of code get executed?

Are you ready for it?

3,432 different ways

Really? Well at least conceptually. In practice, the Just In Time compiler will probably turn the JVM instructions into native code, so the actual number of individual steps will probably be less. But there really are that many paths through the system. You might ask how?

That single line of code is represented in byte code as 7 lines. I could show you the disassembly, but really, it’s 7. You can convince yourself by having a look at the byte-code using a nice byte-code viewer plug-in for eclipse.

What happens if we change the int to a long? We still have 7 lines of byte-code, but with different instructions. We have a total of 4 long reads/writes. Each long read/write requires two individual 32-bit operations – or at lest the JVM can implement it that way. The actual number of atomic operations after the Just In Time compiler has had its way with your byte-code will probably be less, but if we stick to byte-codes and the Java memory model, the number 3,432 is now a whopping 705,432!

Let’s extend that just a bit more. What if you have several lines of code? Each line of Java results in many more lines of byte-code. What if we have have 3 lies of Java? We probably have something like 21 lines of byte-code. How many paths of execution would 21 lines of byte-code executed by two threads have? 538,257,874,440!

Where the first program ended up being a white dwarf, the version using longs was a nova. I’m not sure what to call the thee line Java method, maybe a hyper-nova?

In practice, the actual number of paths through a method will end up being smaller. And, most of the paths do not have any negative side-effects. The problem, however, is that there are a small number of hard to find paths of execution that do cause problems and finding them is like looking for a needle in a haystack.

Remember what adding the keyword synchronized did? If we use it on a three line method, it turns 538,257,874,440 into 2. It collapses the number of paths into 2 for two threads. And 2 is less than 538,257,874,440, for even vary large values of 2.

How did I derive at these magic numbers? Two ways.

I wanted to know how many possible orderings there were for 7 instructions and two threads. I knew it had to do with combinations and permutations but I just wasn’t smart enough to figure it out. Searching on Google didn’t do much for me either. So I decided to write a program to numerically derive the result. I tested my way into a program that would calculate the result.

The basic algorithm is:
  1. Determine all possible orderings of each of the unique “nodes” in a system. For example, if I have 2 threads and 2 instructions, I can generate a natural key (ugh!) to represent each of the different combinations of threads and instructions: T1S1 T1S2 T2S1 2S2.
  2. Produce all valid permutations of these four “nodes”.
  3. Remove any that have invalid orderings.
  4. Count the results.

Many of my first implementations for some of these steps were exercises in writing really inefficient code! But having those tests made it really easy to swap out better algorithms when my brain caught up with what I was doing.

What is an invalid ordering? The code generated by the single line using the pre increment operator has 7 steps. Those 7 steps are in a single sequence with no looping and no conditionals. That’s like saying A is always before B. So if we generate a list of orderings that end up including that combination, we’ve generated an ordering that cannot happen.

So you can describe your possible state space in a few steps:
  1. Register a node for each thread, step combination. 7 threads, 4 steps = 28 nodes.
  2. Register dependences between steps. For example, if I have seven steps and two threads executing the same sequence, I could describe this as: T1S1 -> T1S2 -> T1S3, etc. And for the second thread: T2S1 -> T2S2 -> T2>S3. Since the name is arbitrary, I just used letters, so in fact I had: a -> b -> c -> d -> e -> f -> g for one set of dependencies and h -> i -> j -> k -> l -> m -> o

In fact, here’s the test I used to describe that exact space:


    @Test
    public void twoThreadsAndSevenSteps() {
        calculator = new PathCalculator(14);
        createLine('a', 'b', 'c', 'd', 'e', 'f', 'g');
        createLine('h', 'i', 'j', 'k', 'l', 'm', 'n');
        start();
        int totalPaths = calculator.totalPaths();
        stop(2, 4, totalPaths);
    }

By the time I got to this point, I wrote some “tests” using JUnit as a harness to run my code and display timing information and a summary of the


Time:        4ms -- Threads:  3, Opcodes:  2, Total paths:      90
Time:        1ms -- Threads:  2, Opcodes:  3, Total paths:      20
Time:       54ms -- Threads:  4, Opcodes:  2, Total paths:    2520
Time:        3ms -- Threads:  2, Opcodes:  4, Total paths:      70
Time:       61ms -- Threads:  2, Opcodes:  5, Total paths:     252
Time:     1248ms -- Threads:  2, Opcodes:  6, Total paths:     924
Time:    12819ms -- Threads: 10, Opcodes:  1, Total paths: 3628800
I then used this information to fit a cure to my data and derive a formula for various combinations. For 2 threads, I came up with the following formula. If you let N be the number of steps:
Total Paths = 252 * 3.6667 N-5

The morning after, Uncle Bob sent an email, showing me his work on how he calculated.

If you let:
  1. T be the number of threads
  2. N be the number of steps
Total = (N*T)!   /   N! T

When I plugged numbers into his formula, they fit my formula. His formula generated an exact result as opposed to my estimate based on fitting a curve. Another thing his solution has going for it is the algorithm I came up with, I believe, is NP-complete. The net effect was I that while I was able to calculate result for 2 threads and 6 steps, 2 threads and 7 steps took a long time before running out of memory with a 2GB heap space. Bob’s formula gave me a so-called verifier (as did my formula – only Bob’s was better) and the algorithm seems to grow based on factorials and not polynomials.

What’s the point of all of this? The single, one-line program, is a demonstration of why going from one thread to two threads makes writing/debugging/testing programs so much harder. It also numerically demonstrates why the single responsibility principle is even more important when we start writing concurrent programs. The more you put in one place, the large the state space. Larger state spaces:

  1. Make it harder to find that one or few number of paths that can cause your program to die, under load, in production, while you are on vacation
  2. Make your efforts to test (which is a sampling technique anyway) for concurrency issues all the more difficult
  3. Make it harder to find what might actually have caused a failure once you’ve notice it.

In a later post, I’ll describe how we can improve our chances of covering this huge space of potential orderings.

If you’ve made it this far, wow! Congratulations!

Comments

Leave a response

  1. Avatar
    Germán B. about 8 hours later:

    In many cases it might be convenient to use a concurrency model in which threads don’t share state (Erlang style). I haven’t yet done that and I guess it could be a bit painful to do it in Java. But you’d get rid of the dangerous side-effects.

  2. Avatar
    Brett Schuchert about 17 hours later:

    That is a great thing to do. In fact, all of those possible interactions are irrelevant when you do exactly that. That’s why we avoid instance variables in Servlets and pass everything on the stack.

    In general, any time you can reduce the scope of information (e.g. not sharing data between threads), you reduce the scope of possible side-effects.

    In some cases, however, you’re trying to get multiple threads working on the same problem, especially when you’re working with I/O bound problems. In that case, you have common data. But you want to minimize the scope of possible interaction both to reduce the chance of problems creeping up and to reduce contention.

  3. Avatar
    Curious Mind about 17 hours later:

    Could someone explain how we can derive the formula Total = (N*T)! / ( T!) ^(N) ?

  4. Avatar
    Brett Schuchert about 19 hours later:

    This is from an email Uncle Bob Sent me (so give the credit to him):

    With N steps and T threads there are T x N total steps. Prior to each step there is a context switch that chooses between the T threads. Each path can thus be represented as a string of digits denoting the context switches. Given steps A and B and threads 1 and 2 the six possible paths are 1122, 1212, 1221, 2112, 2121, and 2211. Or in terms of steps it is: A1B1A2B2, A1A2B1B2, A1A2B2B1, A2A1B1B2, A2A1B2B1, and A2B2A1B1.

    For three threads the sequence is 112233, 112323, 113223, 113232, 112233, 121233, 121323, 121332, 123132. 123123, ...

    One characteristic of these strings is that there must always be N instances of each T. So the string 111111 is invalid because it has 6 instances of 1 and zero instances of 2 and 3.

    So we want the permutations of N 1’s, N 2’s, ... and N T’s. This is really just the permutations of N x T things taken N x T at a time (which is (N x T)!), but with all the duplicates removed. So the trick is to count the duplicates and subtract that from (N x T)!.

    Given two steps and two threads, how many duplicates are there? Each four digit string has two 1’s and two 2’s. Each of those pairs could be swapped without changing the sense of the string. You could swap the 1s, or the 2s, both, or neither. So there are four isomorphs for each string, which means that there are three duplicates. So three out of four are duplicates. Or only 1/4 of the permutations are NOT duplicates. 4! * .25 = 6. So this reasoning seems to work.

    How many duplicates are there? In the case where N=2 and T=2 I could swap the 1’s the 2’s or both. In the case where N=2 and T=3 I could swap the 1’s, the 2’s, the 3’s, 1’s and 2’s, 1’s and 3’s, or 2’s and 3’s. Swapping is just the permutations of N. Let’s say there are P permutations of N. The number of different ways to arrange those permutations are PT.

    So the number of possible isomorphs is N!T. And so the number of paths is (T x N)!/(N! ^ T). Again in our T=2, N=2 case we get 6. (24/4).

    For N=2 and T=3 we get 720/8 = 90. (Does that seem right?)

    For N=3 and T=3 we get 9!/6^3 = 1680.

  5. Avatar
    Curious Mind 1 day later:

    I am not convinced by the proof. It is not a question of duplicates, but of removing invalid combinations among the (N*T)! possible ways to arrange them. Invalid combinations are those where step 2 comes first before step 1 is done by a particular thread.

    The proof seems more like a trial and error effort than a rigorous one.

    Just curious about the proof. The formula seems right though.

  6. Avatar
    Brett Schuchert 1 day later:

    I’m not sure where you got the impression that anything I was doing was a proof. Ultimately, when Bob gave me the formula, I was satisfied. That the estimate I derived numerically matched his formula so well told me that I probably correctly wrote the program. However, the program was simply a tool to figure out the number of possibilities.

    As to your concerns, here’s the method in a little more detail.
    1. I used TDD to verify that I was producing all combinations correctly. I ended up working through various algorithms until I eventually wrote a recursive algorithm that looks like how you’d approach it using lisp. While I only verified that the I got all permutations correctly for up to 4, I did verify that for several larger numbers of nodes I got the correct number.
    2. I next used TDD to develop a class that used the permutation generator and then removed invalid paths. By invalid path, I reviewed the entire chain of orderings and looked to see if any transition was invalid. To do so, I used an O(N^2) algorithm. Starting at the first element, I asked (given my dependencies) if any of the following nodes were invalid. I then did that for the next node, the next, etc. I believe I generated the transitive closure correctly so that I did not forget to filter out any paths.
    Here’s one of the unit tests I used for the permutation generator:
        @Test
        public void fourGives24() {
            PermutationGenerator generator = new PermutationGenerator(4);
            List<String> allPermutations = generator.validPermutations();
            assertEquals(24, allPermutations.size());
            assertTrue(allPermutations.contains("abcd"));
            assertTrue(allPermutations.contains("abdc"));
            assertTrue(allPermutations.contains("acbd"));
            assertTrue(allPermutations.contains("acdb"));
            assertTrue(allPermutations.contains("adbc"));
            assertTrue(allPermutations.contains("adcb"));
    
            assertTrue(allPermutations.contains("bacd"));
            assertTrue(allPermutations.contains("badc"));
            assertTrue(allPermutations.contains("bcad"));
            assertTrue(allPermutations.contains("bcda"));
            assertTrue(allPermutations.contains("bdac"));
            assertTrue(allPermutations.contains("bdca"));
    
            assertTrue(allPermutations.contains("cabd"));
            assertTrue(allPermutations.contains("cadb"));
            assertTrue(allPermutations.contains("cbad"));
            assertTrue(allPermutations.contains("cbda"));
            assertTrue(allPermutations.contains("cdab"));
            assertTrue(allPermutations.contains("cdba"));
    
            assertTrue(allPermutations.contains("dabc"));
            assertTrue(allPermutations.contains("dacb"));
            assertTrue(allPermutations.contains("dbac"));
            assertTrue(allPermutations.contains("dbca"));
            assertTrue(allPermutations.contains("dcab"));
            assertTrue(allPermutations.contains("dcba"));
        }
    
    Here’s a sampling of some of the tests I used to verify that only the paths that should be generated, were:
       @Test
    public void noNodesNoPaths() {
        calculator = new PathCalculator(0);
        assertEquals(0, calculator.totalPaths());
    }
    
    @Test
    public void oneNodeResultsInOnePossiblePath() {
        calculator = new PathCalculator(1);
        int totalPaths = calculator.totalPaths();
        assertEquals(1, totalPaths);
    
    }
    
    @Test
    public void threeNodesNoDependencies6Paths() {
        calculator = new PathCalculator(3);
        int totalPaths = calculator.totalPaths();
        assertEquals(6, totalPaths);
    }
    
    @Test
    public void fourNodesNoDependencies24Paths() {
        calculator = new PathCalculator(4);
        int totalPaths = calculator.totalPaths();
        assertEquals(24, totalPaths);
    }
    
    @Test
    public void twoNodesOneDependencyOnePath() {
        calculator = new PathCalculator(2);
        createLine('a', 'b');
        int totalPaths = calculator.totalPaths();
        assertEquals(1, totalPaths);
    }
    
    @Test
    public void threeNodesInALineOnePath() {
        calculator = new PathCalculator(3);
        createLine('a', 'b');
        createLine('b', 'c');
        int totalPaths = calculator.totalPaths();
        assertEquals(1, totalPaths);
    }
    
    @Test
    public void fourNodesWithTwoIndependentDependneciesShouldResultInSixPahts() {
        calculator = new PathCalculator(4);
        createLine('a', 'b');
        createLine('c', 'd');
        int totalPaths = calculator.totalPaths();
        assertEquals(6, totalPaths);
    }
    
    @Test
    public void twoNodesWithFlowInBothDirectionsShouldResultInNoPaths() {
        calculator = new PathCalculator(2);
        createLine('a', 'b');
        createLine('b', 'a');
        int totalPaths = calculator.totalPaths();
        assertEquals(0, totalPaths);
    }
    

    But regardless of that, if you are convinced of the formula, then that’s really all that matters. The primary point is that there are a lot of different ways in which a very small amount of code can execute.

  7. Avatar
    Anthony Bailey 1 day later:

    I did the quickest of sanity checks, and the expression (N*T)! / (T!^N) doesn’t collapse to 1 when T=1, so it can’t be right.

    Having read what Uncle Bob wrote, his reasoning seems correct, you’ve just mistranscribed his result: he got (N*T)! / (N!^T)

  8. Avatar
    Brett Schuchert 1 day later:

    Ah! You are correct. Thanks for finding my error.

    I’ve corrected the original post.

  9. Avatar
    Curious Mind 1 day later:

    Ok. With the newer version, it is easy to prove the formula.

  10. Avatar
    Curious Mind 3 days later:

    It is interesting how a little knowledge of Mathematics can help eliminate a lot of code (and tests.)

    In this case, once we know the formula for the total number of valid paths, not a single line of code is required. After all, the intent was to show the possible paths and how synchronize can reduce them. With the formula, we know the number of paths; there is no need to write any code or tests.

    On another topic, the test code shown has horrendous duplication. Why could not one write a single test method, pass it the value of “T” and “N” and the expected result and see whether it works? That way, it is just a matter of passing a collection and seeing which tests succeed and which fail.

    Adding more tests is as simple as adding more rows (elements) to the collection. If the test input data is stored in a data source (database, text file, ...) then one never has to change the test code! And isn’t that what “soft”ware is about, the ability to change things easily?

    Code duplication is why I don’t like the current way of writing one method for each test case. The test code in the comment by the original author proves my point.

    Sorry for being harsh, but as a contributor to a somewhat popular blog, you should hold yourself to high standards. There is the chance that others may take what they read here as the gospel truth without thinking critically for themselves.

  11. Avatar
    Brett Schuchert 3 days later:

    In this particular case, a little knowledge of mathematics does indeed obviate all need to write any code.

    Your comments about code duplication are well taken and in this case you’re correct. It is possible. In fact, below is just such an example.

    Before I get to that, I do want to ask about this:

    Code duplication is why I don’t like the current way of writing one method for each test case. The test code in the comment by the original author proves my point.

    I don’t see any comments in any of the code in the entire post. What am I missing?

    Should I infer from this that you don’t, in general, like writing test methods but prefer instead to write things closer to the below:

    This is a a test that verifies a filter on class packages works as expected. The method annotated with @Parameters represents a collection of tests. Add a new Object[] array of values to the collection, get a new test:

    package schuchert.contest;
    
    import static junit.framework.Assert.assertEquals;
    
    import java.util.ArrayList;
    import java.util.Collection;
    
    import org.junit.Before;
    import org.junit.Test;
    import org.junit.runner.RunWith;
    import org.junit.runners.Parameterized;
    import org.junit.runners.Parameterized.Parameters;
    
    @RunWith(Parameterized.class)
    public class DynamicInstrumentorFilterTest {
        DynamicInstrumentor transformer;
        private final String filter;
        private final boolean comShouldBeInstrumented;
        private final boolean javaShouldBeInstrumented;
        private final boolean schuchertShouldBeInstrumented;
        private final boolean fooShouldBeInstrumented;
    
        @Before
        public void setup() {
            transformer = new DynamicInstrumentor();
        }
    
        @Parameters
        public static Collection<Object[]> data() {
            ArrayList<Object[]> values = new ArrayList<Object[]>();
            values.add(new Object[] { "", true, true, true, true });
            values.add(new Object[] { "-java.*", true, false, true, true });
            values.add(new Object[] { "+java.*", false, true, false, false });
            values.add(new Object[] { "-java.*::-com.*", false, false, true, true });
            values.add(new Object[] { "+java.*::-schuchert.*::-com.*", false, true, false, false });
            values.add(new Object[] { "+[js].*", false, true, true, false });
            values.add(new Object[] { "+.*m$", true, false, false, false });
            return values;
        }
    
        public DynamicInstrumentorFilterTest(String filter,
                boolean matchComIbm, boolean matchJavaIo, boolean matchSchuchert, boolean matchFoo) {
            this.filter = filter;
            this.comShouldBeInstrumented = matchComIbm;
            this.javaShouldBeInstrumented = matchJavaIo;
            this.schuchertShouldBeInstrumented = matchSchuchert;
            this.fooShouldBeInstrumented = matchFoo;
        }
    
        @Test
        public void checkPattern() {
            transformer.setFilter(filter);
            assertFilterMatchedCorrectly("com/ibm", comShouldBeInstrumented);
            assertFilterMatchedCorrectly("java/io", javaShouldBeInstrumented);
            assertFilterMatchedCorrectly("schuchert/contest/", schuchertShouldBeInstrumented);
            assertFilterMatchedCorrectly("foo", fooShouldBeInstrumented);
        }
    
        private void assertFilterMatchedCorrectly(String string, boolean expected) {
            boolean result = transformer.isClassWeShouldProcess(string);
            assertEquals(String.format("Filter: %s, pattern: %s", filter, string), expected, result);
    
        }
    }
    

    Here’s a more detailed description of Parameterized Tests

  12. Avatar
    Curious Mind 3 days later:

    By “comment” I meant the “response(s)” to the original post, not comments in the code. Sorry for not being clear about it.

  13. Avatar
    Curious Mind 3 days later:

    Yes, something along those lines. But I would go even further by changing the code in

    @Test
        public void checkPattern() {
            transformer.setFilter(filter);
            assertFilterMatchedCorrectly("com/ibm", comShouldBeInstrumented);
            assertFilterMatchedCorrectly("java/io", javaShouldBeInstrumented);
            assertFilterMatchedCorrectly("schuchert/contest/", schuchertShouldBeInstrumented);
            assertFilterMatchedCorrectly("foo", fooShouldBeInstrumented);
        }
    

    to

    
    @Test
        public void checkPattern() {
            transformer.setFilter(filter);
    
            for (Object[] testCase : allTestCases) { 
               assertFilterMatchedCorrectly ( 
                   (String) testCase[0], // input value
                   (Boolean) tesCase[1].boolValue()); // value to compare with
           }
        }
    
    

    Of course. this handles one specific type of test. But even here the reduction in code is obvious.

    By the way, from the example code I could not understand where the ArrayList is being used, or how.

  14. Avatar
    Brett Schuchert 4 days later:

    That’s an example of how JUnit supports so-called parameterized tests. It’s a bit obtuse. The ArrayList has a collection of Object[]. The types of objects in various object arrays in the array list are used to match a constructor. So the basic algorithm is:

    1. Get all tests by calling method with @Parameters annotation
    2. For each element in the collection
      1. call matching ctor
      2. call @Test methods

    The test is annotated with: @RunWith(Parameterized.class), for further details, check out the Parameterized class that ships with JUnit 4.

    JUnit is using reflection to select and call the ctor once for each “test” in the array list. In that example, there are 7 items in the array list so there are 7 tests executed.

  15. Avatar
    unclebob 7 days later:

    It is interesting how a little knowledge of Mathematics can help eliminate a lot of code (and tests.)

    In this case, once we know the formula for the total number of valid paths, not a single line of code is required. After all, the intent was to show the possible paths and how synchronize can reduce them. With the formula, we know the number of paths; there is no need to write any code or tests.

    I disagree. Constructing a mathematical proof is similar to writing a program. There can be subtle bugs. It’s always nice to see empirical results that confirm the conclusions of your proofs.

    When I constructed the line of reasoning that led the the formula, I was far from convinced it was correct. Even now I worry that I overlooked something. The fact that Brett’s empirical model seems to agree with the formula decreases that worry somewhat.

  16. Avatar
    Curious Mind 7 days later:
    Constructing a mathematical proof is similar to writing a program. There can be subtle bugs.

    By definition, a “proof” is correct and without bugs. Once we’ve got a proof, airtight, there is no need for empirical validation.

    More to the point, a valid mathematical proof is true for all possible values of the parameter, while an empirical validation can only be assumed to work for the specific cases tested. There could be a counterexample that invalidates the empirical proof.

    A mathematical proof is true for all possible values of the parameters (within the domain of possible values.) There is no chance of a counterexample to a valid proof.

    I had absolutely no doubts about the proof once the correct formula was posted. Hence, to me the empirical method was simply a waste of time.

  17. Avatar
    Brett 7 days later:

    Proof != Code

    When I took a discrete mathematics course some 20+ years ago, I found a lot of value in the course as a whole, e.g. complexity analysis, proof by induction, and others. HOWEVER, program correctness proofs were, to my mind, completely useless for several reasons.
    1. Practically speaking, proving a trivial for loop was too much work. Proving anything of any size was little more than a way to get a paper published that nobody would/should read.
    2. Proving code is correct != proving that code does what someone wants. More on this below…
    While your comments about proving something are true with respect to math, they have no relationship to software development. WHY?

    Problems are stated in natural language. Yes, there have been efforts to write formal requirements specifications, and tools in support of such efforts, all of which amount to mental masturbation, IMO.

    Most people speak in natural language. Natural language is ambiguous – in fact, much of its expressiveness comes from ambiguity. EVEN IF we could get people to speak in formal languages, there’s still the issues that:
    1. People still don’t know what they want until they see it.
    2. When they do see something, what they want changes
    3. Reality kicks in and what they want/need changes

    I immediately rejected formal specification of requirements as well as program correctness proofs, both of which I saw as, simply put, a big wast of time. I still believe that.

    Furthermore, a formal specification does not change the reality that what we want is a moving target, so even if formal specification were possible, it’s nearly irrelevant because the existence of change makes it so.

    There was/are efforts to get formal “sign off” on requirements. I used to do that when I was working as an architect or technical lead years ago – but those were always ways to “stop the insanity”.

    When I started practicing incremental & iterative development, that helped. I worked on getting sign-off for a short period. Then a few weeks later, I asked for a little more.

    Trying to get “sign-off” is attempting to fix a symptom that is an indication of a good thing… When requirements change it comes from either a perceived new need, or feedback from seeing something. I don’t want to inhibit change, I want to embrace and encourage it. It means I’ve got something that live and worth doing. No changes coming down the pike? Bad…

    Trying to put controls on the work we do and equate it to mathematics, is, in general, a bad idea. There are places where it is relevant. If your domain involves optimal layout, optimal/minimal cost analysis, all of those problems that collapse in the traveling salesmen problem (NP-Complete problems), heuristics and mathematical models can help. But even so, that’s generally part of a system and not THE SYSTEM.

    So there might be parts of problems that collapse into provable subsystems, but general software development does not fit that mold.

    When it does – and I don’t think it ever will – software development will be simply clicking buttons in a wizard and entering formulas. Remember the CASE tool debacle? I’m not worried about losing my job to a case tool anytime soon. And if you look at software development in general, it is becoming more fragmented, not less. There are some trends:
    1. Virtual Machines are mainstream and getting much better all the time.
    2. Dynamic languages are on the cusp of becoming mainstream (FINALLY – I still love smalltalk)
    3. People are accepting multi-paradigm solutions, another good trend
    4. Java Script is a language to watch, with fast VM’s and better browser support
    There’s no “next big” thing on the horizon. There’s a suite of tools and techniques, with enabling technologies such as dynamic typing and virtual machines, dynamic instrumentation or meta object protocols, mixed-mode development, etc.

    All of this makes the notion of proving something correct more and more quaint.

    I’m looking forward to the ensuing chaos !

  18. Avatar
    Curious Mind 8 days later:

    Well, it looks like we’ve digressed quite a bit from the original topic, which was to show the large number of possible paths that can occur when multiple threads simultaneously access even small code fragments ( a small number of low-level instructions.) It started by attempting to find out how many possible valid paths exist for a program with N steps and T threads accessing it.

    Two ways were given to find the number of valid paths: a small program that could calculate this value for a given N and T; and a formula that would do the same.

    My argument was that once you verified the formula using logic and first principles, there would be no reason to write the code to find the answer for specific cases. Simply plugging in the numbers into a scientific calculator would suffice.

    I did not mention anything about the “correctness” of a software program, or a “proof of correctness.” These topics, interesting though they are in their own right, are not what the original discussion was about.

    Just like everything else, mathematics is a tool that we can use when the occasion arises. We do not have to use it for every single software problem, using it only where it is appropriate.

  19. Avatar
    unclebob 8 days later:

    By definition, a “proof” is correct and without bugs.

             a = b
           a^2 = ab
     a^2 - b^2 = ab - b^2
    (a+b)(a-b) = b(a-b)
           a+b = b
            2b = b
             2 = 1
    Q.E.D.
    

    There is a bug in that proof; but many people puzzle over it until it is explained to them. The point is that proofs can appear valid while containing subtle flaws.

  20. Avatar
    Curious Mind 8 days later:

    A widely accepted proof is correct and without bugs. The example shown above merely tests our knowledge of mathematics principles, and, since the bug is known to the person providing the proof, may not be relevant to this case.

    There is a chapter by Jon Bentley in “Beautiful Code” which states that the most beautiful code is the one he never wrote because he found a mathematical validation for it. And that is beauty, indeed!

    Anyway, I believe that a good understanding of the fundamentals of several disciplines makes one a better programmer.

  21. Avatar
    unclebob 9 days later:

    Anyway, I believe that a good understanding of the fundamentals of several disciplines makes one a better programmer.

    No argument there.

  22. Avatar
    Bob Armour 10 days later:

    I would have thought that the ‘proof’ was overkill anyway – all that we really need to know is that the number of routes through a piece of code increases exponentially – in relation to the number of steps/threads – if not managed with the synchronised keyword.

    Interesting discussion, in any case.

  23. Avatar
    Disagreement 28 days later:

    “If you’ve made it this far, wow! Congratulations!”

    I really enjoyed your article, because it doesn’t contradict any of my ideas about software development.

    There are 2 problem, IMHO, with this article though:

    1. Has a very long and difficult explanation of why multithreaded programming is difficult. You don’t need such complex demonstrations, instead it is enough to realize that most software is riddled with bugs, so many that some bugs are considered features, other bugs are kept for compatability purposes and other bugs hide other bugs.

    2. Ending an article with a comment saying “I expect that whoever is reading me is an idiot” is not considered good manners. I agree that most developers seem to think most of the people are idiots, and they are probably right, if your definiton of idiot is “he doesn’t know what I know”. Going by that definition only can mean that being idiotic is something relative (it depends of who you are talking to), and since “everyone knows where his shoes are too tight”, we live in the land or mordon.

    Replacing a clever algorithm with a formula is always faster.

    Testing a formula with a test is a sure way to detet bugs in formulas.

    Either way, the EJB experiment has shown you don’t need multithreaded programs nor programmers who can understand multithreaded programs. All you need is programmers who can devise single threaded algorithms and a deployment environment that can take the single threaded algorithm and run it in parallel.

  24. Avatar
    Brett Schuchert about 1 month later:
    Has a very long and difficult explanation of why multi-threaded programming is difficult.
    I’ve seen lots of books/articles that describe the difficulty with multi-threaded coding but never one that shows things at the level of the JVM. I think many (most) people who develop in Java would understand it much better with just a little background in:
    1. How the JVM structures bytecodes
    2. Frames – or what the term I learned, which was activation records
    3. A mental model of the stack, heap, where things live and how threads interact with all of that
    I don’t think everybody needs to understand everything at a deep level, but it seems that many people (even some “senior consultants” I’ve worked with), really don’t have a fundamental understanding of what’s going on. That leads to a lot of “hunt-and-peck” programming – keep typing still the s*&t works.

    And besides, it’s a freaking blog.

    2. Ending an article with a comment saying “I expect that whoever is reading me is an idiot” is not considered good manners. I agree that most developers seem to think most of the

    Since you ”” quoted me, I can categorically deny what you wrote. I did a search and I did not see the word idiot before your first mention of it. I certainly did not call anybody an idiot. If you got that out of what I wrote you might want to ask yourself why you did. Also, from your perspective, my attempt at a self effacing comment failed.

    Either way, the EJB experiment has shown you don’t need multithreaded programs nor programmers who can understand multithreaded programs. All you need is programmers who ca
    Also disagree. I’ve done a fair bit of EJB development in large team environments and it is not for the light-hearted. It only appears to take away the need to avoid threading. There are still issues:
    1. Reentrant code
    2. Shared objects in the web tier
    3. Shared objects in the ejb tier
    4. Difficulty of defining good ejbs
    5. Stateful versus stateless – I’m not in the came of “everything must be stateless”, though I strive to keep my state as focused as possible
    6. Object allocation causing terrible garbage collection – not a threading issue but an issue anyway

    The list goes on. EJB, before the 3.0 spec, was a solution looking for a problem. Using just a web container + spring + hibernate is more than enough for many (most?) enterprise-level applications that scale well.

    I really like the direction taken in EJB 3 and JPA. I think it’s too little, too late. IBM is only now coming to the market with the technology (JBoss and was it Oracle got there some time ago).

    Frankly, I think the EJB “experiment” was an excellent demonstration of a disaster, which is only being made worse by adding a bus, web services and calling it SOA – that’s a way to sell licenses, but solutions? Not so much.

    So now that I’ve disagreed with your ideas about software development (and article writing apparently), I’m guessing you may no longer like the article – or at least my reply to your comments.

  25. Avatar
    MTS File Converter over 2 years later:

    oh ,my god ,the last one

  26. Avatar
    chanel store over 3 years later:

    Very pleased that the article is what I want! Thank you

  27. Avatar
    virtuemart templates over 3 years later:

    I’ve done a fair bit of EJB development in large team environments and it is not for the light-hearted. It only appears to take away the need to avoid threading. virtuemart templates

  28. Avatar
    Pandora over 3 years later:

    This looks a lot like the way “good” inheritance should behave.

  29. Avatar
    Backup iPhone SMS over 3 years later:

    When code this. it all depends on. you know, not so easy.

  30. Avatar
    http://www.blacktowhiteiphone4.com over 3 years later:

    Want to change your belove iphone 4 form black to white? Hmm, yes, so am I. but when will white iphone 4 available?

  31. Avatar
    Silicone Molding over 3 years later:

    Mold making is the core business of Intertech (Taiwan). With world level technology, Intertech enjoys a very good reputation for making Injection Mold and Plastic Moldsfor their worldwide customers.

  32. Avatar
    Criminal Records over 3 years later:

    There is the chance that others may take what they read here as the gospel truth without thinking critically for themselves.

  33. Avatar
    Matteo over 3 years later:

    Thanks for sharing this to us.

  34. Avatar
    Jones over 3 years later:

    Thanks for sharing this to us.

  35. Avatar
    jaychouchou over 3 years later:

    i actually love this show,, i think its really cool to do a little spin off of Addam’s

    life, i thought it was a little predictable but Craig Roberts hottness makes up for

    that XD lol xx Does anyone know when the next episode is put online,, i cant wait to watch it,, i just

    wish it was longer!! All the more time to nike shoes watch Addam make an embbaresment out of himself,, but in a fit way!! lol XD

  36. Avatar
    cable ties over 3 years later:

    love the ideas in this article. thanks for sharing!

  37. Avatar
    Backup iPhone SMS over 3 years later:

    Thanks for shareing!

  38. Avatar
    iPhone SMS to Mac Backup over 3 years later:

    I really like this essay. Thank you for writing it so seriously.

  39. Avatar
    Sunglass over 3 years later:

    Buy $10 Replica Designer Sunglasses with 3-day FREE SHIPPING Inspired ,MEN designer Sunglasses Women Replica Sunglass at cheap discount price

  40. Avatar
    SEO Firm India over 3 years later:

    zSimply, admirable what you have done here. It is fabulous to see you verbalize from the heart and your clarity on this significant subject can be easily seen. Fantastic post and will look forward to your incoming update.

  41. Avatar
    John Strapp over 3 years later:

    I like this post. A really good one. Thanks guys. roof sarasota

  42. Avatar
    Pascher over 3 years later:

    There was a little mistake before but now I think it’s good. Great article

  43. Avatar
    okey oyunu oyna over 3 years later:

    this code is very useful ..

    internette görüntülü olarak okey oyunu oyna, gerçek kisilerle tanis, turnuva heyecanini yasa.

  44. Avatar
    real estate advertising over 3 years later:

    I always read your blog Thanks :-)

  45. Avatar
    Jewellery over 3 years later:

    Online UK costume and fashion jewellery shop with, WEEWRE565

  46. Avatar
    beats by dr dre headphones over 3 years later:

    I attempted these beats by dr dre studio out in several genres thinking about which i listen to an eclectic mix Beats By Dr Dre. A all natural suit With Solos, you really feel the music, not the headphones. This 2nd part includes the cable television set you’ll should connect in the direction of headphones, a washing cloth as well as the manual. Do not purchase any beats by dr dre solo purple products inside the internet unless you’re getting from an Authorized internet DealerBeats By Dre Just Solo. We are reliable provide good beats by dr dre pro white by reduced price.

  47. Avatar
    beats by dre store over 4 years later:

    here. It is fabulous to see you verbalize from the heart and your clarity on this significant subject can be easily seen. Fantastic post and will look forward to your incoming update.high quality headphones new design headphones

  48. Avatar
    Jewellery XY over 4 years later:

    Great article , very informative. For a guide to gemstones check out our site

  49. Avatar
    canada goose coat over 4 years later:

    When it comes to feather dress, what appears in your mind? Which kind brand of down jacket do you like prefer? Though there are many down jackets for you to choose from, on the word, which one you really enjoy? I want to say that canada goose coats is really your best choice. I believe you can’t agree with me any more. When you take the quality into consideration, you will find that it is superior to any other kind of coat. Besides, discount canada goose jackets is a world well-known brand, which has gained high reputation in the world, which has accepted by our customers and some organization. Because of its high quality, some of our loyal customers have promoted it to the people around them. In their opinion, it is good to informing others to know it. Recently, Canada Goose Trillium Parka is on hot sale. What I have to inform you is that all the products there are made by hand, so they are elaborative and elegant enough. It is really beautiful once you dress in. So, if you are a lovely girl or woman, go to the store to buy one for you. You will appreciate it that you have such a coat.In addition, they also have any other products like canada goose Gloves and canada goose jacket supplier.Hope your will like its!

  50. Avatar
    african Mango dr oz over 4 years later:

    i think this can be bookmarked for future referenses , i think i could make use of this ,many thanks for the time you spend writing this , best regards for Canada

  51. Avatar
    Tips For Bowling over 4 years later:

    No law of nature, however general, has been established all at once; its recognition has always been preceded by many presentiments.

  52. Avatar
    christian louboutin over 4 years later:

    Peep toe shoes used to be popular, now it regress popular again. Too heavy and dramatic square toe shoes may be nightmare for many people, but open a mouth in front, the effect will be greatly different. For women, it is a very good transition. It is very trendy, but unlike pointed toe shoe so eye-catching. In this year, a pair of delicate Christian Louboutin Peep Toe Pumps will be a good choice.

    Christian Louboutin Madame Butterfly 150 Suede Pumps Red

    Technical details of Christian Louboutin Madame Butterfly 150 Suede Pump Red:

    Color: Red
    Material: Suede
    Peep toe
    6(150mm) covered heel
    1.5(35mm) covered platform

    Fashion, delicate, luxurious Christian louboutins shoes on sale, one of its series is Christian Louboutin Peep Toe Pumps, is urbanism collocation. This Christian louboutins shoes design makes people new and refreshing. Red soles shoes is personality, your charm will be wonderful performance.

  53. Avatar
    christian louboutin over 4 years later:

    No law of nature, however general, has been established all at once; its recognition has always been preceded by many presentiments.

  54. Avatar
    alwadifa over 4 years later:

    I liked you blog so im going bookmark it with my prefered websites, you have posted an amazing posts so thank you I liked you blog so im going bookmark it with my prefered websites, you have posted an amazing posts so thank you

  55. Avatar
    Polo Ralph Lauren Pas Cher over 4 years later:

    it is necessary to have a backup of the text message from your phone.

  56. Avatar
    louboutin sales over 4 years later:

    So just what does synchronized do? 55 hoo,good article!!I like the post!59

  57. Avatar
    hermes bolide 31 over 4 years later:

    Do you ever get sick of purchasing a book bag or a piece of luggage year after year because you are “too rough with it?

  58. Avatar
    Plastic Injection Mold over 4 years later:

    With more than 20 years of experience, Intertech provides an extensive integrated operational ability from design to production of molds 100% made in Taiwan. Additional to our own mold making factory, we also cooperate with our team vendors to form a very strong working force in Taiwan.

    For the overseas market, we work very closely with local representatives in order to take care of the technical communication and after-sales service to our customers. We also participate in the EUROMOLD & FAKUMA exhibitions and meet our customers every year in Europe. By concentrating on mold “niche markets”, we play a very useful mold maker role from the Far East whenever customers want to develop their new projects. We provide services from A to Z to our customers on a very economic cost and effect basis.

Comments