Потоки замедляют работу друг друга, что делать?

Написал алгоритм поиска по мотивам расстояния Левенштейна для проекта универского, собственно поиск работает не достаточно быстро как требуется, поэтому попытался использовать потоки. Моя идея заключалась в том, чтоб обрабатывать часть слов, по которым ведётся поиск, в одном потоке, другую часть во втором потоке и так далее. Но когда я прописал собственно всё это дело и начал измерять время работы, я обнаружил интересность: Допустим я ввожу 4-ёх буквенный запрос и пытаюсь замерять время после join() для каждого потока. Получаю в своём случае вот такие числа:

введите сюда описание изображения

Дальше я опишу как именно я выделяю потоки и работаю с ними, а сейчас предположим, что мы просто увидели время работы 7 потоков. А теперь делаем тоже самое, но запускаем лишь один поток(то есть проводим поиск на 1/7 от всего списка слов), получаем такое:

введите сюда описание изображения

Для меня такой результат искренне не понятен. В моей системе стоит 8 ядерный 16 поточный камень, поэтому ему явно хватает возможностей запускать все эти потоки параллельно. Но в данном случае явно видно, что один поток работает в 3-4 раза быстрее, чем он же, но одновременно с другими шестью. Сколько не искал, ничего полезного не нашёл. Потоки используют лишь один общий вектор, но даже если убрать строчку с его использованием - проблема останется. Поэтому проблем с гонкой данных вроде как нет.

Теперь сам кусок кода с потоками:

    vector<thread> workers;
    vector<pair<string, int>> tag_list;
    vector<vector<Points>> points_list((tags_.size() / WORDSPERTHREAD) + 1);//points_list хранит вектор Points от каждого потока\
    заранее выделяем под него память
    int cur_count = 0;

    for (int i = 0; i < tags_.size(); i++)
    {
        //tags_ - контейнер, хранящий теги, по которым ведётся поиск
        if (tags_[i].type != type && type != TagsField::TYPELIST::pANY &&
            type != TagsField::TYPELIST::pANYWITHSPECIALIZATION)//тип тегов, по которым мы ищем
            continue;
        tag_list.push_back({ tags_[i].name,i });//часть списка тегов, которая будет передаваться каждому потоку 
        if (tag_list.size() != WORDSPERTHREAD && i != tags_.size() - 1) // WORDSPERTHREAD констатное выражение, показывающее сколько слов\
            будет лежать в каждом потоке
            continue;
        if (tag_list.empty())
            continue;
        workers.push_back(thread([](vector<string> request_list, vector<pair<string, int>> tag_list,
            vector<Points>& points) -> void
            {
                for (int k = 0; k < tag_list.size(); k++)
                {
                    double min_cur_dist = MAXINT;
                    for (int j = 0; j < request_list.size(); j++)//request_list - вектор строк, хранящий строки запроса без пробелов
                    {
                        if (request_list[j].empty())
                            continue;
                        //double cur_dist = 0;
                        double cur_dist = GetRange(request_list[j], tag_list[k].first);//сама функция поиска
                        if (min_cur_dist > cur_dist)
                            min_cur_dist = cur_dist;//если нашли слово в запросе, более похожее на тег, то обновляем переменную
                    }
                    if (min_cur_dist < MAXINT)//тут отражаем сходимость k-го тега с каким-то словом из запроса
                    {
                        points.push_back(Points(tag_list[k].second, 0, min_cur_dist));//закидываем в наш контейнер результат работы потока
                    }
                }
            }, request_list, tag_list, ref(points_list[cur_count])));//points_list хранит вектор Points от каждого потока\
        cur_count говорит о текущем номере потока
        cur_count++;
        tag_list.clear();
    }


    for (int i = 0; i < workers.size(); i++)
    {
        workers[i].join();//ожидаем пока все потоки справятся с работой

#ifdef LEVENSTAINSEARCHTIME_DEBUG//просто выводим время работы
        auto end = chrono::system_clock::now();
        auto dur = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << fixed << setprecision(6) << (double)dur.count() / 1000000 << 's' << endl;
#endif // LEVENSTAINSEARCHTIME_DEBUG
    }

Собственно весь алгоритм.

Также прикрепляю алгоритм поиска GetRange

constexpr int delete_cost = 2;
constexpr int swap_cost = 1;
constexpr int add_cost = 2;
constexpr int transposition_cost = 2;
constexpr int magic_coefficient = 100;

map<int, vector<int>> distance_code_key
{
    /* '`' */ { 192 , { 49 }},
    /* '1' */ { 49 , { 50, 87, 81 }},
    /* '2' */ { 50 , { 49, 81, 87, 69, 51 }},
    /* '3' */ { 51 , { 50, 87, 69, 82, 52 }},
    /* '4' */ { 52 , { 51, 69, 82, 84, 53 }},
    /* '5' */ { 53 , { 52, 82, 84, 89, 54 }},
    /* '6' */ { 54 , { 53, 84, 89, 85, 55 }},
    /* '7' */ { 55 , { 54, 89, 85, 73, 56 }},
    /* '8' */ { 56 , { 55, 85, 73, 79, 57 }},
    /* '9' */ { 57 , { 56, 73, 79, 80, 48 }},
    /* '0' */ { 48 , { 57, 79, 80, 219, 189 }},
    /* '-' */ { 189 , { 48, 80, 219, 221, 187 }},
    /* '+' */ { 187 , { 189, 219, 221 }},
    /* 'q' */ { 81 , { 49, 50, 87, 83, 65 }},
    /* 'w' */ { 87 , { 49, 81, 65, 83, 68, 69, 51, 50 }},
    /* 'e' */ { 69 , { 50, 87, 83, 68, 70, 82, 52, 51 }},
    /* 'r' */ { 82 , { 51, 69, 68, 70, 71, 84, 53, 52 }},
    /* 't' */ { 84 , { 52, 82, 70, 71, 72, 89, 54, 53 }},
    /* 'y' */ { 89 , { 53, 84, 71, 72, 74, 85, 55, 54 }},
    /* 'u' */ { 85 , { 54, 89, 72, 74, 75, 73, 56, 55 }},
    /* 'i' */ { 73 , { 55, 85, 74, 75, 76, 79, 57, 56 }},
    /* 'o' */ { 79 , { 56, 73, 75, 76, 186, 80, 48, 57 }},
    /* 'p' */ { 80 , { 57, 79, 76, 186, 222, 219, 189, 48 }},
    /* '[' */ { 219 , { 48, 186, 222, 221, 187, 189 }},
    /* ']' */ { 221 , { 189, 219, 187 }},
    /* 'a' */ { 65 , { 81, 87, 83, 88, 90 }},
    /* 's' */ { 83 , { 81, 65, 90, 88, 67, 68, 69, 87, 81 }},
    /* 'd' */ { 68 , { 87, 83, 88, 67, 86, 70, 82, 69 }},
    /* 'f' */ { 70 , { 69, 68, 67, 86, 66, 71, 84, 82 }},
    /* 'g' */ { 71 , { 82, 70, 86, 66, 78, 72, 89, 84 }},
    /* 'h' */ { 72 , { 84, 71, 66, 78, 77, 74, 85, 89 }},
    /* 'j' */ { 74 , { 89, 72, 78, 77, 188, 75, 73, 85 }},
    /* 'k' */ { 75 , { 85, 74, 77, 188, 190, 76, 79, 73 }},
    /* 'l' */ { 76 , { 73, 75, 188, 190, 191, 186, 80, 79 }},
    /* ';' */ { 186 , { 79, 76, 190, 191, 222, 219, 80 }},
    /* '\''*/ { 222 , { 80, 186, 191, 221, 219 }},
    /* 'z' */ { 90 , { 65, 83, 88 }},
    /* 'x' */ { 88 , { 90, 65, 83, 68, 67 }},
    /* 'c' */ { 67 , { 88, 83, 68, 70, 86 }},
    /* 'v' */ { 86 , { 67, 68, 70, 71, 66 }},
    /* 'b' */ { 66 , { 86, 70, 71, 72, 78 }},
    /* 'n' */ { 78 , { 66, 71, 72, 74, 77 }},
    /* 'm' */ { 77 , { 78, 72, 74, 75, 188 }},
    /* '<' */ { 188 , { 77, 74, 75, 76, 190 }},
    /* '>' */ { 190 , { 188, 75, 76, 186, 191 }},
    /* '?' */ { 191 , { 190, 76, 186, 222 }},
};
map<char, int> code_keys_eng
{
        { '`', 192 },
        { '1', 49   },
        { '2', 50   },
        { '3', 51   },
        { '4', 52   },
        { '5', 53   },
        { '6', 54   },
        { '7', 55   },
        { '8', 56   },
        { '9', 57   },
        { '0', 48   },
        { '-', 189  },
        { '=', 187  },
        { 'q', 81   },
        { 'w', 87   },
        { 'e', 69   },
        { 'r', 82   },
        { 't', 84   },
        { 'y', 89   },
        { 'u', 85   },
        { 'i', 73   },
        { 'o', 79   },
        { 'p', 80   },
        { '[', 219  },
        { ']', 221  },
        { 'a', 65   },
        { 's', 83   },
        { 'd', 68   },
        { 'f', 70   },
        { 'g', 71   },
        { 'h', 72   },
        { 'j', 74   },
        { 'k', 75   },
        { 'l', 76   },
        { ';', 186  },
        { '\'', 222 },
        { 'z', 90   },
        { 'x', 88   },
        { 'c', 67   },
        { 'v', 86   },
        { 'b', 66   },
        { 'n', 78   },
        { 'm', 77   },
        { ',', 188  },
        { '.', 190  },
        { '/', 191  },

        { '~' , 192 },
        { '!' , 49  },
        { '@' , 50  },
        { '#' , 51  },
        { '$' , 52  },
        { '%' , 53  },
        { '^' , 54  },
        { '&' , 55  },
        { '*' , 56  },
        { '(' , 57  },
        { ')' , 48  },
        { '_' , 189 },
        { '+' , 187 },

        { '{', 219  },
        { '}', 221  },
        { ':', 186  },
        { '"', 222  },

        { '<', 188  },
        { '>', 190  },
        { '?', 191  },
};
vector<string> phonetic_groups
{
    { "aeiouy", "bp", "ckq", "dt", "lr", "mn", "gj", "fpv", "sxz", "csz" }
};


size_t CostDistanceSymbol(const char& source_symbol, const char& target_symbol)
{
    if (source_symbol == target_symbol)
        return 0;
    size_t distance_cost = 2;
    if (distance_code_key[code_keys_eng[source_symbol]].empty())
        distance_cost = 2;
    vector<int> list = distance_code_key[code_keys_eng[source_symbol]];
    for (int i = 0; i < list.size(); i++)
    {
        if (list[i] == code_keys_eng[target_symbol])
        {
            distance_cost = 1;
            break;
        }
    }
    size_t phonetic_cost = 2;
    for (int i = 0; i < phonetic_groups.size(); i++)
    {
        if (phonetic_groups[i].find(source_symbol) != -1 && phonetic_groups[i].find(target_symbol) != -1)
        {
            phonetic_cost = 1;
            break;
        }
    }
    return min(distance_cost, phonetic_cost);
}

size_t LevenstainDistanceUpgrade(const string& source, const string& target)
{
    if (source.empty())
    {
        return target.size() * add_cost;
    }
    int N = source.size(), M = target.size();
    vector<vector<int>> Dist(N + 1, vector<int>(M + 1, 0));
    for (int j = 1; j <= M; j++)
    {
        Dist[0][j] = Dist[0][j - 1] + add_cost;
    }
    for (int i = 1; i <= N; i++)
    {
        Dist[i][0] = Dist[i - 1][0] + delete_cost;
        for (int j = 1; j <= M; j++)
        {
            //int cur_swap_cost = CostDistanceSymbol(source[i], target[j]);
            int cur_swap_cost = (RegisterMerge(source[i - 1]) == RegisterMerge(target[j - 1]) ? 0 : swap_cost);
            Dist[i][j] = min(Dist[i - 1][j] + delete_cost,
                min(Dist[i][j - 1] + add_cost, Dist[i - 1][j - 1] + cur_swap_cost));
            if (i > 1 && j > 1)
            {
                if (RegisterMerge(source[i]) == RegisterMerge(target[j - 1]) && RegisterMerge(source[i - 1]) == RegisterMerge(target[j]))
                    Dist[i][j] = min(Dist[i][j], Dist[i - 2][j - 2] + transposition_cost);
            }
        }
    }
    return Dist[N][M];
}

double GetRangeWord(const string& source, const string& target)
{
    double word_distance = MAXINT;
    int length = min(source.size() + 1, target.size());
    for (int i = 0; i <= target.size() - length; i++)
    {
        string cropped_target = target.substr(i, length);
        word_distance = min((LevenstainDistanceUpgrade(source, cropped_target) + (i * 2 / 10.0)), word_distance);
    }
    return word_distance;
}

double GetRange(const string& source, const string& target)
{
    if (source.size() <= 3)//в этом случае просто наивные вхождения смотрим
    {
        int pos = RegisterStrMerge(target).find(RegisterStrMerge(source));
        if (pos != -1)
            return (pos * 2 / 10.0);
        else
            return MAXINT;
    }
    vector<string> source_word_list = GetList(source, ' ');
    vector<string> target_word_list = GetList(target, ' ');
    if (source_word_list.empty())
    {
        int distance = 0;
        for (int i = 0; i < target_word_list.size(); i++)
        {
            distance += (target_word_list[i].size() * add_cost * magic_coefficient);
        }
    }
    double distance = 0;
    for (int i = 0; i < source_word_list.size(); i++)
    {
        double min_word_distance = MAXINT;
        int min_pos = 0;
        for (int j = 0; j < target_word_list.size(); j++)
        {
            double cur_word_distance = GetRangeWord(source_word_list[i], target_word_list[j]);
            if (cur_word_distance < min_word_distance)
            {
                min_word_distance = cur_word_distance;
                min_pos = j;
            }
        }
        distance += (min_word_distance * magic_coefficient + abs(i - min_pos) / 10.0);
    }
    return distance;
}

Общие данные вначале (2 вектора и мапа) в алгоритме отключены.


Ответы (0 шт):