C++,Qt - 尽可能快地拆分QByteArray

Question

我正在尝试将QByteArray包含UTF-8编码纯文本(使用空格作为分隔符)的大量文本拆分为最佳性能.我发现如果我将数组转换为QString第一个,我可以获得更好的结果.我尝试使用正则QString.split表达式使用该函数,但性能非常糟糕.这段代码变得更快:

QMutex mutex;
QSet<QString> split(QByteArray body)
{
    QSet<QString>  slova;

    QString s_body = QTextCodec::codecForMib(106)->toUnicode(body);
    QString current;

    for(int i = 0; i< body.size(); i++){
        if(s_body[i] == '\r' || s_body[i] == '\n' || s_body[i] == '\t' || s_body[i] == ' '){

            mutex.lock();
            slova.insert(current);

            mutex.unlock();
            current.clear();
            current.reserve(40);
        } else {
            current.push_back(s_body[i]);
        }
    }
    return slova;
}

"Slova" QSet<QString>目前是,但我可以使用std::set或任何其他格式.此代码应该可以找到阵列中有多少个唯一的单词,并且可以获得最佳性能.

不幸的是,这段代码远远不够快.我希望从中挤出绝对最大值.

使用callgrind,我发现最贪婪的内部函数是:

QString::reallocData (18% absolute cost)
QString::append (10% absolute cost)
QString::operator= (8 % absolute cost)
QTextCodec::toUnicode (8% absolute cost)

显然,这与源于该push_back函数的内存分配有关.解决这个问题的最佳方法是什么？不一定必须是Qt解决方案 - 纯C或C++也是可以接受的.

Answer 1

最大限度地减少您需要执行的复印量。将输入缓冲区保留为 UTF-8，并且不要将std::stringor存储QString在您的集合中；相反，创建一个小类来引用现有的 UTF-8 数据：

#include <QString>

class stringref {
    const char *start;
    size_t length;

public:
    stringref(const char *start, const char *end);
    operator QString() const;
    bool operator<(const stringref& other) const;
};

这可以封装 UTF-8 输入的子字符串。您需要确保它不会比输入字符串的寿命更长；您可以通过巧妙地使用 来做到这一点std::shared_ptr，但如果代码相当独立，那么它应该足够容易处理以推断生命周期。

我们可以从一对指向 UTF-8 数据的指针构造它，并QString在我们想要实际使用它时将其转换为：

stringref::stringref(const char *start, const char *end)
    : start(start), length(end-start)
{}

stringref::operator QString() const
{
    return QString::fromUtf8(start, length);
}

您需要定义operator<以便可以在std::set.

#include <cstring>
bool stringref::operator<(const stringref& other) const
{
    return length == other.length
        ? std::strncmp(start, other.start, length) < 0
        : length < other.length;
}

请注意，我们在取消引用指针之前按长度排序，以减少缓存影响。

现在我们可以编写split方法：

#include <set>
#include <QByteArray>
std::set<stringref> split(const QByteArray& a)
{
    std::set<stringref> words;

    // start and end
    const auto s = a.data(), e = s + a.length();

    // current word
    auto w = s;

    for (auto p = s;  p <= e;  ++p) {
        switch (*p) {
        default: break;
        case ' ': case '\r': case '\n': case '\t': case '\0':
            if (w != p)
                words.insert({w, p});
            w = p+1;
        }
    }

    return words;
}

该算法几乎是您自己的，添加了测试w!=p，这样就不会计算空白的运行。

让我们测试一下，并计算重要部分的时间：

#include <QDebug>
#include <chrono>
int main()
{
    QByteArray body{"foo bar baz\n  foo again\nbar again "};
    // make it a million times longer
    for (int i = 0;  i < 20;  ++i)
        body.append(body);

    using namespace std::chrono;
    const auto start = high_resolution_clock::now();

    auto words = split(body);

    const auto end = high_resolution_clock::now();
    qDebug() << "Split"
             << body.length()
             << "bytes in"
             << duration_cast<duration<double>>(end - start).count()
             << "seconds";

    for (auto&& word: words)
        qDebug() << word;
}

我得到：

在 1.99142 秒内分割 35651584 字节
“bar”
“baz”
“foo”
“again”

编译-O3时间减少到 0.6188 秒，所以不要忘记向编译器寻求帮助！

如果这仍然不够快，那么可能是时候开始考虑并行化任务了。您需要将字符串拆分为大致相等的长度，但前进到下一个空白，以便没有工作跨越两个线程的工作。每个线程应该创建自己的结果集，然后缩减步骤是合并结果集。我不会为此提供完整的解决方案，因为这本身就是另一个问题。