многопоточность — C ++ / отладка (g ++ в AIX) рекурсивная быстрая сортировка, вызывающая ошибки сегментации

Question

многопоточность — C ++ / отладка (g ++ в AIX) рекурсивная быстрая сортировка, вызывающая ошибки сегментации

У меня есть программа, где мне нужно отсортировать большое количество больших числовых распределений. Чтобы сократить время, необходимое для этого, я пытаюсь сделать это многопоточным.

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

Распределения имеют одинаковое значение (то есть qsort будет работать как дерьмо)
Потоки включены.

мяу

#include <boost/thread/thread.hpp>
#include <vector>
#include <stdlib.h> // for rand()

void swapvals(double *distribution, const size_t &d1, const size_t &d2)
{
double temp = 0;
temp = distribution[d2];
distribution[d2] = distribution[d1];
distribution[d1] = temp;
//std::swap(distribution[d1], distribution[d2]);

}

size_t partition(double *distribution,  size_t left, size_t right)
{
const double pivot = distribution[right];

while (left < right) {

while ((left < right) && distribution[left] <= pivot)
left++;

while ((left < right) && distribution[right] > pivot)
right--;

if (left < right)
{
swapvals(distribution, left, right);
}
}
return right;
}

void quickSort(double *distribution, const size_t left, const size_t right)
{
if (left >= right) {
return;
}
size_t part = partition(distribution, left, right);
quickSort(distribution, left, part - 1);
quickSort(distribution, part + 1, right);
}
void processDistribution(double *distributions, const size_t distribution_size)
{

std::clog << "beginning qsorting." << std::endl;
quickSort(distributions, 0, distribution_size - 1);
std::clog << "done qsorting." << std::endl;

}

int main(int argc, char* argv[])
{
size_t distribution_size = 65000;
size_t num_distributions = 10;

std::vector<double *> distributions;

// Create num_distributions distributions.
for (int i = 0; i < num_distributions; i++)
{
double * new_dist = new double[distribution_size];
for (int k = 0; k < distribution_size; k++)
{
// Works when I have actual numbers in the distributions.
// Seg faults when all the numbers are the same.
new_dist[k] =1;
//new_dist[k] = rand() % 1000 + 1; // uncomment this, and it works.
}

distributions.push_back(new_dist);
}

// Submit each distribution to a quicksort thread.
boost::thread_group threads;
for (std::vector<double *>::const_iterator it=distributions.begin(); it != distributions.end(); ++it)
{
// It works when I run processDistribution directly. Segfaults when I run it via threads.
//processDistribution(*it, distribution_size);
threads.create_thread(boost::bind(&processDistribution, *it, distribution_size));
}
threads.join_all();

// Show the results of the sort for all the distributions.
for (std::vector<double *>::const_iterator it=distributions.begin(); it != distributions.end(); ++it)
{
for (size_t i = 0; i < distribution_size; i++)
{
// print first and last 20 results.
if (i < 20 || i > (distribution_size - 20))
std::cout << (*it)[i] << ",";
}
std::cout << std::endl;
}

}

GDB-анализ основного файла дает:

Error in re-setting breakpoint -1: aix-thread: ptrace (52, 18220265) returned -1 (errno = 3 The process does not exist.)
Error in re-setting breakpoint -1: aix-thread: ptrace (52, 18220265) returned -1 (errno = 3 The process does not exist.)
Error in re-setting breakpoint -2: aix-thread: ptrace (52, 18220265) returned -1 (errno = 3 The process does not exist.)
Error in re-setting breakpoint -3: aix-thread: ptrace (52, 18220265) returned -1 (errno = 3 The process does not exist.)
Core was generated by `testthreads'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x00000001000056bc in partition (distribution=0x1101d1430, left=0, right=63626) at testthreads.cpp:18

warning: Source file is more recent than executable.
18
(gdb) bt 7
#0  0x00000001000056bc in partition (distribution=0x1101d1430, left=0, right=63626) at testthreads.cpp:18
#1  0x0000000100005834 in quickSort (distribution=0x1101d1430, left=0, right=63626) at testthreads.cpp:42
#2  0x0000000100005850 in quickSort (distribution=0x1101d1430, left=0, right=63627) at testthreads.cpp:43
#3  0x0000000100005850 in quickSort (distribution=0x1101d1430, left=0, right=63628) at testthreads.cpp:43
#4  0x0000000100005850 in quickSort (distribution=0x1101d1430, left=0, right=63629) at testthreads.cpp:43
#5  0x0000000100005850 in quickSort (distribution=0x1101d1430, left=0, right=63630) at testthreads.cpp:43
#6  0x0000000100005850 in quickSort (distribution=0x1101d1430, left=0, right=63631) at testthreads.cpp:43
(More stack frames follow...)
(gdb) frame 0
#0  0x00000001000056bc in partition (distribution=0x1101d1430, left=0, right=63626) at testthreads.cpp:18
18
(gdb) info locals
pivot = 1
(gdb) info args
distribution = 0x1101d1430
left = 0
right = 63626
(gdb)

Кроме того, моя настоящая программа имеет дело со многими другими потоками и дистрибутивами. А проверки GDB там часто показывают гораздо более причудливые следы стека, которые выглядят как повреждение памяти (обратите внимание, как swapVals вызывается с d1 = 12119, но внутри фрейма стека раздела он проходит как 4568618016):

(gdb) bt 3
#0  0x00000001002aa0b8 in ScenRankReplacer<double>::swapvals (this=0xfffffffffffdfc8, distribution=..., d1=@0x1104c8178: 4568618016, d2=@0x1104c8140: 4568416720, ranking_values=0x1104c81d0,
r1=@0x1104c8170: 1152921504606838728, r2=@0x1002a16c8: 6917529029728344952) at ScenRankReplacer.h:96
#1  0x00000001002a7120 in ScenRankReplacer<double>::partition (this=0xfffffffffffdfc8, distribution=..., ranking_values=0x11069ae50, left=1, right=24237) at ScenRankReplacer.h:122
#2  0x00000001002a16c8 in ScenRankReplacer<double>::quickSort (this=0xfffffffffffdfc8, distribution=..., ranking_values=0x11069ae50, left=1, right=24237) at ScenRankReplacer.h:91
(More stack frames follow...)
(gdb) frame 1
#1  0x00000001002a7120 in ScenRankReplacer<double>::partition (this=0xfffffffffffdfc8, distribution=..., ranking_values=0x11069ae50, left=1, right=24237) at ScenRankReplacer.h:122
122             swapvals(distribution, mid, left, ranking_values, mid - 1, left - 1);
(gdb) p mid
$1 = 12119
(gdb) p left
$2 = 1

Итак … мои вопросы:

Я прав? Я бью лимит стека?
Как же я могу убедиться, что это так (кроме того, что я сделал выше)? Есть ли простой способ обнаружить это? подсказка GDB или что-то?
Почему поток имеет значение? Все темы делятся одинаково
лимит стека?
Самое важное: Как мне заставить это работать ?! Это
рекурсивная быстрая сортировка на массивных наборах данных просто неосуществима?

Ошибка возникает с уровнем компиляции O2.
Модель потока: AIX
gcc версия 4.8.3 (GCC)

2

aix c++debugging gcc multithreading

Решение

Другие решения

поэтому, немного потянув за волосы, я разобрался с ответами на мои вопросы.

Я прав? Я бью лимит стека? Как на земле я
убедиться, что это так (кроме вычета, который я сделал
выше)? А ТАКЖЕ
Есть ли простой способ обнаружить это? ключ GDB или
что-то?

A: Да. Программа переполняла стек. Я не мог установить прямой способ определить, что это имело место в AIX. Однако когда я поместил код в Visual Studio 2015 под Windows и запустил его, программа вылетела с явной ошибкой «переполнение стека».

Я надеялся, что есть способ получить явную ошибку «переполнения стека» в AIX, похожую на результат VS. Я не мог найти способ. Даже компиляция с использованием -fstack-check не дала мне ошибки хранения 🙁

Почему поток имеет значение? Все темы делятся
тот же лимит стека?

A: Размер стека по умолчанию для потоков в AIX удивительно мал!

Из этого блога IBM developerworks:

Для 32-разрядного скомпилированного приложения в AIX размер стека pthread по умолчанию составляет 96 КБ; и для 64-разрядного скомпилированного приложения в AIX,

Самое важное: как мне заставить это работать ?! Является
рекурсивная быстрая сортировка на массивных наборах данных просто невозможна?

Я могу представить себе только два пути:
A1: Первый — увеличить размер стека.

Из Руководства IBM по отладке потоков
Минимальный размер стека для потока составляет 96 КБ. Это также размер стека по умолчанию. Этот номер можно получить во время компиляции, используя символическую константу PTHREAD_STACK_MIN, определенную в заголовочном файле pthread.h.

Обратите внимание, что максимальный размер стека составляет 256 МБ, размер сегмента. Это ограничение указывается символической константой PTHREAD_STACK_MAX в заголовочном файле pthread.h.

Таким образом, можно увеличить размер стека до 256 МБ, что довольно много.

A2: Другой способ — просто избежать потенциально несвязанной рекурсии. Мои наборы данных невероятно большие. Вероятно, недостаточно большой, чтобы тратить 256 МБ стека, но было довольно просто переписать функцию быстрой сортировки итеративно.

void quickSort_iter(double *distribution, size_t left, size_t right)
{
if (left >= right)
return;

std::stack<std::pair<size_t, size_t> > partition_stack;
partition_stack.push(std::pair<size_t, size_t>(left, right));

while (!partition_stack.empty())
{

left = partition_stack.top().first;
right = partition_stack.top().second;
partition_stack.pop();

size_t pivot = partition(distribution, left, right);

if (pivot > 1)
partition_stack.push(std::pair<size_t, size_t>(left, pivot - 1));

if (pivot + 1 < right)
partition_stack.push(std::pair<size_t, size_t>(pivot + 1, right));
}
}

std :: stack создается с использованием стандартного std :: allocator, поэтому внутренне он использует выделения кучи для хранения стека сортирующих разделов и, следовательно, не будет работать вне предела стека.

0

Источник

Accepted Answer

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

Один из способов исправить это — удалить рекурсию и использовать несколько циклов и локальное хранилище для ее замены. Примерно такой (не скомпилированный или протестированный) код:

void quickSort(double *distribution, size_t left, size_t right) {
std::vector<std::pair<size_t, size_t>> ranges;
for (;;) {
for (;;) {
if (left <= right)
break;
size_t part = partition(distribution, left, right);

// save range for later to replace the second recursive call
ranges.push_back(std::make_pair(part + 1, right));

// set right == part - 1, then loop, to replace the first recursive call
right = part - 1;
}
if (ranges.empty())
break;

// Take top off of ranges for the next loop, replacing the second recursive call
left = ranges.back().first;
right = ranges.back().second;
ranges.pop_back();
}
}

1