c++ - 当我在并行合并排序中增加 vector 的大小时出现段错误

标签 c++ c++11 parallel-processing segmentation-fault mergesort

当我尝试使用 2 个线程和超过 450 万的大小运行程序时，它会产生段错误。低于该数字的任何内容都可以顺利运行。简而言之，非常大的数字会产生段错误，我不知道为什么。我想知道错误是否与线程创建或线程的工作分配有关。一些帮助将不胜感激。下面是代码。

#include <iostream>
#include <thread>
#include <vector>
#include <chrono>
#include <ctime>
#include <algorithm>

/* define variables for the problem */
#define UPPER_LIM 10
#define LOWER_LIM  1

using namespace std;

/* function definitions */

int generate_random_number(unsigned int lower_limit, unsigned int upper_limit);
void merge_sort(vector<int>& array, int left, int right);
void merge(vector<int>& array, int left, int middle, int right);
void thread_merge_sort(vector<int>& array, int thread_id, int n, int p, int q);
bool isTest_array_is_in_order(vector<int>& array, int LENGTH);

int main(int argc, const char *argv[]) {
    int NUM_THREADS = atoi(argv[1]);
    int LENGTH = atoi(argv[2]);
    int NUMBERS_PER_THREAD = LENGTH / NUM_THREADS;
    int OFFSET = LENGTH % NUM_THREADS;

    srand(time(0));

    std::vector<int> array;
    array.reserve(LENGTH);

    /* initialize array with random numbers */
    for (int i = 0; i < LENGTH; i++) {
        array.push_back(generate_random_number(LOWER_LIM, UPPER_LIM));
    }

    /* begin timing */
    auto start = std::chrono::high_resolution_clock::now();

    const size_t nthreads = NUM_THREADS; //std::thread::hardware_concurrency();
    {
        // Pre loop
        std::cout << "parallel(" << nthreads << " threads):" << std::endl;
        std::vector<std::thread> workers;

        for (std::size_t t = 0; t < nthreads; t++) {
            workers.push_back(thread(thread_merge_sort, ref(array), t, nthreads, NUMBERS_PER_THREAD, OFFSET));
        }

        for (thread& t: workers) { // await thread termination
            t.join();
        }
    }

    auto elapsed = std::chrono::high_resolution_clock::now() - start;
    auto usec    = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();

    // and print time
    std::cout << "Spent " << usec << " executing  " << nthreads << " in parallel " << " array size " << LENGTH << std::endl;

    /* end timing */

    /* test to ensure that the array is in sorted order */
    if (!isTest_array_is_in_order(array, LENGTH)) {
        fprintf(stderr, "Error: array is not sorted!!\n");
        return 0;
    }
}

/* generate random numbers within the specified limit */
int generate_random_number(unsigned int lower_limit, unsigned int upper_limit) {
    //srand(time(NULL));
    return lower_limit + (upper_limit - lower_limit) * ((double)rand() / RAND_MAX);
}

/** assigns work to each thread to perform merge sort */
void thread_merge_sort(vector<int> &arr, int thread_id, int NUM_THREADS, int NUMBERS_PER_THREAD, int OFFSET) {
    int left = thread_id * (NUMBERS_PER_THREAD);
    int right = (thread_id + 1) * (NUMBERS_PER_THREAD) - 1;
    if (thread_id == NUM_THREADS - 1) {
        right += OFFSET;
    }
    int middle = left + (right - left) / 2;
    if (left < right) {
        merge_sort(arr, left, right);
        merge_sort(arr, left + 1, right);
        merge(arr, left, middle, right);
    }
}

/* test to ensure that the array is in sorted order */
bool isTest_array_is_in_order(vector<int>& arr, int LENGTH) {
    for (int i = 1; i < LENGTH; i++) {
        if (arr[i] >= arr[i - 1]) {
            return true;
        } else {
            return false;
        }
    }
}

/* perform merge sort */
void merge_sort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        merge_sort(arr, left, middle);
        merge_sort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

/* merge function */
void merge(vector<int>& arr, int left, int middle, int right) {
    int i = 0;
    int j = 0;
    int k = 0;
    int left_length = middle - left + 1;
    int right_length = right - middle;
    int left_array[left_length];
    int right_array[right_length];

    /* copy values to left array */
    for (int i = 0; i < left_length; i++) {
        left_array[i] = arr[left + i];
    }

    /* copy values to right array */
    for (int j = 0; j < right_length; j++) {
        right_array[j] = arr[middle + 1 + j];
    }

    i = 0;
    j = 0;
    /** chose from right and left arrays and copy */
    while (i < left_length && j < right_length) {
        if (left_array[i] <= right_array[j]) {
            arr[left + k] = left_array[i];
            i++;
        } else {
            arr[left + k] = right_array[j];
            j++;
        }
        k++;
    }
    /* copy the remaining values to the array */
    while (i < left_length) {
        arr[left + k] = left_array[i];
        k++;
        i++;
    }
    while (j < right_length) {
        arr[left + k] = right_array[j];
        k++;
        j++;
    }
}

最佳答案

因此，首先，我将您的 merge_sort 和合并 stub ，运行 2 个任务和 4500000 个元素:没有段错误。

对于完整的调试，您可以考虑提供完整的代码...

这是我的编译，稍作修改的代码:

    #include <iostream>
    #include <thread>
    #include <vector>
    #include <chrono>
    #include <ctime>
    #include <cstdint>
    #include <algorithm>

    #include <thread>

    /* define variables for the problem */
    constexpr size_t const UPPER_LIM = 10;
    constexpr size_t const LOWER_LIM =  1;

    using namespace std;

    /* function definitions */

    void merge_sort(vector<int>& array, int left, int right){
      return;
    }

    void merge(vector<int>& array, int left, int middle, int right){
      return;
    }

    bool isTest_array_is_in_order(vector<int>& array, int LENGTH){
      return false;
    }

    /**
     * generate random numbers within the specified limit
     */
    int generate_random_number(unsigned int lower_limit, unsigned int upper_limit){
      return lower_limit + (upper_limit - lower_limit) * ((double)rand() / RAND_MAX);
    }

    /**
     * assigns work to each thread to perform merge sort
     */
    void thread_merge_sort(vector<int> &arr, int thread_id, int NUM_THREADS, int NUMBERS_PER_THREAD, int OFFSET){
      int left = thread_id * (NUMBERS_PER_THREAD);
      int right = (thread_id + 1) * (NUMBERS_PER_THREAD) - 1;
      if (thread_id == NUM_THREADS - 1) {
        right += OFFSET;
      }
      int middle = left + (right - left) / 2;
      if (left < right) {
        merge_sort(arr, left, right);
        merge_sort(arr, left + 1, right);
        merge(arr, left, middle, right);
      }
    }

    int main(int argc, const char * argv[]){

      int const NUM_THREADS        = 2; //atoi (argv[1]);
      int const LENGTH             = 4500000; //atoi(argv[2]);
      int const NUMBERS_PER_THREAD = LENGTH / NUM_THREADS;
      int const OFFSET             = LENGTH % NUM_THREADS;

      cout << sizeof(int) << "\n";

      srand(time(0)) ;

      std::vector<int> array;
      array.reserve(LENGTH);

      /* initialize array with random numbers */
      for(int ii=0; ii < LENGTH; ++ii){
        array.push_back(generate_random_number(LOWER_LIM, UPPER_LIM));
      }

      /* begin timing */
      auto start = std::chrono::high_resolution_clock::now();

      const size_t nthreads = NUM_THREADS; //std::thread::hardware_concurrency();
      {
        // Pre loop
        std::cout<<"parallel ("<<nthreads<<" threads):"<<std::endl;
        std::vector<std::thread> workers;

        for(std::size_t tt=0; tt<nthreads; ++tt){
          workers.push_back(thread(thread_merge_sort, ref(array), tt, nthreads, NUMBERS_PER_THREAD, OFFSET));
        }

        // await thread termination
        for(thread& t: workers) {
          t.join();
        }
      }

      auto elapsed = std::chrono::high_resolution_clock::now() - start;
      auto usec    = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();

      // and print time
      std::cout << "Spent " << usec << " executing  " << nthreads << " in parallel " << " array size " << array.size() << "\n";

      /* end timing */
      return 0;
    }

[编辑]:

您的 isTest_array_is_in_order 无法工作，因为您在比较前两个元素后返回。

    bool isTest_array_is_in_order(vector<int>& arr, int LENGTH)
    {
        for(int i=1;i<LENGTH;i++){
            if(arr[i]>=arr[i-1]){
                return true;
    }   else{

        return false;
        }

        }
    }

这是一个应该工作的版本:

    /**
     * test to ensure that the array is in sorted order
     */
    bool isTest_array_is_in_order(vector<int>& arr, int LENGTH){
      bool unorderd = false;
      for(int ii=1;ii<LENGTH;++ii){
        if(arr[ii]<arr[ii-1]){
          unorderd = true;
          break;
        }
      }
      return !unorderd;
    }

[编辑]:

因此，起初使用您的代码，我能够确认您的段错误

我更改了代码，现在它似乎运行得很好
刚刚为 44999999 个元素测试了 16 个线程，效果很好

查看您的代码后，它就在这里崩溃了:

    /* merge function */
    void merge(vector<int>& arr, int left, int middle, int right) {
        int i = 0;
        int j = 0;
        int k = 0;
        int left_length = middle - left + 1;
        int right_length = right - middle;
        int left_array[left_length];
        int right_array[right_length];

在这里，您创建了 2 个本地数组，但在堆栈上，而不是在堆上。
堆栈通常会根据您的操作系统限制在 10 左右的低 MB 范围内。

所以我用 vector 替换了你的 C 数组，并进一步优化了代码:更精细的类型，改变了主要类型，所以我现在可以一次运行对不同的随机变体进行排序。

所以这是我现在的代码:

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <cstdint>
#include <thread>
#include <chrono>
#include <ctime>
#include <iterator>
#include <vector>
#include <array>
#include <random>
#include <algorithm>

using namespace std;

using idx_t  = size_t;
using data_t = int;

/* define variables for the problem */
constexpr data_t const UPPER_LIM =  2000000;
constexpr data_t const LOWER_LIM = 0;

constexpr idx_t const REPEAT_CNT = 10000;

/* function definitions */
std::string to_array_str(vector<data_t>& arr, idx_t max_elem){
  std::stringstream ss;

  idx_t ii=1;
  idx_t cnt = 0;

  for(auto _d:arr){
    ss << setw(8) << _d;
    if(0==(ii%10)){
      ss << ",\n";
      ii=0;
    }else{
      ss << ", ";
    }
    if(cnt>=max_elem) break;
    ++ii;
    ++cnt;
  }
  return ss.str();
}

/**
 * generate random numbers within the specified limit
 */
data_t generate_random_number(data_t const lower_limit, data_t const upper_limit){
  static std::random_device rd;
  static std::mt19937 gen(rd());
  static std::uniform_int_distribution<data_t> dis(lower_limit, upper_limit);
  return dis(gen);
  //return lower_limit + (upper_limit - lower_limit) * ((double)rand() / RAND_MAX);
}

/**
 * test to ensure that the array is in sorted order
 */
bool isTest_array_is_in_order(vector<data_t>& arr){
  bool unorderd = false;
  for(idx_t ii=1;ii<arr.size();++ii){
    if(arr[ii]<arr[ii-1]){
      unorderd = true;
      cout << "unordered Index: " << ii << "\n";
      cout << "arr[ii] " << arr[ii] << " arr[ii-1] " << arr[ii-1] << "\n";

      break;
    }
  }
  return !unorderd;
}

/**
 * merge function
 */
void merge(vector<data_t>& arr, idx_t const left, idx_t const middle, idx_t const right) {
  idx_t const  left_length = middle - left + 1;
  idx_t const right_length = right - middle;
  vector<data_t>  left_array( left_length);
  vector<data_t> right_array(right_length);

  constexpr bool const use_loopcopy = true;
  if(use_loopcopy){
  /* copy values to left array */
  for(idx_t ii=0; ii < left_length; ++ii){
      left_array[ii] = arr[left + ii];
  }
  /* copy values to right array */
  for(idx_t ii=0; ii < right_length; ++ii){
    right_array[ii] = arr[middle + 1 + ii];
  }
  }

  constexpr bool const use_libcode = false;
  if(use_libcode){
  {
    auto from =  arr.begin();
    auto to   = from;
    std::advance(from,left);
    std::advance(to,middle+1);
    std::copy(from,to,left_array.begin());
  }
  {
    auto from = arr.begin();
    auto to   = from;
    std::advance(from,middle+1);
    std::advance(to,right+1);
    std::copy(from,to,right_array.begin());
  }
  }

  idx_t ii = 0;
  idx_t jj = 0;
  idx_t kk = 0;
  /** chose from right and left arrays and copy */
  while((ii < left_length) && (jj < right_length)){
    if(left_array[ii] <= right_array[jj]){
      arr[left + kk] = left_array[ii];
      ++ii;
    } else {
      arr[left + kk] = right_array[jj];
      ++jj;
    }
    ++kk;
  }

  /* copy the remaining values to the array */
  while(ii < left_length){
    arr[left + kk] = left_array[ii];
    ++kk;
    ++ii;
  }

  while(jj < right_length){
    arr[left + kk] = right_array[jj];
    ++kk;
    ++jj;
  }
  return;
}

/**
 * perform merge sort
 */
void merge_sort(vector<data_t>& arr, idx_t const left, idx_t const right) {
  if(left < right){
    idx_t middle = left + ((right - left)>>1);
    //Divide
    merge_sort(arr, left, middle);
    merge_sort(arr, middle + 1, right);
    //Conquer
    merge(arr, left, middle, right);
  }
  return;
}

/**
 * assigns work to each thread to perform merge sort
 */
void thread_merge_sort(vector<data_t>& arr, idx_t const thread_id, idx_t const NUM_THREADS, idx_t const NUMBERS_PER_THREAD, idx_t const OFFSET){
  idx_t left  =  thread_id * (NUMBERS_PER_THREAD);
  idx_t right = (thread_id + 1) * (NUMBERS_PER_THREAD) - 1;
  if(thread_id == (NUM_THREADS - 1)) {
    right += OFFSET;
  }
  merge_sort(arr,left,right);
  return;
}

int main(int argc, const char * argv[]){

  /*
  int const NUM_THREADS        = 16; //atoi (argv[1]);
  int const LENGTH             = 1000000000; //atoi(argv[2]);
  */
  /*
  int const NUM_THREADS        = 8; //atoi (argv[1]);
  int const LENGTH             = 449999; //atoi(argv[2]);
  */
  int const NUM_THREADS        = 8; //atoi (argv[1]);
  int const LENGTH             = 100; //atoi(argv[2])

  int const NUMBERS_PER_THREAD = LENGTH / NUM_THREADS;
  int const OFFSET             = LENGTH % NUM_THREADS;

  cout << sizeof(int) << "\n";

  //srand(time(0)) ;

  std::vector<int> array(LENGTH);
  //array.reserve(LENGTH);

  constexpr size_t  nthreads = NUM_THREADS; //std::thread::hardware_concurrency();
  std::cout<<"parallel ("<<nthreads<<" threads):"<<std::endl;


  uint64_t time = 0;
  bool ordered = true;
  for(idx_t ii=0; ii<REPEAT_CNT; ++ii){

    /* initialize array with random numbers */
    for(int ii=0; ii < LENGTH; ++ii){
      //array.push_back(generate_random_number(LOWER_LIM, UPPER_LIM));
      array[ii]=(generate_random_number(LOWER_LIM, UPPER_LIM));
    }

    /* begin timing */
    auto start = std::chrono::high_resolution_clock::now();

    {
      // Pre loop
      std::vector<std::thread> workers;

      for(std::size_t tt=0; tt<nthreads; ++tt){
        workers.push_back(thread(thread_merge_sort, ref(array), tt, nthreads, NUMBERS_PER_THREAD, OFFSET));
      }

      // await thread termination
      for(thread& t: workers) {
        t.join();
      }

      ordered &= isTest_array_is_in_order(array);
      if(!ordered) break;
    }

      auto elapsed = std::chrono::high_resolution_clock::now() - start;
      auto usec    = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
      time = (usec + time)>>1;
  }

  // and print time
  //cout << "Spent " << usec << "[µs] executing " << nthreads << " Threads in parallel working on " << array.size() << " elements " << "\n";
  cout << "Spent " << time << "[µs] executing " << nthreads << " Threads in parallel working on " << array.size() << " elements " << "\n";

  //cout << "Result is ordered: " << isTest_array_is_in_order(array) << "\n";
  cout << "Result is ordered: " << ordered << "\n";

  cout << to_array_str(array,100) << "\n";

  return 0;
}

但是，即使该代码现在不再导致段错误，使用不同的参数，事实证明，
除了单线程运行之外，它几乎不会产生排序数组。
所以 chqrlie 的分析是正确的，因为单线程的排序部分也需要排序。

关于c++ - 当我在并行合并排序中增加 vector 的大小时出现段错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60549511/

上一篇：c++ - 如何为静态类模板特化模拟构造函数？

下一篇：c++ - extern和extern “C”用于变量

相关文章：

C++: Operator= 多态性重载

parallel-processing - 用于混合分布式和共享内存的混合 OpenMP + OpenMPI？

c++ - 并行程序中的 Multimap 或排序 vector

c++ - 返回对 const 类型的 const 指针的引用

c++ - 预编译头文件的行为导致错误

c++ - 派生可变参数类模板的调用函数模板重载

c++11 - 使用 cmake 构建和打包 LLVM clang 3.4

c++ - 为什么数组的类型推导优先于对数组的引用优先指针？

c - 如何在 openmp 中并行化 while 循环 - 共轭梯度

c++ - 如何包装 C++ 函数？

©2024 IT工具网  联系我们