src/gromacs/domdec/hash.h

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2012,2014,2015,2017,2018, 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 /*! \internal \file
  36  * \brief
  37  * This file declares functions for a simple hash map used by domain
  38  * decomposition.
  39  *
  40  * It is limited to integer keys and integer values. The purpose is highest
  41  * efficiency and lowest memory usage possible.  Thus the code is in a header,
  42  * so it can be inlined where it is used.
  43  *
  44  * Note that we could use std::unordered_map for this functionality,
  45  * but that is an order of magnitude slower and impacts the DD performance.
  46  *
  47  * \author Berk Hess <hess@kth.se>
  48  * \ingroup module_domdec
  49  */
  50
  51 #ifndef GMX_DOMDEC_HASH_H
  52 #define GMX_DOMDEC_HASH_H
  53
  54 #include <cstdio>
  55
  56 //! Forward declation
  57 static void gmx_hash_resize(gmx_hash_t * /*hash*/, int /*nkey_used_estimate*/);
  58
  59 /*! \internal \brief Hashing key-generation helper struct */
  60 struct gmx_hash_e_t
  61 {
  62     public:
  63         //! The (unique) key for storing/looking up a value
  64         int  key  = -1;
  65         //! The value belonging to key
  66         int  val  = -1;
  67         //! Index for the next element in the array with indentical value key%mod, -1 if there is no next element
  68         int  next = -1;
  69 };
  70
  71 /*! \internal \brief Hashing helper struct */
  72 struct gmx_hash_t
  73 {
  74     public:
  75         //! Constructor
  76         gmx_hash_t(int numKeysUsedEstimate) :
  77             nkey(0)
  78         {
  79             gmx_hash_resize(this, numKeysUsedEstimate);
  80         }
  81
  82         //! Keys are looked up by first checking array index key%mod in hash
  83         int                       mod;
  84         //! mask=log2(mod), used to replace a % by the faster & operation
  85         int                       mask;
  86         //! The actual array containing the keys, values and next indices
  87         std::vector<gmx_hash_e_t> hash;
  88         //! The number of keys stored
  89         int                       nkey;
  90         //! Index in hash where we should start searching for space to store a new key/value
  91         int                       start_space_search;
  92 };
  93
  94 //! Clear all the entries in the hash table.
  95 static void gmx_hash_clear(gmx_hash_t *hash)
  96 {
  97     for (gmx_hash_e_t &entry : hash->hash)
  98     {
  99         /* Note: clearing entry.val is not needed */
 100         entry.key  = -1;
 101         entry.next = -1;
 102     }
 103     hash->start_space_search = hash->mod;
 104
 105     hash->nkey = 0;
 106 }
 107
 108 //! Reallocate hash table data structures.
 109 static void gmx_hash_resize(gmx_hash_t *hash, int nkey_used_estimate)
 110 {
 111     GMX_RELEASE_ASSERT(hash->nkey == 0, "Table needs to be empty for resize");
 112
 113     /* Memory requirements:
 114      * nkey_used_est*(2+1-2(1-e^-1/2))*3 ints
 115      * where nkey_used_est is the local number of keys used.
 116      *
 117      * Make the direct list twice as long as the number of local keys.
 118      * The fraction of entries in the list with:
 119      * 0   size lists: e^-f
 120      * >=1 size lists: 1 - e^-f
 121      * where f is: the #keys / mod
 122      * The fraction of keys not in the direct list is: 1-1/f(1-e^-f).
 123      * The optimal table size is roughly double the number of keys.
 124      */
 125     /* Make the hash table a power of 2 and at least double the number of keys */
 126     hash->mod = 4;
 127     while (2*nkey_used_estimate > hash->mod)
 128     {
 129         hash->mod *= 2;
 130     }
 131     hash->mask   = hash->mod - 1;
 132     hash->hash.resize(hash->mod);
 133 }
 134
 135 /*! \brief Clear all the entries in the hash table.
 136  *
 137  * With the current number of keys check if the table size is still
 138  * good, if not optimize it with the current number of keys.
 139  */
 140 static inline void gmx_hash_clear_and_optimize(gmx_hash_t *hash)
 141 {
 142     gmx_hash_clear(hash);
 143
 144     /* Resize the hash table when the occupation is < 1/4 or > 2/3 */
 145     if (hash->nkey > 0 &&
 146         (4*hash->nkey < hash->mod || 3*hash->nkey > 2*hash->mod))
 147     {
 148         gmx_hash_resize(hash, hash->nkey);
 149     }
 150 }
 151
 152 //! Set the hash entry for key to value.
 153 static void gmx_hash_set(gmx_hash_t *hash, int key, int value)
 154 {
 155     unsigned int ind = (key & hash->mask);
 156
 157     if (hash->hash[ind].key >= 0)
 158     {
 159         /* Search the last entry in the linked list for this index */
 160         unsigned int ind_prev = ind;
 161         while (hash->hash[ind_prev].next >= 0)
 162         {
 163             ind_prev = hash->hash[ind_prev].next;
 164         }
 165         /* Search for space in the array */
 166         ind = hash->start_space_search;
 167         while (ind < hash->hash.size() && hash->hash[ind].key >= 0)
 168         {
 169             ind++;
 170         }
 171         /* If we are at the end of the list we need to increase the size */
 172         if (ind == hash->hash.size())
 173         {
 174             hash->hash.resize(hash->hash.size() + 1);
 175         }
 176         hash->hash[ind_prev].next = ind;
 177
 178         hash->start_space_search = ind + 1;
 179     }
 180     hash->hash[ind].key = key;
 181     hash->hash[ind].val = value;
 182
 183     hash->nkey++;
 184 }
 185
 186 //! Delete the hash entry for key.
 187 static inline void gmx_hash_del(gmx_hash_t *hash, int key)
 188 {
 189     int ind, ind_prev;
 190
 191     ind_prev = -1;
 192     ind      = key & hash->mask;
 193     do
 194     {
 195         if (hash->hash[ind].key == key)
 196         {
 197             if (ind_prev >= 0)
 198             {
 199                 hash->hash[ind_prev].next = hash->hash[ind].next;
 200
 201                 /* This index is a linked entry, so we free an entry.
 202                  * Check if we are creating the first empty space.
 203                  */
 204                 if (ind < hash->start_space_search)
 205                 {
 206                     hash->start_space_search = ind;
 207                 }
 208             }
 209             hash->hash[ind].key  = -1;
 210             hash->hash[ind].val  = -1;
 211             hash->hash[ind].next = -1;
 212
 213             hash->nkey--;
 214
 215             return;
 216         }
 217         ind_prev = ind;
 218         ind      = hash->hash[ind].next;
 219     }
 220     while (ind >= 0);
 221 }
 222
 223 //! Change the value for present hash entry for key.
 224 static inline void gmx_hash_change_value(gmx_hash_t *hash, int key, int value)
 225 {
 226     int ind = (key & hash->mask);
 227
 228     do
 229     {
 230         if (hash->hash[ind].key == key)
 231         {
 232             hash->hash[ind].val = value;
 233
 234             return;
 235         }
 236         ind = hash->hash[ind].next;
 237     }
 238     while (ind >= 0);
 239 }
 240
 241 //! Change the hash value if already set, otherwise set the hash value.
 242 static inline void gmx_hash_change_or_set(gmx_hash_t *hash, int key, int value)
 243 {
 244     int ind = (key & hash->mask);
 245
 246     do
 247     {
 248         if (hash->hash[ind].key == key)
 249         {
 250             hash->hash[ind].val = value;
 251
 252             return;
 253         }
 254         ind = hash->hash[ind].next;
 255     }
 256     while (ind >= 0);
 257
 258     gmx_hash_set(hash, key, value);
 259 }
 260
 261 //! Returns if the key is present, if the key is present *value is set.
 262 static inline gmx_bool gmx_hash_get(const gmx_hash_t *hash, int key, int *value)
 263 {
 264     int ind = (key & hash->mask);
 265
 266     do
 267     {
 268         if (hash->hash[ind].key == key)
 269         {
 270             *value = hash->hash[ind].val;
 271
 272             return TRUE;
 273         }
 274         ind = hash->hash[ind].next;
 275     }
 276     while (ind >= 0);
 277
 278     return FALSE;
 279 }
 280
 281 //! Returns the value or -1 if the key is not present.
 282 static int gmx_hash_get_minone(const gmx_hash_t *hash, int key)
 283 {
 284     int ind = (key & hash->mask);
 285
 286     do
 287     {
 288         if (hash->hash[ind].key == key)
 289         {
 290             return hash->hash[ind].val;
 291         }
 292         ind = hash->hash[ind].next;
 293     }
 294     while (ind >= 0);
 295
 296     return -1;
 297 }
 298
 299 #endif