Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benno Evers]

> On May 3, 2018, 9:35 p.m., Benjamin Mahler wrote:
> > 3rdparty/stout/include/stout/strings.hpp
> > Lines 390 (patched)
> > 
> >
> > Can you mention the max length optimization you're doing?

I will add a comment if you think it is non-obvious, but intuitively I would 
have said that this is no more complicated than the other algorithms in this 
file?


> On May 3, 2018, 9:35 p.m., Benjamin Mahler wrote:
> > 3rdparty/stout/include/stout/strings.hpp
> > Lines 411-413 (patched)
> > 
> >
> > Any reason not to do the same max len optimization here?

There was, but as I was typing this reply I realized it not actually valid, so 
I'll update the review to add it as well.


- Benno


---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/#review202383
---


On May 8, 2018, 12:30 p.m., Benno Evers wrote:
> 
> ---
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/63367/
> ---
> 
> (Updated May 8, 2018, 12:30 p.m.)
> 
> 
> Review request for mesos, Alexander Rukletsov and Benjamin Mahler.
> 
> 
> Repository: mesos
> 
> 
> Description
> ---
> 
> This saves an unnecessary memory allocation when
> testing if a string starts or ends with a string literal,
> which accounts for almost all usages of these functions
> in Mesos and in libprocess.
> 
> 
> Diffs
> -
> 
>   3rdparty/stout/include/stout/strings.hpp 
> 067a7923c02342bccd9be1136a981fd6b0e0e9b4 
>   3rdparty/stout/tests/strings_tests.cpp 
> 395540aad88c76a66a43a54edfe9ca1a2d46d3b4 
> 
> 
> Diff: https://reviews.apache.org/r/63367/diff/7/
> 
> 
> Testing
> ---
> 
> 
> Thanks,
> 
> Benno Evers
> 
>

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benno Evers]

---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/
---

(Updated May 8, 2018, 12:30 p.m.)


Review request for mesos, Alexander Rukletsov and Benjamin Mahler.


Repository: mesos


Description
---

This saves an unnecessary memory allocation when
testing if a string starts or ends with a string literal,
which accounts for almost all usages of these functions
in Mesos and in libprocess.


Diffs (updated)
-

  3rdparty/stout/include/stout/strings.hpp 
067a7923c02342bccd9be1136a981fd6b0e0e9b4 
  3rdparty/stout/tests/strings_tests.cpp 
395540aad88c76a66a43a54edfe9ca1a2d46d3b4 


Diff: https://reviews.apache.org/r/63367/diff/7/

Changes: https://reviews.apache.org/r/63367/diff/6-7/


Testing
---


Thanks,

Benno Evers

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benjamin Mahler]

---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/#review202383
---


Ship it!





3rdparty/stout/include/stout/strings.hpp
Lines 390 (patched)


Can you mention the max length optimization you're doing?



3rdparty/stout/include/stout/strings.hpp
Lines 411-413 (patched)


Any reason not to do the same max len optimization here?


- Benjamin Mahler


On May 2, 2018, 6:30 p.m., Benno Evers wrote:
> 
> ---
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/63367/
> ---
> 
> (Updated May 2, 2018, 6:30 p.m.)
> 
> 
> Review request for mesos, Alexander Rukletsov and Benjamin Mahler.
> 
> 
> Repository: mesos
> 
> 
> Description
> ---
> 
> This saves an unnecessary memory allocation when
> testing if a string starts or ends with a string literal,
> which accounts for almost all usages of these functions
> in Mesos and in libprocess.
> 
> 
> Diffs
> -
> 
>   3rdparty/stout/include/stout/strings.hpp 
> 067a7923c02342bccd9be1136a981fd6b0e0e9b4 
>   3rdparty/stout/tests/strings_tests.cpp 
> 395540aad88c76a66a43a54edfe9ca1a2d46d3b4 
> 
> 
> Diff: https://reviews.apache.org/r/63367/diff/6/
> 
> 
> Testing
> ---
> 
> 
> Thanks,
> 
> Benno Evers
> 
>

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benno Evers]

---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/
---

(Updated May 2, 2018, 6:30 p.m.)


Review request for mesos, Alexander Rukletsov and Benjamin Mahler.


Changes
---

Added free micro-optimizations.


Repository: mesos


Description
---

This saves an unnecessary memory allocation when
testing if a string starts or ends with a string literal,
which accounts for almost all usages of these functions
in Mesos and in libprocess.


Diffs (updated)
-

  3rdparty/stout/include/stout/strings.hpp 
067a7923c02342bccd9be1136a981fd6b0e0e9b4 
  3rdparty/stout/tests/strings_tests.cpp 
395540aad88c76a66a43a54edfe9ca1a2d46d3b4 


Diff: https://reviews.apache.org/r/63367/diff/6/

Changes: https://reviews.apache.org/r/63367/diff/5-6/


Testing
---


Thanks,

Benno Evers

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benno Evers]

> On April 11, 2018, 2:06 a.m., Benjamin Mahler wrote:
> > 3rdparty/stout/include/stout/strings.hpp
> > Lines 390-392 (patched)
> > 
> >
> > This is definitely simple but is this how C++20 std libraries implement 
> > this?
> > 
> > It seems non-optimal to always have to scan the entire prefix array for 
> > the null character? E.g. startsWith("foo", "bar ... <1MB>"). Ideally this 
> > could trip to false after checking the first character only?

In `libc++` the implementation is the same:

```
template >
class basic_string_view {
/* ... */

_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
basic_string_view(const _CharT* __s)
: __data(__s), __size(_Traits::length(__s)) {}

/* ... */

_LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
bool starts_with(basic_string_view __s) const _NOEXCEPT
{ return size() >= __s.size() && compare(0, __s.size(), __s) == 0; }

/* ... */

_LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
bool starts_with(const value_type* __s) const _NOEXCEPT
{ return starts_with(basic_string_view(__s)); }

/* ... */
}
```

As far as I can see, it's not yet implemented in `libstdc++`, and I don't have 
access to the Windows standard library.

I think it's a bit of a trade-off, with this version you do an additional scan 
but gain vectorizability (if that is a word). If you don't know the length in 
advance, you can't really vectorize because you might accidentally read off the 
end of the string.

There does seem to be another free optimization here though: We don't need the 
full length of the prefix, as soon as we're at length `s.size()+1` we can abort.


- Benno


---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/#review200870
---


On April 3, 2018, 4:27 p.m., Benno Evers wrote:
> 
> ---
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/63367/
> ---
> 
> (Updated April 3, 2018, 4:27 p.m.)
> 
> 
> Review request for mesos, Alexander Rukletsov and Benjamin Mahler.
> 
> 
> Repository: mesos
> 
> 
> Description
> ---
> 
> This saves an unnecessary memory allocation when
> testing if a string starts or ends with a string literal,
> which accounts for almost all usages of these functions
> in Mesos and in libprocess.
> 
> 
> Diffs
> -
> 
>   3rdparty/stout/include/stout/strings.hpp 
> 067a7923c02342bccd9be1136a981fd6b0e0e9b4 
>   3rdparty/stout/tests/strings_tests.cpp 
> 395540aad88c76a66a43a54edfe9ca1a2d46d3b4 
> 
> 
> Diff: https://reviews.apache.org/r/63367/diff/5/
> 
> 
> Testing
> ---
> 
> 
> Thanks,
> 
> Benno Evers
> 
>

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benjamin Mahler]

---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/#review200870
---




3rdparty/stout/include/stout/strings.hpp
Lines 390-392 (patched)


This is definitely simple but is this how C++20 std libraries implement 
this?

It seems non-optimal to always have to scan the entire prefix array for the 
null character? E.g. startsWith("foo", "bar ... <1MB>"). Ideally this could 
trip to false after checking the first character only?


- Benjamin Mahler


On April 3, 2018, 4:27 p.m., Benno Evers wrote:
> 
> ---
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/63367/
> ---
> 
> (Updated April 3, 2018, 4:27 p.m.)
> 
> 
> Review request for mesos, Alexander Rukletsov and Benjamin Mahler.
> 
> 
> Repository: mesos
> 
> 
> Description
> ---
> 
> This saves an unnecessary memory allocation when
> testing if a string starts or ends with a string literal,
> which accounts for almost all usages of these functions
> in Mesos and in libprocess.
> 
> 
> Diffs
> -
> 
>   3rdparty/stout/include/stout/strings.hpp 
> 067a7923c02342bccd9be1136a981fd6b0e0e9b4 
>   3rdparty/stout/tests/strings_tests.cpp 
> 395540aad88c76a66a43a54edfe9ca1a2d46d3b4 
> 
> 
> Diff: https://reviews.apache.org/r/63367/diff/4/
> 
> 
> Testing
> ---
> 
> 
> Thanks,
> 
> Benno Evers
> 
>

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benjamin Mahler]

> On Jan. 24, 2018, 5:02 p.m., Michael Park wrote:
> > I would prefer a more general, systematic approach to this situation.
> > I really don't want to be deal with adding `string` and `const char []`
> > overloads everywhere. Ideally, we'd have a `string_view` class that we
> > could use instead of `string` here.
> > 
> > Now, as far as performance goes, there are a couple of things to note.
> >   (1) It seems like the claim is that it speeds up the tests? by how much?
> >   (2) The claim that we avoid an unnecessary allocation isn't actually
> >   true considering that the strings (at least in our tests) probably
> >   fit within the short-string optimization.
> >   (3) Is this change by itself a big win somewhere? or will it require
> >   a systematic change where `string` can be a `string_view`?
> >   If the former, I'd be fine with optimizing these functions, but
> >   if it's the former, I'd say we should invest in a `string_view` class.
> > 
> > I quite like performance, but some more evidence would be helpful here.
> > 
> > Now, under the assumption that the performance argument to be justified,
> > we can simply make the existing function a template and generalize the 
> > logic:
> > 
> > ```cpp
> > template 
> > bool startsWith(const string& s, const Stringish& prefix) {
> >   return s.size() >= distance(begin(prefix), end(prefix)) &&
> >  equal(begin(prefix), end(prefix), begin(s));
> > }
> > ```
> 
> Benno Evers wrote:
> I don't think the template version will work, unless there's an overload 
> of `std::end` for `const char*`? In general, the standard library also 
> includes overloads for `const char*` for most functions taking string 
> arguments (including the proposed `std::string_view::starts_with()`) so I 
> doubt there's some magic bullet to avoid that.
> 
> If we plan to embrace `string_view` in the future, we can still upgrade 
> the signature from `const char*` to `string_view`  once we made the switch to 
> C++17; nothing in this review makes it harder to introduce that. (unless you 
> want to avoid ABI breakage, but this would also prevent the template solution 
> above)
> 
> For the performance, I actually didn't do any measurements, but it seems 
> reasonable to assume that doing something will take more time than doing 
> nothing. Even if the string will be SSO-able on many platforms (not on all 
> though, we still build for e.g. Ubuntu 14.04 where the C++11 ABI isn't used 
> by default), it still has to be constructed first, which isn't free: 
> https://godbolt.org/g/SUJ9Tn
> 
> When testing this function in isolation, I can see about 30% speedup. In 
> the context of mesos, I don't expect to see a huge impact, but even a free 
> 0.1% would be nice to have, in particular in a function that was subject to 
> performance concerns in the past. (MESOS-5715)
> 
> Finally, having written all of this, my main motivation for this patch 
> was actually purely aesthetic: Paying a non-zero overhead to use an 
> abstraction just doesn't feel right in C++, no matter how small the practical 
> implications. ;)

Since C++20 will include starts_with and ends_with, it seems ok to just mimic 
the C++20 signatures now and put a TODO to remove these when we migrate to 
C++20.


- Benjamin


---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/#review196140
---


On April 3, 2018, 4:27 p.m., Benno Evers wrote:
> 
> ---
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/63367/
> ---
> 
> (Updated April 3, 2018, 4:27 p.m.)
> 
> 
> Review request for mesos, Alexander Rukletsov and Benjamin Mahler.
> 
> 
> Repository: mesos
> 
> 
> Description
> ---
> 
> This saves an unnecessary memory allocation when
> testing if a string starts or ends with a string literal,
> which accounts for almost all usages of these functions
> in Mesos and in libprocess.
> 
> 
> Diffs
> -
> 
>   3rdparty/stout/include/stout/strings.hpp 
> 067a7923c02342bccd9be1136a981fd6b0e0e9b4 
>   3rdparty/stout/tests/strings_tests.cpp 
> 395540aad88c76a66a43a54edfe9ca1a2d46d3b4 
> 
> 
> Diff: https://reviews.apache.org/r/63367/diff/4/
> 
> 
> Testing
> ---
> 
> 
> Thanks,
> 
> Benno Evers
> 
>

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benno Evers]

---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/
---

(Updated April 3, 2018, 4:27 p.m.)


Review request for mesos, Alexander Rukletsov and Benjamin Mahler.


Changes
---

Rebased onto latest master.


Repository: mesos


Description
---

This saves an unnecessary memory allocation when
testing if a string starts or ends with a string literal,
which accounts for almost all usages of these functions
in Mesos and in libprocess.


Diffs (updated)
-

  3rdparty/stout/include/stout/strings.hpp 
067a7923c02342bccd9be1136a981fd6b0e0e9b4 
  3rdparty/stout/tests/strings_tests.cpp 
395540aad88c76a66a43a54edfe9ca1a2d46d3b4 


Diff: https://reviews.apache.org/r/63367/diff/4/

Changes: https://reviews.apache.org/r/63367/diff/3-4/


Testing
---


Thanks,

Benno Evers

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benno Evers]

> On Jan. 24, 2018, 5:02 p.m., Michael Park wrote:
> > I would prefer a more general, systematic approach to this situation.
> > I really don't want to be deal with adding `string` and `const char []`
> > overloads everywhere. Ideally, we'd have a `string_view` class that we
> > could use instead of `string` here.
> > 
> > Now, as far as performance goes, there are a couple of things to note.
> >   (1) It seems like the claim is that it speeds up the tests? by how much?
> >   (2) The claim that we avoid an unnecessary allocation isn't actually
> >   true considering that the strings (at least in our tests) probably
> >   fit within the short-string optimization.
> >   (3) Is this change by itself a big win somewhere? or will it require
> >   a systematic change where `string` can be a `string_view`?
> >   If the former, I'd be fine with optimizing these functions, but
> >   if it's the former, I'd say we should invest in a `string_view` class.
> > 
> > I quite like performance, but some more evidence would be helpful here.
> > 
> > Now, under the assumption that the performance argument to be justified,
> > we can simply make the existing function a template and generalize the 
> > logic:
> > 
> > ```cpp
> > template 
> > bool startsWith(const string& s, const Stringish& prefix) {
> >   return s.size() >= distance(begin(prefix), end(prefix)) &&
> >  equal(begin(prefix), end(prefix), begin(s));
> > }
> > ```

I don't think the template version will work, unless there's an overload of 
`std::end` for `const char*`? In general, the standard library also includes 
overloads for `const char*` for most functions taking string arguments 
(including the proposed `std::string_view::starts_with()`) so I doubt there's 
some magic bullet to avoid that.

If we plan to embrace `string_view` in the future, we can still upgrade the 
signature from `const char*` to `string_view`  once we made the switch to 
C++17; nothing in this review makes it harder to introduce that. (unless you 
want to avoid ABI breakage, but this would also prevent the template solution 
above)

For the performance, I actually didn't do any measurements, but it seems 
reasonable to assume that doing something will take more time than doing 
nothing. Even if the string will be SSO-able on many platforms (not on all 
though, we still build for e.g. Ubuntu 14.04 where the C++11 ABI isn't used by 
default), it still has to be constructed first, which isn't free: 
https://godbolt.org/g/SUJ9Tn

When testing this function in isolation, I can see about 30% speedup. In the 
context of mesos, I don't expect to see a huge impact, but even a free 0.1% 
would be nice to have, in particular in a function that was subject to 
performance concerns in the past. (MESOS-5715)

Finally, having written all of this, my main motivation for this patch was 
actually purely aesthetic: Paying a non-zero overhead to use an abstraction 
just doesn't feel right in C++, no matter how small the practical implications. 
;)


- Benno


---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/#review196140
---


On Jan. 24, 2018, 3:12 p.m., Benno Evers wrote:
> 
> ---
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/63367/
> ---
> 
> (Updated Jan. 24, 2018, 3:12 p.m.)
> 
> 
> Review request for mesos, Alexander Rukletsov and Benjamin Mahler.
> 
> 
> Repository: mesos
> 
> 
> Description
> ---
> 
> This saves an unnecessary memory allocation when
> testing if a string starts or ends with a string literal,
> which accounts for almost all usages of these functions
> in Mesos and in libprocess.
> 
> 
> Diffs
> -
> 
>   3rdparty/stout/include/stout/strings.hpp 
> 067a7923c02342bccd9be1136a981fd6b0e0e9b4 
>   3rdparty/stout/tests/strings_tests.cpp 
> 395540aad88c76a66a43a54edfe9ca1a2d46d3b4 
> 
> 
> Diff: https://reviews.apache.org/r/63367/diff/3/
> 
> 
> Testing
> ---
> 
> 
> Thanks,
> 
> Benno Evers
> 
>

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Michael Park]

---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/#review196140
---



I would prefer a more general, systematic approach to this situation.
I really don't want to be deal with adding `string` and `const char []`
overloads everywhere. Ideally, we'd have a `string_view` class that we
could use instead of `string` here.

Now, as far as performance goes, there are a couple of things to note.
  (1) It seems like the claim is that it speeds up the tests? by how much?
  (2) The claim that we avoid an unnecessary allocation isn't actually
  true considering that the strings (at least in our tests) probably
  fit within the short-string optimization.
  (3) Is this change by itself a big win somewhere? or will it require
  a systematic change where `string` can be a `string_view`?
  If the former, I'd be fine with optimizing these functions, but
  if it's the former, I'd say we should invest in a `string_view` class.

I quite like performance, but some more evidence would be helpful here.

Now, under the assumption that the performance argument to be justified,
we can simply make the existing function a template and generalize the logic:

```cpp
template 
bool startsWith(const string& s, const Stringish& prefix) {
  return s.size() >= distance(begin(prefix), end(prefix)) &&
 equal(begin(prefix), end(prefix), begin(s));
}
```

- Michael Park


On Jan. 24, 2018, 7:12 a.m., Benno Evers wrote:
> 
> ---
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/63367/
> ---
> 
> (Updated Jan. 24, 2018, 7:12 a.m.)
> 
> 
> Review request for mesos, Alexander Rukletsov and Benjamin Mahler.
> 
> 
> Repository: mesos
> 
> 
> Description
> ---
> 
> This saves an unnecessary memory allocation when
> testing if a string starts or ends with a string literal,
> which accounts for almost all usages of these functions
> in Mesos and in libprocess.
> 
> 
> Diffs
> -
> 
>   3rdparty/stout/include/stout/strings.hpp 
> 067a7923c02342bccd9be1136a981fd6b0e0e9b4 
>   3rdparty/stout/tests/strings_tests.cpp 
> 395540aad88c76a66a43a54edfe9ca1a2d46d3b4 
> 
> 
> Diff: https://reviews.apache.org/r/63367/diff/3/
> 
> 
> Testing
> ---
> 
> 
> Thanks,
> 
> Benno Evers
> 
>

Re: Review Request 63367: Added overloads for strings::startsWith and strings::endsWith().

[Benno Evers]

---
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/63367/
---

(Updated Jan. 24, 2018, 3:12 p.m.)


Review request for mesos, Alexander Rukletsov and Benjamin Mahler.


Changes
---

Add symmetric overload for `strings::startsWith()`


Summary (updated)
-

Added overloads for strings::startsWith and strings::endsWith().


Repository: mesos


Description (updated)
---

This saves an unnecessary memory allocation when
testing if a string starts or ends with a string literal,
which accounts for almost all usages of these functions
in Mesos and in libprocess.


Diffs (updated)
-

  3rdparty/stout/include/stout/strings.hpp 
067a7923c02342bccd9be1136a981fd6b0e0e9b4 
  3rdparty/stout/tests/strings_tests.cpp 
395540aad88c76a66a43a54edfe9ca1a2d46d3b4 


Diff: https://reviews.apache.org/r/63367/diff/3/

Changes: https://reviews.apache.org/r/63367/diff/2-3/


Testing
---


Thanks,

Benno Evers