hash.cpp

Go to the documentation of this file.

/******************************************************************************
** Copyright © 2004 by J.M.McGuiness, coder@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
#include "stdafx.h"
 
#define BOOST_TEST_MODULE libjmmcg_tests
#include <boost/test/included/unit_test.hpp>
 
#include "core/hash.hpp"
#include "core/stats_output.hpp"
 
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
#include "core/ave_deviation_meter.hpp"
 
#include "absl/hash/hash.h"
// TODO #include "folly/hash/Hash.h"
#include "src/include/robin_hood.h"
 
#include <boost/functional/hash.hpp>
 
#include <array>
#include <chrono>
 
using namespace libjmmcg;
 
const std::array guids{
   "FA6AF2C3-5957-48CE-A45D-338A71CA5CC1",
   "D3DA1A9B-DC2A-47A0-9812-A5071CACD4E8",
   "2B482B48-69C4-469F-9DB2-FF79DED69CFE",
   "8DA78ED6-8FE2-4C96-A0A7-FF6DB0CEFCFD",
   "5CA0C6D0-4516-4C26-9C8D-EF159C83CC66",
   "7B519D94-89C3-4E5C-B3D4-0DE31545CA84",
   "31652501-0B76-4BFA-B973-8ABC0C95578B",
   "AC8DDD15-E763-41F0-A111-4100F80DF5BF",
   "142F635A-6DAA-4F5C-9CD2-93379779FD67",
   "9609C637-E667-4307-9B16-D20483E6D4DB",
   "7CA9EA22-D056-4C2B-8C4F-681B4A4AF0FA",
   "F1DCA9C9-E1AF-4844-A52F-97B5356876E8",
   "F025908C-9DD6-424A-85A5-1DF65B1973FC",
   "884C6532-4A3E-4BAE-9D84-7827DEF2B6F1",
   "C876839F-9EFA-484E-85F8-10D2D67A9738",
   "3D85A56A-1177-486D-80D3-9A26A47B8905"
};
 
/**
 * \todo Consider using hashes from <a href="https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/"/>.
 */
struct abseil_t : absl::Hash<std::string> {
   using result_type=std::size_t;
};
struct robin_hood_t : robin_hood::hash<std::string> {
   using result_type=std::size_t;
};
using murmur2_t=hashers::murmur2<std::string>;
using hsieh_t=hashers::hsieh<std::string>;
using hsieh_mpl_t=hashers::mpl::hsieh<std::string, 36>;
using hashes_t=std::vector<murmur2_t::result_type>;
using timed_results_t=ave_deviation_meter<unsigned long long>;
 
template<class H> void __fastcall
hashem(std::ostream &, std::vector<typename H::result_type> &hashes) {
   typedef std::vector<typename H::result_type> hashes_t;
   hashes.reserve(guids.size());
   std::transform(
      guids.begin(),
      guids.end(),
      std::back_insert_iterator<hashes_t>(hashes),
      H()
   );
// std::copy(hashes.begin(), hashes.end(), std::ostream_iterator<hashes_t::value_type>(os, "\n"));
   hashes.clear();
}
 
template<class H> void __fastcall
do_hashing(std::ostream &os, const int num_hashes) {
   typedef std::vector<typename H::result_type> hashes_t;
 
   const unsigned short loops_for_conv=50;
   const double perc_conv_estimate=5.0;
 
   const std::pair<timed_results_t, bool> timed_results(compute_average_deviation<timed_results_t::value_type>(
      perc_conv_estimate,
      loops_for_conv,
      [num_hashes, &os]() {
         hashes_t hashes;
         const auto t1=std::chrono::high_resolution_clock::now();
         for (int i=0; i<num_hashes; ++i) {
            hashem<H>(os, hashes);
         }
         const auto t2=std::chrono::high_resolution_clock::now();
         return timed_results_t::value_type(static_cast<double>(num_hashes*sizeof(guids)/sizeof(guids[0]))/(static_cast<double>(std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count())/1000000));
      }
   ));
   std::cout<<typeid(H).name()<<" hashes/sec="<<timed_results.first<<std::endl;
#ifdef JMMCG_PERFORMANCE_TESTS
   os<<timed_results.first.to_csv()<<std::flush;
   BOOST_CHECK(!timed_results.second);
#endif
}
 
BOOST_AUTO_TEST_SUITE(hashing)
 
BOOST_AUTO_TEST_CASE(create_murmur2) {
   [[maybe_unused]] murmur2_t hasher;
}
 
BOOST_AUTO_TEST_CASE(create_hsieh) {
   [[maybe_unused]] hsieh_t hasher;
}
 
BOOST_AUTO_TEST_CASE(create_hsieh_mpl) {
   [[maybe_unused]] hsieh_mpl_t hasher;
}
 
BOOST_AUTO_TEST_CASE(hash_murmur2) {
   murmur2_t hasher;
   BOOST_CHECK(hasher(guids[0])!=0);
}
 
BOOST_AUTO_TEST_CASE(hash_hsieh) {
   hsieh_t hasher;
   BOOST_CHECK(hasher(guids[0])!=0);
}
 
BOOST_AUTO_TEST_CASE(hash_hsieh_mpl) {
   hsieh_mpl_t hasher;
   BOOST_CHECK(hasher(guids[0])!=0);
}
 
BOOST_AUTO_TEST_SUITE(performance, *stats_to_csv::make_fixture("hash.csv"))
 
/**
   \test <a href="./examples/hash.svg">Graph</a> of performance results for the various hash functions.
         ==========================================================================================
   Results for 1000000 repetitions:
   -# Build 1402: g++v4.7.3, boost v1.54:
      - hashers::murmur2 = 9.53073e+06 hashes/sec
      - hashers::hsieh = 8.69376e+06 hashes/sec
      - hashers::mpl::hsieh = 9.82567e+06 hashes/sec
      - boost::hash = 6.15003e+06 hashes/sec
      - std::hash = 9.74447e+06 hashes/sec
   -# Build 1627: g++v4.8.4, boost v1.56:
      - hashers::murmur2 = 9.477643e+06 hashes/sec
      - hashers::hsieh =   8.87383e+06 hashes/sec
      - hashers::mpl::hsieh = 9.901563e+06 hashes/sec
      - boost::hash = 5.547246e+06 hashes/sec
      - std::hash = 9.806128e+06 hashes/sec
*/
BOOST_AUTO_TEST_CASE(time_hashes) {
#ifdef JMMCG_PERFORMANCE_TESTS
   const std::size_t num_hashes=1000000;
#else
   const std::size_t num_hashes=100;
#endif
   do_hashing<abseil_t>(stats_to_csv::handle->stats, num_hashes);
   do_hashing<robin_hood_t>(stats_to_csv::handle->stats, num_hashes);
   do_hashing<murmur2_t>(stats_to_csv::handle->stats, num_hashes);
   do_hashing<hsieh_t>(stats_to_csv::handle->stats, num_hashes);
   do_hashing<hsieh_mpl_t>(stats_to_csv::handle->stats, num_hashes);
   do_hashing<boost::hash<std::string>>(stats_to_csv::handle->stats, num_hashes);
   do_hashing<std::hash<std::string>>(stats_to_csv::handle->stats, num_hashes);
}
 
BOOST_AUTO_TEST_SUITE_END()
 
BOOST_AUTO_TEST_SUITE_END()