2
\$\begingroup\$

This is the second iteration of the Multithreaded natural language text parser code review. Special thanks goes to G. Sliepen who conducted the first review.

Before reading this post, please read the first iteration, since without it most of the text below doesn’t make sense.

Functional specification

Implement a multithreading parser based on existing natural language tokenizer.

  1. Parser should compile text into sequences of lexem ids.
  2. Parser should create structures to get lexem text by id and id by lexem text.
  3. Lexems id must be unique for lexem, but no any other stronger requirements are provided.

Performance and memory footprint is critical, since the amount of data is huge (gigabytes).

Nice to have the approach which could be portable to GPU for further speed up.

Changes

  1. The approach with std::async implemented; I like it more.
  2. Functions return std::vector relying on RVO/NRVO. It helps.

G. Sliepen, thank you for your points here!

Not changed things are covered in the Answers to code review points and questions section.

The code

Fully functional runnable demo.

Please note that godbolt.org doesn’t run code with MSVC, so don’t expect to see the output.

using lexem_t = unsigned int;

struct LexemData {
    lexem_t id;
    std::size_t count;
};

struct LexemDataAtomic {
    lexem_t id;
    std::atomic<std::size_t> count;

    LexemDataAtomic(unsigned int i, std::size_t count) :
        id{ i },
        count{ count }
    {
    }

    LexemDataAtomic(const LexemDataAtomic& rhs) :
        id{ rhs.id },
        count{ rhs.count.load() }
    {
    }

    LexemDataAtomic& operator=(const LexemDataAtomic& rhs)
    {
        if (&rhs != this)
        {
            id = rhs.id;
            count = rhs.count.load();
        }
    }

    LexemDataAtomic(LexemDataAtomic&&) = delete;  // atomic is not moveable
    LexemDataAtomic& operator=(LexemDataAtomic&&) = delete;
};

template <typename TextBaseType>
struct CompiledText {
    TextBaseType* text_base;
    std::vector<lexem_t> data;

    CompiledText(TextBaseType& text_base) : text_base(&text_base) {}
};

template <typename LexemsMapType, typename DictMapType>
struct TextBase {
    LexemsMapType   lexems_data;
    DictMapType     dict;

    enum {
        use_all_available_threads = 0,
    };
};

struct TextBaseMultiThreaded
    : public TextBase<Concurrency::concurrent_unordered_map<std::string, LexemDataAtomic>,
    Concurrency::concurrent_unordered_map<lexem_t, Concurrency::concurrent_unordered_map<std::string, LexemDataAtomic>::iterator>>
{
    CompiledText<TextBaseMultiThreaded> tokenize(std::string_view text, std::size_t threads = 0);
private:
    void tokenize_chunk_to(std::vector<lexem_t>& compiled, std::string_view text, lexem_t start_id);
    std::vector<lexem_t> tokenize_chunk(std::string_view text, lexem_t start_id);
};

struct TextBaseSingleThreaded
    : public TextBase<std::unordered_map<std::string, LexemData>,
    std::unordered_map<lexem_t, std::unordered_map<std::string, LexemData>::iterator>>
{
    CompiledText<TextBaseSingleThreaded> tokenize(std::string_view text);
};

CompiledText<TextBaseSingleThreaded> TextBaseSingleThreaded::tokenize(std::string_view text)
{
    CompiledText<TextBaseSingleThreaded> compiled_text(*this);
    lexem_t id = 0;

    for (auto lexem : TokenRange(text)) {
        auto res = lexems_data.insert({ std::string(lexem), { id, 0 } });

        if (res.second) {
            dict[id] = res.first;
            ++id;
        }

        res.first->second.count++;

        const auto code = res.first->second.id;
        compiled_text.data.push_back(code);
    }

    return compiled_text;
}

void TextBaseMultiThreaded::tokenize_chunk_to(std::vector<lexem_t>& compiled, std::string_view text, lexem_t start_id)
{
    auto id = start_id;

    for (auto lexem : TokenRange(text)) {
        auto res = lexems_data.insert({ std::string(lexem),{ id, 0} });

        if (res.second) {
            dict[id] = res.first;
            ++id;
        }

        ++(res.first->second.count);

        const auto code = res.first->second.id;
        compiled.push_back(code);
    }
}

std::vector<lexem_t> TextBaseMultiThreaded::tokenize_chunk(std::string_view text, lexem_t start_id)
{
    std::vector<lexem_t> compiled;

    auto id = start_id;

    for (auto lexem : TokenRange(text)) {
        auto res = lexems_data.insert({ std::string(lexem),{ id, 0} });

        if (res.second) {
            dict[id] = res.first;
            ++id;
        }

        ++(res.first->second.count);

        const auto code = res.first->second.id;
        compiled.push_back(code);
    }

    return compiled;
}

// If n_chunks == 0, use all available threads
CompiledText<TextBaseMultiThreaded> TextBaseMultiThreaded::tokenize(std::string_view text, std::size_t n_chunks)
{
    n_chunks = n_chunks != use_all_available_threads ? n_chunks : std::max((std::size_t)std::thread::hardware_concurrency(), (std::size_t)1);

    std::size_t chunk_size = text.size() / n_chunks;

    std::vector<std::future<std::vector<lexem_t>>> results;
    results.reserve(n_chunks);

    std::size_t carry = 0;

    const TokenRange empty({});
    auto delimiters = empty.begin().get_delimiters();

    CompiledText<TextBaseMultiThreaded> compiled_text(*this);

    for (std::size_t chunk = 0; chunk < n_chunks; ++chunk) {
        if (carry >= chunk_size) {
            carry -= chunk_size;
            continue;
        }

        std::size_t chunk_start = chunk * chunk_size + carry;
        std::size_t chunk_end = (chunk + 1) * chunk_size;

        std::string_view search_range = text.substr(chunk_end - 1);

        carry = search_range.find_first_of(delimiters);

        if (std::string_view::npos == carry) {
            carry = search_range.size();
        }

        chunk_end += carry;

        results.push_back(std::async(std::launch::async, &TextBaseMultiThreaded::tokenize_chunk, this,
            text.substr(chunk_start, chunk_end - chunk_start), (lexem_t)(chunk * chunk_size)));
    }

    for (auto& result : results) {
        compiled_text.data.append_range(result.get());
    }

    return compiled_text;
}

Final thoughts

The main problem this approach is that in case I use Concurrency::concurrent_unordered_map during parsing, the resulting dictionary will stay in it and reading from this map is slower (in my tests about 2.24 times) than from std::unordered_map. I need to read text of lexems in some time critical parts of the system, so this would have an impact.

Of course, I can copy data from Concurrency::concurrent_unordered_map back to std::unordered_map, but since this will be sequential operation, this will almost kill all the benefit from multithreading.

I have some ideas how to mitigate and improve this, but I am still in two minds if this approach worth further research.

Maybe I should consider other structures and algorithms like:

  1. B-trees
  2. Heap processing (like heap sorting does)
  3. Convolution (like with std::transform_reduce or std::ranges::fold_left)

Most likely, this should be done on plain structures without hash maps.

This, actually, was main question when I posted this for the first code review, if the approach correct and what approach could work better here.

So, unless I get some advice on better algorithms and data structures or figure out one myself, I have to put this research on hold, even feeling that with multicore systems like GPU this could be solved times faster than just with naïve sequential approach.

Answers to code review points and questions

On the approach and multithreading

The term “naïve” although having a special meaning in programming have a kind of connotation, which allows to assume that it is very straightforward and not optimal and there is a better well-known or at least visible approach. Posting this code and design I was eager to hear this kind of feedback to learn more about possible implementation. Could you please give a hint, what kind of approach wouldn’t be naïve?

Please note that functional specification explicitly states that amount of data expected to be huge; some of the answers below will rely on this fact and the fact that I don’t focus at the moment on some inefficiency for small texts; this could be handled, but this it not the point of the code at the moment.

  1. Taking into account a huge size of data, the slowest thread shouldn’t be much slower that any other as they have almost the same amount of lexems on average; at least I don’t expect something critical. Do you see any way to improve this?
  2. I have exactly as many threads as CPU cores which is specified in the code with the call to std::max((std::size_t)std::thread::hardware_concurrency(). Actually, I tested, reducing this number by one to give one thread to OS and other stuff, I even tried 2 times more and less threads; nothing changed dramatically, since OS and C++ Library handle threads well and unless the gap is huge, this doesn’t affect performance; nowadays applications runs dozens, even hundreds threads without dramatic impact. Of course, I am aware about switching and balance.
  3. My chunks can’t be small by functional specification. With gigabytes of text, I would need millions of CPU cores to have small chunks.

So, to put in a nutshell, I can’t get the point you make on multithreading issues in my code.

On functional decomposition

This really hits a record. The add_to_data function will consist of one line of code and which is most important, for this I will need to return the code of the added/found lexem from add_to_dictionary function and then pass to add_to_data. I don’t care about performance because of inlining and optimizations, I care about the code structure. Is it worth to extract one line of obvious code only with a sole purpose to name it?

Just want to take a chance of asking you if you could help me with my questions posted in form of comments to Natural language text fast tokenizer (Rev.3) (as a separate code review section if you will create one). Maybe your answers to these questions will help me to get this decomposition.

On copying strings

We already discussed this in the comments for Multithreaded natural language text parser. Additionally to the fact that I will release the text buffer after processing, let me add some extra points:

  1. If I replace std::string with std::string_view here, the overall execution time increases from 1.7 seconds to 2.85 seconds, which is 1.67 times degradation for the whole task, so this place suffers even larger performance degradation. The reason is quite simple, with the large text data, your approach is cache unfriendly. Every access to string will most likely hit another cache page, killing existing cache and leading to significant memory bottlenecks, since lexem strings will be sparse in memory. In my case they are located much denser.
  2. On the excessive creation of std::string, this could lead only to one copy; in most cases it wouldn’t lead even to extra memory allocation because of SSO (short string optimization); so the price is not so high.

On the expected performance

  1. Starting and stopping threads today is not so expensive when I need the amount of threads equal to the number of cores on CPU and load each thread for seconds of work.
  2. Of course, I am aware of Amdahl's law, but do you really think it should be a showstopper for parallel algorithms? Even if on N cores I could achieve N/2 speed up, doesn’t it worth doing on today’s CPU and GPU?
  3. Simple std::copy shows that I can process gigabytes per second, so I am definitely not memory-bound so far, at least, overall. Although, I would agree that caching could suffer. Again, is it a showstopper to get some performance improvement?
  4. On atomic/mutex, I totally agree with you. But (a) it works and works now about 4.5 times faster on 16 cores CPU than a single threaded version; (b) that is exactly the reason I published the code, to learn if this task could be solved better and faster with other approaches.
  5. Every thread gives time decrease, so charting is not so necessary here. The key question is different, namely, is the approach correct?

On my performance expectations. If I get something like speed up about 0.75*CPU cores number, I would consider this a success, but having 0.5*CPU cores number would be a good enough result.

Again, I am not saying that the approach is the best, as I stated above, the main goal of the posting this question was to get some help with the approach itself. I feel this could be solved faster, but can’t get this done so far.

\$\endgroup\$
3
  • \$\begingroup\$ Could you please provide a regex for the tokens? Have you tried using flex or some other lexer generator tool? \$\endgroup\$ Feb 18 at 20:52
  • \$\begingroup\$ @Incomputable, let's use etc.|i.e.|\.{3}|\w+(?:['-]\w+)?|\+|\p{P} (demo). No, I haven't. I am not sure how they could help me with the multi-threading. Most likely you aimed at the Natural language text fast tokenizer (Rev.3) which is a part of this code, since your question seems more related to the tokenizer rather then to the parser. If so, I will be thankful if you step in there. If I am wrong, please go ahead in the current one. \$\endgroup\$ Feb 19 at 22:36
  • \$\begingroup\$ There was a paper on parallel parser generator and tried it on C programming language, IIRC. I forgot what the paper was, but there is some research in that direction. \$\endgroup\$ Feb 21 at 17:38

1 Answer 1

3
\$\begingroup\$

About your feedback

  1. Taking into account a huge size of data, the slowest thread shouldn’t be much slower that any other as they have almost the same amount of lexems on average;

The problem isn't the number of lexems, but rather the variation in time it takes to process each lexem. Part of that is because there is a varying amount of work per lexem (hash map lookup and insertion are not deterministic), and part of it comes from the operating system needing to do stuff, other programs running their threads, the CPU handling interrupts, and many other things that are happening. These variations do not cancel each other out over a long time, but slowly add up (it's like a random walk). The total variation at the end will just be a small fraction of the total time your program runs, so you could ignore it, but you could also avoid mostly it.

  1. I have exactly as many threads as CPU cores […] reducing this number by one to give one thread to OS and other stuff, I even tried 2 times more and less threads; nothing changed dramatically,

If the total time your program runs is not changed when you use 2 times less threads, then that means your program is not CPU-bound, and instead having more threads just makes it less efficient. You want to see a dramatic change when adding or removing threads; ideally having twice the number of threads should halve the time your program takes. If not, consider that those threads could be doing something more useful for another program, or just be idle so they don't consume energy.

  1. My chunks can’t be small by functional specification. With gigabytes of text, I would need millions of CPU cores to have small chunks.

You should decouple the size of the chunk from the number of cores. For example, if you have 8 cores and 16 chunks, you start 8 threads and have each thread process 2 chunks.

Is it worth to extract one line of obvious code only with a sole purpose to name it?

If it becomes even more obvious afterwards, yes.

  1. Of course, I am aware of Amdahl's law, but do you really think it should be a showstopper for parallel algorithms? Even if on N cores I could achieve N/2 speed up, doesn’t it worth doing on today’s CPU and GPU?

It depends. Sometimes a parallel algorithm is much slower per core than a non-parallel one. In that case, while you could still throw lots of cores at it for some speedup, you are wasting more energy to run the program than if everything was running on a single core.

Another reason I mentioned this is that if parallelism doesn't give you the speedup you expected, then maybe you should focus your attention to the serial steps in your algorithm. Maybe those can be improved, or maybe some of the serial steps you have could be made parallel as well.

  1. Simple std::copy shows that I can process gigabytes per second, so I am definitely not memory-bound so far, at least, overall.

std::copy is the best case scenario for memory access. Your algorithm might not be able to achieve the same bandwidth.

it works and works now about 4.5 times faster on 16 cores CPU than a single threaded version

Ok, so in your parallel version, that sounds like each thread is running 3.56 times slower than the single threaded version. Either that, or the serial steps in your algorithm are indeed quite large (23.3% of the total runtime according to Amdahl's law), or something inbetween.

I think it is likely you can get more performance. I would first identify where the bottleneck really is, and measure the time for setting up the chunks, for running the threads, and for creating the compiled_text vector afterwards. Using a profiler like perf might also help finding out where most of the time is spent.

Avoid code duplication

tokenize_chunk() and tokenize_chunk_to() are almost identical. You can implement one using the other:

std::vector<lexem_t> TextBaseMultiThreaded::tokenize_chunk(std::string_view text, lexem_t start_id) {
    std::vector<lexem_t> compiled;
    tokenize_chunk_to(compiled, text, start_id);
    return compiled;
}

But TextBaseSingleThreaded::tokenize() also looks very similar to TextBaseMultiThreaded::tokenize_chunk(). Ideally you avoid that duplication as well. Or do you need TextBaseSingleThreaded at all? Why not call TextBaseMultiThreaded::tokenize() with just 1 chunk? That does start a separate thread though, but you could detect the case of n_chunks == 1 and use std::launch::deferred instead of std::launch::async.

Incorrect start_id being passed?

When you create the async tasks, you pass chunk * chunk_size as the start_id parameter. However, shouldn't that be chunk_start instead?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you for such a fast review! Some fast answers: (1) My wording on "I even tried 2 times more and less threads; nothing changed dramatically" is bad, of course I meant "nothing changed dramatically from the perspective of threading management"; of course, performance reduced with less threads number, but "accordingly"; just wording. (2) The tokenize_chunk_to is redundant code, I forgot to remove it after the refactoring, sorry. (3) The tokenize works with std::unordered_map while tokenize_chunk works with concurrent one, so this is intentional, but I will see if could be templated. \$\endgroup\$ Feb 18 at 22:11
  • \$\begingroup\$ Thank you again for the review. I've posted the Rev3 with my comments, answers and questions. I am especially interested in your help with answers to my questions on functional decomposition and my concerns in Rev.3. Could you please take a look? \$\endgroup\$ Mar 17 at 10:52

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.