SVN / public / code / vorlesung-09 / InliningDemoMain.cpp

Revision 8201
Date
Committerhb1003
Download
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// Copyright 2026, University of Freiburg
// Chair of Algorithms and Data Structures
// Author: Hannah Bast <bast@cs.uni-freiburg.de>

#include "./InliningDemoFunctions.h"
#include "Timer.h"
#include <cstdlib>
#include <iostream>
#include <vector>

// Check that the given vetor is sorted in reverse order.
std::string isSorted(const std::vector<int> &v) {
  for (size_t i = 0; i < v.size() - 1; ++i) {
    if (v[i] < v[i + 1]) {
      return "NOT sorted";
    }
  }
  return "SORTED";
}

// Bubble sort (in reverse order), with the comparison function hard-coded.
void bubbleSortComparisonHardCoded(std::vector<int> &v) {
  size_t n = v.size();
  for (size_t i = 0; i < n; ++i) {
    for (size_t j = 0; j < n - 1; ++j) {
      if (v[j] < v[j + 1]) {
        std::swap(v[j], v[j + 1]);
      }
    }
  }
}

// Bubble sort, with the comparison function given as argument.
void bubbleSortComparisonFunctionPointer(std::vector<int> &v,
                                         bool (*compare)(int, int)) {
  size_t n = v.size();
  for (size_t i = 0; i < n; ++i) {
    for (size_t j = 0; j < n - 1; ++j) {
      if (!compare(v[j], v[j + 1])) {
        std::swap(v[j], v[j + 1]);
      }
    }
  }
}

// Bubble sort, with the comparison function given as template argument.
template <class Compare>
void bubbleSortComparisonFunctionTemplate(std::vector<int> &v,
                                          Compare compare) {
  size_t n = v.size();
  for (size_t i = 0; i < n; ++i) {
    for (size_t j = 0; j < n - 1; ++j) {
      if (!compare(v[j], v[j + 1])) {
        // if (!compare.compare(v[j], v[j + 1])) {
        std::swap(v[j], v[j + 1]);
      }
    }
  }
}

// Measure the overhead of function calls in a tight loop.
int main(int argc, char **argv) {
  // Parse command line arguments.
  if (argc != 1 && argc != 2) {
    std::cerr << "Usage: " << argv[0] << " <number of elements>" << std::endl;
    return 1;
  }
  int n = argc == 2 ? std::atoi(argv[1]) : 50'000;

  // Create a vector with the integers from 1 to n.
  std::vector<int> v_original(n);
  for (int i = 0; i < n; ++i) {
    v_original[i] = i + 1;
  }

  // V1: Bubble sort with hard-coded comparison function.
  {
    std::vector v = v_original;
    Timer timer;
    bubbleSortComparisonHardCoded(v);
    std::cout << "V1: " << timer << " ... " << isSorted(v) << std::endl;
  }

  // V2: Bubble sort with given comparison function, inlinable.
  {
    std::vector v = v_original;
    Timer timer;
    bubbleSortComparisonFunctionPointer(v, compareInlinable);
    std::cout << "V2: " << timer << " ... " << isSorted(v) << std::endl;
  }

  // V3: Bubble sort with given comparison function, not inlinable.
  {
    std::vector v = v_original;
    Timer timer;
    bubbleSortComparisonFunctionPointer(v, compareNotInlinable);
    std::cout << "V3: " << timer << " ... " << isSorted(v) << std::endl;
  }

  // V4: Bubble sort with given comparison function as template.
  {
    Compare compare;
    std::vector v = v_original;
    Timer timer;
    bubbleSortComparisonFunctionTemplate(v, compare);
    std::cout << "V4: " << timer << " ... " << isSorted(v) << std::endl;
  }

  // V5: Bubble sort with given comparison function as lambda.
  {
    std::vector v = v_original;
    Timer timer;
    bubbleSortComparisonFunctionTemplate(v, [](int x, int y) { return x > y; });
    std::cout << "V5: " << timer << " ... " << isSorted(v) << std::endl;
  }
}