4
\$\begingroup\$

for a thesis I am creating a program that constructs curling sequences. The curling number of a sequence is defined as 'the largest frequency of any period at the end of the sequence'. (For example, 11232323 has curling number 3, because 23 is repeated three times)

Currently, I am mostly interested in the appearance of a 1 as curling number, when the sequence is generated with any possible combination of 2's and 3's (for example, we generate 2322322 and want to find the first occurence of '1' as curling number).

I changed to multi-threading recently, but my performance lacks for what I need.

Does anyone have any suggestions on how to improve the speed of this multi-threaded program? I hope I provided enough comments to make it clear, but any questions will be answered.

#include <vector>
#include <iostream>
#include <chrono>
#include <thread>
#include <mutex>
#include <cmath>
#pragma warning (disable : 26451)
using namespace std::chrono;

const int range = 200;                          // used to reserve size for each sequence
std::mutex m_tail;                              // thread-lock for the tail
int tail = 0;                                   // value to keep track of the longest tail encountered
int length = 0;                                 // user input to define length of generator 

thread_local std::vector<short int> sequence(range);    // sequence for each individual thread
thread_local long double duur = 0;              // value for each individual thread to time functions


// this function finds the curling number (curl) of a sequence
// the curl of a sequence is defined as: the highest frequency of a period at the end of a sequence
// some examples:
// the curl of 11232323 is 3, because 23 is the most-repeated element at the end of the sequence
// the curl of 2222 is 4, because 2 is the most-repeated element at the end of the sequence
// the curl of 1234 is 1, because every period at the end of the sequence is repeated only once
int krul(short int j, short int last_curl) {
    short int curl = 1;                                     // the minimum curl of a sequence is 1
    for (short int length = 1; length <= int(j / (curl + 1) + 1); ++length) {
        short int freq = 1;                                 // the minimum frequency of any period is 1
        while ((freq + 1) * length <= j and std::equal(sequence.begin() + j - (freq + 1) * length, sequence.begin() + j - freq * length, sequence.begin() + j - length)) {
                                                            // while within length of the sequence, and while periods match, continue
            ++freq;                                         // if they match, the frequency is increased with 1
            if (freq > curl) {                              // if the frequency of this period is higher than the curl yet
                curl = freq;                                // update the value for curl
                if (curl > last_curl) {                     // mathematical break: the curl can't be 'last_curl + 2', so when we encounter 'last_curl + 1' we can stop
                    return curl;
                }
            }
        }
    }
    return curl;
}

// this function constructs a whole sequence by adding the curling number and then recalculating the curling number since the sequence got a new element
// and then adds the new curling number and recalculates and so on and so on
int constructor(std::vector<short int> sequence_generator) {
    sequence = (std::move(sequence_generator));             // we move the sequence from the generator to the main sequence
    short int j = length;
    short int last_curl = length;
    for (j; j <= range; ++j) {                              // the sequence is built from starting length to given range
        krul(j, last_curl);
        short int curl = krul(j, last_curl);                // the resulting curling number is the highest of all the candidate curling numbers.
        if (curl == 1) { return j; }                        // for this program, we want to stop if the curling number == 1 and return the length of the sequence (j)
        sequence[j] = curl;
        if (curl >= 4) { return j + 1; }                    // if the curling number >= 4, the next curling number is 1 so we can already break and return the length of the sequence (j + 1)
        last_curl = curl;                                   // we update the value of last_curl for the next calculation
    }
    return 0;                                               // we don't encounter this because each sequence breaks, but just in case we return 0
}

// this function takes a number and generates its binary twin, but then existing of 2's and 3's
// because we want every possible generator existing of any combination of 2's and 3's
// and after construction of the generator we call the constructor of the sequence
int decToBinary(unsigned long long n) {
    std::vector<short int> sequence_generator(range);
    for (long int i = length - 1; i >= 0; i--) {
        long int k = n >> i;
        if (k & 1) {
            sequence_generator[length - 1 - i] = 3;
        }
        else {
            sequence_generator[length - 1 - i] = 2;
        }
    }
    return (constructor(sequence_generator) - length);              // the 'tail' of the sequence is the total length ('j' of constructor) minus the length of the generator
}

// this function starts a thread and calls the decToBinary function for a range of sequences
void multi_threader(int thread_number, int thread_count) {
    std::cout << "thread " << thread_number << " initiated!" << std::endl;

    auto start_time = high_resolution_clock::now();                 // timer to keep track of elapsed time of thread
    int thread_tail = 0;                                            // value to keep track of maximum tail length of this thread
    
    unsigned long long start = (thread_number - 1) * pow(2, length) / (thread_count);   // start value for this thread
    unsigned long long stop = pow(2, length) / (thread_count)*thread_number;            // end value for this thread
    for (unsigned long long int i = start; i < stop; ++i) {
        auto start2 = high_resolution_clock::now();                                     // partial timer start

        int local_tail = decToBinary(i);                                                // tail of this sequence
        
        if (local_tail > thread_tail) {                                                 // if larger than any earlier tail in this sequence...
            thread_tail = local_tail;                                                   // update its value
        }
        auto stop2 = high_resolution_clock::now();                                      // partial timer end
        duur = duur + duration_cast<microseconds>(stop2 - start2).count();              // print elapsed partial time
    }
    
    {
        std::lock_guard<std::mutex> l(m_tail);                      // lock 'tail' while editing
        if (thread_tail > tail) {                                   // if largest tail in this thread is larger than any thread before...
            tail = thread_tail;                                     // update the value
        }
    }
    
    std::cout << duur / 1000 << std::endl;
    auto stop_time = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop_time - start_time).count() / 1000;
    std::cout << "thread " << thread_number << " exited, duration: " << duration << " ms, result " << thread_tail << std::endl;
}

// this function calls for as many threads as the user requests and passes the length the user requested on to the thread
void iterate_generator() {
    std::vector<std::thread> thread_vector;
    int thread_count, thread_number;
    thread_number = 0;
    std::cout << "enter the length for the sequence generator (e.g. 10, maximum 40)" << std::endl;
    std::cin >> length;
    length = 25;            // example value
    std::cout << "enter the desired number of threads (e.g. 2, maximum 4)" << std::endl;
    std::cin >> thread_count;
    thread_count = 4;       //example value

    // start the threads and join them
    for (int i = 0; i < thread_count; ++i) {
        ++thread_number;
        std::thread th = std::thread([thread_number, thread_count]() {multi_threader(thread_number, thread_count); });
        thread_vector.push_back(std::move(th));
    }

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


int main() {
    while (true) {
        iterate_generator();
        std::cout << tail << std::endl << std::endl;
    }
}

Thanks in advance!!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Great first question! The Code Review required format is somewhat unforgiving, but you met it on the first try. \$\endgroup\$
    – Reinderien
    Commented Nov 26, 2020 at 17:57

1 Answer 1

4
\$\begingroup\$

Here are my suggestions:

  • Don't use "cin >>". Use "getline(cin,str)" and write a parsing function. I typed "q", intending to quit the program, and it repeatedly started and joined threads and crashed with a "Resource temporarily unavailable" error.

  • Don't cap the number of threads at 4. My main box has 12 threads (6 cores, 2 per core), and I'm thinking of getting one with 144 threads (2 processors, 18 cores each, 4 per core). Use thread::hardware_concurrency() as a default, and make it configurable.

  • I ran it with 1 and 4 threads on length 15 (after commenting out the example values) and got 177 ms vs. (41,43,43,45) ms. This is not bad. The time with one thread should be close to the sum of the times with many threads (which is 172 ms), and it is.

  • As far as the locking goes, it is good. You have one mutex, and it protects a short piece of code.

  • I ran the program with length 23 and 4 threads and stopped it with the debugger. All worker threads were in the krul function at line 29. If there were a problem with multithreading, some threads would have been asleep or waiting for a lock. I suggest therefore that you try to improve the algorithm.

\$\endgroup\$
3
  • \$\begingroup\$ Thank you for taking the time to look at the program! As of yet, I didn't do any error handling, so cin can indeed easily crash the program. I will fix this. Next, the cap at 4 isn't functioning, that's some old text, sorry. I will probably implement hardware_concurrency, though! I do have a question: do you know a better way to use the thread_local sequence? Because when I switched from global to thread_local (because otherwise they mix results), I quadrupled the times... Oh.. and if you do get a 144-core box.. do you mind to run a calculation? ;) \$\endgroup\$ Commented Nov 27, 2020 at 9:40
  • \$\begingroup\$ I don't know much about thread_local. I use a runnable object (one with an operator() method) with local variables. Unless someone dumps a huge amount of money in my lap, it'll be months before I buy the box. It'll be a POWER box, so not directly comparable to the AMD box I'm on now. What compiler and OS are you using? This may affect performance; I've seen readers-writer locks behave differently on Linux and Windows. I develop on Linux, usually compiling with clang. \$\endgroup\$ Commented Nov 27, 2020 at 10:57
  • \$\begingroup\$ I'm using VS on Windows. I timed the mutex lock function and it is totally neglectable! \$\endgroup\$ Commented Nov 27, 2020 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.