Compiler Explorer

Source code

#include <algorithm>
#include <atomic>
#include <chrono>
#include <cstring>
#include <iostream>
#include <limits>
#include <locale>
#include <random>
#include <ranges>
#include <sstream>
#include <thread>
#include <vector>
#include <unordered_map>
#include <concurrent_unordered_map.h>

namespace fast {
    template <typename Fn>
    class CharacterClass
    {
        std::array<char, std::numeric_limits<char>::max() + 1> cache = {};

public:
        explicit CharacterClass(Fn fn, const std::locale& locale = {})
        {
            set_locale(fn, locale);
        }

void set_locale(Fn fn, const std::locale& locale)
        {
            auto const func = [&locale, &fn](char c) { return fn(c, locale); };
            std::ranges::copy(std::views::iota(0u, cache.size())
                | std::views::transform(func),
                cache.begin());
        }

bool operator()(char c) const { return cache[c]; }
    };

CharacterClass isalpha(std::isalpha<char>);
    CharacterClass isdigit(std::isdigit<char>);
    CharacterClass isalnum(std::isalnum<char>);
}

class TokenRange {
    std::string_view data;
public:
    class Iterator {
        const std::string_view delimiters = " ";
        const std::vector<std::string_view> stable_lexems = { "...", "i.e.", "etc.", "etc..." };
        const std::string_view inword_symbols = "-\'";

std::string_view data;
        std::string_view lexem;
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = std::string_view;
        using difference_type = std::ptrdiff_t;

Iterator() {}
        Iterator(std::string_view data) : data(data) { extract_lexem(); }
        std::string_view operator*() const { return lexem; }
        Iterator& operator++();
        Iterator operator++(int);
        friend bool operator==(const Iterator& it1, const Iterator& it2) { return it1.lexem == it2.lexem; }
        friend bool operator!=(const Iterator& it1, const Iterator& it2) { return it1.lexem != it2.lexem; }
        Iterator& operator=(const Iterator& it) { data = it.data; lexem = it.lexem; return *this; }

std::string_view get_delimiters() const { return delimiters; }
    private:
        void extract_lexem();
        void skip_delimiters();
        bool check_for_stable_lexems();
    };

TokenRange(std::string_view data) : data(data) {}

Iterator begin() const {
        return Iterator(data);
    }

Iterator end() const {
        return {};
    }
};

void TokenRange::Iterator::skip_delimiters()
{
    while (!data.empty() && std::ranges::contains(delimiters, data.front())) {
        data.remove_prefix(1);
    }
}

bool TokenRange::Iterator::check_for_stable_lexems()
{
    auto it = std::ranges::max_element(stable_lexems, std::less<std::size_t>(),
        [&](auto stable_lexem) {
            return data.starts_with(stable_lexem) ? stable_lexem.size() : 0;
        }
    );

if (it != stable_lexems.end() && data.starts_with(it->data())) {
        lexem = data.substr(0, it->size());
        data = data.substr(it->size());
        return true;
    }

return false;
}

void TokenRange::Iterator::extract_lexem()
{
    skip_delimiters();

if (check_for_stable_lexems()) {
        return;
    }

std::size_t index = 0;
    while (index < data.size())
    {
        if (std::ranges::contains(delimiters, data[index])) {
            break;
        }

if (!fast::isalnum(data[index])) {
            if (index == 0) {
                ++index;
            }
            break;
        }

const bool is_next_char_inword_symbol = (index + 1) < data.size() ? std::ranges::contains(inword_symbols, data[index + 1]) : false;
        if (is_next_char_inword_symbol) {
            ++index;
        }

++index;
    }

lexem = data.substr(0, index);
    data = data.substr(index);
}

TokenRange::Iterator& TokenRange::Iterator::operator++()
{
    extract_lexem();
    return *this;
}

TokenRange::Iterator TokenRange::Iterator::operator++(int)
{
    Iterator temp(data);
    extract_lexem();
    return temp;
}

using lexem_t = unsigned int;

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

struct LexemDataAtomic {
    lexem_t	id;
    std::atomic<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 TextBaseSingleThreaded 
    : public TextBase<std::unordered_map<std::string, LexemData>, 
                      std::unordered_map<lexem_t, std::unordered_map<std::string, LexemData>::iterator>> 
{
    void tokenize(CompiledText<TextBaseSingleThreaded>& compiled_text, const std::string_view& text);
};

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>>
{
    void tokenize(CompiledText<TextBaseMultiThreaded>& compiled_text, const std::string_view& text, std::size_t threads = 0);
private:
    void tokenize_chunk(std::vector<lexem_t>& compiled, TextBaseMultiThreaded& text_base, const std::string_view& text, lexem_t start_id);
};

void TextBaseSingleThreaded::tokenize(CompiledText<TextBaseSingleThreaded>& compiled_text, const std::string_view& text)
{
    lexem_t id = 0;

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

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

res.first->second.count++;

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

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

for (auto lexem : TokenRange(text)) {

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

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

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

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

// If n_chunks == 0, use all available threads
void TextBaseMultiThreaded::tokenize(CompiledText<TextBaseMultiThreaded>& compiled_text, const 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::vector<std::thread> threads;

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

std::vector<std::vector<lexem_t>> compiled(n_chunks);

std::size_t carry = 0;

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

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;

auto text_for_chunk = text.substr(chunk_start, chunk_end - chunk_start);

threads.emplace_back(&TextBaseMultiThreaded::tokenize_chunk, this, std::ref(compiled[chunk]), std::ref(compiled_text.text_base),
                             text.substr(chunk_start, chunk_end - chunk_start), (lexem_t)(chunk * chunk_size));
    }

for (auto& thread : threads) {
        thread.join();
    }

for (auto comp : compiled) {
        compiled_text.data.insert(compiled_text.data.end(), comp.begin(), comp.end());
    }
}

void generate_text(std::string& text, std::size_t length)
{
    std::vector<char> alphabet;

for (char c = 'a'; c <= 'z'; ++c)
        alphabet.push_back(c);

for (std::size_t i = 0; i < 5; ++i)
        alphabet.push_back(' ');

for (std::size_t i = 0; i < 3; ++i)
        alphabet.push_back(',');

for (std::size_t i = 0; i < 2; ++i)
        alphabet.push_back('.');

text.resize(length);

std::mt19937 generator(0);
    std::uniform_int_distribution<std::size_t> gen(0, alphabet.size() - 1);

std::ranges::generate(text, [&]() { return alphabet[(std::size_t)gen(generator)]; });
}

int main()
{
    _CrtSetReportHook2(_CRT_RPTHOOK_INSTALL, [](int, char*, int*) { return 1; });

{
        std::string sample = "Let's consider, this semi-simple sample, i.e. test data a+b with ints: 100, etc. For ... some testing...";

std::stringstream simply_parsed;

for (auto token : TokenRange(sample)) {
            simply_parsed << token << " | ";
        }

std::cout << "Simply parsed version: " << simply_parsed.str() << "\n";

TextBaseSingleThreaded single_threaded_text_base;
        CompiledText<TextBaseSingleThreaded> single_threaded_compiled_text(single_threaded_text_base);

single_threaded_text_base.tokenize(single_threaded_compiled_text, sample);

std::stringstream single_threaded;

for (std::size_t i = 0; i < single_threaded_compiled_text.data.size(); ++i) {
            single_threaded << single_threaded_text_base.dict[single_threaded_compiled_text.data[i]]->first << " | ";
        }

std::cout << "\nSingle-threaded version:" << single_threaded.str() << "\n";

TextBaseMultiThreaded multi_threaded_text_base;
        CompiledText<TextBaseMultiThreaded> multi_threaded_compiled_text(multi_threaded_text_base);

multi_threaded_text_base.tokenize(multi_threaded_compiled_text, sample);

std::stringstream multi_threaded;
        
        for (std::size_t i = 0; i < multi_threaded_compiled_text.data.size(); ++i) {
            multi_threaded << multi_threaded_text_base.dict[multi_threaded_compiled_text.data[i]]->first << " | ";
        }

std::cout << "\nMulti-threaded version:\n" << multi_threaded.str() << "\n\n";

std::cout << (simply_parsed.str() == single_threaded.str() ? "Single threaded test passed: OK" : "Single threaded test failed") << "\n";
        std::cout << (simply_parsed.str() == multi_threaded.str() ? "Multi threaded test passed : OK" : "Multi threaded test failed") << "\n";
    }

#define PERF
#ifdef PERF
    {
        std::cout << "\nPerformance testing:";

const std::size_t text_length = 1'000'000'0;

std::string text;
        generate_text(text, text_length);

TextBaseSingleThreaded single_threaded_text_base;
        CompiledText<TextBaseSingleThreaded> single_threaded_compiled_text(single_threaded_text_base);
        TextBaseMultiThreaded multi_threaded_text_base;
        CompiledText<TextBaseMultiThreaded> multi_threaded_compiled_text(multi_threaded_text_base);

{
            std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();

single_threaded_text_base.tokenize(single_threaded_compiled_text, text);

std::chrono::high_resolution_clock::time_point now = std::chrono::high_resolution_clock::now();
            std::cout << "\nDuration of the single-threaded version = " << (std::chrono::duration<double>(now - start));
        }

{
            std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();

multi_threaded_text_base.tokenize(multi_threaded_compiled_text, text);

std::chrono::high_resolution_clock::time_point now = std::chrono::high_resolution_clock::now();
            std::cout << "\nDuration of the multi-threaded version = " << (std::chrono::duration<double>(now - start));
        }

auto is_compiled_texts_equal = std::ranges::equal(single_threaded_compiled_text.data, multi_threaded_compiled_text.data, std::equal_to{},
            [&](auto lex) {
                return single_threaded_text_base.dict[lex]->first; },
                [&](auto lex) {
                return multi_threaded_text_base.dict[lex]->first; });

std::cout << "\n\n" << (is_compiled_texts_equal ? "Test passed: OK" : "Test failed") << "\n";

}
#endif //PERF
}