Grok Task First

In every task I have ever attempted to optimize or have seen optimized, the BIG improvements happen by understanding exactly what the task is and perhaps more importantly deciding what it is not. Of all the places in discussing optimization that I have used the word Grok This is the place where I really mean Grok.

At times this optimization technique improves performance but 10^9 or more, code level optimizations generally yield much less.

To do this you will need to get outside the square quite a bit.

Some simple examples.

On an Apple II (showing my age), I wanted to interactively display 3D gas cloud representations of orbitals. To actually work out the density of dots in space was a big task involving highbrow maths (high for me at the time anyway) so what I produce was a piece wise linear model of the function which visually was far more than adequate.

In an asteroids game, we need to compute gravitational force. We could use a piecewise linear interpolation like I did above or we could get real dirty and use

F = Gravity[ Distance >> 4 ];

A step wise lookup table.

Hash functions often use divide modulo prime etc to get the appropriate avalanche effect, of change any input bit change half the outputs. Divides are expensive. I have become rather fond ofT += LUT[ (x += c) & 255 ] ; where LUT is a table of random numbers. I then get to make all my table sizes modulo nice numbers like 0x7FF.

Or (to save space on a look up table), you could use a function like:

    char hash(char c)
    {
        return (c ^ M) + N;
    }

and choose M and N such that x = hash(x) takes 256 cycles to return the original x

A better example is usually when very large spaces need to be searched. I once wrote a program to solve one of those pentomino packing problems. I started it and then worked out how long it would take. I found that I was probably going to die before it terminated.

Hmmm. Thinks.... More Thinks..... AhHa Eureka Grok it.

Rewrite code, solves problem in 10 minutes. Describing how I changed the search is non trivial, but powerfully useful even when manually solving such packing problems.

Reminds me of a little program I wrote for finding anagrams - the idea was to use arrays of 26 entries to count the occurrences of each letter; clamping each array to contain 0 to 3 enables the entire array to be held in 64 bits, and then bitwise operations can be used to compare the array in parallel -- EddieEdwards

These optimizations may look like code level optimizations to some people but each of them either implements something other than exactly what the specification said, but was good enough for the job, or (in the last case) was arrived at by saying so what is you really want to happen. -- AlanChristiansen

So is it really an OptimizationPattern? Your cases fit into different categories:

Those which change the specification
Algoritmic transformations

You should DoTheSimplestThingThatCouldPossiblyWork anyway - that's basic ExtremeProgramming.

Changing the specification after the fact is highly dangerous - I note that your example in this case is from hobbyist work. How can we do things like this in the professional sphere? [We do, of course, in games programming ... but making such things formally acceptable is a lot more tricky. ExtremeProgrammingForGames has to deal with this sort of issue.]

Stepwise lookup belongs to a category of OptimizationPatterns called, perhaps, DiscardSuperfluousPrecision, which again changes the behaviour of the code.

The hash table example gives me a bad feeling too, although I think your description is too terse to really understand it ... could you explain this in more detail? I like hash functions that are analytically sound ... yours may or may not be (from the description).

The example of search space transformation is another good one. In this case it's a "true" optimization since it does not affect the code's behaviour.

But overall, I doubt whether GrokTaskFirst is an OptimizationPattern. You call it a "rule" there, which is fine, but OptimizationPatterns are not rules or laws (cf DesignPatterns).

What do you think?

-- EddieEdwards

Whats an analytically sound hash function? Which assumption does the analysis rely on?

The analysis relies on knowing the distribution of objects to be hashed. This can be assumed to be uniform (for "random" data) or else biased towards, say, C identifiers. Once you know the distribution, you can work out the probability of a hash collision, and compare this with the best possible behaviour.

It's never analytically sound in a strong sense, but (as in cryptography) you can save yourself from hash functions which can be shown to perform extremely badly. And - as in Cryptography - you should view any new hashing algorithm with suspicion. It's easy to invent an algorithm that sounds reasonable, but by doing a small amount of probabilistic analysis you can at least prove it to be not unreasonable. ;) -- EddieEdwards

The other comment was "changing the specification after the fact" and how this is dangerous. Well given th rule OptimizeLater we are only ever going to do this after the fact. Perhaps I will cast it in a different light. Perhaps what we are really doing is finally understanding the specification. The specification for an asteroids game probably said little about how mathematically precise the gravity effect had to be. We should of course check with the client what just how much they are prepared to trade precision for speed or RAM.

It's still changing the specification, no matter how you look at it. When a client accepts some work with the gravity precision set to a certain level, that new precision must become part of the specification (albeit implicitly). Once you've shown a client something - even something that was never formally specced - you've implicitly specced it out.

Obviously this sort of optimization happens all the time, and I have seen it done wrong many times too. In the standard games industry scenario, it takes a release-complain-fix iteration (over at least a month) to find out that the precision was unacceptably altered. So while I acknowledge the usefulness of this technique (it's obviously very widely used) I think it is necessary to point out the caveats in big print!

Of course, this is something that the DesignPatterns template does extremely well. Once we have an OptimizationPatterns template this sort of discussion then belongs in a specific section of the paper. [I'm worried that I'm coming across as a nay-sayer for this technique. If this discussion was in the "caveats" section of a paper, the context and applicability of my arguments would be much more clear]. - EddieEdwards

Here's an example that I like. It's not related to programming, but it illustrates the point. It comes from the TrIz literature. TRIZ is a "theory of invention", and if you want to know more, just do a Web search for TRIZ. They have lots more examples like this one...

A group of automotive engineers had been trying unsuccessfully to develop a muffler that would allow a certain vehicle to pass a noise test. They had considered all sorts of new materials and designs and had not been able to devise something that was effective without being prohibitively expensive. The problem was finally "solved" by someone who recognized that the problem was to pass the test, not to design a better muffler. The original setup had the exhaust exiting the muffler via a short horizontal pipe. By bending the pipe downwards, the additional noise attenuation provided by the ground was sufficient to pass the test with a standard muffler.

I like this example too because it really gets outside the square. -- AlanChristiansen

I think the rule here is AvoidOverSpecification?. Don't specify the gravity precision for asteroids if you don't really care about it. Sometimes we happen to know a good answer in advance, and we're tempted to include the answer in the spec to save some effort, but that can impede optimization.

CategoryOptimization