in reply to CPU cycles DO NOT MATTER!

One minor nit:
CPUs double in speed every 18 months while the cost drops by half (Moore's Law).

Moore's Law actually states that the number of transistors on a chip doubles every 18 months, not the execution speed.

I agree that most micro optimizations are moot, but when it comes to choose an efficient algorithm you can really shoot yourself in the foot by choosing a slow one. You might not notice that when you test it with only 1k test data, but you will when that big database rolls over your script ;-)

Replies are listed 'Best First'.
Re^2: CPU cycles DO NOT MATTER!
by Limbic~Region (Chancellor) on Apr 17, 2008 at 14:13 UTC
    moritz,
    I also don't remember it saying the cost is cut in half.

    Cheers - L~R

[reply]
      I don't think the original does. That follows, though.

      If you're fitting twice as many transistors into the same space, then the same chip design using the new process will cost about half as much because you can produce twice as many per wafer.

      Yet usually that's not how it works, because there are new processor designs that use more transistors by the time the process change comes about.

[reply]
        If you're fitting twice as many transistors into the same space, then the same chip design using the new process will cost about half as much because you can produce twice as many per wafer

        You're neglecting the fact that smaller structures need purer "raw" material, which implies much more preprocessing.

        Also this calculation only works as long as you can get lamps with sufficiently short wavelengths. If you can't anymore, you have to resort to electron beams, which are slooooow.

        To turn a tiny bit more on topic: this a good example that you can't just stop thinking at one abstraction layer, which we recently discussed in another meditation ;-)

[reply]
Re^2: CPU cycles DO NOT MATTER!
by Gavin (Archbishop) on Apr 17, 2008 at 21:19 UTC

    In the late 90's Moore revised his prophecy to saying that he expected the number of transistors to double every 2 years.

    In a 2000 interview with U.S. News & World Report, Moore said that he expected this rate to hold for another 10 to 15 years.

[reply]
Re^2: CPU cycles DO NOT MATTER!
by dragonchild (Archbishop) on Apr 17, 2008 at 14:40 UTC
    Sure. Algorithms can matter. But, they only do so now when dealing with large datasets. As systems get larger, the size of datasets where algorithm choice doesn't matter also gets larger proportionately. So, heapsort vs. bubble-sort matters a lot when working with randomized arrays of 100_000 elements. It doesn't matter at all when dealing with arrays of 1_000 elements. In 3 years, 100_000 elements will be moot.
    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
[reply]
      Sure. Algorithms can matter. But, they only do so now when dealing with large datasets

      But "large" depends strongly on the algorithm.

      I remember reading a node here (can't find it, sorry) about a regex taking exponential time matching some piece of HTML.

      For an algorithm that needs exponential time a line of 80 chars can be long. Really. In 10 years that limit might be 100. Or 120.

      Typical examples are the knapsack problem that appear in real world applications over and over again, which takes exponential time when solved with brute force. Approximation algorithms can solve it much faster, even if a bit inaccurate.

      I'm sure even you would argue that you should optimize when a O(2**n) code hits you.

      But if you normally don't optimize, you have no feeling for what is slow and what isn't, don't know about profiling etc. Which is why I do optimize my applications from time to time.

      BTW a real world project that has been hit by missing optimizations recently is the KindaPerl6 compiler, which was so slow during bootstrap that it just wasn't practicable anymore. It took the fun out of the development process, and now I haven't seen a single kp6 commit since... lemme check... 2008-03-16. (Surely this wasn't the only problem, but IMHO it was the one with largest impact).

[reply]
      A reply falls below the community's threshold of quality. You may see it by logging in.

In Section Meditations