Выделение большого блока памяти в C ++

Question

Я пытаюсь выделить большой блок памяти для 3D-матрицы в C ++ со значением с плавающей запятой. Его размеры 44100x2200x2. Это должно занять ровно 44100x2200x2x4 байта памяти, что составляет около 7,7 ГБ. Я компилирую свой код, используя g ++ на 64-битной машине x86 с Ubuntu. Когда я просматриваю процесс с помощью htop, я вижу, что использование памяти увеличивается до 32 ГБ и быстро уничтожается. Я сделал ошибку в подсчете памяти?

Это мой код:

#include <iostream>

using namespace std;
int main(int argc, char* argv[]) {
  int N = 22000;
  int M = 44100;
  float*** a = new float**[N];
  for (int m = 0; m<N; m+=1) {
    cout<<((float)m/(float)N)<<endl;
    a[m] = new float*[M - 1];
    for (int n = 0; n<M - 1; n+=1) {
      a[m][n] = new float[2];
    }
  }
}

РЕДАКТИРОВАТЬ: мой расчет был неправильным, и я выделил ближе к 38 ГБ. Я исправил код, чтобы выделить 15 ГБ.

#include <iostream>

using namespace std;
int main(int argc, char* argv[]) {
  unsigned long  N = 22000;
  unsigned long  M = 44100;
  unsigned long blk_dim = N*(M-1)*2;
  float* blk = new float[blk_dim];
  unsigned long b = (unsigned long) blk;

  float*** a = new float**[N];
  for (int m = 0; m<N; m+=1) {
    unsigned long offset1 = m*(M - 1)*2*sizeof(float);
    a[m] = new float*[M - 1];
    for (int n = 0; n<M - 1; n+=1) {
      unsigned long offset2 = n*2*sizeof(float);
      a[m][n] = (float*)(offset1 + offset2 + b);
    }
  }
}

Answer 1

Просто для того, чтобы завершить один уже полученный ответ, приведенный ниже пример в основном является расширением ответа, приведенного здесь на о том, как создать непрерывный двумерный массив , и иллюстрирует использование только 3 вызовов * 1003. *.

Преимущество заключается в том, что вы сохраняете синтаксис [][][], который вы обычно используете с тройными указателями (хотя я настоятельно рекомендую не писать код, использующий «3 звезды», как это, но у нас есть то, что у нас есть). Недостатком является то, что для указателей выделяется больше памяти с добавлением в единый пул памяти данных.

#include <iostream>
#include <exception>

template <typename T>
T*** create3DArray(unsigned pages, unsigned nrows, unsigned ncols, const T& val = T())
{
    T*** ptr = nullptr;  // allocate pointers to pages
    T** ptrMem = nullptr;
    T* pool = nullptr;
    try 
    {
        ptr = new T**[pages];  // allocate pointers to pages
        ptrMem = new T*[pages * nrows]; // allocate pointers to pool
        pool = new T[nrows*ncols*pages]{ val };  // allocate pool

        // Assign page pointers to point to the pages memory,
        // and pool pointers to point to each row the data pool
        for (unsigned i = 0; i < pages; ++i, ptrMem += nrows)
        {
            ptr[i] = ptrMem;
            for (unsigned j = 0; j < nrows; ++j, pool += ncols)
                ptr[i][j] = pool;
        }
        return ptr;
     }
     catch(std::bad_alloc& ex)
     {
         // rollback the previous allocations
        delete [] ptrMem;
        delete [] ptr;
        throw ex; 
    }
}

template <typename T>
void delete3DArray(T*** arr)
{
    delete[] arr[0][0]; // remove pool
    delete[] arr[0];  // remove the pointers
    delete[] arr;     // remove the pages
}

int main()
{
    double ***dPtr = nullptr;
    try 
    {
        dPtr = create3DArray<double>(4100, 5000, 2);
    }
    catch(std::bad_alloc& )
    {
        std::cout << "Could not allocate memory";
        return -1;
    }
    dPtr[0][0][0] = 10;  // for example
    std::cout << dPtr[0][0][0] << "\n";
    delete3DArray(dPtr);  // free the memory
}

Живой пример

Answer 2

Вероятно, это была упрощенная версия вашей проблемы, но используемая вами структура данных («трехзвездочные» массивы) почти никогда не будет той, которую вы хотите. Если вы создаете плотную матрицу, как здесь, и выделяете места для каждого элемента, нет никакого преимущества в том, чтобы делать миллионы крошечных выделений. Если вы хотите разреженную матрицу, вам обычно нужен формат, подобный сжатой разреженной строке.

Если массив является «прямоугольным» (или я предполагаю, что трехмерный будет «квадратным»), и все строки и столбцы имеют одинаковый размер, эта структура данных является просто расточительной по сравнению с выделением одного блока памяти , Вы выполняете миллионы крошечных выделений, выделяете пространство для миллионов указателей и теряете локальность памяти.

Этот шаблон создает абстракцию с нулевой стоимостью для динамического трехмерного массива. (Хорошо, почти: избыточно хранить как длину базового одномерного std::vector, так и отдельных измерений.) API использует a(i, j, k) в качестве эквивалента a[i][j][k] и a.at(i,j,k) в качестве варианта с границами. проверка.

Этот API также имеет опцию для заполнения массива функцией индексов, f(i,j,k). Если вы звоните a.generate(f), он устанавливает каждый a(i,j,k) = f(i,j,k). Теоретически, эта сила уменьшает расчет смещения во внутреннем цикле, чтобы сделать его намного быстрее. API также может передавать генерирующую функцию в конструктор как array3d<float>(M, N, P, f). Расширьте его, как вам угодно.

#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::ptrdiff_t;
using std::size_t;

/* In a real-world implementation, this class would be split into a
 * header file and a definitions file.
 */
template <typename T>
  class array3d {
    public:
    using value_type = T;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using reference = T&;
    using const_reference = const T&;
    using pointer = T*;
    using const_pointer = const T*;
    using iterator = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;
    using reverse_iterator = typename std::vector<T>::reverse_iterator;
    using const_reverse_iterator = typename
      std::vector<T>::const_reverse_iterator;

/* For this trivial example, I don’t define a default constructor or an API
 * to resize a 3D array.
 */
    array3d( const ptrdiff_t rows,
             const ptrdiff_t cols,
             const ptrdiff_t layers )
    {
      const ptrdiff_t nelements = rows*cols*layers;

      assert(rows > 0);
      assert(cols > 0);
      assert(layers > 0);
      assert(nelements > 0);

      nrows = rows;
      ncols = cols;
      nlayers = layers;
      storage.resize(static_cast<size_t>(nelements));
    }

/* Variant that initializes an array with bounds and then fills each element
 * (i,j,k) with a provided function f(i,j,k).
 */
    array3d( const ptrdiff_t rows,
             const ptrdiff_t cols,
             const ptrdiff_t layers,
             const std::function<T(ptrdiff_t, ptrdiff_t, ptrdiff_t)> f )
    {
      const ptrdiff_t nelements = rows*cols*layers;

      assert(rows > 0);
      assert(cols > 0);
      assert(layers > 0);
      assert(nelements > 0);

      nrows = rows;
      ncols = cols;
      nlayers = layers;
      storage.reserve(static_cast<size_t>(nelements));

      for ( ptrdiff_t i = 0; i < nrows; ++i )
        for ( ptrdiff_t j = 0; j < ncols; ++j )
          for ( ptrdiff_t k = 0; k < nlayers; ++k )
            storage.emplace_back(f(i,j,k));

      assert( storage.size() == static_cast<size_t>(nelements) );
    }

    // Rule of 5:
    array3d( const array3d& ) = default;
    array3d& operator= ( const array3d& ) = default;
    array3d( array3d&& ) = default;
    array3d& operator= (array3d&&) = default;

    /* a(i,j,k) is the equivalent of a[i][j][k], except that the indices are
     * signed rather than unsigned.  WARNING: It does not check bounds!
     */
    T& operator() ( const ptrdiff_t i,
                    const ptrdiff_t j,
                    const ptrdiff_t k ) noexcept
    {
      return storage[make_index(i,j,k)];
    }

    const T& operator() ( const ptrdiff_t i,
                          const ptrdiff_t j,
                          const ptrdiff_t k ) const noexcept
    {
      return const_cast<array3d&>(*this)(i,j,k);
    }

    /* a.at(i,j,k) checks bounds.  Error-checking is by assertion, rather than
     * by exception, and the indices are signed.
     */
    T& at( const ptrdiff_t i, const ptrdiff_t j, const ptrdiff_t k )
    {
      bounds_check(i,j,k);
      return (*this)(i,j,k);
    }

    const T& at( const ptrdiff_t i,
                 const ptrdiff_t j,
                 const ptrdiff_t k ) const
    {
      return const_cast<array3d&>(*this).at(i,j,k);
    }

/* Given a function or function object f(i,j,k), fills each element of the
 * container with a(i,j,k) = f(i,j,k).
 */
    void generate( const std::function<T(ptrdiff_t,
                                         ptrdiff_t,
                                         ptrdiff_t)> f )
    {
      iterator it = storage.begin();

      for ( ptrdiff_t i = 0; i < nrows; ++i )
        for ( ptrdiff_t j = 0; j < ncols; ++j )
          for ( ptrdiff_t k = 0; k < nlayers; ++k )
            *it++ = f(i,j,k);

      assert(it == storage.end());
    }

/* Could define a larger API, e.g. begin(), end(), rbegin() and rend() from the STL.
 * Whatever you need.
 */

    private:
    ptrdiff_t nrows, ncols, nlayers;
    std::vector<T> storage;

    constexpr size_t make_index( const ptrdiff_t i,
                                 const ptrdiff_t j,
                                 const ptrdiff_t k ) const noexcept
    {
      return static_cast<size_t>((i*ncols + j)*nlayers + k);
    }

    // This could instead throw std::out_of_range, like STL containers.
    constexpr void bounds_check( const ptrdiff_t i,
                                 const ptrdiff_t j,
                                 const ptrdiff_t k ) const
    {
      assert( i >=0 && i < nrows );
      assert( j >= 0 && j < ncols );
      assert( k >= 0 && k < nlayers );
    }
};

// In a real-world scenario, this test driver would be in another source file:

constexpr float f( const ptrdiff_t i, const ptrdiff_t j, const ptrdiff_t k )
{
  return static_cast<float>( k==0 ? 1.0 : -1.0 *
                             ((double)i + (double)j*1E-4));
}

int main(void)
{
  constexpr ptrdiff_t N = 2200, M = 4410, P = 2;
  const array3d<float> a(N, M, P, f);

  // Should be: -1234.4321
  cout << std::setprecision(8) << a.at(1234,4321,1) << endl;

  return EXIT_SUCCESS;
}

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

Конечно, если границы массива являются константами, просто объявите их constexpr и используйте массив с фиксированными границами.

К сожалению, каждый новый программист C ++ сначала узнает о char** argv, потому что это заставляет людей думать, что «двумерный» массив - это «рваный» массив указателей на строки.

В реальном мире это почти никогда не лучшая структура данных для работы.

Answer 3

Вы забыли одно измерение и затраты на выделение памяти. Показанный код очень неэффективно выделяет память в третьем измерении, что приводит к чрезмерным накладным расходам.

float*** a = new float**[N];

Это выделит примерно 22000 * sizeof(float **), что составляет 176кб. Незначительно.

a[m] = new float*[M - 1];

Единственное распределение здесь будет для 44099 * sizeof(float *), но вы получите 22000 из них. 22000 * 44099 * sizeof(float *), или примерно 7,7 ГБ дополнительной памяти. Это где вы перестали считать, но ваш код еще не закончен. У него долгий путь.

a[m][n] = new float[2];

Это одно выделение из 8 байтов, но это выделение будет выполнено 22000 * 44099 раз. Это еще один 7,7 Гб сброшен в канализацию. Теперь у вас более 15 гигабайт памяти, необходимой приложению, примерно, это должно быть выделено.

Но каждое выделение не освобождается , а new float[2] требует больше , чем 8 байтов. Каждый индивидуально выделенный блок должен отслеживаться вашей библиотекой C ++, чтобы он мог быть переработан delete. Наиболее упрощенная реализация распределения кучи на основе списка ссылок требует одного прямого указателя, одного обратного указателя и количества байтов в выделенном блоке. Предполагая, что для выравнивания ничего не нужно дополнять, это составляет как минимум 24 байта служебной информации на распределение на 64-битной платформе.

Теперь, поскольку ваше третье измерение содержит 22000 * 44099 выделений, 22000 выделений для второго измерения и одно выделение для первого измерения: если я рассчитываю на пальцы, это потребует (22000 * 44099 + 22000 + 1) * 24 или еще 22 гигабайта памяти, просто чтобы израсходовать ресурсы самой простой базовой схемы выделения памяти.

Теперь нам нужно около 38 гигабайт оперативной памяти, используя самое простое, из возможных, отслеживание выделения кучи, если я правильно сделал математику. Ваша реализация C ++, скорее всего, будет использовать немного более сложную логику выделения кучи с большими издержками.

Избавьтесь от new float[2]. Вычислите размер вашей матрицы и new один кусок 7,7 ГБ, затем вычислите, куда должны указывать остальные ваши указатели. Кроме того, выделите один фрагмент памяти для второго измерения вашей матрицы и вычислите указатели для первого измерения.

Ваш код размещения должен выполнять ровно три new оператора. Один для указателя первого измерения, Один для указателей второго измерения. И еще один огромный массив данных, который включает в себя ваше третье измерение.