C++ Существует ли быстрый многомерный массив, который позволяет использовать подмассивы разного размера?

Недавно я перешел с Java на C++ и заметил падение производительности при использовании массивов стандартной библиотеки. Я написал одну и ту же программу на Java и C++ (или, по крайней мере, настолько похожую, насколько я мог себе представить), чтобы записывать время их выполнения.

Java-код:

    public static void main(String args[]) {
        long stime = System.currentTimeMillis();
        
        double[][] arr = new double[4][];
        arr[0] = new double[5];
        arr[1] = new double[10];
        arr[2] = new double[5];
        arr[3] = new double[8];
        
        for(int l = 0; l < arr.length; l++) {
            for(int i  = 0; i < arr[l].length; i++) {
                arr[l][i] = 1;
            }
        }
        
        for(int t = 0; t < 100000000; t++) {
            for(int l = 0; l < arr.length; l++) {
                for(int i  = 0; i < arr[l].length; i++) {
                    arr[l][i] += t;
                    arr[l][i] *= t;
                    arr[l][i] /= t;
                }
            }
        }
        
        System.out.println("time: " + ((System.currentTimeMillis() - stime) / 1000.0f));
    }

Код С++:

int main()
{
    int subarray_sizes[] = {5,10,5,8};

    double** arr = new double*[4];
    arr[0] = new double[subarray_sizes[0]];
    arr[1] = new double[subarray_sizes[1]];
    arr[2] = new double[subarray_sizes[2]];
    arr[3] = new double[subarray_sizes[3]];

    for(int l = 0; l < 4; l++){
        for(int i = 0; i < subarray_sizes[l]; i++){
            arr[l][i] = 1;

        }
    }

    for(int t = 0; t < 100000000; t++){
        for(int l = 0; l < 4; l++){
            for(int i = 0; i < subarray_sizes[l]; i++){
                arr[l][i] += t;
                arr[l][i] *= t;
                arr[l][i] /= t;
            }
        }
    }

    delete[] arr[3];
    delete[] arr[2];
    delete[] arr[1];
    delete[] arr[0];
    delete[] arr;
}

Один запуск программы на Java занял 3,125 секунды, а программы на C++ — 25,372 секунды. Я понимаю, что это не лучший способ измерения производительности, однако я сомневаюсь, что это расхождение во времени выполнения вызвано просто случайностью.

Я также видел векторы, используемые вместо массивов во многих программах на C++, поэтому я написал программу с векторами. Код С++:

int main()
{
    int subarray_sizes[] = {5,10,5,8};

    std::vector<std::vector<double>> arr(4);
    arr[0].resize(5);
    arr[1].resize(10);
    arr[2].resize(5);
    arr[3].resize(8);

    for(int l = 0; l < arr.size(); l++){
        for(int i = 0; i < arr[l].size(); i++){
            arr[l][i] = 1;

        }
    }

    for(int t = 0; t < 100000000; t++){
        for(int l = 0; l < arr.size(); l++){
            for(int i = 0; i < arr[l].size(); i++){
                arr[l][i] += t;
                arr[l][i] *= t;
                arr[l][i] /= t;
            }
        }
    }
}

Однако это дало худшие результаты - 46,806 секунды.

Короче говоря, мне интересно, есть ли в C++ структура данных, которая позволяет мне иметь подмассивы переменной длины, время выполнения которых сопоставимо со временем выполнения массивов в Java.

вам необходимо скомпилировать программу на C++ в режиме выпуска с включенной оптимизацией! в Visual Studio измените раскрывающийся список Debug на панели инструментов на Release, а в gcc вы должны скомпилировать его с помощью -O3 опции компиляции.

Ahmed AEK 15.08.2024 20:59

И запустите тест без подключенного отладчика.

Thomas Weller 15.08.2024 21:00

Кроме того, поскольку вы выполняете операции с массивами, вам следует включить векторизацию, установить Enable Enhanced Instruction Set на AVX2 или AVX512 в Visual Studio и -march=native в GCC, на godbolt код занимает примерно 1,5 секунды с включенными оптимизациями.

Ahmed AEK 15.08.2024 21:08

@AhmedAEK, я использую Code::Blocks вместо Visual Studio, но я скомпилировал с -O3, и да, производительность значительно лучше (~ 1,7 секунды). Спасибо за помощь!

Evelyn 15.08.2024 21:14

Ваша проблема явно связана с отсутствием флагов компиляции, но по вопросу о том, как создавать быстрые многомерные массивы разных размеров: выделите один вектор, размер которого равен сумме всех размеров векторов суммы. Создайте второй vector<size_t> со смещениями, где начинается каждый подвектор. Это позволяет избежать затрат на распределение, улучшает локальность данных для кэширования, снижает накладные расходы и позволяет выполнять скалярные операции над всеми записями с помощью одного цикла, который хорошо векторизуется. То же самое работает в Java

Homer512 15.08.2024 21:16

Примечание: массивы массивов и векторы векторов имеют неизбежный штраф из-за того, что данные не являются смежными. Иногда этот штраф может быть очень заметным. Чтобы работать с одним смежным блоком, начните с чего-то вроде того, что здесь делает Дуг, и увеличивайте сложность, если того требуют обстоятельства.

user4581301 15.08.2024 21:18

Нет, это не просто случайность, просто вы не знаете, как включить оптимизацию для вашего компилятора C++.

john 15.08.2024 21:23

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

Joel 15.08.2024 21:23

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

Thomas Matthews 15.08.2024 21:29

Измените double** arr = new double*[4]; на double* arr[4];. Нет необходимости динамически выделять четыре указателя.

Drew Dormann 15.08.2024 21:34
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
10
61
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я взял вашу первую версию дословно:

$ g++ -O2 foo.cpp -o foo
$ time foo

real    0m0.822s
user    0m0.800s
sys 0m0.005s

Как предлагали другие, вы хотите, чтобы оптимизация была включена. Я почти ничего не включал (аргумент -O2 — это нуль, а не ноль), и я не запускал IDE в режиме отладки. Как видите, я сделал это из командной строки.

Я использую Mac M2 — машине около 9 месяцев.

Видите ли, 8/10 секунды.

Другие вопросы по теме