3
\$\begingroup\$

This is the second iteration of the Natural language text fast tokenizer code review. Special thanks goes to G. Sliepen and Toby Speight who conducted the first review.

Functional specification

Implement a function for fast tokenization of text in char[] buffer handling some natural language specifics below:

  1. Consider ‘ ‘ (space) as a delimiter, keeping a way to extends the list of delimiters later.
  2. Extract stable collocations like “i.e.”, “etc.”, “…” as a single lexem.
  3. In case word contains characters like ‘-‘ and ‘’’ (examples: semi-column, half-, cat’s) return the whole construct as a whole lexem. (3.1) Otherwise, split word and return parts as separate lexems and each non-alphanumeric "inword" symbols as separate lexems.
  4. Return sequences of numbers (integers without signs) as a single lexem.

Performance is critical, since the amount of data is huge. The function should be thread-safe.

Note: The defect in specification was found by Matthieu M in question for first code review when I already posted current Rev.2.: any "inword" non-alphanumeric character except described in item 3 above returns as separate lexems which contradicted original functional specification. Since I still in two minds about behaviour I want here, the item 3.1 has been added which describes how it works now. If you change the code and removing 3.1 to keep lexems with internal non-alphanumeric as a whole (like "a|b") will simplify the code, please feel free to fix on the fly. I will fix this in Rev3.

Answers/comments on the items in the first Code Review iteration

  1. I am not sure we need tokenize function since we can just use TokenRange(sample); why do we need a wrapper here? Any purpose or risks without it?
  2. Thank you for the explanation on the full std::ranges approach. Taking into account that I will need to use the tokenized with the execution policies which are still missing in std::ranges, I will stay with current implementation so far; considering to make view just for learning ranges/views/projections.
  3. The question about regex library usage is still on the table. Isn’t regex the tool intended exactly for these purposes? Shouldn’t the code with regex be shorter in times? The only concern is performance, which I mentioned in the first post.
  4. I decided not to inherit Iterator to std::iterator because of KISS principle; so far I don’t see any benefits from it. When I see how this could be really used, I will rework this as a separate exercise.

Changelog

  1. The code reworked to ranges approach with TokenRange.
  2. To avoid offset recalculation for operator++, the mutable next field introduced.
  3. Recent C++ features used including switching to std::isdigit and std::isalpha.

Concerns

  1. The main issue is this Iterator::end(). In the tutorials they say that the best approach is to transparently pass the end() iterator of underlying data, but since here I can’t return data.end(), the empty range is returned and I am still in two minds if end() is the only case when empty range could occur, so this could lead to false-positive check to end() if I am correct. Please, comment.
  2. Mutable next to pass the offset from operator* to operator++ is not the best solution here, but I don’t see anything better. Any suggestions?
  3. Still don’t like the code in the inner while loop in the TokenRange::Iterator::operator*. It is hard to grasp and prove to be correct, but don’t see any way to simplify it.
  4. Still not sure if class Iterator is the best place for these dilimiters, stable_lexems and inword_lexems; I want them to be configurable later, but still in two minds if they should belong to TokenRange or to Iterator, since formally they don’t define the range, but the way to iterate the range. On the other hand, any hardcoded values is evil, so I should request them in constructor and I don’t want to have them in every iterator’s ctor. Putting them into TokenRange and copy to Iterator on creation to be able to adjust seems as overengineering.

The code

Here is the updated code for the code review; could you please take a look and suggest further ways to improve?

Fully functional demo.

#include <algorithm>
#include <cstring>
#include <iostream>
#include <ranges>
#include <vector>

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.", "..." };
        const std::string_view inword_lexems = "-\'";

        std::string_view data;
        mutable size_t next = ((size_t)-1);
    public:
        Iterator(std::string_view data = {}) : data(data) { skip_delimiters(); }
        std::string_view operator*() const;
        Iterator& operator++();
        friend bool operator==(const Iterator& it1, const Iterator& it2) { return it1.data == it2.data; }
    private:
        void skip_delimiters();
    };

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

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

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

void TokenRange::Iterator::skip_delimiters()
{
    size_t skip = 0;
    while (skip < data.size() && std::ranges::contains(delimiters, data[skip])) {
        ++skip;
    }

    data.remove_prefix(skip);
}

std::string_view TokenRange::Iterator::operator*() const
{
    size_t i = 0;

    while (!data.empty() && i == 0) {
        auto it = std::ranges::find_if(stable_lexems, [&](auto stable_lexem)
            {
                return data.starts_with(stable_lexem);
            });

        if (it != stable_lexems.end()) {
            next = it->size()+(data.size()-data.size());
            return data.substr(0, it->size());
        }

        while (i < data.size() && !std::ranges::contains(delimiters, data[i])) {
            const bool is_inword_char = std::ranges::contains(inword_lexems, data[i]);

            if (is_inword_char && i != 0 && std::isalpha(data[i - 1])) {
                ++i;
                continue;
            }

            if (!std::isalpha(data[i]) && !std::isdigit(data[i])) {
                if (i == 0) {
                    ++i;
                }
                break;
            }

            ++i;
        }
    }

    next = i + (data.size() - data.size());
    return data.substr(0,i);
}

TokenRange::Iterator& TokenRange::Iterator::operator++()
{ 
    if (next == ((size_t)-1)) {
        operator*();
    }

    data.remove_prefix(next);
    skip_delimiters();

    next = ((size_t)-1);

    return *this;
}

int main()
{
    std::string sample = "Let's consider, this semi-simple sample, i.e. test data with ints: 100, etc. For ... some testing...";
        
    for (auto token : TokenRange(sample)) {
        std::cout << token << " | ";
    }
}

Performance

I was really surprised with the performance results I got with this new code. Tested on my local PC, the new code is about 18% faster than my original code despite the fact that std::string_view is at least twice larger (pointer and size) than const char*.

I expected the new version to be at least somewhat slower if not dramatically, but it seems that std::ranges library does its work best to provide code which compiler could optimize even better than my original code.

So, at least at this stage no ground for being afraid of expenses.

Being honest, I was used to think that low-level C-style which is closer to assembler language should compile better; the reality is different for our luck.

Here is a demo for those who interested in performance measurements.

Please, note that godbolt.org is not suited for performance measurements (at least, as I know it), so the results could differ dramatically. You could just copy the code to your local PC and check.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You're still misspelling std::size_t. It's not portable to assume that the standard library will define global-namespace equivalents of std-namespace identifiers (it's allowed to, but not required to). And you're still passing possibly-negative characters to std::isalpha() and std::isdigit(). It doesn't look like you've taken advice. \$\endgroup\$ Feb 12 at 8:01
  • \$\begingroup\$ @TobySpeight, thank you for the input. I was sure your point was that isalpha() is not safe and switching to std::isalpha() should solve the problem alongside with moving to std functions. I will check more careful this time and will make the adjustment. On the std::size_t, as I answered in my comment to your previous answer, taking into account how std::size_t defined I made conscious decision to use size_t. Please see the standard 17.7/2 and 18.1/3 which makes them absolutely interchangeable and portable. Someday I could change my mind, but so far size_t is enough for me. \$\endgroup\$ Feb 12 at 10:20
  • \$\begingroup\$ Previous review was more concerned with the difference between std::isalpha() from <cctype> and std::isaplha from <locales>. The latter can be used directly with plain char but not the former. \$\endgroup\$ Feb 12 at 10:31
  • 1
    \$\begingroup\$ You have no definition in scope for size_t, only std::size_t. If you really need an unqualified version, you need to include a C compatibility header or to write using std::size_t;. It is not portable to assume that size_t is defined everywhere that std::size_t is. \$\endgroup\$ Feb 12 at 10:33
  • \$\begingroup\$ @TobySpeight, I've published the [Rev.3]( codereview.stackexchange.com/questions/289472/…) which covers all your points. Could you please take a look? Please pay special attention to Reservation 2; since it related to singed/unsigned problem, maybe you could help me realize why CLang is unhappy with unsigned char here? \$\endgroup\$ Feb 13 at 13:06

1 Answer 1

3
\$\begingroup\$

I've make a partial review below. It's only partial, because it's become clear that the code is a bit too much work in progress. Not only the formatting, but also the correctness. Further, that also makes it pretty hard to follow. In general, it would help if you sometimes described in prose what a section of code does. I believe the size-size issue below was caused by refactoring and changing the meaning of code, too. Having those comments and proof-reading them afterwards helps avoid these issues. That said, despite these flaws, your code is not a mess and generally well-structured.

Formatting Consistency

Sometimes you put the opening { and closing } on the same line with the function header, sometimes only the opening { and sometimes neither. Use one style consistently. Don't cram too much into one line. The compiler won't generate smaller or faster code for it, but it will make the code harder to read and understand.

Cornercase Skipping Space Characters

The function skipping the initial spaces will fail if there is only spaces. I'd rewrite it like this:

while (true) {
    if (input is empty) {
        break;
    }
    if (input[0] is not a delimiter) {
        break;
    }
    input.drop_prefix(1);
}

Putting multiple condition checks into the while condition won't generate smaller or faster code. It does make it less readable which in turn makes it more likely that you miss errors.

Use Of C-Style Casts

I'm referring to ((size_t)-1), which is bad for two reasons. Firstly, it's a magic number. Secondly, it uses C-style casts. Using a named constant (npos for example) would be much more readable.

Mutable Data

You raised the question concerning the mutable next yourself and whether it's necessary. I don't think it is. If you look at what's happening on the input sequence, you find these steps:

  1. skip separators
  2. find end of token to process it
  3. skip to end of token
  4. go to step 1

I've ignore the checks for EOF here for now, since it's not important here. The point is that step 2 (operator *) assumes a constant iterator. However, it must store the end of the token for step 3 (operator ++) in order to not repeat the forward scan there.

As alternative, I'd combine skipping separators and scanning for the end of the token. So, in the constructor, you do that once from the initial position and remember both the start and end of the token. operator* then just returns the subsequence you determined there. operator++ then drops the determined token from the head of the sequence and then searches for the next exactly like the constructor.

As additional benefit, multiple or zero calls to operator* will be handled much more gracefully.

Unicode Compliance

Is that even a goal for you? If your input is plain ASCII, quite a few things simplify. For example, all the locale-specific is* can much easier be implemented as ranges::contains() calls.

Skipping Stable Lexems

The code there does (data.size()-data.size()), which makes no sense to me, it's zero. Does this even work correctly?

\$\endgroup\$
7
  • \$\begingroup\$ Thank you so much for your help here! I agree with many points, but let me postpone the acceptance before I clarify some moments. Let me address them one by one. (1) I believe that the code which need be commented (at least such simple code) is ill-written, so I avoid comments as much as possible, but let me think of it in terms of code review; \$\endgroup\$ Feb 12 at 22:52
  • \$\begingroup\$ (2) I believe, my code is mostly consistently formatted according to my style; with this I mean that the same things are formatted similarly. I prefer dense code because I like to see everything in one screen without scrolling. Let's look at the final version when it comes and if you show me better formatting, I would be thankful; \$\endgroup\$ Feb 12 at 22:52
  • \$\begingroup\$ (3) I can't see why skip_delimiters() could fail because of "only delimiters"; just tested, everything works just fine. Don't see a reason for 9 lines instead of 5 with multiple remove_prefix calls. For me the condition in while is C/C++-classic, used everywhere and well-readable; can provide many examples from the C++ standard library. \$\endgroup\$ Feb 12 at 22:53
  • \$\begingroup\$ (4) is* functions works even faster with my Fast tolower function as I mentioned in rev1, I just avoided code overcomplication here. Totally agree with all other your points and especially love your solution for operator*() and operator++(). I will implement all this in rev.3. \$\endgroup\$ Feb 12 at 22:53
  • \$\begingroup\$ Hey @DamirTenishev, thanks for the feedback. Concerning the skip_delimiters(), it works. I'm not sure what I saw there. Concernig the multiple remove_prefix() calls, they boil down to a pointer adjustment operation that I'd expect to be inlined. So, using data.empty() and data.remove_prefix(1) and data.front() would be the way to go. If you insist on it, you can also keep that while-loop structure with it: while (!data.empty() && is_separator(data.front())) data.remove_prefix(1);. \$\endgroup\$
    – uli
    Feb 13 at 9:48

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.