src/gromacs/domdec/hashedmap.h

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2018,2019,2020, by the GROMACS development team, led by
   5  * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   6  * and including many others, as listed in the AUTHORS file in the
   7  * top-level source directory and at http://www.gromacs.org.
   8  *
   9  * GROMACS is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU Lesser General Public License
  11  * as published by the Free Software Foundation; either version 2.1
  12  * of the License, or (at your option) any later version.
  13  *
  14  * GROMACS is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public
  20  * License along with GROMACS; if not, see
  21  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  22  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  23  *
  24  * If you want to redistribute modifications to GROMACS, please
  25  * consider that scientific software is very special. Version
  26  * control is crucial - bugs must be traceable. We will be happy to
  27  * consider code for inclusion in the official distribution, but
  28  * derived work must not be called official GROMACS. Details are found
  29  * in the README & COPYING files - if they are missing, get the
  30  * official version at http://www.gromacs.org.
  31  *
  32  * To help us fund GROMACS development, we humbly ask that you cite
  33  * the research papers on the package. Check out http://www.gromacs.org.
  34  */
  35 /*! \libinternal \file
  36  * \brief
  37  * Defines structures and functions for mapping from keys to entries
  38  * indices using a hash table.
  39  * The functions are performance critical and should be inlined.
  40  *
  41  * \inlibraryapi
  42  * \ingroup module_domdec
  43  *
  44  * \author Berk Hess <hess@kth.se>
  45  *
  46  */
  47 #ifndef GMX_DOMDEC_HASHEDMAP_H
  48 #define GMX_DOMDEC_HASHEDMAP_H
  49
  50 #include <climits>
  51
  52 #include <algorithm>
  53 #include <utility>
  54 #include <vector>
  55
  56 #include "gromacs/compat/utility.h"
  57 #include "gromacs/utility/basedefinitions.h"
  58 #include "gromacs/utility/exceptions.h"
  59
  60 namespace gmx
  61 {
  62
  63 /*! \libinternal \brief Unordered key to value mapping
  64  *
  65  * Efficiently manages mapping from integer keys to values.
  66  * Note that this basically implements a subset of the functionality of
  67  * std::unordered_map, but is an order of magnitude faster.
  68  */
  69 template<class T>
  70 class HashedMap
  71 {
  72 private:
  73     /*! \libinternal \brief Structure for the key/value hash table */
  74     struct hashEntry
  75     {
  76         int key = -1;  /**< The key */
  77         T   value;     /**< The value(s) */
  78         int next = -1; /**< Index in the list of the next element with the same hash, -1 if none */
  79     };
  80
  81     /*! \brief The table size is set to at least this factor time the nr of keys */
  82     static constexpr float c_relTableSizeSetMin = 1.5;
  83     /*! \brief Threshold for increasing the table size */
  84     static constexpr float c_relTableSizeThresholdMin = 1.3;
  85     /*! \brief Threshold for decreasing the table size */
  86     static constexpr float c_relTableSizeThresholdMax = 3.5;
  87
  88     /*! \brief Resizes the table
  89      *
  90      * \param[in] numElementsEstimate  An estimate of the number of elements that will be stored
  91      */
  92     void resize(int numElementsEstimate)
  93     {
  94         GMX_RELEASE_ASSERT(numElements_ == 0, "Table needs to be empty for resize");
  95
  96         /* The fraction of table entries with 0   size lists is e^-f.
  97          * The fraction of table entries with >=1 size lists is 1 - e^-f
  98          * where f is: the #elements / tableSize
  99          * The fraction of elements not in the direct list is: 1 - (1 - e^-f)/f.
 100          * Thus the optimal table size is roughly double #elements.
 101          */
 102         /* Make the hash table a power of 2 and at least 1.5 * #elements */
 103         int tableSize = 64;
 104         while (tableSize <= INT_MAX / 2
 105                && static_cast<float>(numElementsEstimate) * c_relTableSizeSetMin > tableSize)
 106         {
 107             tableSize *= 2;
 108         }
 109         table_.resize(tableSize);
 110
 111         /* Table size is a power of 2, so a binary mask gives the hash */
 112         bitMask_                        = tableSize - 1;
 113         startIndexForSpaceForListEntry_ = tableSize;
 114     }
 115
 116 public:
 117     /*! \brief Constructor
 118      *
 119      * \param[in] numElementsEstimate  An estimate of the number of elements that will be stored, used for optimizing initial performance
 120      *
 121      * Note that the estimate of the number of elements is only relevant
 122      * for the performance up until the first call to clear(), after which
 123      * table size is optimized based on the actual number of elements.
 124      */
 125     HashedMap(int numElementsEstimate) { resize(numElementsEstimate); }
 126
 127     /*! \brief Returns the number of elements */
 128     int size() const { return numElements_; }
 129
 130     /*! \brief Returns the number of buckets, i.e. the number of possible hashes */
 131     int bucket_count() const { return bitMask_ + 1; }
 132
 133 private:
 134     /*! \brief Inserts or assigns a key and value
 135      *
 136      * \tparam    allowAssign  Sets whether assignment of a key that is present is allowed
 137      * \param[in] key          The key for the entry
 138      * \param[in] value        The value for the entry
 139      * \throws InvalidInputError from a debug build when attempting to insert a duplicate key with \p allowAssign=true
 140      */
 141     // cppcheck-suppress unusedPrivateFunction
 142     template<bool allowAssign>
 143     void insert_assign(int key, const T& value)
 144     {
 145         size_t ind = (key & bitMask_);
 146
 147         if (table_[ind].key >= 0)
 148         {
 149             /* Loop over the entries for this hash.
 150              * If we find the matching key, return the value.
 151              */
 152             int ind_prev = ind;
 153             if (table_[ind_prev].key == key)
 154             {
 155                 if (allowAssign)
 156                 {
 157                     table_[ind].value = value;
 158                     return;
 159                 }
 160                 else
 161                 {
 162 // Note: This is performance critical, so we only throw in debug mode
 163 #ifndef NDEBUG
 164                     GMX_THROW(InvalidInputError("Attempt to insert duplicate key"));
 165 #endif
 166                 }
 167             }
 168             while (table_[ind_prev].next >= 0)
 169             {
 170                 ind_prev = table_[ind_prev].next;
 171                 if (table_[ind_prev].key == key)
 172                 {
 173                     if (allowAssign)
 174                     {
 175                         table_[ind_prev].value = value;
 176                         return;
 177                     }
 178                     else
 179                     {
 180 #ifndef NDEBUG
 181                         GMX_THROW(InvalidInputError("Attempt to insert duplicate key"));
 182 #endif
 183                     }
 184                 }
 185             }
 186             /* Search for space in table_ */
 187             ind = startIndexForSpaceForListEntry_;
 188             while (ind < table_.size() && table_[ind].key >= 0)
 189             {
 190                 ind++;
 191             }
 192             /* If we are at the end of the list we need to increase the size */
 193             if (ind == table_.size())
 194             {
 195                 table_.resize(table_.size() + 1);
 196             }
 197             table_[ind_prev].next = ind;
 198
 199             startIndexForSpaceForListEntry_ = ind + 1;
 200         }
 201
 202         table_[ind].key   = key;
 203         table_[ind].value = value;
 204
 205         numElements_ += 1;
 206     }
 207
 208 public:
 209     /*! \brief Inserts entry, key should not already be present
 210      *
 211      * \param[in] key    The key for the entry
 212      * \param[in] value  The value for the entry
 213      * \throws InvalidInputError from a debug build when attempting to inser         */
 214     void insert(int key, const T& value) { insert_assign<false>(key, value); }
 215
 216     /*! \brief Inserts an entry when the key is not present, otherwise sets the value
 217      *
 218      * \param[in] key    The key for the entry
 219      * \param[in] value  The value for the entry
 220      */
 221     void insert_or_assign(int key, const T& value) { insert_assign<true>(key, value); }
 222
 223     /*! \brief Delete the entry for key \p key, when present
 224      *
 225      * \param[in] key  The key
 226      */
 227     void erase(int key)
 228     {
 229         int ind_prev = -1;
 230         int ind      = (key & bitMask_);
 231         do
 232         {
 233             if (table_[ind].key == key)
 234             {
 235                 if (ind_prev >= 0)
 236                 {
 237                     table_[ind_prev].next = table_[ind].next;
 238
 239                     /* This index is a linked entry, so we free an entry.
 240                      * Check if we are creating the first empty space.
 241                      */
 242                     if (ind < startIndexForSpaceForListEntry_)
 243                     {
 244                         startIndexForSpaceForListEntry_ = ind;
 245                     }
 246                 }
 247                 table_[ind].key  = -1;
 248                 table_[ind].next = -1;
 249
 250                 numElements_ -= 1;
 251
 252                 return;
 253             }
 254             ind_prev = ind;
 255             ind      = table_[ind].next;
 256         } while (ind >= 0);
 257     }
 258
 259     /*! \brief Returns a pointer to the value for the given key or nullptr when not present
 260      *
 261      * \todo Use std::as_const when CUDA 11 is a requirement.
 262      *
 263      * \param[in] key  The key
 264      * \return a pointer to value for the given key or nullptr when not present
 265      */
 266     T* find(int key) { return const_cast<T*>(gmx::compat::as_const(*this).find(key)); }
 267
 268     /*! \brief Returns a pointer to the value for the given key or nullptr when not present
 269      *
 270      * \param[in] key  The key
 271      * \return a pointer to value for the given key or nullptr when not present
 272      */
 273     const T* find(int key) const
 274     {
 275         int ind = (key & bitMask_);
 276         do
 277         {
 278             if (table_[ind].key == key)
 279             {
 280                 return &table_[ind].value;
 281             }
 282             ind = table_[ind].next;
 283         } while (ind >= 0);
 284
 285         return nullptr;
 286     }
 287
 288     /*! \brief Clear all the entries in the list
 289      *
 290      * Also optimizes the size of the table based on the current
 291      * number of elements stored.
 292      */
 293     void clear()
 294     {
 295         const int oldNumElements = numElements_;
 296
 297         for (hashEntry& entry : table_)
 298         {
 299             entry.key  = -1;
 300             entry.next = -1;
 301         }
 302         startIndexForSpaceForListEntry_ = bucket_count();
 303         numElements_                    = 0;
 304
 305         /* Resize the hash table when the occupation is far from optimal.
 306          * Do not resize with 0 elements to avoid minimal size when clear()
 307          * is called twice in a row.
 308          */
 309         if (oldNumElements > 0
 310             && (oldNumElements * c_relTableSizeThresholdMax < bucket_count()
 311                 || oldNumElements * c_relTableSizeThresholdMin > bucket_count()))
 312         {
 313             resize(oldNumElements);
 314         }
 315     }
 316
 317 private:
 318     /*! \brief The hash table list */
 319     std::vector<hashEntry> table_;
 320     /*! \brief The bit mask for computing the hash of a key */
 321     int bitMask_ = 0;
 322     /*! \brief Index in table_ at which to start looking for empty space for a new linked list entry */
 323     int startIndexForSpaceForListEntry_ = 0;
 324     /*! \brief The number of elements currently stored in the table */
 325     int numElements_ = 0;
 326 };
 327
 328 } // namespace gmx
 329
 330 #endif