2
\$\begingroup\$

The purpose of this code per the title is to utilise the multi-threading (even though the improvement might be minor or even have negative impact, although comments on how to improve efficiency are appreciated). As part of the work, we are expected to read a file and print the 20 most frequently used words.

#include <iostream>
#include <iterator>
#include <set>
#include <vector>
#include <algorithm>
#include <map>
#include <mutex>
#include <fstream>
#include <pthread.h>
#include <queue>
#include "mingw-std-threads-master/mingw-std-threads-master/mingw.thread.h"
#include "mingw-std-threads-master/mingw-std-threads-master/mingw.mutex.h"

//bad practise but convenient for this code example
using namespace std;

//File to read so that we can find the most frequent used words.
#define FILENAME "mobydick.txt"

//The amount of words to find which are most used.
#define WORDS_TO_FIND 20

map<string,int> word_count;
queue<string> word_queue;
std::mutex m;

//Not great approach but condition_variable is not available in my environment.
bool keep_running = true;

//Ignore punctuations coming from the stream, and to read only valid "english" letters from the input stream.
//This is an improvement but it still doesn't cover all cases.
struct letter_only: ctype<char>
{
    letter_only(): ctype<char>(get_table()) {}

    static ctype_base::mask const* get_table()
    {
        static vector<ctype_base::mask> rc(ctype<char>::table_size,ctype_base::space);

        fill(&rc['a'], &rc['z'+1], ctype_base::alpha);
        return &rc[0];
    }
};

void insert()
{
    string word;

    while(keep_running || (!keep_running && !word_queue.empty()))
    {
        if(!word_queue.empty())
        {
            m.lock();
            word = word_queue.front();
            word_queue.pop();

            if (word_count.find(word) == word_count.end())
            {
                word_count.insert(pair<string, int>(word, 1));
            }
            else
            {
                word_count.find(word).operator*().second++;
            }
            m.unlock();
        }
    }
}

void read_file()
{
    ifstream file;

    file.imbue(locale(locale(), new letter_only()));

    file.open(FILENAME);

    if (!file.is_open())
    {
        exit(-1);
    }

    string word;
    while (file >> word)
    {
        m.lock();
        word_queue.push(word);
        m.unlock();
    }

    file.close();
    keep_running = false;
}

void print_results()
{
    int biggestNum = 0;
    string word;

    for(int i = 0; i < WORDS_TO_FIND; i++)
    {
        for(auto it = word_count.begin(); it != word_count.end(); ++it )
        {
            if (it->second > biggestNum)
            {
                biggestNum = it->second;
                word = it->first;
            }
        }

        if(word.length() > 0)
        {
            word_count.erase(word);
            cout << word + ": " << biggestNum << endl;
        }

        biggestNum = 0;
    }
}

int main()
{
    /** Thoughts...
    * The only ways I know to improve disk read performance are:
     * 1) read the data from a compressed source.
     * 2) use faster disks, or RAID array. or
     * 3) split the data onto separate disks and read 1 thread per disk. Usually, if a single thread can't keep up
     * with your disk read time, you have big problems.
    **/

    //An option to consider is task-based parallelism.. std::async which lets the platform decide when to spawn a thread.


    thread first(read_file);
    first.detach();

    thread second(insert);
    second.join(); //wait for read_file and insert to finish before printing the results

    print_results();

    return 0;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ //bad practise but convenient for this code example using namespace std; Bite the bullet and just do it properly. \$\endgroup\$ Mar 13 '18 at 17:37
  • 1
    \$\begingroup\$ Can't say I am convinced that threading this problem will make it faster. All the extra overhead of synchronization will probably make it slower than a single threaded version. \$\endgroup\$ Mar 13 '18 at 17:41
1
\$\begingroup\$

Code Review

A lot of people like to put some logical order on the includes.

#include <iostream>
#include <iterator>
#include <set>
#include <vector>
#include <algorithm>
#include <map>
#include <mutex>
#include <fstream>

I like to put containers together, streams stuff together, C stuff together; others like to order them alphabetically. But with this many includes some sort of logic is probably a good idea.

You don't need to use this old library.

#include <pthread.h>

Threading is now part of the C++ standard. All the threading and mutex classes are included.

Not sure what these are:

#include "mingw-std-threads-master/mingw-std-threads-master/mingw.thread.h"
#include "mingw-std-threads-master/mingw-std-threads-master/mingw.mutex.h"

But that seems awfully deeply nested. Which usually means that there are are top level includes that include these files indirectly. A comment with a link to the documentation would be nice especially since a maintainer is not likely to know about these.

Hmmm

//bad practise but convenient for this code example
using namespace std;

C Macro

No need to use macros. There are better C++ alternatives.

//File to read so that we can find the most frequent used words.
#define FILENAME "mobydick.txt"

//The amount of words to find which are most used.
#define WORDS_TO_FIND 20

Notice we can type these correctly now.

// http://en.cppreference.com/w/cpp/string/basic_string/operator%22%22s
static std::string constexpr fileName    = "mobydick.txt"s;
static int constexpr         wordsToFind = 20;

Globals

Globals is a bad idea. These should be wrapped in a class object.

map<string,int> word_count;
queue<string> word_queue;
std::mutex m;                // inconsistent use of std::

//Not great approach but condition_variable is not available in my environment.
bool keep_running = true;

Locals

Love it.
Not enough people work out how to use the streams and locals correctly.

//Ignore punctuations coming from the stream, and to read only valid "english" letters from the input stream.
//This is an improvement but it still doesn't cover all cases.
struct letter_only: ctype<char>
{
    letter_only(): ctype<char>(get_table()) {}

    static ctype_base::mask const* get_table()
    {
        static vector<ctype_base::mask> rc(ctype<char>::table_size,ctype_base::space);

        fill(&rc['a'], &rc['z'+1], ctype_base::alpha);
        return &rc[0];
    }
};

Insert

Your lock is over too large a surface area. You lock the queue even while you are working on word_count and this is not used by the reader thread. The reader thread could be actively using the queue while you play with the word count object.

You should also look into using RAII to correctly lock and unlock your lock.

You read loop is a busy loop. You are going to melt the processor doing this. It would be better to use a condition variable and force the thread to sleep if the queue is empty (which it will be most of the time).

Lastly you overcomplicated the addition.

std::string getWord()
{
    std::lock_guard<std::mutex>  lock(m);   // Only lock as long as you need.
    std::word result = word_queue.front();
    word_queue.pop();
    return result;
}
void insert()
{
    string word;

    while(keep_running || (!keep_running && !word_queue.empty()))
    {
        // Add condition variable here.
        if(!word_queue.empty())
        {
            // Call getWord() that locks as part of the access
            // It is in a separate function so that the RAII lock
            // can simply unlock on exit.
            word = getWord();

            // If word does not exist. The [] operator inserts a value
            // using `word` as the key and zero-initializes the value 
            // so for an int the value inserted is a zero.
            // 
            // It returns a reference to the value, so you can simply
            // increment the result of the operation.
            ++word_count[word];
       }
    }
}

Optimization

This is very expensive.

    for(int i = 0; i < WORDS_TO_FIND; i++)
    {
        for(auto it = word_count.begin(); it != word_count.end(); ++it )
        {

You are basically looping over all the words 20 times. This list could be huge. There are 171,476 words in the english language (assume no spelling mistakes many more if you include these). You can replace this and loop over the words once and just keep track of the top 20.

\$\endgroup\$
2
  • \$\begingroup\$ Did you mean "Your lock is over too large a surface area"? \$\endgroup\$
    – yuri
    Mar 13 '18 at 21:09
  • \$\begingroup\$ @yuri yes. Fixed. \$\endgroup\$ Mar 13 '18 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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