================ @@ -0,0 +1,129 @@ +//===--- HashKeyMap.h - Wrapper for maps using hash value key ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// +/// Defines HashKeyMap template. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_PROFILEDATA_HASHKEYMAP_H +#define LLVM_PROFILEDATA_HASHKEYMAP_H + +#include "llvm/ADT/Hashing.h" +#include <iterator> +#include <utility> + +namespace llvm { + +namespace sampleprof { + +/// This class is a wrapper to associative container MapT<KeyT, ValueT> using +/// the hash value of the original key as the new key. This greatly improves the +/// performance of insert and query operations especially when hash values of +/// keys are available a priori, and reduces memory usage if KeyT has a large +/// size. +/// All keys with the same hash value are considered equivalent (i.e. hash +/// collision is silently ignored). Given such feature this class should only be +/// used where it does not affect compilation correctness, for example, when +/// loading a sample profile. The original key is not stored, so if the user +/// needs to preserve it, it should be stored in the mapped type. +/// Assuming the hashing algorithm is uniform, we use the formula +/// 1 - Permute(n, k) / n ^ k where n is the universe size and k is number of +/// elements chosen at random to calculate the probability of collision. With +/// 1,000,000 entries the probability is negligible: +/// 1 - (2^64)!/((2^64-1000000)!*(2^64)^1000000) ~= 3*10^-8. +/// Source: https://en.wikipedia.org/wiki/Birthday_problem +/// +/// \param MapT The underlying associative container type. +/// \param KeyT The original key type, which requires the implementation of +/// llvm::hash_value(KeyT). +/// \param ValueT The original mapped type, which has the same requirement as +/// the underlying container. +/// \param MapTArgs Additional template parameters passed to the underlying +/// container. +template <template <typename, typename, typename...> typename MapT, + typename KeyT, typename ValueT, typename... MapTArgs> +class HashKeyMap : ---------------- huangjd wrote:
I moved it out from SampleProf.h because it is used outside of profile reader, now Trnasforms/IPO uses it several places https://github.com/llvm/llvm-project/pull/66164 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
