Утечка памяти в C ++ при выполнении операций сдвига в цикле - PullRequest
Новая
       7

Утечка памяти в C ++ при выполнении операций сдвига в цикле

0 голосов
/ 08 сентября 2018

Мне удалось свести проблему к следующему коду, который использует почти 500 МБ памяти при запуске на моем ноутбуке, что в свою очередь вызывает std :: bad_alloc в полной программе. В чем здесь проблема? Насколько я вижу, неупорядоченная карта использует только что-то вроде (32 + 32) *4096* 4096 бит = 134,2 МБ, что даже близко не соответствует тому, что использует программа. 

#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;
}

РЕДАКТИРОВАТЬ: я знаю, что некоторые сдвиги битов могут вызвать неопределенное поведение, но я на 99% уверен, что проблема не в этом.

РЕДАКТИРОВАТЬ2: Что мне нужно, так это подсчет количества х в данном наборе, которые некоторые функции сопоставляют с каждым у во втором наборе (размером 4096 * 4096). Будет ли лучше хранить эти числа в массиве? Т.е. у меня есть функция от f: A до B, и мне нужно знать размер множества {x в A: f (x) = y} для каждого y в B. В этом случае A и B оба являются набором неотрицательные целые числа менее 2 ^ 12 = 4096. (В идеале я хотел бы расширить это до 2 ^ 32).

1 Ответ

0 голосов
/ 08 сентября 2018

... который использует почти 500 МБ памяти ... В чем здесь проблема?

По сути, нет проблем с использованием памяти, которую вы наблюдаете. std::unordered_map создан для быстрой работы с большим количеством элементов. Таким образом, память не является главным приоритетом. Например, чтобы оптимизировать изменение размера, оно часто выделяет при создании некоторые заранее вычисленные цепочки хешей . Кроме того, ваша мера количества элементов, умноженного на размер элемента, не учитывает фактический объем памяти каждого узла в этой карте с точки зрения структуры данных, который должен по крайней мере включать несколько указателей на смежные элементы. в списке своего ведра .

Сказав это, не ясно, вам даже нужно использовать std::unorderd_map в этом сценарии. Вместо этого, учитывая сопоставление, ваш пробный магазин определен как

{x в A: f (x) = y} для каждого y в B

у вас может быть один массив фиксированного размера (используйте для этого std::array), который будет просто содержать для каждого индекса i, представляющего элемент в наборе B , число элементов из набора A , который соответствует критериям.

...