Много стеков и динамическое распределение

Question

В многомерном массиве, где второе измерение будет иметь известные размеры (хотя и разные для каждого первого измерения), было бы быстрее с точки зрения производительности для фактического построения этих массивов для жесткого кода:

int* number[1000];

int secondDim[1];
number[0] = secondDim;

int secondDimTwo[2];
number[1] = secondDim;

и т.д.. и т.д. 1000 раз (я знаю, я знаю)

или динамически распределять каждое второе измерение:

for(int i = 0; i < 1000; i++)
    number[i] = new int[i+1];

Просто пытаюсь обернуть мою голову вокруг концепции здесь.

Answer 1

Как правило, вы можете предполагать, что распределение стека будет быстрее.Просто помните, что у стека ограниченная емкость, и чрезмерное использование больших массивов, выделенных стеком, может привести, подождите его ... переполнение стека!

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

namespace meta
{
    template <size_t N>
    struct sum
    {
        static const int value = (N + 1) * N / 2;
    };
}

template <size_t Size>
struct MultiArray
{
    // actual buffer
    int numbers[ meta::sum<Size>::value ];

    // run-time indexing
    int* getArray(size_t dimensions)
    {
        // get sum of (dimensions-1)
        size_t index = (dimensions * (dimensions-1)) >> 1;
        return &numbers[index];
    }

    // compile-time indexing
    template <size_t dimensions>
    int* getArray()
    {
        size_t index = meta::sum<dimensions - 1>::value ;
        return &numbers[ index ];
    }

    int* operator[](size_t index)
    {
        return getArray(index);
    }
};

Теперь вам решать, где его хранить.

MultiArray<1000> storedOnStack;
MultiArray<1000>* storedOnHeap = new MultiArray<1000>();

Для доступа к внутренним массивам вам нужны аксессоры:

int* runTimeResolvedArray = storedOnStack.getArray(10);
int* compileTimeResolvedArray = storedOnStack.getArray<10>();
int* runTimeResolvedArray2 = storedOnStack[10];
storedOnStack[10][0] = 666;

Надеюсь, это поможет!

РЕДАКТИРОВАТЬ: Я также должен сказать, что мне не нравится термин "распределение стека".Это вводит в заблуждение.Распределение стека - это, по сути, просто увеличение регистра указателя стека.Таким образом, если вы «выделите» 100 байтов в стеке, указатель будет увеличен на 100 байтов.Но если вы выделите 100 байт в куче, тогда это будет сложно - текущий распределитель должен найти подходящее пустое пространство памяти, обновить карту выделения и так далее, и так далее.

Если это однократное распределение - продолжайте и сделайте это в куче, накладные расходы динамического выделения не будут заметны.Но если делать это много раз в секунду, тогда выбирайте распределение стека.Кроме того, массивы стека могут быть потенциально более быстрыми для доступа, потому что содержимое стека, скорее всего, будет в кеше.Но очевидно, что действительно огромные массивы не поместятся в кеш.Итак, ответчик: профиль .

Answer 2

Лучший способ - выделить весь массив за один раз, чтобы все данные были смежными (лучше кэширование).

int * arr; arr = malloc (sizeof (int) * sum (1, n)); Вы должны определить функцию суммы.

Просто выделите двумерный массив (первый дим) и установите указатели в правильное положение в обр.

Answer 3

Пока вы не профилируете и не узнаете, что проблема заключается в динамическом размещении:

std::vector<std::vector<int> > number;
for ( size_t i = 0; i < 1000; ++ i ) {
    number.push_back( std::vector<int>( i + 1 );
}

или (возможно, немного быстрее, особенно если ваш компилятор еще не имеет семантики перемещения):

std::vector<std::vector<int> > number( 1000 );
for ( size_t i = 0; i != number.size() ; ++ i ) {
    number[i].resize( i + 1 );
}

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

class TriangularMatrix
{
    std::vector<int> myData;
    size_t mySize;

    size_t rowIndex( size_t i ) const
    {
        return (i * (i + 1)) / 2;
    }
public:
    TriangularMatrix( size_t size )
        : myData( rowIndex( size ) )
        , mySize( size )
    {
    }
    int* operator[]( size_t i )  // Returns row
    {
        assert( i < mySize );
        return &myData[rowIndex( i )];
    }
    int const* operator[]( size_t i ) const  // Returns row
    {
        assert( i < mySize );
        return &myData[rowIndex( i )];
    }
    int& operator( int i, int j )  // indexation
    {
        assert( j <= i );
        return operator[]( i )[ j ];
    }
    int const& operator( int i, int j ) const  // indexation
    {
        assert( j <= i );
        return operator[]( i )[ j ];
    }
};

На самом деле, я думаю, что-то подобноебыть намного чище и читабельнее.

Answer 4

Если вы уже знаете размер нужного вам массива, вы должны использовать массив в стеке.
Обратите внимание, что обычно динамическое распределение обходится дороже, чем выделение в стеке.
Если разница в производительности значительнаДостаточно для вашего случая можно определить только по профилированию.

Кроме того, избегайте динамического распределения, поскольку оно более подвержено ошибкам, если только вы не используете какое-либо управление ресурсами на основе RAII .