8

I am working with some very large std::unordered_maps (hundreds of millions of entries) and need to save and load them to and from a file. The way I am currently doing this is by iterating through the map and reading/writing each key and value pair one at a time:

std::unordered_map<unsigned long long int, char> map;

void save(){
    std::unordered_map<unsigned long long int, char>::iterator iter;
    FILE *f = fopen("map", "wb");
    for(iter=map.begin(); iter!=map.end(); iter++){
        fwrite(&(iter->first), 8, 1, f);
        fwrite(&(iter->second), 1, 1, f);
    }
    fclose(f);
}

void load(){
    FILE *f = fopen("map", "rb");
    unsigned long long int key;
    char val;
    while(fread(&key, 8, 1, f)){
        fread(&val, 1, 1, f);
        map[key] = val;
    }
    fclose(f);
}

But with around 624 million entries, reading the map from a file took 9 minutes. Writing to a file was faster but still took several minutes. Is there a faster way to do this?

14
  • You may provide your own Allocator implementation to optimize memory management for the creation of new map entries.
    – user9212993
    Commented Jan 23, 2018 at 19:29
  • 4
    Your poor std::map is having to rebalance its red-black tree on every new entry it receives - you're reading all values in sorted order so it has more-or-less worst performance possible. Commented Jan 23, 2018 at 19:36
  • 1
    Not related to your question, but what is the highest key used? Or: how sparse is your map? Commented Jan 23, 2018 at 19:38
  • 1
    Will you be changing the map after reading it in with load? Commented Jan 23, 2018 at 19:39
  • 1
    OK, so no way to represent the "map" by an ordinary char[624000000]... Commented Jan 23, 2018 at 20:09

5 Answers 5

12

C++ unordered_map implementations must all use chaining. There are a variety of really good reasons why you might want to do this for a general purpose hash table, which are discussed here.

This has enormous implications for performance. Most importantly, it means that the entries of the hash table are likely to be scattered throughout memory in a way which makes accessing each one an order of magnitude (or so) less efficient that would be the case if they could somehow be accessed serially.

Fortunately, you can build hash tables that, when nearly full, give near-sequential access to adjacent elements. This is done using open addressing.

Since your hash table is not general purpose, you could try this.

Below, I've built a simple hash table container with open addressing and linear probing. It assumes a few things:

  1. Your keys are already somehow randomly distributed. This obviates the need for a hash function (though decent hash functions are fairly simple to build, even if great hash functions are difficult).

  2. You only ever add elements to the hash table, you do not delete them. If this were not the case you'd need to change the used vector into something that could hold three states: USED, UNUSED, and TOMBSTONE where TOMBSTONE is the stated of a deleted element and used to continue linear search probe or halt a linear insert probe.

  3. That you know the size of your hash table ahead of time, so you don't need to resize/rehash it.

  4. That you don't need to traverse your elements in any particular order.

Of course, there are probably all kinds of excellent implementations of open addressing hash tables online which solve many of the above issues. However, the simplicity of my table allows me to convey the important point.

The important point is this: my design allows all the hash table's information to be stored in three vectors. That is: the memory is contiguous.

Contiguous memory is fast to allocate, fast to read from, and fast to write to. The effect of this is profound.

Using the same test setup as my previous answer, I get the following times:

Save. Save time = 82.9345 ms
Load. Load time = 115.111 ms

This is a 95% decrease in save time (22x faster) and a 98% decrease in load time (62x faster).

Code:

#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

const int TEST_TABLE_SIZE = 10000000;



template<class K, class V>
class SimpleHash {
 public:
  int usedslots = 0;

  std::vector<K> keys;
  std::vector<V> vals;
  std::vector<uint8_t> used;

  //size0 should be a prime and about 30% larger than the maximum number needed
  SimpleHash(int size0){
    vals.resize(size0);
    keys.resize(size0);
    used.resize(size0/8+1,0);
  }

  //If the key values are already uniformly distributed, using a hash gains us
  //nothing
  uint64_t hash(const K key){
    return key;
  }

  bool isUsed(const uint64_t loc){
    const auto used_loc = loc/8;
    const auto used_bit = 1<<(loc%8);
    return used[used_loc]&used_bit;    
  }

  void setUsed(const uint64_t loc){
    const auto used_loc = loc/8;
    const auto used_bit = 1<<(loc%8);
    used[used_loc] |= used_bit;
  }

  void insert(const K key, const V val){
    uint64_t loc = hash(key)%keys.size();

    //Use linear probing. Can create infinite loops if table too full.
    while(isUsed(loc)){ loc = (loc+1)%keys.size(); }

    setUsed(loc);
    keys[loc] = key;
    vals[loc] = val;
  }

  V& get(const K key) {
    uint64_t loc = hash(key)%keys.size();

    while(true){
      if(!isUsed(loc))
        throw std::runtime_error("Item not present!");
      if(keys[loc]==key)
        return vals[loc];

      loc = (loc+1)%keys.size();
    }
  }

  uint64_t usedSize() const {
    return usedslots;
  }

  uint64_t size() const {
    return keys.size();
  }
};

typedef SimpleHash<uint64_t, char> table_t;

void SaveSimpleHash(const table_t &map){
  std::cout<<"Save. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "wb");
  uint64_t size = map.size();
  fwrite(&size, 8, 1, f);
  fwrite(map.keys.data(), 8, size, f);
  fwrite(map.vals.data(), 1, size, f);
  fwrite(map.used.data(), 1, size/8+1, f);
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Save time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

table_t LoadSimpleHash(){
  std::cout<<"Load. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "rb");

  uint64_t size;
  fread(&size, 8, 1, f);

  table_t map(size);
  fread(map.keys.data(), 8, size, f);
  fread(map.vals.data(), 1, size, f);
  fread(map.used.data(), 1, size/8+1, f);
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Load time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;

  return map;
}

int main(){
  //Perfectly horrendous way of seeding a PRNG, but we'll do it here for brevity
  auto generator = std::mt19937(12345); //Combination of my luggage
  //Generate values within the specified closed intervals
  auto key_rand  = std::bind(std::uniform_int_distribution<uint64_t>(0,std::numeric_limits<uint64_t>::max()), generator);
  auto val_rand  = std::bind(std::uniform_int_distribution<int>(std::numeric_limits<char>::lowest(),std::numeric_limits<char>::max()), generator);

  table_t map(1.3*TEST_TABLE_SIZE);
  std::cout<<"Created table of size "<<map.size()<<std::endl;

  std::cout<<"Generating test data..."<<std::endl;
  for(int i=0;i<TEST_TABLE_SIZE;i++)
    map.insert(key_rand(),(char)val_rand()); //Low chance of collisions, so we get quite close to the desired size

  map.insert(23,42);
  assert(map.get(23)==42);

  SaveSimpleHash(map);
  auto newmap = LoadSimpleHash();

  //Ensure that the load worked
  for(int i=0;i<map.keys.size();i++)
    assert(map.keys.at(i)==newmap.keys.at(i));
  for(int i=0;i<map.vals.size();i++)
    assert(map.vals.at(i)==newmap.vals.at(i));  
  for(int i=0;i<map.used.size();i++)
    assert(map.used.at(i)==newmap.used.at(i));    
}
2
  • 1
    +1 There's another advantage of having a pointer-free design like yours: If K and V are pointer-free as well, it is easy to put the necessary arrays in an mmap'ed file, or shared memory for that matter. Teaching this to std::vector means having to deal with the C++ allocator model though, which is a bit confusing, especially the propagation and equality stuff.
    – Arne Vogel
    Commented Jan 24, 2018 at 8:54
  • 1
    By pointer-free I mean that the allocated memory does not contain pointers. The top-level object obviously contains some pointers. The memory-mapped hash table would not be fully self-containing (or even transaction safe) just like that.
    – Arne Vogel
    Commented Jan 24, 2018 at 9:05
3

(Edit: I've added a new answer to this question which achieves a 95% decrease in wall-times.)

I made a Minimum Working Example that illustrates the problem you are trying to solve. This is something you should always do in your questions.

I then eliminated the unsigned long long int stuff and replaced it with uint64_t from the cstdint library. This ensures that we are operating on the same data size, since unsigned long long int can mean almost anything depending on what computer/compiler you use.

The resulting MWE looks like:

#include <chrono>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iostream>
#include <random>
#include <unordered_map>
#include <vector>

typedef std::unordered_map<uint64_t, char> table_t;
const int TEST_TABLE_SIZE = 10000000;

void Save(const table_t &map){
  std::cout<<"Save. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "wb");
  for(auto iter=map.begin(); iter!=map.end(); iter++){
      fwrite(&(iter->first), 8, 1, f);
      fwrite(&(iter->second), 1, 1, f);
  }
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Save time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

//Take advantage of the limited range of values to save time
void SaveLookup(const table_t &map){
  std::cout<<"SaveLookup. ";
  const auto start = std::chrono::steady_clock::now();

  //Create a lookup table
  std::vector< std::deque<uint64_t> > lookup(256);
  for(auto &kv: map)
    lookup.at(kv.second+128).emplace_back(kv.first);

  //Save lookup table header
  FILE *f = fopen("/z/map", "wb");
  for(const auto &row: lookup){
    const uint32_t rowsize = row.size();
    fwrite(&rowsize, 4, 1, f);
  }

  //Save values
  for(const auto &row: lookup)
  for(const auto &val: row)
    fwrite(&val, 8, 1, f);

  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Save time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

//Take advantage of the limited range of values and contiguous memory to
//save time
void SaveLookupVector(const table_t &map){
  std::cout<<"SaveLookupVector. ";
  const auto start = std::chrono::steady_clock::now();

  //Create a lookup table
  std::vector< std::vector<uint64_t> > lookup(256);
  for(auto &kv: map)
    lookup.at(kv.second+128).emplace_back(kv.first);

  //Save lookup table header
  FILE *f = fopen("/z/map", "wb");
  for(const auto &row: lookup){
    const uint32_t rowsize = row.size();
    fwrite(&rowsize, 4, 1, f);
  }

  //Save values
  for(const auto &row: lookup)
    fwrite(row.data(), 8, row.size(), f);

  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Save time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

void Load(table_t &map){
  std::cout<<"Load. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "rb");
  uint64_t key;
  char val;
  while(fread(&key, 8, 1, f)){
      fread(&val, 1, 1, f);
      map[key] = val;
  }
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Load time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

void Load2(table_t &map){
  std::cout<<"Load with Reserve. ";
  map.reserve(TEST_TABLE_SIZE+TEST_TABLE_SIZE/8);
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "rb");
  uint64_t key;
  char val;
  while(fread(&key, 8, 1, f)){
      fread(&val, 1, 1, f);
      map[key] = val;
  }
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Load time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

//Take advantage of the limited range of values to save time
void LoadLookup(table_t &map){
  std::cout<<"LoadLookup. ";
  map.reserve(TEST_TABLE_SIZE+TEST_TABLE_SIZE/8);
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "rb");

  //Read the header
  std::vector<uint32_t> inpsizes(256);
  for(int i=0;i<256;i++)
    fread(&inpsizes[i], 4, 1, f);

  uint64_t key;
  for(int i=0;i<256;i++){
    const char val = i-128;    
    for(int v=0;v<inpsizes.at(i);v++){
      fread(&key, 8, 1, f);
      map[key] = val;
    }
  }

  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Load time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

//Take advantage of the limited range of values and contiguous memory to save time
void LoadLookupVector(table_t &map){
  std::cout<<"LoadLookupVector. ";
  map.reserve(TEST_TABLE_SIZE+TEST_TABLE_SIZE/8);
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "rb");

  //Read the header
  std::vector<uint32_t> inpsizes(256);
  for(int i=0;i<256;i++)
    fread(&inpsizes[i], 4, 1, f);

  for(int i=0;i<256;i++){
    const char val = i-128;    
    std::vector<uint64_t> keys(inpsizes[i]);
    fread(keys.data(), 8, inpsizes[i], f);
    for(const auto &key: keys)
      map[key] = val;
  }

  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Load time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

int main(){
  //Perfectly horrendous way of seeding a PRNG, but we'll do it here for brevity
  auto generator = std::mt19937(12345); //Combination of my luggage
  //Generate values within the specified closed intervals
  auto key_rand  = std::bind(std::uniform_int_distribution<uint64_t>(0,std::numeric_limits<uint64_t>::max()), generator);
  auto val_rand  = std::bind(std::uniform_int_distribution<int>(std::numeric_limits<char>::lowest(),std::numeric_limits<char>::max()), generator);

  std::cout<<"Generating test data..."<<std::endl;
  //Generate a test table
  table_t map;
  for(int i=0;i<TEST_TABLE_SIZE;i++)
    map[key_rand()] = (char)val_rand(); //Low chance of collisions, so we get quite close to the desired size

  Save(map);

  { table_t map2; Load (map2); }
  { table_t map2; Load2(map2); }

  SaveLookup(map);
  SaveLookupVector(map);

  { table_t map2; LoadLookup      (map2); }
  { table_t map2; LoadLookupVector(map2); }
}

On the test data set I use, this gives me a write time of 1982ms and a read time (using your original code) of 7467ms. It seemed as though the read time is the biggest bottleneck, so I created a new function Load2 which reserves sufficient space for the unordered_map prior to reading. This dropped the read time to 4700ms (a 37% savings).

Edit 1

Now, I note that the values of your unordered_map can only take 255 distinct values. Thus, I can easily convert the unordered_map into a kind of lookup table in RAM. That is, rather than having:

123123 1
234234 0
345345 1
237872 1

I can rearrange the data to look like:

0 234234
1 123123 345345 237872

What's the advantage of this? It means that I no longer have to write the value to disk. That saves 1 byte per table entry. Since each table entry consists of 8 bytes for the key and 1 byte for the value, this should give me an 11% savings in both read and write time minus the cost of rearranging the memory (which I expect to be low, because RAM).

Finally, once I've done the above rearrangement, if I have a lot of spare RAM on the machine, I can pack everything into a vector and read/write the contiguous data to disk.

Doing all this gives the following times:

Save. Save time = 1836.52 ms
Load. Load time = 7114.93 ms
Load with Reserve. Load time = 4277.58 ms
SaveLookup. Save time = 1688.73 ms
SaveLookupVector. Save time = 1394.95 ms
LoadLookup. Load time = 3927.3 ms
LoadLookupVector. Load time = 3739.37 ms

Note that the transition from Save to SaveLookup gives an 8% speed-up and the transition from Load with Reserve to LoadLookup gives an 8% speed-up as well. This is right in line our theory!

Using contiguous memory as well gives a total of a 24% speed-up over your original save time and a total of a 47% speed-up over your original load time.

0
1

Since your data seems to be static and given the amount of items, I would certainly consider using an own structure in a binary file and then use memory mapping on that file.

Opening would be instant (just mmap the file).

If you write the values in sorted order, you can use binary search on the mapped data.

If that is not good enough, you could split your data in buckets and store a list with offsets at the beginning of the file - or maybe even use some hash key.

If your keys are all unique and somewhat contiguous, you could even get a smaller file by only storing the char values in file position [key] (and use a special value for null values). Of course that wouldn't work for the full uint64 range, but depending on the data they could be grouped together in buckets containing an offset.

Using mmap this way would also use a lot less memory.


For faster access you could create your own hash map on disk (still with 'instant load').

For example, say you have 1 million hashes (in your case there would be lot more), you could write 1 million uint64 filepos values at the beginning of the file (the hash value would be the position of the uint64 containing the filepos). Each location would point to a block with one ore more key/value pairs, and each of those blocks would start with a count.

If the blocks are aligned on 2 or 4 bytes, a uint32 filepos could be used instead (multiply pos with 2 or 4).

Since the data is static you don't have to worry about possible insertions or deletions, which makes it rather easy to implement.

This has the advantage that you still can mmap the whole file and all the key/value pairs with the same hash are close together which brings them in the L1 cache (as compared to say linked lists)

3
  • Binary search is too slow for what I'm doing. I need to look up values in the map potentially tens of billions of times, if not more
    – Ben
    Commented Jan 23, 2018 at 22:21
  • @Ben In that case you could create your own 'hash map' on disk (see my updated anwer). Several minutes to load the data is really long, with mmap it's instant and uses less memory.
    – Danny_ds
    Commented Jan 23, 2018 at 22:59
  • You are completely right! and I believe it is the best answer. To use mmap would be the way as it would avoid the rehashing, which is, in the last instance, what makes to take a long time when reading from the file (the reading causes normal insertion and consequently rehashes)
    – lrleon
    Commented Jan 5, 2021 at 0:02
0

I would assume you need the map to write the values ordered in the file. It would be better to load only once the values in a container, possibly a std::deque would be better since the amount is large, and use std::sort once, and then iterate through std::deque to write values. You would gain cache performance and also the run time complexity for std::sort is N*Log(N), which would be better than balancing your map ~624 million times or paying cache misses in an unordered map.

6
  • 1
    Order of the entries isn't really important, I'm more concerned with the performance for std::unordered_map actually. I'll add that to my original post.
    – Ben
    Commented Jan 23, 2018 at 19:50
  • What's the reason why you need a map/unordered_map then?
    – AdvSphere
    Commented Jan 23, 2018 at 19:52
  • why std::deque and not std::vector ?
    – Slava
    Commented Jan 23, 2018 at 19:54
  • since the memory is too large, a vector must be contiguous, where a std::queue is continuos by blocks (can have gaps in between).
    – AdvSphere
    Commented Jan 23, 2018 at 19:56
  • It seems what you need to have is O(1) access on the data you write to. Possibly you can just index over and std::queue, O(1), if the keys you'll be using are continuous, and use std::sort as I mentioned above.
    – AdvSphere
    Commented Jan 23, 2018 at 20:01
0

Perhaps a prefix-ordered traversal during save would help to reduce the amount of internal reordering during load?

Of course, you don't have visibility of the internal structure of the STL map containers, so the best you could do would be to simulate that by binary-chopping the iterator as if it was linear. Given that you know the total N nodes, save the node N/2, then N/4, N*3/4, and so-on.

This can be done algorithmically by visiting every odd N/(2^p) node in each pass p: N/2, N*1/4, N*3/4, N*1/8, N*3/8, N*5/8, N*7/8, etc, though you need to ensure that the series maintains step sizes such that N*4/8 = N/2, but without resorting to step sizes of 2^(P-p), and that in the last pass you visit every remaining node. You may find it advantageous to pre-calculate the highest pass number (~log2(N)), and the float value of S=N/(2^P) such that 0.5 < S <= 1.0, and then scale that back up for each p.

But as others have said, you need to profile it first to see if this is your issue, and profile again to see if this approach helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.