# Run
# csplit -k <this file> "/FILE/" "{4}"
# source xx01
mv xx02 anti-optimization.cc
mv xx03 perf.cc
mv xx04 SConstruct
mv xx05 timer.hpp
rm xx00
rm xx01
//// FILE anti-optimization.cc
#include <vector>
#include <list>
using namespace std;
typedef vector<int> Vector;
typedef list<int> List;
void anti_optimization(Vector & v) {}
void anti_optimization(List & l) {}
void anti_optimization(Vector::iterator & v) {}
void anti_optimization(List::iterator & l) {}
//// FILE perf.cc
#include <vector>
#include <list>
#include <cerrno>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#include "timer.hpp"
using namespace std;
typedef vector<int> Vector;
typedef list<int> List;
extern void anti_optimization(Vector & v);
extern void anti_optimization(List & l);
extern void anti_optimization(Vector::iterator & v);
extern void anti_optimization(List::iterator & l);
template<typename T>
typename T::iterator
get_random_removal_point(T & container)
{
assert(container.size() < RAND_MAX);
typename T::iterator place = container.begin();
int index = rand() % container.size();
for(int i=0; i<index; ++i) {
++place;
anti_optimization(place);
}
return place;
}
template<typename T>
void
remove_n_random_elements(T & container, int n)
{
for(int i=0; i<n; ++i) {
container.erase(get_random_removal_point(container));
}
}
template<typename T>
void
setup_container(T & container, int size, bool random_order)
{
typedef typename T::iterator iterator;
for(int i=0; i<size; ++i) {
if (random_order) {
int number_to_insert = rand();
iterator place = lower_bound(container.begin(), container.end(), number_to_insert);
container.insert(place, number_to_insert);
}
else {
container.push_back(i);
}
}
}
template<typename T>
void
run_tests(int container_size, int number_of_removals, bool random_order)
{
T container;
number_of_removals = min(number_of_removals, container_size);
{
srand(0);
BlockTimer timer("container setup time");
setup_container(container, container_size, random_order);
}
assert(adjacent_find(container.begin(), container.end(), greater<int>())
== container.end());
{
srand(1);
BlockTimer timer("removal time");
remove_n_random_elements(container, number_of_removals);
}
anti_optimization(container);
}
int main(int argc, char** argv)
{
if (argc != 4) {
cout << "usage: " << argv[0] << " <container size> <number of removals> <random order? (0 or 1)>\n";
exit(1);
}
errno = 0;
int container_size = strtol(argv[1], NULL, 10);
int number_of_removals = strtol(argv[2], NULL, 10);
bool random_order = strtol(argv[3], NULL, 10) != 0;
if (errno != 0) {
cout << "All arguments must be numbers\n";
exit(1);
}
{
cout << "Vector:\n";
BlockTimer timer("total vector time");
run_tests<Vector>(container_size, number_of_removals, random_order);
}
{
cout << "List:\n";
BlockTimer timer("total list time");
run_tests<List>(container_size, number_of_removals, random_order);
}
}
# FILE SConstruct
Program("time-removals", ["anti-optimization.cc", "perf.cc"], CCFLAGS="-O2")
//// FILE timer.hpp
#ifndef TIMER_HPP
#define TIMER_HPP
#include <iostream>
#if defined(__WIN32) || defined(_MSC_VER)
# define WIN32_LEAN_AND_MEAN
# include <windows.h>
class BlockTimer
{
unsigned long long start_time;
std::string description;
public:
BlockTimer() {}
BlockTimer(std::string const & desc)
{
start(desc);
}
void start(std::string const & desc)
{
description = desc;
start_time = GetTickCount();
}
void finish() {
unsigned long long ms = GetTickCount() - start_time;
std::cout << "> Timer " << description << ": " << ms/1000 << "." << ms % 1000 << "\n";
start_time = 0;
}
~BlockTimer() {
if (start_time != 0) finish();
}
};
#else // Unix version
#include <sys/time.h>
inline unsigned long long timevaldiff(struct timeval *starttime, struct timeval *finishtime)
{
unsigned long long msec;
msec=(finishtime->tv_sec-starttime->tv_sec)*1000;
msec+=(finishtime->tv_usec-starttime->tv_usec)/1000;
return msec;
}
class BlockTimer
{
timeval start_time;
std::string description;
public:
BlockTimer() {}
BlockTimer(std::string const & desc)
{
start(desc);
}
void start(std::string const & desc)
{
description = desc;
gettimeofday(&start_time, NULL);
// start_time = GetTickCount();
}
void finish() {
//unsigned long long ms = GetTickCount() - start_time;
timeval end_time;
gettimeofday(&end_time, NULL);
unsigned long long ms = timevaldiff(&start_time, &end_time);
std::cout << "> Timer " << description << ": " << ms/1000 << "." << ms % 1000 << "\n";
start_time.tv_sec = 0;
}
~BlockTimer() {
if (start_time.tv_sec != 0) finish();
}
};
#endif
// Yo emacs!
// Local Variables:
// c-basic-offset: 4
// indent-tabs-mode: nil
// End:
#endif