DEV Community: benw

CPU Cache

benw — Mon, 14 Oct 2019 10:51:41 +0000

Since the 90's, the performance of CPU's increased dramatically, while the performance of RAM chips did not increase proportionally. In order to mitigate the difference, a caching mechanism was introduced.

During the program execution, there is a good chance that the same code or data gets reused over short periods of time, that is the temporal locality, and there is also spatial locality, the memory addresses accessed are close to each other. Realizing that locality exists is key to the concept of CPU caches as we use them today.

The caching mechanism is fast but small type of memory that stores recently accessed memory locations. There are several types of CPU caches, the data cache, the instruction cache and there is also the TLB (translation look-aside buffer), which caches the translation from a virtual page address to real page address.
In order to create efficient data structures and algorithms we should be aware of cache and how to utilize it:

Compact localized code is going to be fastest.
Compact localized data structures that fit into cache, are going to be fastest.
Data structure traversal that touch only cached data is going to be the fastest.

Cache hierarchy

The cache is organized in several layers, where each cache layer is larger and slower than the previous one.
For example, on an Intel core i-7:

L1 I-Cache (instruction cache) 32Kb per core.
L1 D-Cache (data cache) 32Kb per core.
L2 Cache 256Kb per core.
L3 Cache 8 MB

The smallest unit of memory that is being read or written from the main memory to cache is called a cache-line.
When you read a byte from the main memory, you actually read an entire cache line of 64 bytes (for example) that contains that byte. When designing data structures or algorithm we should utilize as much of the cache line. This is the reason that row major traversal is much faster than column major traversal. When using row major traversal, on access of an element, we get the entire cache line that contains subsequent elements, so while traversing the elements, you get a minimal amount of cache misses, because the cache line is utilized completely. Column traversal on the other hand, has the potential of reading an element and discarding the rest of the cache line.

The hardware will detect access patterns and prefetch the next cache lines accordingly, so if you use every second element in a row major traversal the speed will be pretty much the same. Predictable access patterns matter, as long as it's a linear predictable pattern.

From the hardware perspective, data structure which preserves locality and predictable access patterns such as arrays are favorable. This also means that for some small enough N, traversing an array might be faster than searching binary tree or a hash table.

An Example

Let's explore the principles above using an example. Suppose we are writing a computer vision library that has a functionality to find matching points in a pair of images. Each point has a descriptor and by comparing those descriptors we would find the most similar point in the second image.

We create a data structure that represents a point:


struct Descriptor {
  static constexpr size_t kDescriptorSize = 8;
  std::array<uint8_t, kDescriptorSize> data{0};
};

struct Point {
  uint32_t x, y;
  Descriptor desc;
};

One way to organize the points is in a map, such that we could easily query a point by its coordinates in the image:

  std::map<std::pair<uint32_t, uint32_t>, Point> points;

In order to find the closest point, we compare the descriptors and look for the minimal L2 distance.

    float L2(const Descriptor& desc1, const Descriptor& desc2) {
      auto sqrd_diff{0.f};
      for (auto i(0u); i < Descriptor::kDescriptorSize; i++) {
          sqrd_diff += std::pow(desc1.data[i] - desc2.data[i], 2);
      }
      return std::sqrt(sqrd_diff);
    }

    auto min_dist = std::numeric_limits<float>::max();
    for (const auto& key_point : points) {
      auto l2 = L2(query, key_point.second.desc);
      min_dist = min_dist < l2 ? min_dist : l2;
    }

When using this type of data structure, memory is not contiguous, which means there is a high probability we get a lot of cache misses during the iterations of the loop.

Using google benchmark library, the results of this implementation (with 65536 points):

Run on (4 X 3500 MHz CPU s)
CPU Caches:
  L1 Data 32K (x2)
  L1 Instruction 32K (x2)
  L2 Unified 262K (x2)
  L3 Unified 4194K (x1)
Load Average: 1.42, 1.73, 1.97
-----------------------------------------------------------------------
Benchmark                             Time             CPU   Iterations
-----------------------------------------------------------------------
CalculateL2CacheMissed/65536       8.93 ms         8.91 ms           68

We could consider a different implementation which utilizes better the cache mechanism by iterating over a contiguous block of memory. That way the hardware could prefetch the next cache line and the program will spend less time waiting for memory.

Lets create an array of all descriptors, and a map between an index in the array and a point. Now iterate over the array of descriptors to find the minimal distance and after all computation is done, return the selected point by using the mapping above.

    std::vector<Descriptor> vector_of_descriptors;

    auto min_dist = std::numeric_limits<float>::max();
    for (const auto& descriptor : vector_of_descriptors) {
      auto l2 = L2(query, descriptor);
      min_dist = min_dist < l2 ? min_dist : l2;
    }

Comparing the performance of both implementations:

Run on (4 X 3500 MHz CPU s)
CPU Caches:
  L1 Data 32K (x2)
  L1 Instruction 32K (x2)
  L2 Unified 262K (x2)
  L3 Unified 4194K (x1)
Load Average: 1.42, 1.73, 1.97
-----------------------------------------------------------------------
Benchmark                             Time             CPU   Iterations
-----------------------------------------------------------------------
CalculateL2CacheMissed/65536       8.93 ms         8.91 ms           68
CalculateL2CacheHit/65536          4.42 ms         4.41 ms          157

By choosing a data structure that makes better utilization of the cache we gain twice the performance in this case. So, to sum it up, computer architecture and the caching mechanism specifically is something to consider when the goal is to write efficient data structures and algorithms.
Below are some good resources that expand on this topic.

References

Move Semantics Explained

benw — Sat, 14 Sep 2019 06:43:38 +0000

In C++11 move semantics and rvalue references were added to the language. With their addition, we can significantly increase the performance by avoiding unnecessary copies of temporary objects.

Lvalue and rvalue references

The first thing is to understand the concept of lvalues and rvalues. Simply speaking, lvalue expression may appear on the right or the left hand side of an assignment, whereas an rvalue may appear only on the right hand side. This is an over simplified explanation, and in modern C++ it is more nuanced than that, but for our purposes we can look at some examples to make that clearer:

int* int_ptr = nullptr;
// Example 1.
int i = 0;
int_ptr = &i;
/* Ok! because i is an lvalue,
for which the address can be referenced.*/
*int_ptr = 5;

// Example 2.
int func();
/* ERROR! that's an rvalue. We can't reference
the address of the temporary created on that call. */
func() = 5;

// Example 3.
int& func();
func() = 7;// OK! Like operator[] in std::vector for example.

//Example 4.
int a = 3, b = 4; // both lvalues
(a+b) = b; //ERROR

As we can see from the above examples, an rvalue is an expression whose lifetime ends at the expression it is evaluated in. It can be thought of as an unnamed temporary object in that context.

Move semantics

Suppose we have a class owning a resource which is expensive to construct or copy, for example a large buffer of memory.

class Expensive {
  std::string name_;
  size_t big_arr_size_ = 0;
  uint8_t *big_array_ = nullptr;

 public:
  Expensive(const std::string &name, size_t arr_size)
      : name_(name),
        big_arr_size_(arr_size),
        big_array_(big_arr_size_ ? new uint8_t[arr_size] : nullptr) {
  }

  ~Expensive() {
    delete[] big_array_;
  }
};

The copy constructor and copy assignment operators:

  Expensive(const Expensive &other)
      : name_(other.name_),
        big_arr_size_(other.big_arr_size_),
        big_array_(big_arr_size_ ? new uint8_t[big_arr_size_] : nullptr) {
    std::copy(other.big_array_, other.big_array_ + big_arr_size_, big_array_);
  }

  // note: Might be a better option, using the copy and swap idiom.
  Expensive &operator=(const Expensive &other) {
    if (&other != this) {
      name_ = other.name_;
      if (other.big_arr_size_ != big_arr_size_) {
        // In case throws, would not want to change the state of the object.
        auto new_size = other.big_arr_size_;
        auto new_arr = new_size ? new uint8_t[new_size] : nullptr;
        // resource needs clean up and reallocation
        delete[] big_array_;
        big_arr_size_ = new_size;
        big_array_ = new_arr;
      }
      std::copy(other.big_array_, other.big_array_ + big_arr_size_, big_array_);

    }
    return *this;
  }

During copy construction or copy assignment we allocate and assign values to a (potentially large) buffer for the constructed/assigned object.
Let’s look at the following example:

Expensive first("first", 1024);
Expensive second("second", 2048);

// Assignment of two lvalue. Copy assignment is called.
first = second

/* Assignment of a temporary object,
which is destructed right after expression evaluation.
Copy assignment is called (no move operations defined yet),
but we can do better. */
first = Expensive("third", 4096);

Currently, the sequence of operations in the second assignment is just like in the first. After creating the temporary object, the assignment operator gets called, which in turn calls for allocation, deletion, and copy of the buffer. It could be more efficient to have a special treatment for the second case, where we are dealing with an rvalue, a temporary object which will be destructed right after the assignment. In this way, we could replace the expensive assignment to something more similar to pointer swap, this way we won’t need to reallocate the data and copy its content. That’s where move semantics comes into play with the use of rvalue reference. Syntactically, given a type T, T& is called lvalue reference and T&& is rvalue reference. When we want to construct or assign from rvalue reference we call that a move operation. There is the move assignment and move construction operations, which in our example might look like this:

  Expensive(Expensive &&other) {
    std::swap(name_, other.name_);
    std::swap(big_arr_size_, other.big_arr_size_);
    std::swap(big_array_, other.big_array_);
  }

In this implementation we swap the pointers of the buffer, a much cheaper operation than reallocation and copy. It’s important to leave the object that we moved from (called other in our example) in a well defined state, having its resources cleared. (The created object has empty string, null pointer and zero size, so that requirement is fulfilled).
Note that although “other” is passed as an rvalue reference, it is an lvalue by itself, because it has an address we can reference. If the variable has a name, its an lvalue. The function std::move casts its argument to an rvalue reference (doesn’t distinguish if its argument is an lvalue or an rvalue) so it returns an rvalue.

Let’s look at move assignment:

  Expensive &operator=(Expensive &&other) {
    name_ = std::move(other.name_);
    std::swap(big_arr_size_, other.big_arr_size_);
    std::swap(big_array_, other.big_array_);
    delete[] other.big_array_;
    other.big_array_ = nullptr;
    other.big_arr_size_ = 0;
    return *this;
  }

Note the use of std::move on the name_ member. Since other.name is an lvalue, if we had written name_ = other.name_ then the copy c’tor of std::string would have been called. Since we want to leverage that its a move operation, in order to call the move assignment of std::string we could have just called std::move on other.name, which is returned as an rvalue. The implementation of std::swap is using std::move on its arguments when assigning, so we could have just called std::swap on name_, as it was written in the move c’tor.

Compiler generated special member functions

The special member functions before C++11 were: default c’tor, d’tor, copy c’tor and copy assignment operators. Those member functions were generated if needed ( i.e, they were called in the code) and not explicitly declared in the class. With move semantics, the compiler might generate two more member functions: the move c’tor and the move assignment operator. The move c’tor move constructs each non static data member of the class and similarly, move assignment move-assigns each non-static data member. If a data member is of a type that doesn’t ofer move operation then it will be copy constructed/assigned.

When the class explicitly defines a copy c’tor then the move operations won’t be generated, and if a move operation was explicitly defined, the copy operations won’t be generated. The logic behind that is that if memberwise copy is not appropriate for the class, then probably memberwise move is not either, and that goes the other way around too.
The rule of three states that if you declare any of copy c’tor, copy assignment operator or destructor, you should declare all three. That rule came from the observation that if the class defines some special treatment in d’tor or copy operation, it probably makes some resource management and that resource should be addressed in the copy operations and in the destructor. This rule is the motivation behind the fact that if a d’tor was explicitly defined, the move operations won’t be generated. So compiler generates move operations only if they were not defined and no d’tor or copy operations were defined either.
Now lets take a look at the implication of that last paragraph. Suppose we have a class that contains std::vector, for which we know the move operations are defined.

struct ClassGenMove {
  ClassGenMove() : bytes_(10'000'000) {}
  std::vector<uint8_t> bytes_;
};

So in this example the class does not define d’tor or copy operations, which means the compiler will generate the copy operations, the move operations and the destructor. Since the compiler generated move operation make a memberwise move, move assignment or move construction will take place on bytes_ member, when assigning or constructing from an rvalue.
What happens when we add a destructor:

struct ClassNotGenMove {
  ClassNotGenMove() : bytes_(10'000'000) {}
  std::vector<uint8_t> bytes_;
  ~ClassNotGenMove() = default;
};

As previously noted, the compiler will not generate the move operations. And now we can test the performance for such a change.

template <typename T>
void TimeMoveVsCopy() {
  T sample1, sample2;

  auto num_iter(10000);
  auto start_time = std::chrono::high_resolution_clock::now();
  for (auto i(0); i < num_iter; i++) {
    sample1 = std::move(sample2);
  }
  auto end_time = std::chrono::high_resolution_clock::now();

  std::cout << "Took "
            << std::chrono::duration_cast<std::chrono::microseconds>(end_time -
                                                                     start_time)
                       .count() /
                   num_iter
            << " us" << std::endl;
}
std::cout << "Class with generate move ops:\n";
TimeMoveVsCopy<ClassGenMove>();

std::cout << "Class without generated move ops:\n";
TimeMoveVsCopy<ClassNotGenMove>();

The performance as measured on a MacBook Pro (3.5 GHz Intel Core i7):

Class with generate move ops:
Took 6 us
Class without generated move ops:
Took 745 us

As expected, move operations were not generated and so the copy c’tor of std::vector was called instead, which we see as the impact on performance. Following the rules discussed earlier regarding the compiler generated special member function, after adding the destructor, we need to explicitly declare the move and copy operations, which in this case it’s enough to just use the default. Now we are back to using the move operations as expected.

ClassNotGenMove &operator=(const ClassNotGenMove &) = default;
ClassNotGenMove(const ClassNotGenMove &) = default;
ClassNotGenMove(ClassNotGenMove &&) = default;
ClassNotGenMove &operator=(ClassNotGenMove &&) = default;