eugnsp

#include <benchmark/benchmark.h>

#include <algorithm>
#include <queue>
#include <random>
#include <string>
#include <vector>

template<typename T>
class Vector_priority_queue

eugnsp

// https://github.com/google/benchmark
#include <benchmark/benchmark.h>

#include <cstddef>
#include <cstring>

#define REPEAT4(x) x x x x
#define REPEAT16(x) REPEAT4(x) REPEAT4(x) REPEAT4(x) REPEAT4(x)
#define REPEAT64(x) REPEAT16(x) REPEAT16(x) REPEAT16(x) REPEAT16(x)

eugnsp

#!/bin/bash

set -e

curl -JLO https://www.vmware.com/go/getplayer-linux

FILE=`ls VMware-Player-*.bundle | sort | tail -n 1`

if [[ -z $FILE ]]; then
    echo "Bad filename."

eugnsp

Fewer memory accesses – faster rotation?

A k-rotation (or a k-cyclic shift) of a sequence (a0a2...an-1) is a sequence (aP(1)aP(2)...aP(n-1)), where the index permutation is P(i) = (i + k) % n. The problem is to transform the given sequence into its k-rotation.

There are four well-known algorithms to do it:

1. Dolphin algorithm:

   Compute the number of cycles, nc = gcd(k, n - k); for each cycle (aCi(0)aCi(1)aCi(2)...) with Ci(j) = (i + jk) % n, i = 0, ..., nc - 1, make a cyclic shift of all the elements by one position to obtain (aCi(1)aCi(2)...aCi(0)).

2. Gries–Mills algorithm:. > If k = n - k, swap the subsequences (a0...ak-1) and (ak...an-1); if k < n - k, swap the subsequences (a0...ak-1)

eugnsp

Copy-transpose – strided reads or strided writes?

Suppose we have two square NxN matrices A and B of doubles, and we want to perform a copy with a transposition:

A = transpose(B)

Equivalently, we want to copy a row-major matrix to a column-major one or vice versa.

Below are the results of a simple benchmark for 3 ways to accomplish the task:

1. Two nested loops such that reads are contiguous and writes are strided.

eugnsp

#include <benchmark/benchmark.h>

#include <algorithm>
#include <cstddef>
#include <random>
#include <unordered_set>
#include <vector>

std::mt19937 gen;

eugnsp

% A simple Octave script to calculate the electron spectrum of a periodic 
% 1D tight-binding chain with on-site or hopping disorder with normal 
% distribution. For each disorder realization, eigenstates are computed 
% via exact diagonalization, then FFT is applied to find the eigenstates 
% in the momentum basis (i.e., plane waves) and the corresponding DOS. 
% The results are averaged over independent disorder realizations.

clear variables

N = 200;	  		% Number of sites