2

I managed to reduce the problem to the following code, which uses almost 500MB of memory when it runs on my laptop - which in turn causes a std::bad_alloc in the full program. What is the problem here? As far as I can see, the unordered map only uses something like (32+32)*4096*4096 bits = 134.2MB, which is not even close to what the program uses.

#include<iostream>
#include<unordered_map>

using namespace std;

int main()
{
    unordered_map<int,int> a;
    long long z = 0;

    for (int x = 0; x < 4096; x++)
    {
        for (int y = 0; y < 4096; y++)
        {
            z = 0;

            for (int j = 0; j < 4; j++)
            {
                    z ^= ((x>>(3*j))%8)<<(3*j);
                    z ^= ((y>>(3*j))%8)<<(3*j + 12);
            }

        a[z]++;
        }
    }
    return 0;
}

EDIT: I'm aware that some of the bit shifting here can cause undefined behaviour, but I'm 99% sure that's not what's the problem.

EDIT2: What I need is essentially to count the number of x in a given set that some function maps to each y in a second set (of size 4096*4096). Would it be better to perhaps store these numbers in an array? I.e I have a function f: A to B, and I need to know the size of the set {x in A : f(x) = y} for each y in B. In this case A and B are both the set of non-negative integers less than 2^12=4096. (Ideally I would like to extend this to 2^32).

mss
  • 195
  • 1
  • 8
  • 2
    Besides the two `int`s of payload, each node likely carries some pointers to link them together. Plus, they are allocated on the heap, which has additional overhead. – Igor Tandetnik Sep 08 '18 at 13:07
  • Ah, I see. But how can I rewrite this to use less memory? What I need is essentially to count the number of x in a given set that maps to each y in a second set (of size 4096*4096). Would it be better to perhaps store these numbers in an array? – mss Sep 08 '18 at 13:15
  • "Would it be better to perhaps store these numbers in an array?": yes, as `z`'s max value is bounded in a way, that it will consume much less memory than the map. Btw, why does this matter? This problem seems to be solvable with a paper&pencil method. – geza Sep 08 '18 at 13:26
  • @SkepticalEmpiricist I have a function f: A to B, and I need to know the size of the set {x in A : f(x) = y} for each y in B. – mss Sep 08 '18 at 13:29
  • @geza This is just a minimal example - What I'm really trying to understand is how zero differences propagate through a certain encryption algorithm. – mss Sep 08 '18 at 13:39
  • 1
    Your unordered map stores `int`s. That's it. What an unordered map does for you doesn't come for free. The unordered map has to keep track of each element in an unordered map, in some kind of fashion. A typical implementation of an unordered is a hash table of linked list (for elements that end up hashing to the same value). As such, each value that goes into the map incurs some overhead. Probably a few pointers. But that's already going to be 3-4 times the size of a plain `int`. And that's why your map takes 4 times as much memory as the raw data. – Sam Varshavchik Sep 08 '18 at 13:41
  • @Stensrud: your program does something different, doesn't it? It counts how many times output values occur for `f(x,y)`, where x and y has 12 bits. – geza Sep 08 '18 at 13:45
  • @geza Well, I omitted the function f entirely from the example above, so the remaining code is basically just setting a[w] = 1 for each w in [0,2^24]. There is no real difference between inputs of the form (x,y) where x,y<2^12 and inputs of the form w, where w<2^24... – mss Sep 08 '18 at 13:58
  • You should have given an example then, for which we can understand the problem fully. Anyways, as you've accepted the answer, it doesn't matter anymore :) – geza Sep 08 '18 at 14:07

1 Answers1

2

... which uses almost 500MB of memory ... What is the problem here?

There isn't really a problem, per se, regarding the memory usage you are observing. std::unordered_map is built to run fast for large number of elements. As such, memory isn't a top priority. For example, in order to optimize for resizing, it often allocates upon creation for some pre-calculated hash chains. Also, your measure of the the count of elements multiplied by the element's size is not taking into account the actual memory-footprint, data structure-wise, of each node in this map -- which should at least involve a few pointers to adjacent elements in the list of its bucket.

Having said that, it isn't clear you even need to use std::unorderd_map in this scenario. Instead, given the mapping your trying store is defined as

{x in A : f(x) = y} for each y in B

you could have one fixed-sized array (use std::array for that) that would simply hold for each index i, representing the element in set B, the number of elements from set A that fills the criteria.

Geezer
  • 5,600
  • 18
  • 31
  • That makes sense! The original program is a brute-force search, and therefore speed was important - but I suppose I have to balance speed/memory usage. Any idea of how I can do what I want and use less memory? (See question edit). – mss Sep 08 '18 at 13:27
  • @Stensrud Added the edit, hoping I fully understood your scenario. If this is not the case then let me know – Geezer Sep 08 '18 at 13:41
  • Thank you, that solves the problem. The size of the image space B was 2^32 in the original problem we were trying to solve, and storing 2^32 integers of 32-bit size was a bit too much for my laptop. – mss Sep 08 '18 at 13:45
  • @Stensrud Glad to help. So 2^32 4 byte integers is about 16GB, shouldn't be a real problem for a decent scientific-computing purposed desktop or even laptop these days. Obviously you need the address space so you must build in in 64 bit. – Geezer Sep 08 '18 at 13:48
  • Yup, that sounds about right. My laptop's only got about 7.88GB of usable RAM though, and I think storing things elsewhere will be too slow? – mss Sep 08 '18 at 13:52
  • @Stensrud Writing to disk would have its abvious overhead, of course – Geezer Sep 08 '18 at 13:55