Know Your Limits - Revision history

Greg: Fix dead link.

2012-06-14T19:10:18Z

Fix dead link.

←Older revision		Revision as of 19:10, 14 June 2012
Line 1:		Line 1:
	[[Image:Clearly.jpeg\|thumb\|right]]		[[Image:Clearly.jpeg\|thumb\|right]]

-	''"Man's got to know his limitations." — [http://youtu.be/CG2cux_6Rcw]''	+	''"Man's got to know his limitations." — [http://youtu.be/CG2cux_6Rcw 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 respect 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 respect the limits of your resources.

Greg at 19:02, 14 June 2012

2012-06-14T19:02:35Z

←Older revision		Revision as of 19:02, 14 June 2012
Line 1:		Line 1:
	[[Image:Clearly.jpeg\|thumb\|right]]		[[Image:Clearly.jpeg\|thumb\|right]]

-	''"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://youtu.be/CG2cux_6Rcw]''

	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 respect 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 respect the limits of your resources.

Greg at 20:45, 24 June 2009

2009-06-24T20:45:51Z

←Older revision		Revision as of 20:45, 24 June 2009
Line 7:		Line 7:
	How to respect those limits? Know yourself, know your people, know your budgets, and know your stuff. Especially, as a software engineer, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems. Your job is to create an optimal marriage of software and systems.		How to respect those limits? Know yourself, know your people, know your budgets, and know your stuff. Especially, as a software engineer, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems. Your job is to create an optimal marriage of software and 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(n)=ln(n)'', ''f(n)=n'', ''f(n)=~~n×ln~~(n)'', ''f(n)=n<sup>e</sup>'', and ''f(n)=e<sup>n</sup>''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e<sup>n</sup>)''. 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(n)=log(n)'', ''f(n)=n'', ''f(n)=n×log(n)'', ''f(n)=n<sup>e</sup>'', and ''f(n)=e<sup>n</sup>''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e<sup>n</sup>)''. As Sean Parent puts it, for large enough ''n'' all complexity classes amount to near-infinite, near-linear, or near-constant.

	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on random access time and storage capacity include:		Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on random access time and storage capacity include:

Greg at 20:27, 24 June 2009

2009-06-24T20:27:33Z

←Older revision		Revision as of 20:27, 24 June 2009
Line 9:		Line 9:
	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(n)=ln(n)'', ''f(n)=n'', ''f(n)=n×ln(n)'', ''f(n)=n<sup>e</sup>'', and ''f(n)=e<sup>n</sup>''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e<sup>n</sup>)''. 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(n)=ln(n)'', ''f(n)=n'', ''f(n)=n×ln(n)'', ''f(n)=n<sup>e</sup>'', and ''f(n)=e<sup>n</sup>''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e<sup>n</sup>)''. As Sean Parent puts it, for large enough ''n'' all complexity classes amount to near-infinite, near-linear, or near-constant.

-	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and ~~space~~ include:	+	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on random access time and storage capacity include:

	{\|align="left"		{\|align="left"
	!align="left"\|		!align="left"\|
-	\| style="color:#e76700;" \| ~~Random~~ access time	+	\| style="color:#e76700;" \| access time
-	\|align="right" style="color:#e76700;" \| ~~Storage~~ capacity	+	\|align="right" style="color:#e76700;" \|  capacity
	\|-		\|-
	!align="left"\|register		!align="left"\|register
Line 26:		Line 26:
	\|-		\|-
	!align="right"\|L1 cache		!align="right"\|L1 cache
-	\|align="right"\| < 1 ns	+	\|align="right"\| 1 ns
	\|align="right"\|64 KB		\|align="right"\|64 KB
	\|-		\|-
	!align="right"\|L2 cache		!align="right"\|L2 cache
-	\|align="right"\| < 4 ns	+	\|align="right"\| 4 ns
	\|align="right"\|8 MB		\|align="right"\|8 MB
	\|-		\|-
	!align="left"\|RAM		!align="left"\|RAM
-	\|align="right"\| ~20 ns	+	\|align="right"\|20 ns
	\|align="right"\|32 GB		\|align="right"\|32 GB
	\|-		\|-
	!align="left"\|disk		!align="left"\|disk
-	\|align="right"\| ~10 ms	+	\|align="right"\|10 ms
	\|align="right"\|10 TB		\|align="right"\|10 TB
	\|-		\|-
	!align="left"\|LAN		!align="left"\|LAN
-	\|align="right"\| ~20 ms	+	\|align="right"\|20 ms
	\|align="right"\|> 1 PB		\|align="right"\|> 1 PB
	\|-		\|-
	!align="left"\|Internet		!align="left"\|Internet
-	\|align="right"\| ~100 ms	+	\|align="right"\|100 ms
	\|align="right"\|> 1 ZB		\|align="right"\|> 1 ZB
	\|-		\|-
Line 55:		Line 55:

	{\|align="right"		{\|align="right"
-	\|+ align="bottom" style="color:#e76700;" \| Search time (ns)	+	\|+ align="bottom" style="color:#e76700;" \|          Search time (ns)
	\|-		\|-
	!align="right"\| n		!align="right"\| n
Line 83:		Line 83:
	\|}		\|}

-	Algorithms and data structures 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, whereas searching a B-tree or van Emde Boas tree is ''O(log(n))'' and cache-friendly. ~~Search for~~ "cache-aware" and "cache-oblivious" to know your stuff.	+	Algorithms and data structures 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, whereas searching a B-tree or van Emde Boas tree is ''O(log(n))'' and cache-friendly. Study up on "cache-aware" and "cache-oblivious" to know your stuff.

	''"You pays your money and you makes your choice." — Punch''		''"You pays your money and you makes your choice." — Punch''

Greg at 20:13, 24 June 2009

2009-06-24T20:13:35Z

←Older revision		Revision as of 20:13, 24 June 2009
Line 83:		Line 83:
	\|}		\|}

-	Algorithms and data structures 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, whereas searching a van Emde Boas tree is ''O(log(n))'' and cache-friendly. Search for "cache-aware ~~algorithm~~" and "cache-oblivious ~~algorithm~~" to ~~learn more~~.	+	Algorithms and data structures 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, whereas searching a B-tree or van Emde Boas tree is ''O(log(n))'' and cache-friendly. Search for "cache-aware" and "cache-oblivious" to know your stuff.

	''"You pays your money and you makes your choice." — Punch''		''"You pays your money and you makes your choice." — Punch''

Kevlin: Know your limits moved to Know Your Limits

2009-06-24T14:54:07Z

Know your limits moved to Know Your Limits

←Older revision

Revision as of 14:54, 24 June 2009

Kevlin at 14:53, 24 June 2009

2009-06-24T14:53:53Z

←Older revision		Revision as of 14:53, 24 June 2009
Line 1:		Line 1:
	[[Image:Clearly.jpeg\|thumb\|right]]		[[Image:Clearly.jpeg\|thumb\|right]]

-	''"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]''

	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 respect 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 respect the limits of your resources.
Line 7:		Line 7:
	How to respect those limits? Know yourself, know your people, know your budgets, and know your stuff. Especially, as a software engineer, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems. Your job is to create an optimal marriage of software and systems.		How to respect those limits? Know yourself, know your people, know your budgets, and know your stuff. Especially, as a software engineer, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems. Your job is to create an optimal marriage of software and 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=nln(n)'', ''f=ne'', and ''f=en''. 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(n)=ln(n)'', ''f(n)=n'', ''f(n)=n×ln(n)'', ''f(n)=n<sup>e</sup>'', and ''f(n)=e<sup>n</sup>''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e<sup>n</sup>)''. As Sean Parent puts it, for large enough ''n'' all complexity classes amount to near-infinite, near-linear, or near-constant.

	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and space include:		Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and space include:
Line 34:		Line 34:
	\|-		\|-
	!align="left"\|RAM		!align="left"\|RAM
-	\|align="right"\| ~ 20 ns	+	\|align="right"\| ~20 ns
	\|align="right"\|32 GB		\|align="right"\|32 GB
	\|-		\|-
	!align="left"\|disk		!align="left"\|disk
-	\|align="right"\| ~ 10 ms	+	\|align="right"\| ~10 ms
	\|align="right"\|10 TB		\|align="right"\|10 TB
	\|-		\|-
	!align="left"\|LAN		!align="left"\|LAN
-	\|align="right"\| ~ 20 ms	+	\|align="right"\| ~20 ms
-	\|align="right"\|>1 PB	+	\|align="right"\|> 1 PB
	\|-		\|-
	!align="left"\|Internet		!align="left"\|Internet
-	\|align="right"\| ~ 100 ms	+	\|align="right"\| ~100 ms
-	\|align="right"\|>1 ZB	+	\|align="right"\|> 1 ZB
	\|-		\|-
	\|		\|
Line 83:		Line 83:
	\|}		\|}

-	Algorithms and data structures 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.	+	Algorithms and data structures 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, whereas searching a van Emde Boas tree 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''

Greg at 20:18, 20 June 2009

2009-06-20T20:18:47Z

←Older revision		Revision as of 20:18, 20 June 2009
Line 24:		Line 24:
	\|align="right"\|		\|align="right"\|
	\|align="right"\|64 B		\|align="right"\|64 B
-	\|
	\|-		\|-
	!align="right"\|L1 cache		!align="right"\|L1 cache
	\|align="right"\| < 1 ns		\|align="right"\| < 1 ns
	\|align="right"\|64 KB		\|align="right"\|64 KB
-	\|
	\|-		\|-
	!align="right"\|L2 cache		!align="right"\|L2 cache
	\|align="right"\| < 4 ns		\|align="right"\| < 4 ns
	\|align="right"\|8 MB		\|align="right"\|8 MB
-	\|
	\|-		\|-
	!align="left"\|RAM		!align="left"\|RAM
	\|align="right"\| ~ 20 ns		\|align="right"\| ~ 20 ns
	\|align="right"\|32 GB		\|align="right"\|32 GB
-	\|
	\|-		\|-
	!align="left"\|disk		!align="left"\|disk
	\|align="right"\| ~ 10 ms		\|align="right"\| ~ 10 ms
	\|align="right"\|10 TB		\|align="right"\|10 TB
-	\|
	\|-		\|-
	!align="left"\|LAN		!align="left"\|LAN
	\|align="right"\| ~ 20 ms		\|align="right"\| ~ 20 ms
	\|align="right"\|>1 PB		\|align="right"\|>1 PB
-	\|
	\|-		\|-
	!align="left"\|Internet		!align="left"\|Internet
	\|align="right"\| ~ 100 ms		\|align="right"\| ~ 100 ms
	\|align="right"\|>1 ZB		\|align="right"\|>1 ZB
-	\|	+	\|-
		+	\|
	\|}		\|}

Line 86:		Line 81:
	\|align="right"\| 320		\|align="right"\| 320
	\|align="right"\| 17000		\|align="right"\| 17000
-	\|-
-	\|
	\|}		\|}

Greg at 04:02, 19 June 2009

2009-06-19T04:02:28Z

←Older revision		Revision as of 04:02, 19 June 2009
Line 11:		Line 11:
	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and space include:		Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and space include:

-	{\|	+	{\|align="left"
		+	!align="left"\|
		+	\| style="color:#e76700;" \| Random access time
		+	\|align="right" style="color:#e76700;" \| Storage capacity
	\|-		\|-
	!align="left"\|register		!align="left"\|register
	\|align="right"\| < 1 ns		\|align="right"\| < 1 ns
	\|align="right"\|64 b		\|align="right"\|64 b
		+	\|
	\|-		\|-
	!align="left"\|cache line		!align="left"\|cache line
	\|align="right"\|		\|align="right"\|
	\|align="right"\|64 B		\|align="right"\|64 B
		+	\|
	\|-		\|-
	!align="right"\|L1 cache		!align="right"\|L1 cache
	\|align="right"\| < 1 ns		\|align="right"\| < 1 ns
	\|align="right"\|64 KB		\|align="right"\|64 KB
		+	\|
	\|-		\|-
	!align="right"\|L2 cache		!align="right"\|L2 cache
	\|align="right"\| < 4 ns		\|align="right"\| < 4 ns
	\|align="right"\|8 MB		\|align="right"\|8 MB
		+	\|
	\|-		\|-
	!align="left"\|RAM		!align="left"\|RAM
	\|align="right"\| ~ 20 ns		\|align="right"\| ~ 20 ns
	\|align="right"\|32 GB		\|align="right"\|32 GB
		+	\|
	\|-		\|-
	!align="left"\|disk		!align="left"\|disk
	\|align="right"\| ~ 10 ms		\|align="right"\| ~ 10 ms
	\|align="right"\|10 TB		\|align="right"\|10 TB
		+	\|
	\|-		\|-
	!align="left"\|LAN		!align="left"\|LAN
	\|align="right"\| ~ 20 ms		\|align="right"\| ~ 20 ms
	\|align="right"\|>1 PB		\|align="right"\|>1 PB
		+	\|
	\|-		\|-
	!align="left"\|Internet		!align="left"\|Internet
	\|align="right"\| ~ 100 ms		\|align="right"\| ~ 100 ms
	\|align="right"\|>1 ZB		\|align="right"\|>1 ZB
-	\|-	+	\|
-	\|	+
-	~~\|style="color:#e76700;" \| Random access time~~	+
-	~~\|align="right" style="color:#e76700;" \| Storage capacity~~	+
	\|}		\|}

	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 predictable. 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 predictable. 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''.

-	{\| align="right"	+	{\|align="right"
	\|+ align="bottom" style="color:#e76700;" \| Search time (ns)		\|+ align="bottom" style="color:#e76700;" \| Search time (ns)
	\|-		\|-
Line 79:		Line 86:
	\|align="right"\| 320		\|align="right"\| 320
	\|align="right"\| 17000		\|align="right"\| 17000
		+	\|-
		+	\|
	\|}		\|}

Greg at 17:45, 18 June 2009

2009-06-18T17:45:47Z

←Older revision		Revision as of 17:45, 18 June 2009
Line 3:		Line 3:
	''"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]''

-	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 respect the limits of your resources.

	How to respect those limits? Know yourself, know your people, know your budgets, and know your stuff. Especially, as a software engineer, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems. Your job is to create an optimal marriage of software and systems.		How to respect those limits? Know yourself, know your people, know your budgets, and know your stuff. Especially, as a software engineer, know the space and time complexity of your data structures and algorithms, and the architecture and performance characteristics of your systems. Your job is to create an optimal marriage of software and systems.

←Older revision		Revision as of 20:27, 24 June 2009
Line 9:		Line 9:
	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(n)=ln(n)'', ''f(n)=n'', ''f(n)=n×ln(n)'', ''f(n)=n<sup>e</sup>'', and ''f(n)=e<sup>n</sup>''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e<sup>n</sup>)''. 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(n)=ln(n)'', ''f(n)=n'', ''f(n)=n×ln(n)'', ''f(n)=n<sup>e</sup>'', and ''f(n)=e<sup>n</sup>''. Clearly, as ''n'' gets bigger ''O(log(n))'' is ever so much smaller than ''O(e<sup>n</sup>)''. As Sean Parent puts it, for large enough ''n'' all complexity classes amount to near-infinite, near-linear, or near-constant.

-	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and ~~space~~ include:	+	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on random access time and storage capacity include:

	{\|align="left"		{\|align="left"
	!align="left"\|		!align="left"\|
-	\| style="color:#e76700;" \| ~~Random~~ access time	+	\| style="color:#e76700;" \| access time
-	\|align="right" style="color:#e76700;" \| ~~Storage~~ capacity	+	\|align="right" style="color:#e76700;" \|  capacity
	\|-		\|-
	!align="left"\|register		!align="left"\|register
Line 26:		Line 26:
	\|-		\|-
	!align="right"\|L1 cache		!align="right"\|L1 cache
-	\|align="right"\| < 1 ns	+	\|align="right"\| 1 ns
	\|align="right"\|64 KB		\|align="right"\|64 KB
	\|-		\|-
	!align="right"\|L2 cache		!align="right"\|L2 cache
-	\|align="right"\| < 4 ns	+	\|align="right"\| 4 ns
	\|align="right"\|8 MB		\|align="right"\|8 MB
	\|-		\|-
	!align="left"\|RAM		!align="left"\|RAM
-	\|align="right"\| ~20 ns	+	\|align="right"\|20 ns
	\|align="right"\|32 GB		\|align="right"\|32 GB
	\|-		\|-
	!align="left"\|disk		!align="left"\|disk
-	\|align="right"\| ~10 ms	+	\|align="right"\|10 ms
	\|align="right"\|10 TB		\|align="right"\|10 TB
	\|-		\|-
	!align="left"\|LAN		!align="left"\|LAN
-	\|align="right"\| ~20 ms	+	\|align="right"\|20 ms
	\|align="right"\|> 1 PB		\|align="right"\|> 1 PB
	\|-		\|-
	!align="left"\|Internet		!align="left"\|Internet
-	\|align="right"\| ~100 ms	+	\|align="right"\|100 ms
	\|align="right"\|> 1 ZB		\|align="right"\|> 1 ZB
	\|-		\|-
Line 55:		Line 55:

	{\|align="right"		{\|align="right"
-	\|+ align="bottom" style="color:#e76700;" \| Search time (ns)	+	\|+ align="bottom" style="color:#e76700;" \|          Search time (ns)
	\|-		\|-
	!align="right"\| n		!align="right"\| n
Line 83:		Line 83:
	\|}		\|}

-	Algorithms and data structures 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, whereas searching a B-tree or van Emde Boas tree is ''O(log(n))'' and cache-friendly. ~~Search for~~ "cache-aware" and "cache-oblivious" to know your stuff.	+	Algorithms and data structures 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, whereas searching a B-tree or van Emde Boas tree is ''O(log(n))'' and cache-friendly. Study up on "cache-aware" and "cache-oblivious" to know your stuff.

	''"You pays your money and you makes your choice." — Punch''		''"You pays your money and you makes your choice." — Punch''

←Older revision		Revision as of 20:18, 20 June 2009
Line 24:		Line 24:
	\|align="right"\|		\|align="right"\|
	\|align="right"\|64 B		\|align="right"\|64 B
-	\|
	\|-		\|-
	!align="right"\|L1 cache		!align="right"\|L1 cache
	\|align="right"\| < 1 ns		\|align="right"\| < 1 ns
	\|align="right"\|64 KB		\|align="right"\|64 KB
-	\|
	\|-		\|-
	!align="right"\|L2 cache		!align="right"\|L2 cache
	\|align="right"\| < 4 ns		\|align="right"\| < 4 ns
	\|align="right"\|8 MB		\|align="right"\|8 MB
-	\|
	\|-		\|-
	!align="left"\|RAM		!align="left"\|RAM
	\|align="right"\| ~ 20 ns		\|align="right"\| ~ 20 ns
	\|align="right"\|32 GB		\|align="right"\|32 GB
-	\|
	\|-		\|-
	!align="left"\|disk		!align="left"\|disk
	\|align="right"\| ~ 10 ms		\|align="right"\| ~ 10 ms
	\|align="right"\|10 TB		\|align="right"\|10 TB
-	\|
	\|-		\|-
	!align="left"\|LAN		!align="left"\|LAN
	\|align="right"\| ~ 20 ms		\|align="right"\| ~ 20 ms
	\|align="right"\|>1 PB		\|align="right"\|>1 PB
-	\|
	\|-		\|-
	!align="left"\|Internet		!align="left"\|Internet
	\|align="right"\| ~ 100 ms		\|align="right"\| ~ 100 ms
	\|align="right"\|>1 ZB		\|align="right"\|>1 ZB
-	\|	+	\|-
		+	\|
	\|}		\|}

Line 86:		Line 81:
	\|align="right"\| 320		\|align="right"\| 320
	\|align="right"\| 17000		\|align="right"\| 17000
-	\|-
-	\|
	\|}		\|}

←Older revision		Revision as of 04:02, 19 June 2009
Line 11:		Line 11:
	Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and space include:		Complexity analysis is in terms of an abstract machine, but software runs on real machines. 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 on time and space include:

-	{\|	+	{\|align="left"
		+	!align="left"\|
		+	\| style="color:#e76700;" \| Random access time
		+	\|align="right" style="color:#e76700;" \| Storage capacity
	\|-		\|-
	!align="left"\|register		!align="left"\|register
	\|align="right"\| < 1 ns		\|align="right"\| < 1 ns
	\|align="right"\|64 b		\|align="right"\|64 b
		+	\|
	\|-		\|-
	!align="left"\|cache line		!align="left"\|cache line
	\|align="right"\|		\|align="right"\|
	\|align="right"\|64 B		\|align="right"\|64 B
		+	\|
	\|-		\|-
	!align="right"\|L1 cache		!align="right"\|L1 cache
	\|align="right"\| < 1 ns		\|align="right"\| < 1 ns
	\|align="right"\|64 KB		\|align="right"\|64 KB
		+	\|
	\|-		\|-
	!align="right"\|L2 cache		!align="right"\|L2 cache
	\|align="right"\| < 4 ns		\|align="right"\| < 4 ns
	\|align="right"\|8 MB		\|align="right"\|8 MB
		+	\|
	\|-		\|-
	!align="left"\|RAM		!align="left"\|RAM
	\|align="right"\| ~ 20 ns		\|align="right"\| ~ 20 ns
	\|align="right"\|32 GB		\|align="right"\|32 GB
		+	\|
	\|-		\|-
	!align="left"\|disk		!align="left"\|disk
	\|align="right"\| ~ 10 ms		\|align="right"\| ~ 10 ms
	\|align="right"\|10 TB		\|align="right"\|10 TB
		+	\|
	\|-		\|-
	!align="left"\|LAN		!align="left"\|LAN
	\|align="right"\| ~ 20 ms		\|align="right"\| ~ 20 ms
	\|align="right"\|>1 PB		\|align="right"\|>1 PB
		+	\|
	\|-		\|-
	!align="left"\|Internet		!align="left"\|Internet
	\|align="right"\| ~ 100 ms		\|align="right"\| ~ 100 ms
	\|align="right"\|>1 ZB		\|align="right"\|>1 ZB
-	\|-	+	\|
-	\|	+
-	~~\|style="color:#e76700;" \| Random access time~~	+
-	~~\|align="right" style="color:#e76700;" \| Storage capacity~~	+
	\|}		\|}

	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 predictable. 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 predictable. 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''.

-	{\| align="right"	+	{\|align="right"
	\|+ align="bottom" style="color:#e76700;" \| Search time (ns)		\|+ align="bottom" style="color:#e76700;" \| Search time (ns)
	\|-		\|-
Line 79:		Line 86:
	\|align="right"\| 320		\|align="right"\| 320
	\|align="right"\| 17000		\|align="right"\| 17000
		+	\|-
		+	\|
	\|}		\|}