What Every Programmer Should Know About Memory

What Every Programmer Should Know About Memory

Ulrich Drepper
Red Hat, Inc.
November 21, 2007

Obfuscated Programming Contests

Wiki: Obfuscated code

In C:
Wiki: International Obfuscated C Code Contest
The International Obfuscated C Code Contest Winning entries

In Assembly:
世界编程大赛第一名的3D程序 (or see here)
又是一个64k华丽至极的程序

Programmer Competency Matrix

Programmer Competency Matrix

This can be useful for self-checking on programming skills.

Read/Write Excel on Windows & Linux

On windows read/write Excel is easy. Set up ODBC for read and write connections on source and destination Excel files. For some reason Microsoft does not allow delete records in Excel through the ODBC interface (actually might be in any other interfaces), so delete can be done by replacing the current Excel with a blank Excel at the File System level.

In linux, there are modules created by people in PHP to do this, such as PHPExcel. So you download the library and use it. In Perl, the modules Spreadsheet::ParseExcel and Spreadsheet:WriteExcel are written by Takanori Kawai and John McNamara in 2000 and tincluded into CPAN. If your Perl installation does not come with this, install them (e.g., using PPM on windows or CPAN on linux). Some example code are here. This code works for Excel up to version 2000. I didn't try on more recent versions. On windows Perl also can manipulate Excel using the Win32::OLE package which is recommended.

To write Excel file, there is a shortcut to output to a *.csv file. A *.csv file uses comma as delimiter and is opened by Excel, then you can save it as a true Excel file. To escape comma in a *.csv file, quote the entry by double quotes, e.g., "a,b". To include a double quote in an quoted entry, replace it with two double quotes, e.g., "a""b".

A Perl script to count LOC (Lines Of Code)

#!/usr/bin/perl

#
# This script counts number of lines in files of specified type.
# The counting is done recursively into subdirectory.
# @Usage: perl getLOC.pl [dir|file]
#    If no argument is provided, start from current dir ".".
# @By: XC
# @Created on: 11/29/2009
#

print "\n- Line Counter -\n\n";

# specify file type(s) here. Use "[]" to escape ".".
my @types = ("[.]c", "[.]h"); 
#my @types = ("[.]cs"); #, "[.]aspx");
#my @types = ("[.]asp");

my $dirname = ".";
my $total_loc = 0;

# Get input directory name.
my $argc = $#ARGV + 1;
if ($argc > 0) {
  $dirname = $ARGV[0];
}

# Process the starting directory or file.
if (-d $dirname) { 
  processDIR($dirname); 
} else { 
  if (inTypesArray($dirname)) { countLOC($dirname); }
}

# Output total line count.
print "\n[$dirname] Total Lines: $total_loc\n";

1;


#
# Recursively process directory.
#
sub processDIR() {
  my ($dirname) = @_;
  my $file;

  opendir(DIR, $dirname) or die "can't opendir $dirname: $!";
  # Exclude "." and "..".
  my @files = grep { !/^\.{1,2}$/ } readdir (DIR); 
  closedir(DIR);
  #sort @files;

  foreach (@files) {
    $file = "$dirname/$_"; 

    if (-d $file) {
      processDIR($file); # Is directory. Recursion.
    }
    elsif (inTypesArray($file)) {
      countLOC($file);
    }
  }
}


#
# Determine if this file is of specified type.
#
sub inTypesArray() {
  my ($f) = @_;
  my $t;
  foreach $t (@types) {
    if ($f =~ /$t$/) { return 1; }
  }
  return 0;
}


#
# Count number of lines in the file.
#
sub countLOC() {
  my ($file) = @_;
  my $loc = 0;
  my @lines;
  my $line_ct;

  open(FILE, "$file");
  while(<FILE>) {
    @lines = split(/\r/, $_);
    $line_ct = @lines;
    #$loc ++;
    $loc += $line_ct;
  }
  close(FILE);
  print "[$file] Lines: $loc\n";

  $total_loc += $loc;
}

Programming Pearls - Reading notes

==## Part I ##==Preliminaries

==Column 1== Cracking the Oyster

The major point is find the optimal solution of a problem, instead of going straight with a rash solution.
The coding example is soring with bit vector (aka bitmap).

==Column 2== Aha! Algorithms

- binary search
* search
* find bug by setting checking points in a binary search pattern
* find missing element in an integer range
* finding root for equation: bisection method in numerical analysis

- the power of primitives
Problem: rotating an array ab to ba.
Solutions:
* copying. but this is space inefficient
* juggling
* recursive swapping
* define primitive action reverse(): a b -> a^r b -> a^r b^r -> b a

- sorting
Problem: find anagrams in a dictionary.
Solution: get signature for each word.

==Column 3== Data structures programs

- Use of array
- Structuring data
- Powerful tools for specialized data

Don't write a big program when a little one will do.

==Column 4== Writing correct programs

- binary search - hard to get right
- program verification, invariant

==Column 5== A small matter of programming

- Use assertion for correctness
- Scaffolding
- Automated testing
- debugging
- Timing

==## Part II ##==Performance

==Column 6== Perspective on Performance

- A case study: Andrew Appel's many-body simulation program
- Work at many level to achieve performance improvement:
* problem definition
* system structure
* algorithms and data structures
* code tuning
* hardware

==Column 7==The back of the envelop

- Calculation by reasonable estimation
- Quick check: Test by dimension
- Rules of thumb: e.g., 1) Rule of 72 (for exponential increase), 2) pi seconds is a nanocentury.
- Performance estimates, and little experiments
- Safety factors: compensate ignorance with extra safe factors
- Little's Law: queue size = consumption rate * average wait time

==Column 8==Algorithm design techniques

- Problem: range of array for max sum
- Solutions:
* cubic
* quadratic
* Divide and conquer (n log(n))
* scanning (linear)

==Column 9==Code tuning

- Prevent premature optimization
- Optimization should be made on the bottle-neck part - profiling the program

==Column 10==Squeezing space

- The key is simplicity
- Example: sparse matrix representation of grid.
- When simplicity is not sufficient, there are skills to better utilize space:
* recompute
* sparse data structure
* data compression
* allocation policies
* garbage collection

==## Part III ##==The Product

==Column 11==Sorting

- Insertion sort
- Quick sort

==Column 12== A sample problem

- Problem: sampling: select m from n integers
* by selection
* by shuffling
- Principles: understand the problem, specify an abstraction, explore design space, implement, retrospect.

==Column 13== Searching

- Problem: store a set of integers (w/o associated data).
- linear structure
- binary search trees: STL, BST, BST*, Bins, Bins*, BitVec
- structures for integers

==Column 14== Heaps

- Heap, Priority Queue, Heap sort
Comment: the material here can be found in any data structure and algorithm textbook, nothing new.

== Column 15== Strings of pearls

- We are surrounded by strings
- Words. 1) Map, Set, 2) Hash (no worst case guarantee, no order information)
- Phrases.
* the longest substring problem - solved by suffix array
- Generating sentences

==Appendix 1== A catalog of algorithms

- Sorting
- Searching
- Other Set algorithms
- Algorithms on Strings
- Vector and Matrix algorithms
- Random objects
- Numerical algorithms

==Appendix 4== Rules for code tuning

- Space-for-time rules
- Time-for-space rules
- Loop rules
- Logic rules
- Procedure rules
- Expression rules