diff options
author | Thiago Macieira <thiago.macieira@intel.com> | 2023-12-05 19:58:33 -0800 |
---|---|---|
committer | Thiago Macieira <thiago.macieira@intel.com> | 2023-12-21 11:13:32 -0800 |
commit | b347d487048cf36d609dd31952dbef1813b5b0e5 (patch) | |
tree | bf8a14a71bcee9bb69587bf66840c74667611ed9 | |
parent | 5ea4e27661e1805a6ed01c7a61643f9a50c15d62 (diff) |
QString/QByteArray: further inline the most common indexOf operations
In the case of QString, the vast majority of searches are case-
sensitive, so by inlining we make the user code call qustrchr() directly
instead of QtPrivate::findString(). In the case of QByteArray, the call
is to memchr(), which being a compiler intrinsic, may itself be inlined
or even just resolved at compile time.
In both cases, a great deal of searches use from=0.
Benchmark for QByteArray; before:
8.83207052 nsecs per iteration
22.01568546 CPU cycles per iteration, 2.49 GHz
60.00000331 instructions per iteration, 2.725 instr/cycle
21.00000281 branch instructions per iteration, 2.38 G/sec
After:
6.42561493 nsecs per iteration
16.01623130 CPU cycles per iteration, 2.49 GHz
49.00000261 instructions per iteration, 3.059 instr/cycle
18.00000211 branch instructions per iteration, 2.8 G/sec
This shaves 6 cycles in the execution and 11 instructions (3 of which
were branches), slightly improving the IPC raito, for the QByteArray
case. For QByteArrayView, there are 2 fewer instructions (1 a branch),
but the number of cycles is the same at 16.
Task-number: QTBUG-119750
Change-Id: Ica7a43f6147b49c187ccfffd179e2204ebb6a348
Reviewed-by: Marc Mutz <marc.mutz@qt.io>
-rw-r--r-- | src/corelib/text/qbytearray.cpp | 21 | ||||
-rw-r--r-- | src/corelib/text/qbytearrayalgorithms.h | 2 | ||||
-rw-r--r-- | src/corelib/text/qbytearrayview.h | 14 | ||||
-rw-r--r-- | src/corelib/text/qstring.cpp | 52 | ||||
-rw-r--r-- | src/corelib/text/qstringalgorithms.h | 4 | ||||
-rw-r--r-- | src/corelib/text/qstringview.h | 21 |
6 files changed, 59 insertions, 55 deletions
diff --git a/src/corelib/text/qbytearray.cpp b/src/corelib/text/qbytearray.cpp index a1ae331585..1ff2721265 100644 --- a/src/corelib/text/qbytearray.cpp +++ b/src/corelib/text/qbytearray.cpp @@ -2642,25 +2642,6 @@ QByteArray QByteArray::repeated(qsizetype times) const hashHaystack -= std::size_t(a) << ol_minus_1; \ hashHaystack <<= 1 -static inline qsizetype findCharHelper(QByteArrayView haystack, qsizetype from, char needle) noexcept -{ - if (from < 0) - from = qMax(from + haystack.size(), qsizetype(0)); - if (from < haystack.size()) { - const char *const b = haystack.data(); - if (const auto n = static_cast<const char *>( - memchr(b + from, needle, static_cast<size_t>(haystack.size() - from)))) { - return n - b; - } - } - return -1; -} - -qsizetype QtPrivate::findByteArray(QByteArrayView haystack, qsizetype from, char needle) noexcept -{ - return findCharHelper(haystack, from, needle); -} - qsizetype QtPrivate::findByteArray(QByteArrayView haystack, qsizetype from, QByteArrayView needle) noexcept { const auto ol = needle.size(); @@ -2673,7 +2654,7 @@ qsizetype QtPrivate::findByteArray(QByteArrayView haystack, qsizetype from, QByt } if (ol == 1) - return findCharHelper(haystack, from, needle.front()); + return findByteArray(haystack, from, needle.front()); if (from > l || ol + from > l) return -1; diff --git a/src/corelib/text/qbytearrayalgorithms.h b/src/corelib/text/qbytearrayalgorithms.h index db8b239fd8..7060161bb4 100644 --- a/src/corelib/text/qbytearrayalgorithms.h +++ b/src/corelib/text/qbytearrayalgorithms.h @@ -25,7 +25,7 @@ bool startsWith(QByteArrayView haystack, QByteArrayView needle) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION bool endsWith(QByteArrayView haystack, QByteArrayView needle) noexcept; -[[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION +[[nodiscard]] inline qsizetype findByteArray(QByteArrayView haystack, qsizetype from, char needle) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION diff --git a/src/corelib/text/qbytearrayview.h b/src/corelib/text/qbytearrayview.h index 0541436df9..3ebc2f841c 100644 --- a/src/corelib/text/qbytearrayview.h +++ b/src/corelib/text/qbytearrayview.h @@ -361,6 +361,20 @@ inline quint16 qChecksum(const char *s, qsizetype len, { return qChecksum(QByteArrayView(s, len), standard); } #endif +qsizetype QtPrivate::findByteArray(QByteArrayView haystack, qsizetype from, char needle) noexcept +{ + if (from < 0) + from = qMax(from + haystack.size(), qsizetype(0)); + if (from < haystack.size()) { + const char *const b = haystack.data(); + if (const auto n = static_cast<const char *>( + memchr(b + from, needle, static_cast<size_t>(haystack.size() - from)))) { + return n - b; + } + } + return -1; +} + QT_END_NAMESPACE #endif // QBYTEARRAYVIEW_H diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp index 410b65a62a..4c2bef298f 100644 --- a/src/corelib/text/qstring.cpp +++ b/src/corelib/text/qstring.cpp @@ -133,31 +133,6 @@ static inline bool foldAndCompare(const T a, const T b) searching forward from index position \a from. Returns -1 if \a ch could not be found. */ -static inline qsizetype qFindChar(QStringView str, QChar ch, qsizetype from, Qt::CaseSensitivity cs) noexcept -{ - if (from < -str.size()) // from < 0 && abs(from) > str.size(), avoiding overflow - return -1; - if (from < 0) - from = qMax(from + str.size(), qsizetype(0)); - if (from < str.size()) { - const char16_t *s = str.utf16(); - char16_t c = ch.unicode(); - const char16_t *n = s + from; - const char16_t *e = s + str.size(); - if (cs == Qt::CaseSensitive) { - n = QtPrivate::qustrchr(QStringView(n, e), c); - if (n != e) - return n - s; - } else { - c = foldCase(c); - auto it = std::find_if(n, e, [c](auto ch) { return foldAndCompare(ch, c); }); - if (it != e) - return std::distance(s, it); - } - } - return -1; -} - template <typename Haystack> static inline qsizetype qLastIndexOf(Haystack haystack, QChar needle, qsizetype from, Qt::CaseSensitivity cs) noexcept @@ -794,6 +769,23 @@ const char16_t *QtPrivate::qustrchr(QStringView str, char16_t c) noexcept return std::find(n, e, c); } +/*! + * \internal + * + * Searches case-insensitively for character \a c in the string \a str and + * returns a pointer to it. Iif the character is not found, this function + * returns a pointer to the end of the string -- that is, \c{str.end()}. + */ +Q_NEVER_INLINE +const char16_t *QtPrivate::qustrcasechr(QStringView str, char16_t c) noexcept +{ + const QChar *n = str.begin(); + const QChar *e = str.end(); + c = foldCase(c); + auto it = std::find_if(n, e, [c](auto ch) { return foldAndCompare(ch, QChar(c)); }); + return reinterpret_cast<const char16_t *>(it); +} + // Note: ptr on output may be off by one and point to a preceding US-ASCII // character. Usually harmless. bool qt_is_ascii(const char *&ptr, const char *end) noexcept @@ -9637,15 +9629,12 @@ bool QtPrivate::endsWith(QLatin1StringView haystack, QLatin1StringView needle, Q return qt_ends_with_impl(haystack, needle, cs); } -qsizetype QtPrivate::findString(QStringView haystack0, qsizetype from, char16_t needle0, Qt::CaseSensitivity cs) noexcept -{ - return qFindChar(haystack0, needle0, from, cs); -} - qsizetype QtPrivate::findString(QStringView haystack0, qsizetype from, QStringView needle0, Qt::CaseSensitivity cs) noexcept { const qsizetype l = haystack0.size(); const qsizetype sl = needle0.size(); + if (sl == 1) + return findString(haystack0, from, needle0[0], cs); if (from < 0) from += l; if (std::size_t(sl + from) > std::size_t(l)) @@ -9655,9 +9644,6 @@ qsizetype QtPrivate::findString(QStringView haystack0, qsizetype from, QStringVi if (!l) return -1; - if (sl == 1) - return qFindChar(haystack0, needle0[0], from, cs); - /* We use the Boyer-Moore algorithm in cases where the overhead for the skip table should pay off, otherwise we use a simple diff --git a/src/corelib/text/qstringalgorithms.h b/src/corelib/text/qstringalgorithms.h index 6a007173ab..082f970b6c 100644 --- a/src/corelib/text/qstringalgorithms.h +++ b/src/corelib/text/qstringalgorithms.h @@ -21,6 +21,7 @@ namespace QtPrivate { [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION qsizetype qustrlen(const char16_t *str) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION qsizetype qustrnlen(const char16_t *str, qsizetype maxlen) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION const char16_t *qustrchr(QStringView str, char16_t ch) noexcept; +[[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION const char16_t *qustrcasechr(QStringView str, char16_t ch) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION int compareStrings(QStringView lhs, QStringView rhs, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION int compareStrings(QStringView lhs, QLatin1StringView rhs, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; @@ -52,7 +53,8 @@ namespace QtPrivate { [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION bool endsWith(QLatin1StringView haystack, QStringView needle, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION bool endsWith(QLatin1StringView haystack, QLatin1StringView needle, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; -[[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION qsizetype findString(QStringView haystack, qsizetype from, char16_t needle, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; +[[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION qsizetype findStringInsensitive(QStringView haystack, qsizetype from, char16_t needle) noexcept; +[[nodiscard]] inline qsizetype findString(QStringView str, qsizetype from, QChar needle, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION qsizetype findString(QStringView haystack, qsizetype from, QStringView needle, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION qsizetype findString(QStringView haystack, qsizetype from, QLatin1StringView needle, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; [[nodiscard]] Q_CORE_EXPORT Q_DECL_PURE_FUNCTION qsizetype findString(QLatin1StringView haystack, qsizetype from, QStringView needle, Qt::CaseSensitivity cs = Qt::CaseSensitive) noexcept; diff --git a/src/corelib/text/qstringview.h b/src/corelib/text/qstringview.h index a598d7a445..76acbd92aa 100644 --- a/src/corelib/text/qstringview.h +++ b/src/corelib/text/qstringview.h @@ -456,6 +456,27 @@ inline QStringView qToStringViewIgnoringNull(const QStringLike &s) noexcept R{{char16_t(c), u'\0'}} ; } +qsizetype QtPrivate::findString(QStringView str, qsizetype from, QChar ch, Qt::CaseSensitivity cs) noexcept +{ + if (from < -str.size()) // from < 0 && abs(from) > str.size(), avoiding overflow + return -1; + if (from < 0) + from = qMax(from + str.size(), qsizetype(0)); + if (from < str.size()) { + const char16_t *s = str.utf16(); + char16_t c = ch.unicode(); + const char16_t *n = s + from; + const char16_t *e = s + str.size(); + if (cs == Qt::CaseSensitive) + n = qustrchr(QStringView(n, e), c); + else + n = qustrcasechr(QStringView(n, e), c); + if (n != e) + return n - s; + } + return -1; +} + QT_END_NAMESPACE #endif /* QSTRINGVIEW_H */ |