Re: [llvm-dev] Improvements to std::find and std::count

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Improvements to std::find and std::count

Nat! via cfe-dev
Adding cfe-dev. Removing llvm-dev.  Frontend and libary discussions are better represented on that list.

~Craig

On Sat, Apr 29, 2017 at 7:13 AM, Daniel Cooke via llvm-dev <[hidden email]> wrote:
Hi,

I recently posted a question on StackOverflow regarding the performance of std::find and std::count when provided with char* input: http://stackoverflow.com/questions/43483378/why-arent-stdcount-and-stdfind-optimised-to-use-memchr.

I would propose adding overloads of these functions for char* and const char* inputs that delegate to memchr, something like:

inline const char* find(const char* first, const char* const last, const char value)
{
const auto result = std::memchr(first, value, last - first);
return result != nullptr ? static_cast<const char*>(result) : last;
}

inline typename std::iterator_traits<const char*>::difference_type
count(const char* first, const char* const last, const char value)
{
typename std::iterator_traits<const char*>::difference_type result {0};
while (first && first != last) {
if ((first = static_cast<const char*>(std::memchr(first, value, last - first)))) {
++result;
++first;
}
}
return result;
}

I’ve never contributed to LLVM, so I’m not sure how to proceed, if this is a change that is likely to be accepted?

Best,
Dan


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Improvements to std::find and std::count

Nat! via cfe-dev


On Mon, May 1, 2017 at 10:15 AM, Craig Topper via cfe-dev <[hidden email]> wrote:
Adding cfe-dev. Removing llvm-dev.  Frontend and libary discussions are better represented on that list.

~Craig

On Sat, Apr 29, 2017 at 7:13 AM, Daniel Cooke via llvm-dev <[hidden email]> wrote:
Hi,

I recently posted a question on StackOverflow regarding the performance of std::find and std::count when provided with char* input: http://stackoverflow.com/questions/43483378/why-arent-stdcount-and-stdfind-optimised-to-use-memchr.

I would propose adding overloads of these functions for char* and const char* inputs that delegate to memchr, something like:

inline const char* find(const char* first, const char* const last, const char value)
{
const auto result = std::memchr(first, value, last - first);
return result != nullptr ? static_cast<const char*>(result) : last;
}

inline typename std::iterator_traits<const char*>::difference_type
count(const char* first, const char* const last, const char value)
{
typename std::iterator_traits<const char*>::difference_type result {0};
while (first && first != last) {
if ((first = static_cast<const char*>(std::memchr(first, value, last - first)))) {
++result;
++first;
}
}
return result;
}

I’ve never contributed to LLVM, so I’m not sure how to proceed, if this is a change that is likely to be accepted?

If the change *measurably* improves performance while maintaining correctness then yes, it is very likely to be accepted.
 
The first step would be to write a benchmark that demonstrates the performance difference by adding a test in `libcxx/benchmarks/algorithms.bench.cpp`.
Personally I would write two different benchmarks, one that uses `std::find` and another that uses `std::memchr` on the same set of input.

/Eric


Best,
Dan


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Improvements to std::find and std::count

Nat! via cfe-dev
In reply to this post by Nat! via cfe-dev
On 1 May 2017 9:15 am, "Craig Topper via cfe-dev" <[hidden email]> wrote:
Adding cfe-dev. Removing llvm-dev.  Frontend and libary discussions are better represented on that list.

True, but we might also want to consider whether llvm's loop idiom recognition pass should be able to catch this.

~Craig

On Sat, Apr 29, 2017 at 7:13 AM, Daniel Cooke via llvm-dev <[hidden email]> wrote:
Hi,

I recently posted a question on StackOverflow regarding the performance of std::find and std::count when provided with char* input: http://stackoverflow.com/questions/43483378/why-arent-stdcount-and-stdfind-optimised-to-use-memchr.

I would propose adding overloads of these functions for char* and const char* inputs that delegate to memchr, something like:

inline const char* find(const char* first, const char* const last, const char value)
{
const auto result = std::memchr(first, value, last - first);
return result != nullptr ? static_cast<const char*>(result) : last;
}

inline typename std::iterator_traits<const char*>::difference_type
count(const char* first, const char* const last, const char value)
{
typename std::iterator_traits<const char*>::difference_type result {0};
while (first && first != last) {
if ((first = static_cast<const char*>(std::memchr(first, value, last - first)))) {
++result;
++first;
}
}
return result;
}

I’ve never contributed to LLVM, so I’m not sure how to proceed, if this is a change that is likely to be accepted?

Best,
Dan


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev



_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev