Know Your Limits

From WikiContent

(Difference between revisions)
Jump to: navigation, search
m
m
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]''
 +
 +
[[Image:Clearly.jpeg|thumb|right]][[Image:clearly100.jpeg|thumb|right]]
Your resources are limited. You only have so much time and money to do your work, including the time and money 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. Your target machines are only so powerful. So you have to know the limits of your resources.
Your resources are limited. You only have so much time and money to do your work, including the time and money 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. Your target machines are only so powerful. So you have to know the limits of your resources.
How to respect those limits? Know yourself, know your budgets, and know your stuff. Especially, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems.
How to respect those limits? Know yourself, know your budgets, and know your stuff. Especially, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems.
- 
-
[[Image:Clearly.jpeg|thumb|right]][[Image:clearly100.jpeg|thumb|right]]
 
Space and time complexity are given as the function ''O(f(n))'' which for ''n'' equal the size of the input is the asymptotic space or time required as ''n'' grows to infinity. Important complexity classes include ''f=ln(n)'', ''f=n'', ''f=n*ln(n)'', ''f=n**e'', and ''f=e**n''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e**n)''. As Sean Parent puts it, for large enough ''n'' all complexity classes amount to near-infinite, near-linear, or near-constant.
Space and time complexity are given as the function ''O(f(n))'' which for ''n'' equal the size of the input is the asymptotic space or time required as ''n'' grows to infinity. Important complexity classes include ''f=ln(n)'', ''f=n'', ''f=n*ln(n)'', ''f=n**e'', and ''f=e**n''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e**n)''. As Sean Parent puts it, for large enough ''n'' all complexity classes amount to near-infinite, near-linear, or near-constant.
Line 11: Line 11:
Modern computer systems are organized as hierarchies of physical and virtual machines, including language runtimes, operating systems, 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 language runtimes, operating systems, CPUs, cache memory, random-access memory, disk drives, and networks. Typical limits include:
-
 
+
{|
-
{| border="1"
+
|+ align="bottom" style="color:#e76700;" | Storage capacity
-
|+Storage capacity
+
|-
|-
-
|64 b
+
|align="right"|64 b
-
|register
+
!align="right"|register
|-
|-
-
|64 B
+
|align="right"|64 B
-
|cache line
+
!align="right"|cache line
|-
|-
-
|64 KB
+
|align="right"|64 KB
-
|L1 cache
+
!align="right"|L1 cache
|-
|-
-
|8 MB
+
|align="right"|8 MB
-
|L2 cache
+
!align="right"|L2 cache
|-
|-
-
|32 GB
+
|align="right"|32 GB
-
|RAM
+
!align="right"|RAM
|-
|-
-
|10TB
+
|align="right"|10 TB
-
|disk
+
!align="right"|disk
|}
|}
-
{| border="1"
+
{|
-
|+Random access time
+
|+ align="bottom" style="color:#e76700;" | Random access time
|-
|-
-
|< 1 ns
+
|align="right"| < 1 ns
-
|register
+
!align="right"|register
|-
|-
-
|< 1 ns
+
|align="right"| < 1 ns
-
|L1 cache
+
!align="right"|L1 cache
|-
|-
-
|< 4 ns
+
|align="right"| < 4 ns
-
|L2 cache
+
!align="right"|L2 cache
|-
|-
-
|~ 20 ns
+
|align="right"| ~ 20 ns
-
|RAM
+
!align="right"|RAM
|-
|-
-
|~ 10 ms
+
|align="right"| ~ 10 ms
-
|disk
+
!align="right"|disk
|-
|-
-
|~ 20 ms
+
|align="right"| ~ 20 ms
-
|LAN
+
!align="right"|LAN
|-
|-
-
|~ 100 ms
+
|align="right"| ~ 100 ms
-
|Internet
+
!align="right"|Internet
|}
|}
Line 63: Line 62:
Note that capacity and speed vary by several orders of magnitude. Caching and lookahead are used heavily at every level of our systems to hide this variation, but they only work when access is non-random. When cache misses are frequent the system will be thrashing. For example, to randomly inspect every byte on a hard drive could take 32 years. Even to randomly inspect every byte in RAM could take 11 minutes. You can learn the limits of your systems from the manufacturers' literature, and can monitor the performance of your systems with tools like ''top'', ''oprofile'', ''gprof'', ''ping'', and ''traceroute''.
Note that capacity and speed vary by several orders of magnitude. Caching and lookahead are used heavily at every level of our systems to hide this variation, but they only work when access is non-random. When cache misses are frequent the system will be thrashing. For example, to randomly inspect every byte on a hard drive could take 32 years. Even to randomly inspect every byte in RAM could take 11 minutes. You can learn the limits of your systems from the manufacturers' literature, and can monitor the performance of your systems with tools like ''top'', ''oprofile'', ''gprof'', ''ping'', and ''traceroute''.
-
Algorithms vary in how effectively they use caches. 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. Search for "cache-aware algorithm" and "cache-oblivious algorithm" to learn more.
+
{| align="right"
-
 
+
|+ align="bottom" style="color:#e76700;" | Search time
-
{| border="1"
+
-
|+Search time
+
|-
|-
-
|n
+
!align="right"| n
-
|vEB
+
!vEB
-
|binary
+
!binary
-
|linear
+
! linear
|-
|-
-
|7
+
|align="right"| 8
-
|40 ns
+
|align="right"| 40 ns
-
|90 ns
+
|align="right"| 90 ns
-
|50 ns
+
|align="right"| 50 ns
|-
|-
-
|63
+
|align="right"| 64
-
|70 ns
+
|align="right"| 70 ns
-
|150 ns
+
|align="right"| 150 ns
-
|180 ns
+
|align="right"| 180 ns
|-
|-
-
|511
+
|align="right"| 512
-
|100 ns
+
|align="right"| 100 ns
-
|230 ns
+
|align="right"| 230 ns
-
|1200 ns
+
|align="right"| 1200 ns
|-
|-
-
|4095
+
|align="right"| 4096
-
|160 ns
+
|align="right"| 160 ns
-
|320 ns
+
|align="right"| 320 ns
-
|17000 ns
+
|align="right"| 17000 ns
|}
|}
 +
Algorithms vary in how effectively they use caches. 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. Search for "cache-aware algorithm" and "cache-oblivious algorithm" to learn more.
''"You pays your money and you makes your choice." -- Punch''
''"You pays your money and you makes your choice." -- Punch''

Revision as of 02:05, 15 March 2009

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

Your resources are limited. You only have so much time and money to do your work, including the time and money 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. Your target machines are only so powerful. So you have to know the limits of your resources.

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

Space and time complexity are given as the function O(f(n)) which for n equal the size of the input is the asymptotic space or time required as n grows to infinity. Important complexity classes include f=ln(n), f=n, f=n*ln(n), f=n**e, and f=e**n. Clearly, as n gets bigger O(log(n)) is ever so much smaller than O(e**n). As Sean Parent puts it, for large enough n all complexity classes amount to near-infinite, near-linear, or near-constant.

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

Storage capacity
64 b register
64 B cache line
64 KB L1 cache
8 MB L2 cache
32 GB RAM
10 TB disk


Random access time
< 1 ns register
< 1 ns L1 cache
< 4 ns L2 cache
~ 20 ns RAM
~ 10 ms disk
~ 20 ms LAN
~ 100 ms Internet


Note that capacity and speed vary by several orders of magnitude. Caching and lookahead are used heavily at every level of our systems to hide this variation, but they only work when access is non-random. When cache misses are frequent the system will be thrashing. For example, to randomly inspect every byte on a hard drive could take 32 years. Even to randomly inspect every byte in RAM could take 11 minutes. You can learn the limits of your systems from the manufacturers' literature, and can monitor the performance of your systems with tools like top, oprofile, gprof, ping, and traceroute.

Search time
n vEB binary linear
8 40 ns 90 ns 50 ns
64 70 ns 150 ns 180 ns
512 100 ns 230 ns 1200 ns
4096 160 ns 320 ns 17000 ns

Algorithms vary in how effectively they use caches. 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. Search for "cache-aware algorithm" and "cache-oblivious algorithm" to learn more.

"You pays your money and you makes your choice." -- Punch

Personal tools