Вопрос по multithreading, algorithm, c++, c++11 – Сторнирование строки с использованием потоков

3

Недавно меня попросили в интервью реализовать функцию обратного преобразования строк с использованием потоков. Я придумал большую часть решения ниже. Выбрано или нет, это отдельная история :-). Я попытался запустить приведенное ниже решение на своем домашнем ПК под управлением Windows 8 для предварительного просмотра. Компилятор VC11 Beta.

Вопрос в том, что многопоточный код всегда работает быстрее или на 1 миллисекунду медленнее, чем последовательный код. Вводимые мной данные представляют собой текстовый файл размером 32,4 МБ. Есть ли способ сделать многопоточный код быстрее? Или это то, что вводимые данные слишком малы, чтобы иметь какое-либо значение?

РЕДАКТИРОВАТ

Я только написалvoid Reverse(char* str, int beg, int end, int rbegin, int rend); а такж
void CustomReverse(char* str); методы в интервью. Весь остальной код написан дома.

<code> template<typename Function>
    void TimeIt(Function&& fun, const char* caption)
    {
        clock_t start = clock();     
        fun();     
        clock_t ticks = clock()-start;     
        std::cout << std::setw(30) << caption          << ": "          << (double)ticks/CLOCKS_PER_SEC << "\n"; 
    }

    void Reverse(char* str)
    {


        assert(str != NULL);
        for ( int i = 0, j = strlen(str) - 1; i < j; ++i, --j)
        {
            if ( str[i] != str[j])
            {
                std::swap(str[i], str[j]);
            }
        }

    }

     void Reverse(char* str, int beg, int end, int rbegin, int rend)
        {
            for ( ; beg <= end && rbegin >= rend; ++beg, --rbegin)
            {
                if ( str[beg] != str[rbegin])
                {
                    char temp = str[beg];
                    str[beg] = str[rbegin];
                    str[rbegin] = temp;
                }
            }
        }

        void CustomReverse(char* str)
        {
            int len = strlen(str);
            const int MAX_THREADS = std::thread::hardware_concurrency();
            std::vector<std::thread> threads;

            threads.reserve(MAX_THREADS);

            const int CHUNK = len / MAX_THREADS > (4096) ? (4096) : len / MAX_THREADS;

            /*std::cout << "len:" << len << "\n";
            std::cout << "MAX_THREADS:" << MAX_THREADS << "\n";
            std::cout << "CHUNK:" << CHUNK << "\n";*/

        for ( int i = 0, j = len - 1; i < j; )
                {
                    if (i + CHUNK < j && j - CHUNK > i )
                    {
                        for ( int k = 0; k < MAX_THREADS && (i + CHUNK < j && j - CHUNK > i ); ++k)
                        {                                                
                             threads.push_back( std::thread([=, &str]() { Reverse(str, i,    
                                                    i + CHUNK, j, j - CHUNK); }));
                            i += CHUNK + 1;
                            j -= CHUNK + 1;
                        }


                        for ( auto& th : threads)
                        {
                            th.join();
                        }

                        threads.clear();
                    }
                    else
                    {          
                                        char temp = str[i];
                                        str[i] = str[j];
                                        str[j] = str[i];
                        i++;
                        j--;
                    }
                }
            }


        void Write(std::ostream&& os, const std::string& str)
        {
           os << str << "\n";
        }

        void CustomReverseDemo(int argc, char** argv)
        {
            std::ifstream inpfile;
            for ( int i = 0; i < argc; ++i)
                std::cout << argv[i] << "\n";

            inpfile.open(argv[1], std::ios::in);

            std::ostringstream oss;
            std::string line;

            if (! inpfile.is_open())
            {
                return;
            }
            while (std::getline(inpfile, line))
            {
                oss << line;
            }

            std::string seq(oss.str());
            std::string par(oss.str());

            std::cout << "Reversing now\n";

            TimeIt( [&] { CustomReverse(&par[0]); }, "Using parallel code\n");  
            TimeIt( [&] { Reverse(&seq[0]) ;}, "Using Sequential Code\n");
            TimeIt( [&] { Reverse(&seq[0]) ;}, "Using Sequential Code\n");
            TimeIt( [&] { CustomReverse(&par[0]); }, "Using parallel code\n");      



            Write(std::ofstream("sequential.txt"), seq);
            Write(std::ofstream("Parallel.txt"), par);
        }

        int main(int argc, char* argv[])
        {
            CustomReverseDemo(argc, argv);
        }
</code>
Также: почему вы урезаете размер куска до 4096, чтобы оптимизировать кеш? sergico
Многопоточный код довольно часто медленнее, чем последовательный код. Предположение, что МТ быстрее, как правило, совершенно неверно. Crazy Eddie
@ sergico Добавлено TimeIt fn., заменено std :: swap на код подкачки. Что касается размера куска, какой может быть лучший размер? Jagannath
Возможно, вы страдаете от преждевременной оптимизации. Указывал ли интервьюер какие-либо ограничения производительности, потому что, если они этого не сделали, вы можете написать НАМНОГО более простой код. Кроме того, если проблема заключалась только в том, чтобы разработать функцию обращения строк, которая использует потоки, вы пошли слишком далеко. Michael Price
Я пытался скомпилировать и запустить ваш код, но, к сожалению, похоже, что моя система не поддерживает std :: thread (я получил MAX_THREAD = 0: - /). Мой единственный вопрос: что именно делает TimeIt? Это ваша собственная функция измерения времени? Может быть проблема в этом? sergico

Ваш Ответ

6   ответов
1

Мои усилия "Перевернуть строку, используя потоки"

Я проверил это с 2-ядерным процессором с VC11 Beta и mingw (gcc 4.8) на Windows 7

Результаты тестирования:

VC11 Бета:

7 Мб файл

Debug

Простое обратное: 0,468

Async реверс: 0,275

Выпус

Простое обратное: 0,006

Async реверс: 0,014

98 Мб файл

Debug

Простое обратное: 5.982

Async реверс: 3.091

Выпус

Простое обратное: 0.063

Async реверс: 0,079

782 Мб фай

Выпус

Простое обратное: 0,567

Async реверс: 0,689

Mingw:

782 Мб фай

Выпус

Простое обратное: 0,583

Async реверс: 0,566

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

Так что доверяй своему компилятору =)

Ну, я мог бы сказать это в интервью, но просто попытался ответить на вопрос, не допрашивая интервьюера. Jagannath
5

Ваш размер блока 4096 слишком мал, чтобы его стоить. Запуск потока может быть столь же дорогостоящим, как и фактическая операция. Вы часто присоединяетесь к вилке (для каждого символа CHUNK * MAX_THREADS). Это вводит много ненужных точек соединения (последовательных частей) и накладных расходов.

Статически разделите строку на фрагменты MAX_THREADS и запустите потоки MAX_THREADS. Есть более эффективные способы сделать это, но по крайней мере это даст вам некоторое ускорение.

Я не могу прийти к правильному размеру блока. Для того чтобы код был нечитаемым, является ли он пустым CustomReverse (char * str); п. это было сложно или весь код написан плохо? Jagannath
У меня были проблемы с логикой цикла. Также понимание того, что я и J представляют. Я думаю, это был только я. usr
1

вы не используете все старые добрые части стандартной библиотеки, такие какstd::string а такжеiterators

Вы не должны сами писать потоки, а вместо этого использовать библиотеку параллельных алгоритмов, которая предлагает что-то вродеparallel_for конструировать.

Ваша задача может быть упрощена до этого:

  std::string str;

  // fill string

  auto worker = [&] (iter begin, iter end) {
      for(auto it = begin; it != end; ++it) {
        std::swap(*it, *(std::end(str) - std::distance(std::begin(str), it) - 1));
      }
  };

  parallel_for(std::begin(str), 
    std::begin(str) + std::distance(std::begin(str), std::end(str)) / 2, worker);

Обратите внимание, что вам нужен довольно большой текстовый файл, чтобы ускорить этот параллельный подход. 34 МБ может быть недостаточно.

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

Почему быстрое снижение? Он даже не мог читать так быстро. inf
Что касается параллелизма, то он использует индексы, а не итераторы. parallel_for_each принимает итераторы, но лямбда принимает только 1 аргумент вместо 2 аргументов в вашем работнике. Я принимаю предложение не создавать темы явно. Но решение, которое вы дали, не работает. Jagannath
Да. Размер файла был одной из проблем. Поскольку это был вопрос для интервью, а не для C ++ в Windows, я не мог дать им решение Parallel_for. Jagannath
@ Jagannath Я не предназначался для определенногоparallel_for, вы, вероятно, ссылаетесь на PPL. inf
Похоже, это неверное решение.parallel_for разделит строку на части и обратит символы в каждом фрагменте. Результирующая строка не будет обратной версией исходной. Anton Pegushin
1
Ограничение размера фрагмента до 4096 не имеет никакого смысла. Один раз, а затем синхронизация в конце всегда должна быть шаблоном для параллельных операций (подумайте, карта / уменьшить)

Проверка наличия одинаковых символов - это плохо для любого вида оптимизации конвейера. Просто сделайте обмен (). В параллельной и последовательной версии вы используете другой код для обмена. Зачем
Извините за std :: swap (). В реальном коде такого не было. Я экспериментировал с разными случаями и скопировал этот код сюда. Jagannath
Для параллельной версии я подумал обратное (char * str, int beg, int end, int rbegin, int rend); это способ сделать обратное. Jagannath
1

я вижу, что многопоточная версия (на основе TBB, см. Ниже) работает в среднем в 3 раза лучше, чем серийная версия. Должен признать, что для этого 3-кратного ускорения он использует 12 ядер Real-HW :). Я немного поэкспериментировал с размерами зерен (вы можете указать их в TBB для объекта класса block_range), но это не оказало какого-либо существенного влияния, по умолчанию auto_partitioner, кажется, в состоянии разделить данные почти оптимально. Код, который я использовал:

tbb::parallel_for(tbb::blocked_range<size_t>(0, (int)str.length()/2), [&] (const tbb::blocked_range<size_t>& r) {
    const size_t r_end = r.end();
    for(size_t i = r.begin(); i < r_end; ++i) {
        std::swap(*(std::begin(str) + i), *(std::end(str) - 1 - i));
    }
});
0

Проверенный код

#include <iostream>
#include <mutex>
#include <thread>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

void strrev(char *p, char *q, int num)
{
    for(int i=0;i < num ; ++i,--q, ++p)
        *q = *p;
}

int main(int argc, char **argv)
{
    char *str;
    if(argc>1)
    {
        str = argv[1];
        printf("String to be reversed %s\n", str);
    }
    else
    {
        return 0;
    }

    int length = strlen(str);
    int N = 5;
    char *rev_str = (char *)malloc(length+1);
    rev_str[length] = '\0';

    if (N>length)
    {
        N = length;
    }

    std::vector<std::thread> threads;

    int begin=0, end=length-1, k = length/N;
    for(int i=1; i <= N; ++i)
    {
        threads.emplace_back(strrev, &str[begin], &rev_str[end], k);
        //strrev(&str[begin], &rev_str[end], k);
        begin += k;
        end -= k;
    }

    while (true)
    {
        if (end < 0 && begin > length-1)
        {
            break;
        }
        rev_str[end] = str[begin];
        --end; ++begin;
    }

    for (auto& i: threads)
    {
        i.join();
    }

    printf("String after reversal %s\n", rev_str);

    return 0;
}

Похожие вопросы