8heap's Introduction

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

8heap's People

Contributors

Stargazers

Watchers

8heap's Issues

.travis failing on compile with boost and google test

Travis build fails with

0.90s$ make HeapAuxTest
Scanning dependencies of target HeapAuxTest
[ 50%] Building CXX object CMakeFiles/HeapAuxTest.dir/HeapAuxTest.cpp.o
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:18:25: error: ‘boost::iterators::counting_iterator’ has not been declared
 using boost::iterators::counting_iterator;
                         ^~~~~~~~~~~~~~~~~
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:19:25: error: ‘boost::iterators::transform_iterator’ has not been declared
 using boost::iterators::transform_iterator;
                         ^~~~~~~~~~~~~~~~~~
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:32:17: error: expected constructor, destructor, or type conversion before ‘(’ token
 TYPED_TEST_SUITE(HeapAuxTest, Implementations);
                 ^
In file included from /usr/include/gtest/gtest.h:66:0,
                 from /home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:14:
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:34:1: error: ‘gtest_type_params_HeapAuxTest_’ was not declared in this scope
 TYPED_TEST(HeapAuxTest, Clear) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:34:1: error: template argument 3 is invalid
 TYPED_TEST(HeapAuxTest, Clear) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:42:1: error: ‘gtest_type_params_HeapAuxTest_m’ was not declared in this scope
 TYPED_TEST(HeapAuxTest, Push3) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:42:1: error: template argument 3 is invalid
 TYPED_TEST(HeapAuxTest, Push3) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:64:1: error: ‘gtest_type_params_HeapAuxTest_’ was not declared in this scope
 TYPED_TEST(HeapAuxTest, Heapify3) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:64:1: error: template argument 3 is invalid
 TYPED_TEST(HeapAuxTest, Heapify3) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:77:1: error: ‘gtest_type_params_HeapAuxTest_’ was not declared in this scope
 TYPED_TEST(HeapAuxTest, Sort3) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:77:1: error: template argument 3 is invalid
 TYPED_TEST(HeapAuxTest, Sort3) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:91:1: error: ‘gtest_type_params_HeapAuxTest_’ was not declared in this scope
 TYPED_TEST(HeapAuxTest, Heapify100) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:91:1: error: template argument 3 is invalid
 TYPED_TEST(HeapAuxTest, Heapify100) {
 ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp: In member function ‘virtual void {anonymous}::HeapAuxTest_Heapify100_Test<gtest_TypeParam_>::TestBody()’:
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:95:3: error: ‘counting_iterator’ was not declared in this scope
   counting_iterator<value_type> zero(0);
   ^~~~~~~~~~~~~~~~~
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:95:3: note: suggested alternative:
In file included from /home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:12:0:
/usr/include/boost/iterator/counting_iterator.hpp:22:7: note:   ‘boost::counting_iterator’
 class counting_iterator;
       ^~~~~~~~~~~~~~~~~
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:95:31: error: expected primary-expression before ‘>’ token
   counting_iterator<value_type> zero(0);
                               ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:95:39: error: there are no arguments to ‘zero’ that depend on a template parameter, so a declaration of ‘zero’ must be available [-fpermissive]
   counting_iterator<value_type> zero(0);
                                       ^
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:95:39: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
/home/travis/build/sorenlassen/8heap/HeapAuxTest.cpp:100:35: error: ‘zero’ was not declared in this scope
   auto begin = transform_iterator(zero, revert);
                                   ^~~~
make[3]: *** [CMakeFiles/HeapAuxTest.dir/HeapAuxTest.cpp.o] Error 1
make[2]: *** [CMakeFiles/HeapAuxTest.dir/all] Error 2
make[1]: *** [CMakeFiles/HeapAuxTest.dir/rule] Error 2
make: *** [HeapAuxTest] Error 2
The command "make HeapAuxTest" exited with 2.
0.00s$ ./HeapAuxTest
/home/travis/.travis/functions: line 109: ./HeapAuxTest: No such file or directory
The command "./HeapAuxTest" exited with 127.

My guess is this is due to wrong Boost and Google Test versions being installed in the .travis build

Failed to compile HeapAuxTest.cpp with Heap8Embed.hpp

make runtests
gcc -g -std=c11 -msse4 -O2 -c h8.c
g++ -g -std=c++17 -msse4 -lgtest -lgtest_main h8.o HeapTest.cpp -o HeapTest.out
g++ -g -std=c++17 -msse4 -lgtest -lgtest_main h8.o h8Test.cpp -o h8Test.out
g++ -g -std=c++17 -msse4 -O2 -c Sort8.cpp
g++ -g -std=c++17 -msse4 -lgtest -lgtest_main Sort8.o Sort8Test.cpp -o Sort8Test.out
g++ -g -std=c++17 -msse4 -lgtest -lgtest_main minposTest.cpp -o minposTest.out
g++ -g -std=c++17 -msse4 -lgtest -lgtest_main HeapAuxTest.cpp -o HeapAuxTest.out
In file included from HeapAuxTest.cpp:10:
./Heap8Embed.hpp:65:27: error: non-const reference cannot bind to vector element
    return std::make_pair(n->values.values[i], n->shadows[i]);
                          ^~~~~~~~~~~~~~~~~~~
HeapAuxTest.cpp:98:29: note: in instantiation of member function 'Heap8Embed<(anonymous namespace)::ShadowArray>::entry' requested here
  EXPECT_EQ(p3, this->heap_.entry(0));
                            ^
/usr/local/include/gtest/internal/gtest-internal.h:470:44: note: in instantiation of member function '(anonymous
      namespace)::HeapAuxTest_Sort3_Test<Heap8Embed<(anonymous namespace)::ShadowArray> >::TestBody' requested here
  Test* CreateTest() override { return new TestClass; }
                                           ^
/usr/local/include/gtest/internal/gtest-internal.h:728:13: note: in instantiation of member function 'testing::internal::TestFactoryImpl<(anonymous
      namespace)::HeapAuxTest_Sort3_Test<Heap8Embed<(anonymous namespace)::ShadowArray> > >::CreateTest' requested here
        new TestFactoryImpl<TestClass>);
            ^
/usr/local/include/gtest/internal/gtest-internal.h:732:57: note: in instantiation of member function 'testing::internal::TypeParameterizedTest<HeapAuxTest,
      testing::internal::TemplateSel<HeapAuxTest_Sort3_Test>, testing::internal::Types<Heap8Embed<(anonymous namespace)::ShadowArray>> >::Register' requested here
                                 typename Types::Tail>::Register(prefix,
                                                        ^
HeapAuxTest.cpp:90:1: note: in instantiation of member function 'testing::internal::TypeParameterizedTest<HeapAuxTest,
      testing::internal::TemplateSel<HeapAuxTest_Sort3_Test>, testing::internal::Types<Heap8Aux<int>, Heap8Embed<(anonymous namespace)::ShadowArray> > >::Register'
      requested here
TYPED_TEST(HeapAuxTest, Sort3) {
^
/usr/local/include/gtest/gtest-typed-test.h:214:27: note: expanded from macro 'TYPED_TEST'
              CaseName)>::Register("",                                        \
                          ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/utility:661:17: note: passing argument to parameter '__t1' here
make_pair(_T1&& __t1, _T2&& __t2)
                ^
1 error generated.
make: *** [HeapAuxTest.out] Error 1

Recommend Projects