3
\$\begingroup\$

Is there a chance to implement the code below better with the features of recent C++ versions?

Functional specification

Having a large text and already built prefix array find the longest substrings (limited by the number of repetitions) getting benefit from already existing prefix array, if reasonable. Provide the version which would benefit from multi-threading keeping the code as simple as possible.

Implementation

The fully functional demo.

Reservation: current implementation utilizes execution policies, so using ranges/projections/views under the question; would work if multi-threading requirement from above met.

The code has raised my question on SO Is there a way to introduce transparent sentinels before the begin and at the end of std::vector data?, where I tried to simplify array borders checking guards, introducing sentinels and people answered that here we need to simplify the code first to see if this ever needed. So, I publish the code to see if this code could be written much simpler before trying sentinels.

Most important pieces of code under the question are below.

Helper function to simplify the core search function:

std::size_t findMatchLength(const char* text, std::size_t index1, std::size_t index2) {
    // Limit the offset so we do not read past the beginning of the array.
    auto limit = std::min(index1, index2);
    for (std::size_t offset = 0; offset <= limit; ++offset)
        if (text[index1 - offset] != text[index2 - offset])
            return offset;

    return limit + 1;
}

As a second thought, I am in two minds about the findMatchLength function. It works pretty well to simplify the findLongestSimilarSequences function and self-documenting its flow, but violates Occam's razor principle, introducing a new essence. When I figured out the name for it, I based on the usage context in the findLongestSimilarSequences function. On the other hand, I can't explain its existence in higher scope, namely I can't give it a good generic name which explains what exactly it does and can't explain usage of both indexes out of context of findLongestSimilarSequences. So, from this perspective, this is a bad candidate for extraction and generalization. Please, correct me if I am wrong here.

Another helper function template to update maximum value in multi-threading environment.

template<typename T>
void update_max(std::atomic<T>& max_value, T const& value) noexcept
{
    T prev_value = max_value;
    while (prev_value < value && 
           !max_value.compare_exchange_weak(prev_value, value))
    {}
}

The search function itself:

void findLongestSimilarSequences(std::string& text, const std::vector<int>& index) {
    constexpr std::size_t largest_sequence = std::numeric_limits<std::size_t>::max();
    const int max_repetitions = 5; // Could be replaced with smallest sequence to find

    std::vector <std::size_t> adjacent_matches(index.size());

    for (int repetitions = 2; repetitions <= max_repetitions; ++repetitions) {
        std::atomic<std::size_t> max_match_length = 0;
        std::for_each(std::execution::par_unseq, index.begin(), index.end() - (repetitions - 1), [&](const int& item) {
            size_t idx = &item - std::data(index);

            std::size_t match_length = findMatchLength(text.c_str(), item, *(&item + (repetitions-1)));

            adjacent_matches[idx] = match_length;

            if (match_length < largest_sequence) {
                update_max(max_match_length, match_length);
            }
        });

        if (max_match_length < 1)
            continue;

        std::cout << "Longest equal sequence(s) repeated " << repetitions << " times is " << max_match_length << " chars" << std::endl;

        std::cout << "The susequence(s) are:" << std::endl;

        for (int i = 0; i < adjacent_matches.size()-1; ++i) {
            if (adjacent_matches[i] == max_match_length) {
                std::cout << text.substr(index[i] - (max_match_length - 1),max_match_length) << std::endl;
            }
        }
    }
}

Concerns for this function

  1. I don’t like the code structure, is there a way to simplify it and make more readable?
  2. I don’t like two responsibilities of the function, namely to find substrings and to print them, but I don’t see better solutions (maybe callback for printing?) because the text size is large and there could be too many results to keep them in maps and other dynamic structures which will cause significant memory fragmentation and could be time-consuming.
  3. Some other questions are in form of comments in the code.

The main function is quite simple:

int main()
{
    std::string text = "This-string-contains-repetitions-and-these-repetitions-the-string-contains-as-repetitions-these-repetitions";
    
    // Am I correct that this wouldn't create a copy of array on return from function?
    // Will copy elision do its work or should I do something explicit?
    auto prefix_array_index = buildPrefixArrayIndex(text); 

    findLongestSimilarSequences(text, prefix_array_index);
}

Please don’t pay much attention to using std::string and its functions here, in the real code the text is compiled in lexems ids and stored in std::vector<int>, but this implementation would grow the code size here which I want to avoid.

Please don’t pay much attention to the function buildPrefixArrayIndex, as well, since it is provided only to make the code executable and testable. In real code it is based on std::vector and offsets.

std::vector<int> buildPrefixArrayIndex(const std::string& str) {
    std::vector<int> suffix_array(str.length());
    std::iota(suffix_array.begin(), suffix_array.end(), 0);

    std::sort(std::execution::par_unseq, suffix_array.begin(), suffix_array.end(), [&](int lhs, int rhs) {
    auto lstr = str.substr(0, lhs + 1);
        // Could be replaced with rbegin(), but I am not sure that code will be readable
        std::reverse(lstr.begin(),lstr.end());

        auto rstr = str.substr(0,rhs+1);
        std::reverse(rstr.begin(), rstr.end());

        return lstr < rstr;
        });

    return suffix_array;
}

Can you please conduct code review and show the way to implement this code with the latest versions of C++? I want to keep with pure C++ without any libraries like boost (of course, STL is applicable).

\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Redesign the interface

You already have some doubts about your code's structure, in particular that findLongestSimilarSequences() has too many responsibilities. You want the function to just do the finding part, and move the loop that prints the longest sequences out of it. So ideally, you want to be able to write something like:

for (int repetitions = 2; repetitions <= 5; ++repetitions) {
    std::cout << "Longest equal sequence(s) repeated " << repetitions << " times:\n";
    for (auto sequence: findLongestSimilarSequences(text, index, repetitions)) {
        std::cout << sequence << "\n";
    }
}

So findLongestSimilarSequences() has to return something that can be iterated over. That can be as simple as a std::vector<std::string_view>, which is quite efficient. Consider that you already allocate a vector of size index.size() in your function.

std::vector<std::string_view>
findLongestSimilarSequences(const std::string& text,
                            const std::vector<int>& index,
                            int min_repetitions)
{
    // Build adjacent_matches
    …

    // Create the result
    std::vector<std::string_view> result;

    for (int i = 0; i < adjacent_matches.size() - 1; ++i) {
        if (adjacent_matches[i] == max_match_length) {
            result.emplace_back(text.data() + index[i] - (max_match_length - 1), max_match_length);
        }
    }

    return result;
}

But when looking at your code, I also have other questions about the interface:

  • Why is your text not passed as a const reference?
  • Why not use std::string_view for text?
  • Why limit it to strings at all? It seems to me that you could make this work for any kind of range.
  • Why does the caller need to pass a vector named index? What if you pass the wrong "index"? Either let findLongestSimilarSequences calculate this index, or create a class that encapsulates both the text and index, and pass a reference to that to this function.
  • Why does the name say "SimilarSequences"? That implies they might not be exactly identical. I think "RepeatedSubsequences" would be a better name.

Keep code simple and clear

I had to read findMatchLength() a few times to understand why it works, as normally I would expect a function like this to compare to substrings in the forward direction. I guess it's smart to pass indices to the end of the substrings, so you can use the minimum of those to avoid out-of-bounds reads, and in this particular use case you don't care about finding the match length of the strings reversed.

A much more intuitive interface would be to just pass two substrings, and compare them forwards. Then you can also use STL algorithms such as std::mismatch(), or even better, its ranges version:

std::size_t findMatchLength(std::string_view str1, std::string_view str2) {
    return std::ranges::mismatch(str1, str2).in1 - str1.begin();
}

The standard library might get an atomic max function

There have been proposals to get atomic max and min functions into the standard library. While your update_max() looks fine, consider renaming it and changing the interface to the proposed atomic_fetch_max(), which will have an interface very similar to std::atomic_fetch_add(). This would make refactoring your code later to make use of a standard function simpler.

template<typename T>
T atomic_fetch_max(std::atomic<T>* obj, typename std::atomic<T>::value_type arg) noexcept
{
    auto prev = obj->load(std::memory_order_relaxed);
    while (prev < arg && !obj->compare_exchange_weak(prev, arg)) {}
    return prev;
}

Your code can return duplicates

Try adding a dash at the end of your test string in main(). Your code doesn't find subsequences with an exact number of repetitions, but rather with a minimum number of repetitions. And when the actual number of repetitions found is larger than the minimum number of repetitions, it will print the same subsequence multiple times.

Other issues

  • Use "\n" instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed, which is usually unnecessary and has a negative impact on performance.
  • You use int in some places to hold sizes, like the loop iterator i and as the value type of the vector index. If the text is larger than can be represented by an int, your code will no longer work correctly. Always prefer to use std::size_t for sizes, counts and indices.
  • You can avoid the atomic variable by changing the for_each() into a transform_reduce(). However, it probably doesn't improve performance in a significant way.
\$\endgroup\$
15
  • 1
    \$\begingroup\$ auto prev = *obj; won't compile (*obj is a std::atomic<T> so auto picks that, not T, and the deleted copy-constructor saves us from compiling with an atomic local var). You want auto prev = obj->load(std::memory_order_relaxed); which produces a T. \$\endgroup\$ Commented Jan 20 at 14:05
  • 1
    \$\begingroup\$ Is there any advantage to typename std::atomic<T>::value_type arg over just T in the args? (And which doesn't apply to the return value where you just used T?) I see that prototype is just copied from P0493R1; they don't mention a motivation for value_type. (Damir also asked why not T const &, but that has an easy answer: T should be small for lock-free atomics, probably at most long long or double for max to make sense, so can be passed more efficiently by value than by reference.) \$\endgroup\$ Commented Jan 20 at 14:09
  • \$\begingroup\$ I just did this indeed to exactly copy the way the proposal and already standardized atomic operations are declared. The standard also says value_type should be equal to T, so indeed it seems very unnecessary. Maybe this is a good question for StackOverflow? \$\endgroup\$
    – G. Sliepen
    Commented Jan 20 at 14:50
  • 1
    \$\begingroup\$ What happened to std::atomic::value_type? sheds some light on the change from T to ...::value_type - wg21.link/P0558R1 fixed an apparent defect. I haven't waded through the details. \$\endgroup\$ Commented Jan 20 at 14:52
  • 1
    \$\begingroup\$ If I read P0558R1 correctly, it seems to be to help with type deduction when you call the atomic function with a value of a different type than T. \$\endgroup\$
    – G. Sliepen
    Commented Jan 20 at 14:55

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.