src/gromacs/domdec/hashedmap.h

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2018,2019, 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 <vector>
  54
  55 #include "gromacs/compat/utility.h"
  56 #include "gromacs/utility/basedefinitions.h"
  57 #include "gromacs/utility/exceptions.h"
  58
  59 namespace gmx
  60 {
  61
  62 /*! \libinternal \brief Unordered key to value mapping
  63  *
  64  * Efficiently manages mapping from integer keys to values.
  65  * Note that this basically implements a subset of the functionality of
  66  * std::unordered_map, but is an order of magnitude faster.
  67  */
  68 template<class T>
  69 class HashedMap
  70 {
  71 private:
  72     /*! \libinternal \brief Structure for the key/value hash table */
  73     struct hashEntry
  74     {
  75         int key = -1;  /**< The key */
  76         T   value;     /**< The value(s) */
  77         int next = -1; /**< Index in the list of the next element with the same hash, -1 if none */
  78     };
  79
  80     /*! \brief The table size is set to at least this factor time the nr of keys */
  81     static constexpr float c_relTableSizeSetMin = 1.5;
  82     /*! \brief Threshold for increasing the table size */
  83     static constexpr float c_relTableSizeThresholdMin = 1.3;
  84     /*! \brief Threshold for decreasing the table size */
  85     static constexpr float c_relTableSizeThresholdMax = 3.5;
  86
  87     /*! \brief Resizes the table
  88      *
  89      * \param[in] numElementsEstimate  An estimate of the number of elements that will be stored
  90      */
  91     void resize(int numElementsEstimate)
  92     {
  93         GMX_RELEASE_ASSERT(numElements_ == 0, "Table needs to be empty for resize");
  94
  95         /* The fraction of table entries with 0   size lists is e^-f.
  96          * The fraction of table entries with >=1 size lists is 1 - e^-f
  97          * where f is: the #elements / tableSize
  98          * The fraction of elements not in the direct list is: 1 - (1 - e^-f)/f.
  99          * Thus the optimal table size is roughly double #elements.
 100          */
 101         /* Make the hash table a power of 2 and at least 1.5 * #elements */
 102         int tableSize = 64;
 103         while (tableSize <= INT_MAX / 2
 104                && static_cast<float>(numElementsEstimate) * c_relTableSizeSetMin > tableSize)
 105         {
 106             tableSize *= 2;
 107         }
 108         table_.resize(tableSize);
 109
 110         /* Table size is a power of 2, so a binary mask gives the hash */
 111         bitMask_                        = tableSize - 1;
 112         startIndexForSpaceForListEntry_ = tableSize;
 113     }
 114
 115 public:
 116     /*! \brief Constructor
 117      *
 118      * \param[in] numElementsEstimate  An estimate of the number of elements that will be stored, used for optimizing initial performance
 119      *
 120      * Note that the estimate of the number of elements is only relevant
 121      * for the performance up until the first call to clear(), after which
 122      * table size is optimized based on the actual number of elements.
 123      */
 124     HashedMap(int numElementsEstimate) { resize(numElementsEstimate); }
 125
 126     /*! \brief Returns the number of elements */
 127     int size() const { return numElements_; }
 128
 129     /*! \brief Returns the number of buckets, i.e. the number of possible hashes */
 130     int bucket_count() const { return bitMask_ + 1; }
 131
 132 private:
 133     /*! \brief Inserts or assigns a key and value
 134      *
 135      * \tparam    allowAssign  Sets whether assignment of a key that is present is allowed
 136      * \param[in] key          The key for the entry
 137      * \param[in] value        The value for the entry
 138      * \throws InvalidInputError from a debug build when attempting to insert a duplicate key with \p allowAssign=true
 139      */
 140     // cppcheck-suppress unusedPrivateFunction
 141     template<bool allowAssign>
 142     void insert_assign(int key, const T& value)
 143     {
 144         size_t ind = (key & bitMask_);
 145
 146         if (table_[ind].key >= 0)
 147         {
 148             /* Loop over the entries for this hash.
 149              * If we find the matching key, return the value.
 150              */
 151             int ind_prev = ind;
 152             if (table_[ind_prev].key == key)
 153             {
 154                 if (allowAssign)
 155                 {
 156                     table_[ind].value = value;
 157                     return;
 158                 }
 159                 else
 160                 {
 161 // Note: This is performance critical, so we only throw in debug mode
 162 #ifndef NDEBUG
 163                     GMX_THROW(InvalidInputError("Attempt to insert duplicate key"));
 164 #endif
 165                 }
 166             }
 167             while (table_[ind_prev].next >= 0)
 168             {
 169                 ind_prev = table_[ind_prev].next;
 170                 if (table_[ind_prev].key == key)
 171                 {
 172                     if (allowAssign)
 173                     {
 174                         table_[ind_prev].value = value;
 175                         return;
 176                     }
 177                     else
 178                     {
 179 #ifndef NDEBUG
 180                         GMX_THROW(InvalidInputError("Attempt to insert duplicate key"));
 181 #endif
 182                     }
 183                 }
 184             }
 185             /* Search for space in table_ */
 186             ind = startIndexForSpaceForListEntry_;
 187             while (ind < table_.size() && table_[ind].key >= 0)
 188             {
 189                 ind++;
 190             }
 191             /* If we are at the end of the list we need to increase the size */
 192             if (ind == table_.size())
 193             {
 194                 table_.resize(table_.size() + 1);
 195             }
 196             table_[ind_prev].next = ind;
 197
 198             startIndexForSpaceForListEntry_ = ind + 1;
 199         }
 200
 201         table_[ind].key   = key;
 202         table_[ind].value = value;
 203
 204         numElements_ += 1;
 205     }
 206
 207 public:
 208     /*! \brief Inserts entry, key should not already be present
 209      *
 210      * \param[in] key    The key for the entry
 211      * \param[in] value  The value for the entry
 212      * \throws InvalidInputError from a debug build when attempting to inser         */
 213     void insert(int key, const T& value) { insert_assign<false>(key, value); }
 214
 215     /*! \brief Inserts an entry when the key is not present, otherwise sets the value
 216      *
 217      * \param[in] key    The key for the entry
 218      * \param[in] value  The value for the entry
 219      */
 220     void insert_or_assign(int key, const T& value) { insert_assign<true>(key, value); }
 221
 222     /*! \brief Delete the entry for key \p key, when present
 223      *
 224      * \param[in] key  The key
 225      */
 226     void erase(int key)
 227     {
 228         int ind_prev = -1;
 229         int ind      = (key & bitMask_);
 230         do
 231         {
 232             if (table_[ind].key == key)
 233             {
 234                 if (ind_prev >= 0)
 235                 {
 236                     table_[ind_prev].next = table_[ind].next;
 237
 238                     /* This index is a linked entry, so we free an entry.
 239                      * Check if we are creating the first empty space.
 240                      */
 241                     if (ind < startIndexForSpaceForListEntry_)
 242                     {
 243                         startIndexForSpaceForListEntry_ = ind;
 244                     }
 245                 }
 246                 table_[ind].key  = -1;
 247                 table_[ind].next = -1;
 248
 249                 numElements_ -= 1;
 250
 251                 return;
 252             }
 253             ind_prev = ind;
 254             ind      = table_[ind].next;
 255         } while (ind >= 0);
 256     }
 257
 258     /*! \brief Returns a pointer to the value for the given key or nullptr when not present
 259      *
 260      * \param[in] key  The key
 261      * \return a pointer to value for the given key or nullptr when not present
 262      */
 263     T* find(int key) { return const_cast<T*>(gmx::compat::as_const(*this).find(key)); }
 264
 265     /*! \brief Returns a pointer to the value for the given key or nullptr when not present
 266      *
 267      * \param[in] key  The key
 268      * \return a pointer to value for the given key or nullptr when not present
 269      */
 270     const T* find(int key) const
 271     {
 272         int ind = (key & bitMask_);
 273         do
 274         {
 275             if (table_[ind].key == key)
 276             {
 277                 return &table_[ind].value;
 278             }
 279             ind = table_[ind].next;
 280         } while (ind >= 0);
 281
 282         return nullptr;
 283     }
 284
 285     /*! \brief Clear all the entries in the list
 286      *
 287      * Also optimizes the size of the table based on the current
 288      * number of elements stored.
 289      */
 290     void clear()
 291     {
 292         const int oldNumElements = numElements_;
 293
 294         for (hashEntry& entry : table_)
 295         {
 296             entry.key  = -1;
 297             entry.next = -1;
 298         }
 299         startIndexForSpaceForListEntry_ = bucket_count();
 300         numElements_                    = 0;
 301
 302         /* Resize the hash table when the occupation is far from optimal.
 303          * Do not resize with 0 elements to avoid minimal size when clear()
 304          * is called twice in a row.
 305          */
 306         if (oldNumElements > 0
 307             && (oldNumElements * c_relTableSizeThresholdMax < bucket_count()
 308                 || oldNumElements * c_relTableSizeThresholdMin > bucket_count()))
 309         {
 310             resize(oldNumElements);
 311         }
 312     }
 313
 314 private:
 315     /*! \brief The hash table list */
 316     std::vector<hashEntry> table_;
 317     /*! \brief The bit mask for computing the hash of a key */
 318     int bitMask_ = 0;
 319     /*! \brief Index in table_ at which to start looking for empty space for a new linked list entry */
 320     int startIndexForSpaceForListEntry_ = 0;
 321     /*! \brief The number of elements currently stored in the table */
 322     int numElements_ = 0;
 323 };
 324
 325 } // namespace gmx
 326
 327 #endif