8heap

An implementation of an 8-ary heap using SSE instruction phminposuw to calculate the horizontal minimum of unsigned 16 bit integers. The implementation provides faster delete minimum and heapify operations over a standard binary heap by leveraging the 8-ary trees shallower depth without paying the cost of the minimum of 8 elements due to the speed up from the SSE4 instruction.

Requirements

• CMake >= 3.11
• Boost >= 1.65

You can install these with

brew install cmake boost

Installation

Installing from this git repository is as simple as

git clone https://github.com/sorenlassen/8heap.git

Build, Tests, Benchmarks

You can either use make or CMake to run.

Make

To use Make you first need to install googletest

pushd $HOME # or whereever you want to clone googletest
git clone https://github.com/google/googletest.git
cd googletest
mkdir build
cd build/
cmake ..
make
make install
popd

Then run the following command

make runtests

To run the benchmarks install

brew install google-benchmark gflags folly

and then

make runbenchmarks

CMake

To use CMake you first need to install gflags

brew install gflags

Then run the following commands

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Debug ..
make runtests

To benchmark, still in the build directory, clean the test libraries built above

make clean

and then

cmake -DCMAKE_BUILD_TYPE=Release ..
make runbenchmarks
make runfollybenchmarks