0

Code given below is not executed completely;
I have looked for everything on web but I don't know why it is working for starting numbers from nums (i.e. 1000 and sometimes 5000) and after that it starts execution but in between program terminates itself and stopes working.

#include <bits/stdc++.h>
// #include <iostream>
// #include <chrono>
// #include <vector>

#define UPPER_LIMIT 10

using namespace std;
using namespace std::chrono;

bool inTimeLimit = true;
bool isFinished = false;
bool isRunning = true;

class Timer {
public:
    time_point<high_resolution_clock> start, end;

    Timer() {
        start = high_resolution_clock::now();
    }

    ~Timer() {
        end = high_resolution_clock::now();
        auto durationTime = durationCounter();

        cout << "\n\nTaken time Duration " << (unsigned long long)durationTime << " us; " << (unsigned long long)durationTime * 0.001  << "ms.";
    }

    float durationCounter() {
        auto currTime = high_resolution_clock::now();
        auto durationTime = duration_cast<microseconds>(currTime - start);

        return durationTime.count();
    }
};


void printVector(vector <int> v) {
    cout << endl;
    for (int x : v) {
        cout << setw(3) << x << " ";
    }
}

void printVectorToFile(ofstream &fout , vector <int> v, string msg) {


    fout << "\n\n===================\n\n";
    fout << msg << endl;
    fout << endl;
    for (int x : v) {
        fout << setw(5) << x << " ";
    }
    fout << endl;
}

void swap (int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

vector <int> randomArrayGenerator(int n) {

    vector<int> v(n);
    for (int i = 0; i < n; ++i)
        v[i] = i + 1;

    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        int pos = rand() % n;
        swap(&v[i], &v[pos]);
    }

    return v;
}

string sortingChecker(vector<int> v) {
    for (int i = 0; i < (int)v.size() - 1; ++i)
    {
        if (v[i] > v[i + 1])    return "false";
    }
    return "true";
}

bool sortChecker(vector<int> v) {
    for (int i = 0; i < (int)v.size() - 1; ++i)
    {
        if (v[i] > v[i + 1])    return false;
    }
    return true;
}


// Merge function

void merge(vector <int> &v, int begin, int middle, int end) {
    vector <int> left, right;

    for (int i = begin; i < middle + 1; ++i)
    {
        left.push_back(v[i]);
    }
    for (int i = middle + 1; i <= end; ++i)
    {
        right.push_back(v[i]);
    }


    int p1 = 0, p2 = 0, n1 = left.size(), n2 = right.size(), p = begin;
    while ((p1 < n1 ) || (p2 < n2)) {
        if ((p1 != n1 ) && ((p2 == n2) || left[p1] < right[p2]))
            v[p++] = left[p1++];
        else
            v[p++] = right[p2++];
    }

}


void mergeSortByIteration(vector <int> &v, bool &isTimeDelayed) {

    int low = 0, high = v.size();
    cout << "Thread ID: " << this_thread::get_id() << endl;
    // n :for taking individual block of vector containing number of elements n=[1,2,4,8,..]
    for (int n = 1; n < high; n *= 2) {
        if (isTimeDelayed) return;
        // taking block according to n and then sorting them by merge function
        // n=1 => i=0,2,4,8,16
        // n=2 => i=0,4,8
        for (int i = 0; i < high; i += 2 * n) {
            if (isTimeDelayed) return;
            int begin = i;
            int mid =  i + n - 1;
            int end = min(i + 2 * n - 1 , high - 1);

            merge(v, begin, mid, end);
        }

    }

}

// Merge by recurision

void mergeSortByRecursion (vector <int> &v, int begin, int end, bool &isTimeDelayed) {
    if (end <= begin || isTimeDelayed) return;
    int middle = begin + (end - begin) / 2;
    mergeSortByRecursion(v, begin, middle, isTimeDelayed);
    mergeSortByRecursion(v, middle + 1, end, isTimeDelayed);
    merge(v, begin, middle, end);

}


int main() {

    int nums[] = {1000, 5000, 10000, 50000, 100000};

    // int nums[] = {50000};
    ofstream vectorOutput ;
    vectorOutput.open("outputTexts\\prac1_resultedArrays.txt", ios::trunc);;
    for (int n : nums)
// ``````` Merge by Iteration ````````
    {
        vector<int> num, arr = randomArrayGenerator(n);
        cout << "\n=======";
        cout << "\n\nMerge by Iteration:" << endl;
        num = arr;


        cout << "Array size: " << num.size() << endl;

        bool isTimeOut = false, isSorted = false;
        Timer timer;

        std::thread worker(mergeSortByIteration, ref(num), ref(isTimeOut));

        // mergeSortByIteration(num, isTimeOut);

        // std::thread worker(mergeSortByRecursion, ref(num), 0, n - 1, ref(isTimeOut));


        while ( ( ( timer.durationCounter() / 1000000 ) < 5) && (!isSorted ) ) {
            // this_thread::sleep_for(seconds(1));
            // cout  << timer.durationCounter()  << " ";
            isSorted = sortChecker(num);
        }

        if ( ( ( ( timer.durationCounter() / 1000000 ) > 5) && (!isSorted ) ) )
        {
            isTimeOut = true;
            cout << endl << "!!!!!Execution Terminated ---- Time Limit reached!!!!!!" << endl;
        }

        if (worker.joinable())
            worker.join();

        printVector(num);

        cout << "\nCheck result for sorted Vector:" << (isSorted ? "true" : "false") << endl;

        // printVectorToFile(vectorOutput, num, "Merge By Iteration for size:" + to_string(n) );

    }

    cout << "\n\ndone" << endl;

    return 0;
}

can anyone help me out here? If issue is not clear fill free to ask.

  • 2
    You're copying `num` while it's being sorted by a different thread. This will inevitably cause problems sooner or later, and at seemingly random times. – molbdnilo Aug 23 '21 at 07:39
  • 2
    Did you try to debug it? Consider running it under thread sanitizer - add `-fsanitize=thread` to GCC,Clang. It is an amazing tool for these sorts of bugs. – Quimby Aug 23 '21 at 07:39
  • @molbdnilo It is data race, but in practice, it should not cause program crash. At least on most modern architectures where aligned reads/writes (`num` elements) are always atomic. I don't see any resizing of `num` in the threaded region. – Daniel Langr Aug 23 '21 at 07:46
  • 1
    Read [Why should I not #include ?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – n. m. could be an AI Aug 23 '21 at 08:05
  • Your `mid` calculation is wrong, you can and do get `mid > end`. – n. m. could be an AI Aug 23 '21 at 08:25
  • I have add join() call through which main will wait so.. but thank you for response @molbdnilo – TDTejani Sherlock Aug 23 '21 at 09:20
  • @Quimby can you suggest me how to use this feature? – TDTejani Sherlock Aug 23 '21 at 09:24
  • @DanielLangr I aggree, but still programme is not working correctly... can you try it and check if it is running – TDTejani Sherlock Aug 23 '21 at 09:26
  • @TDTejaniSherlock As I said, all that needs to be done is to add `-fsanitize=thread` to the compiler flags. The program will then print any errors during its execution, like valgrind but much faster. Works with gcc, Clang, not with Visual studio. See [thread sanitizer](https://clang.llvm.org/docs/ThreadSanitizer.html). – Quimby Aug 23 '21 at 09:42
  • @Quimby $:g++ src\sample.cpp -o bin\sample.exe -Wall -fsanitize=thread && bin\sample src\sample.cpp: In function 'void mergeSortByIteration(std::vector&, bool&)': src\sample.cpp:126:6: warning: unused variable 'low' [-Wunused-variable] 126 | int low = 0, high = v.size(); | ^~~ C:/msys64/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/10.3.0/../../../../x86_64-w64-mingw32/bin/ld.exe: cannot find -ltsan collect2.exe: error: ld returned 1 exit status – TDTejani Sherlock Aug 23 '21 at 09:47
  • @TDTejaniSherlock Oh, apparently mingw does not support it either, [see](https://sourceforge.net/p/tdm-gcc/bugs/195/). Sorry for misleading you, I do not have much experience with Windows development environments. – Quimby Aug 23 '21 at 09:50
  • 1
    The crash is not because of the threads. It is because of invalid index calculations. [Demo](https://godbolt.org/z/9KPs5P6sK) Any thread errors are in addition to that. Another common failure reason is `using namespace std;` in conjunction with user-defined function names `sort`, `swap` etc. – n. m. could be an AI Aug 23 '21 at 10:47
  • @Quimby is through -fsanitize programe works completely... – TDTejani Sherlock Aug 23 '21 at 14:40

0 Answers0