Clean up String::find and similar functions to remove duplicate code, and speed up comparison.#101247
Conversation
String::find to remove duplicate code, and speed up comparison slightly.
22cebbb to
3e000ed
Compare
String::find to remove duplicate code, and speed up comparison slightly.String::find to remove duplicate code, and speed up comparison.
|
When implementing #101493 I realized I should have used |
4205232 to
88bedca
Compare
|
I included the other |
effe962 to
e4b39cf
Compare
String::find to remove duplicate code, and speed up comparison.String::find and similar functions to remove duplicate code, and speed up comparison.
e4b39cf to
348433a
Compare
348433a to
90468e2
Compare
90468e2 to
b61ed1a
Compare
|
Since #104332 was merged, a good bit of this PR was superseded. |
0c12dc1 to
8206228
Compare
| constexpr int64_t Span<T>::rfind_sequence(const Span<T> &p_span, uint64_t p_from) const { | ||
| template <typename T1> | ||
| constexpr int64_t Span<T>::rfind_sequence(const Span<T1> &p_span, uint64_t p_from) const { | ||
| for (int64_t i = p_from; i >= 0; i--) { |
There was a problem hiding this comment.
should probably be i = Minimum(p_from, size() - p_span.size()) or spans_equal might search out of bounds
There was a problem hiding this comment.
Span is designed to be a low-level API, much like C++ low level APIs. In that, it assumes the caller knows what they're doing, and passes valid arguments.
If Span was defensive, and checked for the size against the parameter, it could measurably slow down rfind_sequence calls in a loop (which is something we actually do). The reason being that, on every iteration, it would make an unnecessary size check, even though it is known that the passed index is correct.
There was a problem hiding this comment.
If that's intentionnal then it's all good. It's just that you cannot shoot yourself in the foot with find_sequence, but you can with rfind_sequence, just need (a little) extra care when reviewing code where it's implied.
There was a problem hiding this comment.
Is it worth DEV_ASSERT()ing this?
There was a problem hiding this comment.
Good idea! Note that the function wasn't introduced in this PR, but I guess it's a good opportunity to foolproof it a bit.
8206228 to
e0046ca
Compare
|
This looks fine barring query about the |
e0046ca to
750efec
Compare
…on with `memcmp` where possible.
750efec to
43a8009
Compare
lawnjelly
left a comment
There was a problem hiding this comment.
Looks good.
(I haven't tested, buy I trust the author has tested, and from discussions in RC it seems like the string stuff would crash immediately if problems.)
I added the new unit tests for this reason. They should cover the changes' correctness. |
|
Thanks! |
I cleaned up all
Stringfind-like functions. They were very inconsistent implementation wise, unnecessarily long, and had one or two opportunities for optimization.Changes
string_equal_lower, to make implementations simpler.memcmpwhere possible (-> 2x speed up).if (src_len == 1)already. Due to my check added in Optimize string single char contains calls. #100024, this branch is no longer necessary.I'm pretty sure the new code doesn't change any behavior, except print no errors if
p_fromwas too large onfind.Benchmark
My changes can improve string-string case sensitive finds (
find,rfind,findmk) by 2x:2131mson master (5b52b4b)1054mson this PR (3e000ed43dd6905f77c4840d1ab49bc443ab6cb7)All other find functions will experience a ~10% speed up (tested earlier).