Skip to content

sorenlassen/8heap

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

8heap

Build Status

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

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