The Status of the P=NP Problem

Computation has become a standard tool in just about every academic field. Whole subfields of biology, chemistry, physics, economics and others are devoted to large-scale computational modeling, simulations, and problem solving.

As we solve larger and more complex problems with greater computational power and cleverer algorithms, the problems we cannot tackle begin to stand out. The theory of NP-completeness helps us understand these limitations and the P versus NP problem begins to loom large not just as an interesting theoretical question in computer science, but as a basic principle that permeates all the sciences.

Really interesting discussion of P=NP at ACM Magazine -- where are we at now, and what's going to happen to the problem?

Hat tip Charlie Cheever via quora

Edit: This article was current until this:

http://www.scribd.com/doc/35539144/pnp12pt

Oh, that's why you should use Varnish and not Squid.

The really short answer is that computers do not have two kinds of storage any more.

It used to be that you had the primary store, and it was anything from acoustic delaylines filled with mercury via small magnetic dougnuts via transistor flip-flops to dynamic RAM.

And then there were the secondary store, paper tape, magnetic tape, disk drives the size of houses, then the size of washing machines and these days so small that girls get disappointed if think they got hold of something else than the MP3 player you had in your pocket.

And people program this way.

They have variables in "memory" and move data to and from "disk".

Take Squid for instance, a 1975 program if I ever saw one: You tell it how much RAM it can use and how much disk it can use. It will then spend inordinate amounts of time keeping track of what HTTP objects are in RAM and which are on disk and it will move them forth and back depending on traffic patterns.

Well, today computers really only have one kind of storage, and it is usually some sort of disk, the operating system and the virtual memory management hardware has converted the RAM to a cache for the disk storage.

So what happens with squids elaborate memory management is that it gets into fights with the kernels elaborate memory management, and like any civil war, that never gets anything done.

What happens is this: Squid creates a HTTP object in "RAM" and it gets used some times rapidly after creation. Then after some time it get no more hits and the kernel notices this. Then somebody tries to get memory from the kernel for something and the kernel decides to push those unused pages of memory out to swap space and use the (cache-RAM) more sensibly for some data which is actually used by a program. This however, is done without squid knowing about it. Squid still thinks that these http objects are in RAM, and they will be, the very second it tries to access them, but until then, the RAM is used for something productive.

This is what Virtual Memory is all about.

If squid did nothing else, things would be fine, but this is where the 1975 programming kicks in.

After some time, squid will also notice that these objects are unused, and it decides to move them to disk so the RAM can be used for more busy data. So squid goes out, creates a file and then it writes the http objects to the file.

Here we switch to the high-speed camera: Squid calls write(2), the address i gives is a "virtual address" and the kernel has it marked as "not at home".

So the CPU hardwares paging unit will raise a trap, a sort of interrupt to the operating system telling it "fix the memory please".

The kernel tries to find a free page, if there are none, it will take a little used page from somewhere, likely another little used squid object, write it to the paging poll space on the disk (the "swap area") when that write completes, it will read from another place in the paging pool the data it "paged out" into the now unused RAM page, fix up the paging tables, and retry the instruction which failed.

Squid knows nothing about this, for squid it was just a single normal memory acces.

So now squid has the object in a page in RAM and written to the disk two places: one copy in the operating systems paging space and one copy in the filesystem.

Squid now uses this RAM for something else but after some time, the HTTP object gets a hit, so squid needs it back.

First squid needs some RAM, so it may decide to push another HTTP object out to disk (repeat above), then it reads the filesystem file back into RAM, and then it sends the data on the network connections socket.

Did any of that sound like wasted work to you ?

Hm, instructive.

Handy Ruby one liners by David Thomas

HANDY ONE-LINERS FOR RUBY                             November 16, 2005
compiled by David P Thomas <davidpthomas@gmail.com>         version 1.0

Latest version of this file can be found at:
    http://www.fepus.net/ruby1line.txt

Last Updated: Wed Nov 16 08:35:02 CST 2005

FILE SPACING:

# double space a file
    $  ruby -pe 'puts' < file.txt
# triple space a file
    $  ruby -pe '2.times {puts}' < file.txt
# undo double-spacing (w/ and w/o whitespace in lines)
    $  ruby -lne 'BEGIN{$/="\n\n"}; puts $_' < file.txt
    $  ruby -ne 'BEGIN{$/="\n\n"}; puts $_.chomp' < file.txt
    $  ruby -e 'puts STDIN.readlines.to_s.gsub(/\n\n/, "\n")' < file.txt

NUMBERING:

# number each line of a file (left justified).
    $  ruby -ne 'printf("%-6s%s", $., $_)' < file.txt
# number each line of a file (right justified).
    $  ruby -ne 'printf("%6s%s", $., $_)' < file.txt
# number each line of a file, only print non-blank lines
    $  ruby -e 'while gets; end; puts $.' < file.txt
# count lines (emulates 'wc -l')
    $  ruby -ne 'END {puts $.}' < file.txt
    $  ruby -e 'while gets; end; puts $.' < file.txt

TEXT CONVERSION AND SUBSTITUTION:

# convert DOS newlines (CR/LF) to Unix format (LF)
# - strip newline regardless; re-print with unix EOL
    $  ruby -ne 'BEGIN{$\="\n"}; print $_.chomp' < file.txt

# convert Unix newlines (LF) to DOS format (CR/LF)
# - strip newline regardless; re-print with dos EOL
    $  ruby -ne 'BEGIN{$\="\r\n"}; print $_.chomp' < file.txt

# delete leading whitespace (spaces/tabs/etc) from beginning of each line
    $  ruby -pe 'gsub(/^\s+/, "")' < file.txt

# delete trailing whitespace (spaces/tabs/etc) from end of each line
# - strip newline regardless; replace with default platform record separator
    $  ruby -pe 'gsub(/\s+$/, $/)' < file.txt

# delete BOTH leading and trailing whitespace from each line
    $  ruby -pe 'gsub(/^\s+/, "").gsub(/\s+$/, $/)' < file.txt

# insert 5 blank spaces at the beginning of each line (ie. page offset)
    $  ruby -pe 'gsub(/%/, "   ")' < file.txt
    FAILS! $  ruby -pe 'gsub(/%/, 5.times{putc " "})' < file.txt

# align all text flush right on a 79-column width
    $  ruby -ne 'printf("%79s", $_)' < file.txt

# center all text in middle of 79-column width
    $  ruby -ne 'puts $_.chomp.center(79)' < file.txt
    $  ruby -lne 'puts $_.center(79)' < file.txt

# substitute (find and replace) "foo" with "bar" on each line
    $  ruby -pe 'gsub(/foo/, "bar")' < file.txt

# substitute "foo" with "bar" ONLY for lines which contain "baz"
    $  ruby -pe 'gsub(/foo/, "bar") if $_ =~ /baz/' < file.txt

# substitute "foo" with "bar" EXCEPT for lines which contain "baz"
    $  ruby -pe 'gsub(/foo/, "bar") unless $_ =~ /baz/' < file.txt

# substitute "foo" or "bar" or "baz".... with "baq"
    $  ruby -pe 'gsub(/(foo|bar|baz)/, "baq")' < file.txt

# reverse order of lines (emulates 'tac') IMPROVE
    $  ruby -ne 'BEGIN{@arr=Array.new}; @arr.push $_; END{puts @arr.reverse}' < file.txt

# reverse each character on the line (emulates 'rev')
    $  ruby -ne 'puts $_.chomp.reverse' < file.txt
    $  ruby -lne 'puts $_.reverse' < file.txt

# join pairs of lines side-by-side (like 'paste')
    $  ruby -pe '$_ = $_.chomp + " " + gets if $. % 2' < file.txt

# if a line ends with a backslash, append the next line to it
    $  ruby -pe 'while $_.match(/\\$/); $_ = $_.chomp.chop + gets; end' < file.txt
    $  ruby -e 'puts STDIN.readlines.to_s.gsub(/\\\n/, "")' < file.txt

# if a line begins with an equal sign, append it to the previous line (Unix)
    $  ruby -e 'puts STDIN.readlines.to_s.gsub(/\n=/, "")' < file.txt

# add a blank line every 5 lines (after lines 5, 10, 15, etc)
    $  ruby -pe 'puts if $. % 6 == 0' < file.txt

SELECTIVE PRINTING OF CERTAIN LINES

# print first 10 lines of a file (emulate 'head')
    $  ruby -pe 'exit if $. > 10' < file.txt

# print first line of a file (emulate 'head -1')
    $  ruby -pe 'puts $_; exit' < file.txt

# print the last 10 lines of a file (emulate 'tail'); NOTE reads entire file!
    $  ruby -e 'puts STDIN.readlines.reverse!.slice(0,10).reverse!' < file.txt

# print the last 2 lines of a file (emulate 'tail -2'); NOTE reads entire file!
    $  ruby -e 'puts STDIN.readlines.reverse!.slice(0,2).reverse!' < file.txt

# print the last line of a file (emulates 'tail -1')
    $  ruby -ne 'line = $_; END {puts line}' < file.txt

# print only lines that match a regular expression (emulates 'grep')
    $  ruby -pe 'next unless $_ =~ /regexp/' < file.txt

# print only lines that DO NOT match a regular expression (emulates 'grep')
    $  ruby -pe 'next if $_ =~ /regexp/' < file.txt

# print the line immediately before a regexp, but not the regex matching line
    $  ruby -ne 'puts @prev if $_ =~ /regex/; @prev = $_;' < file.txt

# print the line immediately after a regexp, but not the regex matching line
    $  ruby -ne 'puts $_ if @prev =~ /regex/; @prev = $_;' < file.txt

# grep for foo AND bar AND baz (in any order)
    $  ruby -pe 'next unless $_ =~ /foo/ && $_ =~ /bar/ && $_ =~ /baz/' < file.txt

# grep for foo AND bar AND baz (in order)
    $  ruby -pe 'next unless $_ =~ /foo.*bar.*baz/' < file.txt

# grep for foo OR bar OR baz
    $  ruby -pe 'next unless $_ =~ /(foo|bar|baz)/' < file.txt

# print paragraph if it contains regexp; blank lines separate paragraphs
    $  ruby -ne 'BEGIN{$/="\n\n"}; print $_ if $_ =~ /regexp/' < file.txt

# print paragraph if it contains foo AND bar AND baz (in any order); blank lines separate paragraphs
    $  ruby -ne 'BEGIN{$/="\n\n"}; print $_ if $_ =~ /foo/ && $_ =~ /bar/ && $_ =~ /baz/' < file.txt

# print paragraph if it contains foo AND bar AND baz (in order); blank lines separate paragraphs
    $  ruby -ne 'BEGIN{$/="\n\n"}; print $_ if $_ =~ /(foo.*bar.*baz)/' < file.txt

# print paragraph if it contains foo OR bar OR baz; blank lines separate paragraphs
    $  ruby -ne 'BEGIN{$/="\n\n"}; print $_ if $_ =~ /(foo|bar|baz)/' < file.txt

# print only lines of 65 characters or greater
    $  ruby -pe 'next unless $_.chomp.length >= 65' < file.txt
    $  ruby -lpe 'next unless $_.length >= 65' < file.txt

# print only lines of 65 characters or less
    $  ruby -pe 'next unless $_.chomp.length < 65' < file.txt
    $  ruby -lpe 'next unless $_.length < 65' < file.txt

# print section of file from regex to end of file
    $  ruby -pe '@found=true if $_ =~ /regex/; next unless @found' < file.txt

# print section of file based on line numbers (eg. lines 2-7 inclusive)
    $  ruby -pe 'next unless $. >= 2 && $. <= 7' < file.txt

# print line number 52
    $  ruby -pe 'next unless $. == 52' < file.txt

# print every 3rd line starting at line 4
    $  ruby -pe 'next unless $. >= 4 && $. % 3 == 0' < file.txt

# print section of file between two regular expressions, /foo/ and /bar/
    $  ruby -ne '@found=true if $_ =~ /foo/; next unless @found; puts $_; exit if $_ =~ /bar/' < file.txt

SELECTIVE DELETION OF CERTAIN LINES

# print all of file except between two regular expressions, /foo/ and /bar/
    $  ruby -ne '@found = true if $_ =~ /foo/; puts $_ unless @found; @found = false if $_ =~ /bar/' < file.txt

# print file and remove duplicate, consecutive lines from a file (emulates 'uniq')
    $  ruby -ne 'puts $_ unless $_ == @prev; @prev = $_' < file.txt

# print file and remove duplicate, non-consecutive lines from a file (careful of memory!)
    $  ruby -e 'puts STDIN.readlines.sort.uniq!.to_s' < file.txt

# print file except for first 10 lines
    $  ruby -pe 'next if $. <= 10' < file.txt

# print file except for last line
    $  ruby -e 'lines=STDIN.readlines; puts lines[0,lines.size-1]' < file.txt

# print file except for last 2 lines
    $  ruby -e 'lines=STDIN.readlines; puts lines[0,lines.size-2]' < file.txt

# print file except for last 10 lines
    $  ruby -e 'lines=STDIN.readlines; puts lines[0,lines.size-10]' < file.txt

# print file except for every 8th line
    $  ruby -pe 'next if $. % 8 == 0' < file.txt

# print file except for blank lines
    $  ruby -pe 'next if $_ =~ /^\s*$/' < file.txt

# delete all consecutive blank lines from a file except the first
    $  ruby -e 'BEGIN{$/=nil}; puts STDIN.readlines.to_s.gsub(/\n(\n)+/, "\n\n")' < file.txt

# delete all consecutive blank lines from a file except for the first 2
    $  ruby -e 'BEGIN{$/=nil}; puts STDIN.readlines.to_s.gsub(/\n(\n)+/, "\n\n")' < file.txt

# delete all leading blank lines at top of file
    $  ruby -pe '@lineFound = true if $_ !~ /^\s*$/; next if !@lineFound' < file.txt


If you have any additional scripts to contribute or if you find errors
in this document, please send an e-mail to the compiler.  Indicate the
version of ruby you used, the operating system it was compiled for, and
the nature of the problem.  Various scripts in this file were written or
contributed by:

 David P Thomas <davidpthomas@gmail.com>    # author of this document


Tue Jun 26 18:17:36 CDT 2007
 * Thanks to Taylor Carpenter <taylor@codecafe.com> for feedback on improving redirection format.