threads.cpp

Go to the documentation of this file.

/* -*- coding: latin-1 -*- */
/** \file threads/threads/threads.cpp (January 6, 2018)
 *
 * GPLv3 --- Copyright (C) 2017, 2018 Olivier Pirson
 * http://www.opimedia.be/
 */

// \cond
#include <cassert>

#include <algorithm>
#include <thread>
// \endcond

#include "../../sequential/sequential/sequential.hpp"

#include "threads.hpp"


namespace threads {

  /* ***********
   * Functions *
   *************/

  std::set<nat_type>
  threads_check_gentle_varsigma_odd__by_range(unsigned int nb_thread,
                                              nat_type first_n, nat_type last_n,
                                              const std::set<nat_type> &previous_bad_table,
                                              bool print_bad,
                                              unsigned int range_size) {
    assert(nb_thread >= 1);
    assert(sigmaodd::is_odd(first_n));
    assert(3 <= first_n);
    assert(first_n <= last_n);
    assert(last_n <= sigmaodd::MAX_POSSIBLE_N);
    assert(sigmaodd::is_even(range_size));
#ifdef PRIME16
    assert(n < 65536);
#endif

    const nat_type bad_first_n = (previous_bad_table.empty()
                                  ? first_n
                                  : 0);

    std::set<nat_type> bad_table(previous_bad_table);

    std::set<nat_type>* new_bad_tables = new std::set<nat_type>[nb_thread]();  // empty-initialized
    std::thread* threads = new std::thread[nb_thread];  // threads[0] never used

    for (nat_type n = first_n; n <= last_n; ) {
      const nat_type bad_last_n = n - 1;

      // Start each slave thread on a range
      const nat_type master_n = n;
      unsigned int nb_slave_required = 0;

      n += range_size;  // reserve range for master thread

      for (unsigned int i = 1; (i < nb_thread) && (n <= last_n); ++i, n += range_size) {
        ++nb_slave_required;
        threads[i] = std::thread
          ([bad_first_n, bad_last_n, i, last_n, n, range_size,
            &bad_table, &new_bad_tables] {
            new_bad_tables[i]
              = sequential::sequential_check_gentle_varsigma_odd
                (n, std::min(n + range_size - 1, last_n),
                 bad_table,
                 bad_first_n, bad_last_n,
                 false);
          });
      }

      // Run on master thread
      new_bad_tables[0]
        = sequential::sequential_check_gentle_varsigma_odd
          (master_n, std::min(master_n + range_size - 1, last_n),
           bad_table,
           bad_first_n, bad_last_n,
           false);

      // Wait end of each slave thread
      for (unsigned int i = 1; i <= nb_slave_required; ++i) {
        threads[i].join();
      }

      // Update bad_table
      for (unsigned int i = 0; i < nb_thread; ++i) {
        if (!new_bad_tables[i].empty()) {  // new bad numbers identified
          bad_table.insert(new_bad_tables[i].cbegin(), new_bad_tables[i].cend());
          if (print_bad) {
            sequential::sequential_print_in_order(new_bad_tables[i]);
          }
          new_bad_tables[i].clear();
        }
      }
    }

    delete[] new_bad_tables;
    delete[] threads;

    return bad_table;
  }


  std::set<nat_type>
  threads_check_gentle_varsigma_odd__dynamic(unsigned int nb_thread,
                                             nat_type first_n, nat_type last_n,
                                             const std::set<nat_type> &previous_bad_table,
                                             bool print_bad,
                                             unsigned int range_size,
                                             unsigned int master_range_size) {
    assert(nb_thread >= 1);
    assert(sigmaodd::is_odd(first_n));
    assert(3 <= first_n);
    assert(first_n <= last_n);
    assert(last_n <= sigmaodd::MAX_POSSIBLE_N);
    assert(sigmaodd::is_even(range_size));
    assert(sigmaodd::is_even(master_range_size));
#ifdef PRIME16
    assert(n < 65536);
#endif

    const nat_type bad_first_n = (previous_bad_table.empty()
                                  ? first_n
                                  : 0);

    std::set<nat_type> bad_table(previous_bad_table);

    nat_type* first_ns = new nat_type[nb_thread];
    std::set<nat_type>* new_bad_tables = new std::set<nat_type>[nb_thread]();  // empty-initialized

    std::set<nat_type>* current_bad_tables = new std::set<nat_type>[nb_thread]();  // current_bad_tables[0] never used
    bool* is_finisheds = new bool[nb_thread];  // is_finisheds[0] never used
    std::thread* threads = new std::thread[nb_thread];  // threads[0] never used

    // Starts empty slave threads to simplify following code (all slave threads are used)
    for (unsigned int i = 1; i < nb_thread; ++i) {
      threads[i] = std::thread([] {});
      is_finisheds[i] = true;
      first_ns[i] = first_n;
    }

    for (nat_type n = first_n; n <= last_n; ) {
      // Start each slave thread on a range
      first_ns[0] = n;

      // Update the last known possible bad number
      nat_type bad_last_n = sequential::sequential_min_array(first_ns, nb_thread) - 1;

      n += master_range_size;  // reserve range for master thread

      for (unsigned int i = 1; (i < nb_thread) && (n <= last_n); ++i) {
        if (is_finisheds[i]) {  // if slave thread i is free
          is_finisheds[i] = false;
          first_ns[i] = n;

          // Update the last known possible bad number
          bad_last_n = sequential::sequential_min_array(first_ns, nb_thread) - 1;

          // Update bad_table
          bad_table.insert(new_bad_tables[i].cbegin(), new_bad_tables[i].cend());
          if (print_bad) {
            sequential::sequential_print_in_order(new_bad_tables[i]);
          }
          current_bad_tables[i] = bad_table;

          // Start this slave thread on its range
          threads[i].join();
          threads[i] = std::thread
            ([bad_first_n, bad_last_n, i, range_size, last_n, n,
              &current_bad_tables, &first_ns, &is_finisheds, &new_bad_tables] {
              new_bad_tables[i]
                = sequential::sequential_check_gentle_varsigma_odd
                  (first_ns[i],
                   std::min(n + range_size - 1, last_n),
                   current_bad_tables[i],
                   bad_first_n, bad_last_n,
                   false);
              current_bad_tables[i].clear();
              is_finisheds[i] = true;
            });

          // Next range
          n += range_size;
        }
      }

      // Run on master thread
      new_bad_tables[0]
        = sequential::sequential_check_gentle_varsigma_odd
          (first_ns[0],
           std::min(first_ns[0] + master_range_size - 1, last_n),
           bad_table,
           bad_first_n, bad_last_n,
           false);

      // Update bad_table
      bad_table.insert(new_bad_tables[0].cbegin(), new_bad_tables[0].cend());
      if (print_bad) {
        sequential::sequential_print_in_order(new_bad_tables[0]);
      }
      new_bad_tables[0].clear();
    }

    // Wait end of each slave thread
    for (unsigned int i = 1; i < nb_thread; ++i) {
      threads[i].join();

      // Update bad_table
      bad_table.insert(new_bad_tables[i].cbegin(), new_bad_tables[i].cend());
      if (print_bad) {
        sequential::sequential_print_in_order(new_bad_tables[i]);
      }
    }

    delete[] first_ns;
    delete[] is_finisheds;
    delete[] new_bad_tables;
    delete[] threads;

    return bad_table;
  }


  std::set<nat_type>
  threads_check_gentle_varsigma_odd__one_by_one(unsigned int nb_thread,
                                                nat_type first_n, nat_type last_n,
                                                const std::set<nat_type> &previous_bad_table,
                                                bool print_bad) {
    assert(nb_thread >= 1);
    assert(sigmaodd::is_odd(first_n));
    assert(3 <= first_n);
    assert(first_n <= last_n);
    assert(last_n <= sigmaodd::MAX_POSSIBLE_N);
#ifdef PRIME16
    assert(n < 65536);
#endif

    const nat_type bad_first_n = (previous_bad_table.empty()
                                  ? first_n
                                  : 0);

    std::set<nat_type> bad_table(previous_bad_table);

    bool* is_lowers = new bool[nb_thread];
    nat_type* ns = new nat_type[nb_thread];
    std::thread* threads = new std::thread[nb_thread];  // threads[0] never used

    for (nat_type n = first_n; n <= last_n; ) {
      unsigned int nb_thread_required = 0;

      // Assign one number for each thread
      // and start each slave thread
      for ( ; (nb_thread_required < nb_thread) && (n <= last_n); n += 2) {
        if (!sigmaodd::is_first_mersenne_prime_unitary_divide_or_square(n)) {
          ns[nb_thread_required] = n;

          if (nb_thread_required > 0) {  // if not master thread
            threads[nb_thread_required] = std::thread
              ([bad_first_n, nb_thread_required, is_lowers, ns,
                &bad_table] {
                is_lowers[nb_thread_required]
                  = sequential::sequential_is_varsigma_odd_lower(ns[nb_thread_required],
                                                                 bad_table,
                                                                 bad_first_n, ns[0] - 1);
              });
          }

          ++nb_thread_required;
        }
      }

      // Run on master thread
      is_lowers[0]
        = sequential::sequential_is_varsigma_odd_lower(ns[0],
                                                       bad_table,
                                                       bad_first_n, ns[0] - 1);

      // Wait end of each slave thread
      for (unsigned int i = 1; i < nb_thread_required; ++i) {
        threads[i].join();
      }

      // Update bad_table
      for (unsigned int i = 0; i < nb_thread_required; ++i) {
        if (!is_lowers[i]) {  // new bad number identified
          bad_table.insert(ns[i]);
          if (print_bad) {
            std::cout << ns[i] << std::endl;
          }
        }
      }
      if (print_bad) {
        std::cout.flush();
      }
    }

    delete[] is_lowers;
    delete[] ns;
    delete[] threads;

    return bad_table;
  }

}  // namespace threads