Title: Code Critique Competition 100

Author: Martin Moene

Date: 02 July 2016 20:58:44 +01:00 or Sat, 02 July 2016 20:58:44 +01:00

Summary: Set and collated by Roger Orr. A book prize is awarded for the best entry.

Body: 

Participation in this competition is open to all members, whether novice or expert. Readers are also encouraged to comment on published entries, and to supply their own possible code samples for the competition (in any common programming language) to scc@accu.org.

Note: If you would rather not have your critique visible online, please inform me. (Email addresses are not publicly visible.)

The 100th critique

This issue contains the 100th in the code critique series which was started by Francis Glassborow (and a regular feature by the time I joined ACCU) and then continued under the oversight of David A. Caabeiro.

The code critique comes under the heading of ‘Dialogue’ and has attracted entries from a wide range of members over the years. It’s a relatively easy place for people to contribute to the magazine, to learn something from the act of critiquing the code, and perhaps be inspired to try their hand at an article in the future.

I continue to enjoy setting them – but I’m still no nearer understanding why some issues attract many critiques and others attract only one! C/C++ example code generally is the most popular, but I do occasional produce problems written in other languages. I’m always keen to hear from people who have written (or come across) code that might form the basis of a critique – anonymity is provided if desired (!)

Last issue’s code

I wanted to learn a bit about C++ threading so I tried writing a thread pool example. But it sometimes crashes – I’ve managed to get it down to a small example.

Sometimes I get what I expected as output, for example:

     Worker done
     Worker done
     Ending thread #2
     Ending thread #0
     Worker done
     Ending thread #1
     Worker done
     Ending thread #3
     Worker done
     All done

But other times I get a failure, for example:

     Worker done
     Ending thread #0
     Worker done
     Awaiting thread #1
     Worker done
     W
     <crash>

I’m not sure what to do next – can you help?

The program is in Listing 1.

#include <algorithm>
using namespace std;
#include <array>
#include <chrono>
using namespace chrono;
#include <cstdlib>
#include <iostream>
#include <thread>

static const int POOL_SIZE = 4;

// Allow up to 4 active threads
array<thread, POOL_SIZE> pool;

// Example 'worker' -- would in practice
// perform some, potentially slow, calculation
void worker()
{
  this_thread::sleep_for(
    milliseconds(rand() % 1000));

  cout << "Worker done\n";
}

// Launch the thread functoid 't' in a new
// thread, if there's room for one
template <typename T>
bool launch(T t)
{
  auto it = find_if(pool.begin(), pool.end(),
    [](thread const &thr)
    { return thr.get_id() == thread::id(); }
  );
  if (it == pool.end())
  {
    // everyone is busy
    return false;
  }

  *it = thread([=]()
  {
    t();
    thread self;
    swap(*it, self);
    self.detach();
    cout << "Ending thread #"
      << (it - pool.begin()) << "\n";
  });
  return true;
}

int main()
{
  while (launch(worker))
  {}
  // And finally run one in this thread as an
  // example of what we do when the pool is full
  worker();
  for (auto & it : pool)
  {
    thread thread;
    swap(thread, it);
    if (thread.joinable())
    {
      cout << "Awaiting thread #"
        << (&it - &*pool.begin()) << "\n";
      thread.join();
    }
  }
  cout << "All done\n";
}
			

Critiques

Felix Petriconi <felix@petriconi.net>

I personally would first include all necessary headers and then add a global using namespace std.

Since chrono is only used in the worker() function, I personally wouldn’t use a namespace inclusion for a single occurrence. Alternatively one could simply add using std::chrono::milliseconds at the beginning of the worker function.

Instead of a fixed size of threads I would go for the native number of available cores of the used platform with:

  std::thread::hardware_concurrency()

There is also no need to make POOL_SIZE a static variable. A simple constant would be fine for such a purpose.

Good that std::array is used here, but hardware_concurrency() is not a constant value during compile-time so one should probably use a vector.

For this example the usage of rand() is probably OK. But in general one should avoid using it, because the distribution is bad. See Stephan T. Lavavej’s talk at the Going Native 2013 conference.

Using std::cout itself is thread safe, but the output is not synchronized. So I recommend creating a log function that synchronizes the output to std::cout.

Inside launch(), I would never pass an iterator into a thread. It is very dangerous in general to pass an iterator to something other than an algorithm-like function. I only use iterators locally within the scope of the current function or method. In this example the access to the thread objects happens without synchronization between the main thread and the spawned thread which results in undefined behaviour. So in the main thread a free slot is searched and in the spawn thread a) swapping the objects and b) detaching it happens. This must be done synchronized, e.g. with a mutex. As well there is again the problem with using std::cout. Please see above.

In the main function the loop variable is named it. This is misleading for a reader, because it is not an iterator, but a reference to the array objects. One sees the problem at the statement

  &it -&*pool.begin()

From my point of view this looks somehow strange. Either I would encapsulate a std::thread object into some struct, that has an additional thread number attribute, or I would have let the pool be:

  vector<std::pair<int, std::thread>>
  pool(thread::hardware_concurrency());

so that the thread number is stored in the first element of the pair, or more simply I would use a classic for loop with an index like

  for (size_t i = 0; i < pool.size(); ++i) 

and then use the operator[] to access the individually thread elements. Again there is a race condition, because the thread function detaches the thread potentially at the same time as the main thread tries to do it.

In the code the array variable is named pool. But there is no pooling of threads. Here they are started with each new function and then it finishes. Normally one tries to reuse a thread for all the tasks, because spawning a new thread is very expensive.

I know that the code was written for getting to know threading. I experienced myself that threading is not easy and that are there are many traps that one can step into. So if I would need a thread pool for production code I would always try to look for a ready tested solution, before I try to build something by myself.

John Roden <john.roden@iol.ie>

Besides the main routine, the program starts four other threads whose administrative information is stored in an array of thread objects (the pool). This array is manipulated in both the main routine and each thread (by swap() functions). The result is that the main routine is not seeing the original thread objects when it awaits on threads to complete. The swap() functions aren’t necessary in this case.

The program also detaches each thread with the result that the thread is no longer joinable. Tests reveal that the wait loop at the end sometimes sees a thread as joinable but by the time it tries to join it, the thread has detached and is no longer joinable – the program hangs in my test (it could legitimately crash!). There is no reason to detach the threads in this case.

My solution to the program’s problems is to remove the swap() and detach() lines and access the original thread objects in every case.

These are the lines (commented-out) which need to be disabled in the code:

  40        t();
  41         //thread self;
  42         //swap(*it, self);
  43         //it->detach();
  44         cout << "Ending thread #"
  45           << (it - pool.begin()) << "\n";

  60        //thread thread;
  61        //swap(thread, it);
  62        if (it.joinable())

In this example the threads do not need to change any shared information; if they did, a mutex of some sort would be needed but that complexity can be avoided here. The cout function is guaranteed to remain uncorrupted when used by multiple threads (C++11) but it is possible to get the output from different threads interleaved. When this is a problem, a mutex lock guard would be needed for each cout.

James Holland <James.Holland@babcockinternational.com>

Compiling and running the program revealed the crashing problems the student was complaining about. If the program contains threads and crashes intermittently, the problem stands a good chance of being caused by race conditions.

An inspection of the student’s code reveals plenty of opportunities for race conditions. For example, the main thread calls launch(), that creates a thread object in one of the elements of the thread pool array, and starts to execute the worker function via a lambda. At more or less the same time, the lambda function calls the detach() function of the object just stored in the thread pool. I said more or less, because it is not possible to know which event will happen first; creating the thread object in the pool or calling the detach function. If the detach function is called first, the object will be the original default constructed thread. Calling detach() on a default constructed thread results in std::system_error being thrown. This is probably not what was intended. There is also a potential race condition with swap() within the lambda function.

Incidentally, I am not quite sure what the student had in mind when creating a default constructed thread and swapping it with the one in the pool. Perhaps it is something leftover from the student’s main project. In any case it is a potential source of trouble. In fact any harmful race condition should be removed from the code.

It should be noted that the last line of the lambda uses the iterator (it) that refers to the thread object in the pool. This use of it does not cause a race condition because the code refers directly to the iterator and not what the iterator is pointing at (namely, the thread object). This just goes to show that making sure multi-threaded code is free of harmful race conditions is a tricky business. Because of this, it is best to keep the program design as simple as possible.

The code below runs the worker function in four threads (stored in the thread pool) and then waits for all the threads to finish executing before exiting. I believe it to be free of harmful race conditions but it still may not execute reliably. If thread() is unable to start a new thread, it will throw an exception of type std::system_error. To guard against this, no more threads should be created than given by std::thread::hardware_concurrency(). This function returns the number of hardware threads available. Unfortunately, the number returned is not guaranteed to be accurate, it is just an estimate. Because of this, the call of the std::thread constructor should be enclosed within a try-catch block.

Finally, I have made use of a mutex to ensure that a thread writes a complete line of text on the console without interruption from another thread. This simply improves the display formatting.

I have been able to describe only a few features of std::threads. For a comprehensive treatment, I would recommend the book C++ Concurrency in Action by Anthony Williams, ISBN 9781933988771. Also recommended is Scott Meyers’ book, Effective Modern C++, ISBN 9871491903995. Scott has a chapter devoted to concurrency and gives many useful hints and tips.

Finally, although not perfect, I provided an amended version of the student’s code with race conditions removed.

  #include <algorithm>
  #include <array>
  #include <chrono>
  #include <cstdlib>
  #include <iostream>
  
  using namespace std;
  static const int POOL_SIZE = 4;
  array<std::thread, POOL_SIZE> pool;
  std::mutex m;
  void worker()
  {
    std::this_thread::sleep_for(
      std::chrono::milliseconds(rand() % 1000));
    std::lock_guard<std::mutex> guard(m);
    cout << "Worker done\n";
  }
  template <typename T>
  bool launch(T t)
  {
    auto it = find_if(pool.begin(), pool.end(),
      [](std::thread const & thr)
      {
        return thr.get_id() ==
               std::thread::id();
      });
    if (it == pool.end())
    {
      return false;
    }
    *it = std::thread([=]()
      {
        t();
        std::lock_guard<std::mutex> guard(m);
        cout << "Ending thread #" <<
          (it - pool.begin()) << "\n";
      });
    return true;
  }
  int main()
  {
    while (launch(worker))
    {}
    worker();
    for (auto & it : pool)
    {
      it.join();
    }
    std::lock_guard<std::mutex> guard(m);
    cout << "All done\n";

  }

Commentary

There has been a fair bit of discussion over the years since C++11 was completed about the pros and cons of exposing direct access to threads in the C++ library. The original plan had been to get the basic mechanism into the standard and the to introduce higher level abstractions, implemented using the basic functionality, in subsequent versions of C++.

Unfortunately the higher level abstractions have been somewhat slower to appear than hoped, although there should be some parallel algorithms coming in C++17, with the result that much code is still being written using ‘raw’ std::thread. (While outside the scope of this critique, there are various libraries, not in the C++ standard, that do provide some higher level building blocks.)

One difficulty with writing threaded code is that it can be hard to prove the code is correct and any bugs often only appear intermittently. It is, as Felix and James variously pointed out, good to have a clear program design and to make use of existing, debugged, libraries or idioms for threading.

This example is purporting to demonstrate a thread pool but, as Felix said “there is no pooling of threads”. The programmer might have done better to have taken some examples from, for instance, Anthony’s book and to work through those rather than designing their own ‘pool’-like system.

Multi-threaded code involves two levels of correctness (at least). The first level is that of thread-safety, i.e. that the various threads in the program manipulate data structures in a way that avoids undefined behaviour or crashes. The second level is ensuring that the behaviour of the program is meaningful and consistent, with whatever execution order the various threads involved end up using.

In this program, as each critique mentioned, the use of cout is thread-safe (because the standard guarantees there will be no data races when used like it is here) but the output can be interleaved and therefore inconsistent. However, the use of pool is not even thread-safe as multiple threads modify the array using swap() and iteration without any mechanism to make the access correct.

There are two main directions for making the use of pool correct. One way is to use explicit synchronisation (probably using a mutex) and the other way is to ensure clear ownership of the object so that only one thread accesses the object (John’s solution takes this route).

The Winner of CC 99

The three critiques seemed to cover the main problems with the code between them. I’m not sure I’d want to go quite as far as Felix and never allow an iterator to be passed to a thread, but it is definitely a bit of a ‘code smell’ and would need to be designed carefully to ensure the access remains valid whatever the subsequent execution pattern.

There was some discussion in the critiques about the best way to size the number of threads to use for the machine executing the program rather than using a fixed value (POOL_SIZE) – possibly involving std::thread::hardware_concurrency(). This function returns the ‘number of hardware thread contexts’ (but this should only be considered as a hint.) You can normally create many more threads than this, but only this number of threads can actually execute simultaneously. (This is additionally subject to other platform-specific constraints, such as thread affinity masks.)

Overall I think Felix provided the fullest critique so I have awarded him this issue’s prize.

Code critique 100

(Submissions to scc@accu.org by Aug 1st)

I wanted to do something slightly different for this, the 100th code critique column, so I have based this issue’s critique on the ‘left-pad’ function that was part of npm but was withdrawn by the author, breaking a large number of components on the Internet. See http://blog.npmjs.org/post/141577284765/kik-left-pad-and-npm for some more official information about the issue and http://www.haneycodes.net/npm-left-pad-have-we-forgotten-how-to-program/ for some discussion about some of the issues it raises.

(The left-pad story was briefly discussed on accu-general during the ‘NIH syndrome’ thread.)

Please feel free to comment on the Javascript code itself, or on the wider issues raised by the story.

Listing 2 contains leftpad.js, and a trivial test page is provided in Listing 3 if you want to play with the function in a browser.

function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}
			

<!DOCTYPE html>
<html>
<head><title>CC100</title></head>
<body>

<h1>Code Critique 100</h1>

<script src="leftpad.js"></script> 

<script>
function testLeftpad() {
  result.innerHTML = '"' + 
  leftpad(text.value, len.value, pad.value) + 
  '"';
}
</script>

<table>
<tr><td>Text to pad</td><td>
  <input type="text" id="text" value="1234">
</td></tr>
<tr><td>Length</td><td>
  <input type="text" id="len" value="10">
</td></tr>
<tr><td>Pad char</td><td>
  <input type="text" id="pad" value="0">
</td></tr>
</table>

<br/><button onclick="testLeftpad()">
Try out leftpad
</button>

<pre id="result"></pre>

</body>
</html>
			

You can also get the current problem from the accu-general mail list (next entry is posted around the last issue’s deadline) or from the ACCU website (http://accu.org/index.php/journal). This particularly helps overseas members who typically get the magazine much later than members in the UK and Europe.

Notes: 

More fields may be available via dynamicdata ..