Я перевожу программу, которая выполняет числовое моделирование с FORTRAN на C ++.
Мне приходится иметь дело с большими матрицами типа double размером 800MB.
это
double M[100][100][100][100];
выдает ошибку сегментации, потому что стек не такой большой.
Использование new, delete неудобно, потому что мне нужно четыре цикла for для размещения моего массива и даже для его освобождения.
std :: array находится в стеке, так что это не хорошо.
std :: vector был бы хорошим выбором, поэтому
Первый вопрос
Подходит ли std :: vector для быстрого моделирования или
vector<vector<vector<vector<int,100>,100>,100>,100>
будет нести много бесполезных и тяжелых данных?
Второй вопрос
Знаете ли вы какие-либо данные о других структурах, которые я могу использовать? Может быть, есть что-то от повышения.
На данный момент я просто использую это решение:
double * M = new double [100000000];
и я получаю доступ к записям, которые мне нужны.
Если я не найду другого эффективного решения, я напишу класс, который автоматически управляет этим последним методом.
Третий вопрос Как вы думаете, это значительно снизит производительность?
Вы можете рассмотреть std::valarray
который был разработан, чтобы быть конкурентоспособным с FORTRAN. Он хранит элементы в виде плоского массива и поддерживает математические операции, а также операции для нарезки и косвенного доступа.
Похоже, что вы планируете в любом случае. Хотя даже страница руководства предполагает, что могут быть более гибкие альтернативы.
Использование чего-либо в стеке определенно намного эффективнее. память процесса ограничена ОС (стек + куча), и ваша проблема в том, что в большинстве случаев вы можете превысить объем памяти, выделенный процессу.
Чтобы устранить ограничение памяти, я бы посоветовал вам взглянуть на stxxl. Это библиотека, которая реализует большинство контейнеров и алгоритмов STL, но при необходимости использует внешнюю память. Конечно, это ухудшит производительность …
Программисты, как правило, подходят к каждой проблеме, сначала написав больше кода. Который затем должен быть сохранен. Каждая проблема не Гвоздь…
Больше кода здесь не самое простое и эффективное решение. Больше кода также, вероятно, произведет исполняемый файл, который помедленнее.
Память стека — это просто память — она ничем не отличается от кучи памяти. Он просто управляется процессом по-разному и подчиняется различным ограничениям ресурсов. Для операционной системы нет никакой разницы, использует ли процесс 1 ГБ памяти в своем стеке или 1 ГБ из своей кучи.
В этом случае ограничение размера стека, скорее всего, является искусственной настройкой конфигурации. В системе Linux ограничение размера стека может быть сброшено для оболочки и ее дочерних процессов:
bash-4.1$ ulimit -s unlimited
bash-4.1$ ulimit -s
unlimited
bash-4.1$
Увидеть этот вопрос и его ответы Больше подробностей.
Все POSIX-совместимые системы должны иметь одинаковые функции, так как ограничение размера стека POSIX-стандартное ограничение ресурса.
Также вы можете довольно легко запустить поток с произвольно большим стеком:
#include <pthread.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <stdio.h>
void *threadFunc( void *arg )
{
double array[1024][1024][64];
memset( array, 0, sizeof( array ) );
return( NULL );
}
int main( int argc, char **argv )
{
// create and memset the stack lest the child thread start thrashing
// the machine with "try to run/page fault/map page" cycles
// the memset will create the physical page mappings
size_t stackSize = strtoul( argv[ 1 ] ? argv[ 1 ] : "1073741824",
NULL, 0 );
void *stack = mmap( 0, stackSize, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANON, -1, 0 );
memset( stack, 0, stackSize );
// create a large stack for the child thread
pthread_attr_t attr;
pthread_attr_init( &attr );
pthread_attr_setstacksize( &attr, stackSize );
pthread_attr_setstackaddr( &attr, stack );
pthread_t tid;
pthread_create( &tid, &attr, threadFunc, NULL );
void *result;
pthread_join( tid, &result );
return( 0 );
}
Проверка ошибок была опущена.
Это также работает, если вы запускаете ulimit -s unlimited
перед запуском скомпилированной программы (и, конечно, если на машине достаточно виртуальной памяти …):
#include <string.h>
int main( int argc, char **argv )
{
double array[1024][1024][64];
memset( array, 0, sizeof( array ) );
return( 0 );
}
В некоторых случаях может быть полезно привести 1-D указатель к 4-D прямоугольному массиву для включения декартовой индексации (а не линейной индексации):
#include <cstdio>
#define For( i, n ) for( int i = 0; i < n; i++ )
double getsum( double *A, int *n, int loop )
{
// Cast to 4-D array.
typedef double (* A4d_t)[ n[2] ][ n[1] ][ n[0] ];
A4d_t A4d = (A4d_t) A;
// Fill the array with linear indexing.
int ntot = n[0] * n[1] * n[2] * n[3];
For( k, ntot ) A[ k ] = 1.0 / (loop + k + 2);
// Calc weighted sum with Cartesian indexing.
double s = 0.0;
For( i3, n[3] )
For( i2, n[2] )
For( i1, n[1] )
For( i0, n[0] )
s += A4d[ i3 ][ i2 ][ i1 ][ i0 ] * (i0 + i1 + i2 + i3 + 4);
return s;
}
int main()
{
int n[ 4 ] = { 100, 100, 100, 100 };
double *A = new double [ n[0] * n[1] * n[2] * n[3] ];
double ans = 0.0;
For( loop, 10 )
{
printf( "loop = %d\n", loop );
ans += getsum( A, n, loop );
}
printf( "ans = %30.20f\n", ans );
return 0;
}
что занимает 5,7 сек с g ++ — 6.0 -O3 на Mac OSX 10.9. Может быть интересно сравнить производительность с vector<vector<...>>
или пользовательский класс представления массива. (Я пробовал последнее раньше, и в то время приведенное выше приведение массива было несколько быстрее, чем мой (наивный) класс массива.)
Я думаю, что ответ на этот вопрос вполне основан на мнении.
Концепция чего-либо «хорошо«строго зависит от использования структуры данных.
В любом случае, если количество элементов не изменяется во время выполнения, а ваша проблема — это практически доступ к памяти, то, на мой взгляд, лучшее решение — это непрерывный массив блоков.
Как правило, в этих случаях мой выбор прост T* data = new T[SIZE];
инкапсулирован в класс, который правильно обрабатывает доступ.
Использование указателя позволяет мне чувствовать себя немного более комфортно в отношении управления памятью, но на самом деле std::vector<T>
это практически то же самое.
Это все, что я могу сказать по знаниям, которые вы предоставили в своем вопросе. В любом случае, я могу предложить вам также позаботиться об использовании данных.
Например: чтобы максимизировать производительность вашего приложения, попробуйте использовать кэши и избежать промахов. Таким образом, вы можете попытаться понять, есть ли «доступ-модель» к вашим данным, или, даже, если вы можете масштабировать свою проблему, думая о многопоточном контексте.
В заключение, на мой взгляд, в целом смежный вектор double
это лучший выбор. Это отвечает на ваш вопрос. Но если вы заботитесь о производительности, вы должны подумать о том, как использовать как можно лучше кэши а также процессорные механизмы (как многопоточность).