Generic Programming and Library Development

Quarter 4, 2007

Assignment 1

Problem formulation:

The starting point for this assignment is a routine, called it X, available at the C++ standard library under the header <algorithm> or <numeric>. You will get X from Jyrki.

The tools you need are a text editor (e.g. emacs), a C++ compiler (e.g. g++), and a tool to make time measurements (e.g. Benz [1]).

In 2001, Steffen Nissen pointed out that loop unrolling could be used to optimize many of the standard-library routines. In this assignment your task is to examine whether Steffen's optimization technique is relevant for routine X in your execution environment. More concretely,

1) write a small test program that tests the correctness of X (your test program should not output anything if everything is all right);

2) take the unoptimized version of X available at the CPH STL [2] and test its correctness (if it is not available, you have to develop it yourself; or if the current version does not compile, you have to correct the compiler errors first);

3) create another version of X using Steffen's macros [3] and test its correctness; and

4) compare the efficiency of the two versions of X for a random-access container (e.g. vector) containing built-in data (e.g. integers).

Independent of the outcome of your experiment, you are welcome to commit your programs to the CPH STL CVS repository. This way you will get full access to all files created in the project. Ask Jyrki for further details.

References:

[1]

http://cphstl.dk/tools.html

[2]

http://cphstl.dk/Program/Algorithm/Implementation/X.cpp or http://cphstl.dk/Program/Numeric/Implementation/X.cpp

[3]

http://cphstl.dk/Program/Optimization/optimization

Appendix: Code for find

Directory structure

Benz
  drive.c++
  experiment.c++
  form.py

Optimized
  find.cpp

Unittest
  test_find.c++

Unoptimized
  find.cpp

makefile

Unoptimized/find.cpp

namespace cphstl {

  template <typename P, typename E>
  P find (P first, P one_past_the_end, const E& elem) {
    while (first != one_past_the_end) {
      if (*first == elem) {
	return first;
      }
      ++first;
    }
    return one_past_the_end;
  }

}

Optimized/find.cpp

#include <iterator> // defines std::iterator_traits
#include "optimization" // defines UNROLLED_LOOP

namespace cphstl {

  template <typename P, typename E>
  inline P find (P first, P one_past_the_end, const E& elem, 
		 std::input_iterator_tag used_for_branching) {
    while (first != one_past_the_end) {
      if (*first == elem) {
	return first;
      }
      ++first;
    }
    return one_pass_the_end;
  }
  
  template <typename R, typename E>
  inline R find (R first, R one_past_the_end, const E& elem, 
		 std::random_access_iterator_tag used_for_branching) {
    UNROLLED_LOOP(first, one_past_the_end,
      if (*first == elem) {
        return first;
      }
    )
    return one_past_the_end;
  }

  template <typename X, typename E>
  X find(X first, X one_past_the_end, const E& elem) {
  
    typename std::iterator_traits<X>::iterator_category strength;
    return cphstl::find(first, one_past_the_end, elem, strength);
  }

}

Unittest/test_find.c++

#if defined(STD)
#define NAMESPACE std
#include <algorithm> // defines std::find
#else
#define NAMESPACE cphstl
#include "find.cpp" //defines cphstl::find
#endif

#include <cassert>
#include <iterator>

template <typename F>
void generate (
  F first,
  F beyond
) {

  typedef typename std::iterator_traits<F>::value_type E;
  
  F p = first;
  while (p != beyond) {
    *p = E(2 * (p - first) + 1); 
    ++p;
  }
}

int main() {

  const unsigned int bign = 12;

  typedef int E;
  typedef E* (*routine)(E*, E*, const E&);
  routine search = NAMESPACE::find;

  for (unsigned int n = 0; n <= bign; n++) {
    E a[12];
    generate(a, a + n);
    for (unsigned int i = 0; i < n; i++) {
      if (n > 0) assert(search(a, a + n, a[i]) == a + i);
      else assert(search(a, a + n, a[i]) == a);
      assert(search(a, a + n, a[i] - 1) == a + n);
      assert(search(a, a + n, a[i] + 1) == a + n);
    }
    E b[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
    assert(search(b, b + n, -1) == b + n);
    if (n > 0)  assert(b <= search(b, b + n, 0) && search(b, b + n, 0) < b + n);
    else assert(search(b, b + n, 0) == b);
    if (n > 0) assert(search(b, b + n, 0) < b + n);
    else assert(search(b, b + n, 0) == b);
    assert(search(b, b + n, 1) == b + n);
  }

  return 0;
}

Benz/drive.c++

#include <iostream> // defines std::cout and std::endl
#include <ctime> // defines std::clock
#include "experiment.c++" // defines experiment

#ifndef N
#define N 1000000
#endif

int main() {
  experiment<int> e(N);
  clock_t start = clock();
  e();
  clock_t ticks = clock() - start;

  double ns_per_N = 1.0e9 / (double(CLOCKS_PER_SEC) * double(N));
  std::cout << ns_per_N * double(ticks) << std::endl; 
  return 0;
}  

Benz/experiment.c++

/*
Experiment for the find() function

*/

#if defined(STD)
#define NAMESPACE std
#include <algorithm> // defines std::find
#else
#define NAMESPACE cphstl
#include "find.cpp" //defines cphstl::find
#endif

#include <vector> // defines std::vector
#include <cassert> // defines assert

template <typename E>
class experiment {
public:
  experiment(unsigned int n) {
    a.resize(n, E(0));
    s = E(1);
  }
  void operator()() {
    typedef typename std::vector<E>::iterator R;
    R answer = NAMESPACE::find(a.begin(), a.end(), s);
    assert(answer == a.end());
  }
private:
  E s;
  std::vector<E> a;
};

Benz/form.py

"""
Benchmarking the find() function

shell> echo $PYTHONPATH
/home/disk04/jyrki/CPHSTL/Tool/Benz/
"""

import benz
import os

class find_case(benz.case):
  def __init__(self, n, element, directory):
    benz.case.__init__(self)
    self.n = n
    self.compiler = '/home/disk04/jyrki/Script/Gfilt/gfilt'
    self.compiler_options.extend(['-O6', '-funroll-all-loops', 
      '-DN=' + str(n), '-D' + directory])
    home = os.environ['HOME']
    self.include_paths.extend(['Benz/',
      home + '/CPHSTL/Program/Optimization/'])
    if directory != 'STD':
     self.include_paths.extend([directory])
    self.driver_file = 'Benz/drive.c++'

  def output(self):
    if self.driver_output != '':
      return (self.n, self.driver_output)
    else:
      return ()

class find_curve(benz.curve_suite):
  def __init__(self, element, namespace, directory, linetype, pointtype):
    benz.curve_suite.__init__(self)
    self.title = directory + ' ' + namespace + '::find()' 
    self.linetype = linetype
    self.pointtype = pointtype
    for k in range(10, 25):
      n = 1 << k;
      self.add(find_case(n, element, directory))

class find_plot(benz.plot_suite):
  """
  Measure the efficiency of the find() function
  """
  def __init__(self):
    benz.plot_suite.__init__(self)
    self.title = 'Runtime of an unsuccessful search for a vector of size n'
    self.xlabel = 'Input size [n]'
    self.ylabel = 'Execution time per element [nanoseconds]'
    self.add(find_curve('int', 'std', 'STD', 1, 3))
    self.add(find_curve('int', 'cphstl', 'Unoptimized', 2, 4))
    self.add(find_curve('int', 'cphstl', 'Optimized', 3, 6)) 
    self.gnuplot_commands += """
set title '%(title)s'
set xlabel '%(xlabel)s'
set ylabel '%(ylabel)s'
""" % self.__dict__

if __name__ == '__main__':
  benz.main(task = find_plot(), runner = benz.gnuplot_runner)

UNIX makefile

CXX = g++
CXXFLAGS += -O6 -funroll-all-loops

INCLUDE_PATHS = -I$(HOME)/CPHSTL/Program/Optimization/

.PHONY: default clean plot

default: plot

plot:
        python Benz/form.py

%/unittest:
        $(CXX) -I$(@D) $(INCLUDE_PATHS) -D$(@D) Unittest/test_find.c++
        ./a.out

%/testdrive:
        $(CXX) -I$(@D) $(INCLUDE_PATHS) -D$(@D) Benz/drive.c++
        ./a.out

clean:
        -rm -f a.out */a.out plot.* driver.*