# Know Your Limits

### From WikiContent

(New page: "Man's got to know his limitations." -- [http://www.youtube.com/watch?v=t2JnCXvm_Qc Dirty Harry] Your resources are limited. You only have so much time to do your work, including the ti...) |
|||

Line 1: | Line 1: | ||

- | |||

"Man's got to know his limitations." -- [http://www.youtube.com/watch?v=t2JnCXvm_Qc Dirty Harry] | "Man's got to know his limitations." -- [http://www.youtube.com/watch?v=t2JnCXvm_Qc Dirty Harry] | ||

Line 10: | Line 9: | ||

Modern computer systems are organized as hierarchies of physical and virtual machines, including operating systems, language runtimes, CPUs, cache memory, random-access memory, disk drives, and networks. Typical limits include: | Modern computer systems are organized as hierarchies of physical and virtual machines, including operating systems, language runtimes, CPUs, cache memory, random-access memory, disk drives, and networks. Typical limits include: | ||

- | + | {| border="1" | |

- | + | ||

- | {| | + | |

|+Storage capacity | |+Storage capacity | ||

|- | |- | ||

Line 34: | Line 31: | ||

|} | |} | ||

- | {| | + | |

+ | {| border="1" | ||

|+Access time | |+Access time | ||

|- | |- | ||

Line 55: | Line 53: | ||

|LAN | |LAN | ||

|- | |- | ||

- | |~ 100 ms | + | |~ 100-1000 ms |

|Internet | |Internet | ||

|} | |} | ||

- | Caching and lookahead is used heavily at every level to hide | + | Note that capacity and speed vary by several orders of magnitude. Caching and lookahead is used heavily at every level of the system to hide this variation. |

Algorithms vary in how effectively they use caches. When cache misses are frequent the system will be thrashing. For instance, linear search makes good use of lookahead, but requires O(n) comparisons. Binary search of a sorted array requires only O(log(n)) comparisons, but tends to be cache-hostile. And searching a von Embde Boas array is O(log(n)) and cache-friendly. "You pays your money and you makes your choice." | Algorithms vary in how effectively they use caches. When cache misses are frequent the system will be thrashing. For instance, linear search makes good use of lookahead, but requires O(n) comparisons. Binary search of a sorted array requires only O(log(n)) comparisons, but tends to be cache-hostile. And searching a von Embde Boas array is O(log(n)) and cache-friendly. "You pays your money and you makes your choice." |

## Revision as of 21:28, 25 February 2009

"Man's got to know his limitations." -- Dirty Harry

Your resources are limited. You only have so much time to do your work, including the time needed to keep your knowledge, skills, and tools up-to-date. You can only work so hard, so fast, so smart, and so long. Your tools are only so powerful and fast. Your target machines are only so powerful and fast. So you have to know the limits of your resources.

How to respect those limits? Know yourself, and know your stuff. Especially, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics your systems.

Space and time complexity are given as the function *O(f(n))* where n is the size of the input and *f(n)* is the asymptotic space or time required as *n* grows to infinity. Important complexity classes include *f=log(n)*, *f=n*, *f=n**2*, and *f=e**n*. Clearly, *O(log(n))* is ever so much smaller than "'O(e**n)*.*

Modern computer systems are organized as hierarchies of physical and virtual machines, including operating systems, language runtimes, CPUs, cache memory, random-access memory, disk drives, and networks. Typical limits include:

64 b | register |

64 B | cache line |

64 KB | L1 cache |

> 1 MB | L2 cache |

32 GB | RAM |

10TB | disk |

< 1 ns | register |

< 1 ns | L1 cache line |

< 4 ns | L2 cache line |

~ 20 ns | RAM |

~ 10 ms | disk |

~ 20 ms | LAN |

~ 100-1000 ms | Internet |

Note that capacity and speed vary by several orders of magnitude. Caching and lookahead is used heavily at every level of the system to hide this variation.

Algorithms vary in how effectively they use caches. When cache misses are frequent the system will be thrashing. For instance, linear search makes good use of lookahead, but requires O(n) comparisons. Binary search of a sorted array requires only O(log(n)) comparisons, but tends to be cache-hostile. And searching a von Embde Boas array is O(log(n)) and cache-friendly. "You pays your money and you makes your choice."