Производительность переключения внутри цикла - PullRequest
Новая
       5

Производительность переключения внутри цикла

0 голосов
/ 06 мая 2018

У нас есть карта типов сообщений в список сообщений. Учитывая критичный к производительности кусок кода, такой как это: 

struct row_t {
    int message_type; //0,1,2,3,4,5
};
map<int, vector<row_t>> message_map;

for (auto x : message_map) {
    int message_type = x.first;
    vector<row_t> message_rows = x.second;

    for (row_t row : message_rows) {
        //LARGE CODE CHUNK
        switch(row.message_type) { //same as switch(message_type)
            case 0:
                add_0_to_database();
                break;
            case 1:
                add_0_to_database();
                break;
            //...
            default:
                break;
        }
    }
}

Оператор switch будет выполняться на каждой итерации внутреннего цикла, даже если каждый элемент в message_rows имеет одинаковый тип.

Эту проблему можно устранить, запустив оператор switch только один раз до запуска внутреннего цикла: 

for (auto x : message_map) {
    int message_type = x.first;
    vector<row_t> message_rows = x.second;

    switch(message_type) {
        case 0:
            for (row_t row : message_rows) {
                //LARGE CODE CHUNK
                add_0_to_database(row);
            }
            break;
        case 1:
            for (row_t row : message_rows) {
                //LARGE CODE CHUNK
                add_1_to_database(row);
            }
            break;
        //...
        default:
            break;
    }
}

Но теперь у нас есть несколько избыточных внутренних циклов, и код "LARGE CODE CHUNK" необходимо дублировать несколько раз.

Мой вопрос: могут ли современные компиляторы (в частности, g ++) оптимизировать версию 1, чтобы быть такой же эффективной, как версия 2?

Или мне следует перейти на версию 2 и, возможно, рассмотреть возможность использования какого-либо другого метода для удаления избыточности, например, установить указатель функции на add_{0/1}_to_database в операторе switch и затем использовать указатель на функцию в цикле?

1 Ответ

0 голосов
/ 07 мая 2018

Предположительно, ваш реальный row_t сложнее, чем показано в вопросе.Если это не так, нет необходимости перебирать вектор.Просто используйте длину.

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

  1. Использование std::map.Обход заказанной карты может быть дорогим.Подумайте о переключении на std::unordered_map, которые были введены в c ++ 11.Использование цикла на основе диапазона означает, что вы используете c ++ 11 или более позднюю версию.

  2. Чрезмерное копирование.Внешний цикл for (auto x : message_map) делает копию, как и vector<row_t> message_rows = x.second и for (row_t row : message_rows).Вы копируете вектор дважды, плюс дополнительную копию каждого элемента.Используйте ссылки.

Решение: рассмотрите возможность использования указателя на функцию.Простой подход состоит в том, чтобы переместить оператор switch из внутреннего цикла, но вместо цикла, как указано в вопросе, установите указатель функции: 

for (auto& x : message_map) // Note the use of auto& to avoid copying.
{
    int message_type = x.first;
    std::vector<row_t>& message_rows = x.second; // Avoid copying!
    void (* add_to_database)(const row_t&) = nullptr;

    switch(message_type)
    {
    case 0:
        add_to_database = add_0_to_database;
        break;
    case 1:
        add_to_database = add_1_to_database;
        break;
    //...
    default:
        // This might be an error that should be handled here.
        break;
    }

    for (row_t& row : message_rows) // Avoid copying!
    {
        // LARGE CODE CHUNK
        add_to_database (row);
    }
}

Этот оператор switch немного уродлив.Версия 2.0 преобразует это в другую карту: 

typedef void (*AddFunction)(const row_t&);
std::unordered_map<int, AddFunction> add_function_map;

// Outside the loop, populate the map:
add_function_map[0] = add_0_to_database;
add_function_map[1] = add_1_to_database;
// Rest of add_function_map population elided.

// The loop is now short and sweet.
for (auto& x : message_map) // Note the use of auto& to avoid copying.
{
    int message_type = x.first;
    std::vector<row_t>& message_rows = x.second; // Avoid copying!
    AddFunction add_to_database = add_function_map[message_type];
    for (row_t& row : message_rows) // Avoid copying!
    {
        // LARGE CODE CHUNK
        add_to_database (row);
    }
}
...