{"id":24544,"date":"2019-07-30T00:00:00","date_gmt":"2019-07-30T00:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/cppblog\/?p=24544"},"modified":"2019-07-30T18:16:05","modified_gmt":"2019-07-30T18:16:05","slug":"improving-the-performance-of-standard-library-functions","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/improving-the-performance-of-standard-library-functions\/","title":{"rendered":"Improving the Performance of Standard Library Functions"},"content":{"rendered":"

In Visual Studio 2019 version 16.2 we improved the codegen of several standard library functions. Guided by your feedback on Developer Community (Inlining std::lldiv<\/a> and Improved codegen for std::fmin, std::fmax, std::round, std::trunc<\/a>) we focused on the variants of standard division (std::div<\/code>, std::ldiv<\/code>, std::lldiv<\/code>) and std::isnan<\/code>.<\/p>\n

Originally function calls to the standard library, rather than inline assembly instructions, were generated upon each invocation of variations of std::div<\/code> and std::isnan<\/code>, regardless of the compiler optimization flags passed. Since these standard library function definitions live inside of the runtime, their definitions are opaque to the compiler and therefore not candidates for inlining and optimization. Furthermore, the function overhead of calling both std::div<\/code> and std::isnan<\/code> is greater than the actual cost of these operations. On most platforms, std::div<\/code> can be computed in a single instruction that returns both quotient and remainder while std::isnan<\/code> requires only a comparison and condition flag check. Inlining these calls would remove both function call overhead and allow optimizations to kick in since the compiler has the additional context of the calling function.<\/p>\n

To support inline assembly code generation we added a number of different functions as compiler intrinsics (also known as builtins) for std::isnan<\/code>, std::div<\/code>, and friends. Registering an intrinsic effectively “teaches” the meaning of that function to the compiler and results in greater control over the code generated. We went with a codegen solution rather than a library change to avoid altering library headers.<\/p>\n

Optimizing std::div and Friends<\/h3>\n

The MSVC compiler has pre-existing support for optimizing bare division and remainder operations. Therefore, to feed calls to std::div<\/code> into this existing compiler infrastructure, we recognize std::div<\/code> as a compiler intrinsic and then transform the inputs of our recognized call into the canonical format the compiler is expecting for division and remainder operations.<\/p>\n

Optimizing std::isnan<\/h3>\n

Replacing calls to std::isnan<\/code> was the more complicated of the two categories of functions we targeted due to the conflicting requirements of the C and C++ standards. According to the C standard, isnan<\/code> and the function it wraps, fpclassify<\/code>, are required to be implemented as macros, while C++ requires both operations to be implemented as function overloads. Below is a diagram of the call structure in C++ vs C, with functions that are required to be implemented as function overloads inside bolded blue boxes, functions that are required to be implemented as macros in dashed purple boxes, and those without a requirement in green.<\/p>\n

\"Diagram<\/p>\n

To get a unified solution for C and C++ code, we had to bypass both std::isnan<\/code> and std::fpclassify<\/code> to look at the functions std::fpclassify<\/code> wraps. We chose the green functions to register as compiler intrinsics since they lack any implementation requirements. Additionally, since each overload in either standard accomplishes the same task, we can transform instances of one standard’s intrinsics (we chose the C++ standard) into instances of our added C intrinsics. The table below demonstrates the results of the unification process that reduces the intrinsics we operate on after the initial pass from six to three.<\/p>\n\n\n\n\n\n\n\n\n\n
Function<\/td>\nIntrinsic function<\/td>\nIntrinsic After Unification<\/td>\n<\/tr>\n
_fdtest<\/code><\/td>\nIV__FDTEST<\/code><\/td>\nIV__FDCLASS<\/code><\/td>\n<\/tr>\n
_dtest<\/code><\/td>\nIV__DTEST<\/code><\/td>\nIV__DCLASS<\/code><\/td>\n<\/tr>\n
_ldtest<\/code><\/td>\nIV__LDTEST<\/code><\/td>\nIV__LDCLASS<\/code><\/td>\n<\/tr>\n
_fdclass<\/code><\/td>\nIV__FDCLASS<\/code><\/td>\nIV__FDCLASS<\/code><\/td>\n<\/tr>\n
_dclass<\/code><\/td>\nIV__DCLASS<\/code><\/td>\nIV__DCLASS<\/code><\/td>\n<\/tr>\n
_ldclass<\/code><\/td>\nIV__LDCLASS<\/code><\/td>\nIV__LDCLASS<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

Back to std::isnan<\/code>. The reasoning behind adding six new compiler intrinsics was to improve the code generation for std::isnan<\/code>. However, referencing the diagram from before, while we’ve transformed the functions that std::fpclassify<\/code> calls into, that hasn’t actually changed any of the codegen for std::isnan<\/code>. In the _dclass<\/code> case for example, we\u2019ve recognized all _dclass<\/code> calls as intrinsics, but as we\u2019re not changing the code generated for _dclass<\/code>, the code emitted is still the same call to _dclass<\/code> that we started out with.<\/p>\n

The last step required to recognize std::isnan<\/code> as an intrinsic and therefore enable more efficient code generation involves pattern matching. Checking if a float\/double\/etc. is a NaN looks something like this:<\/p>\n

isnan(double x) {\r\n    return FP_NAN == IV__DCLASS(x);\r\n}<\/pre>\n
Where FP_NAN<\/code> is a constant defined in both C and C++ standards. Now that it’s easy to identify calls to _dclass<\/code> and friends, the optimizer was extended to recognize the above pattern (a call to one of the three unified intrinsics followed by a comparison to the FP_NAN<\/code> constant) and transform it into the new std::isnan<\/code> intrinsic, IV_ISNAN<\/code>.<\/p>\n
Results<\/h3>\n
To better illustrate the codegen differences, below are samples of the different x64 code generation for both std::isnan<\/code> and std::div<\/code>.<\/p>\n
std::isnan(double)<\/h4>\n\n\n\n\n
Reference<\/td>\nWith Intrinsics<\/td>\n<\/tr>\n
lea rcx, QWORD PTR _X$[rsp]<\/code><\/p>\n
movsd QWORD PTR _X$[rsp], xmm0<\/code><\/p>\n
call\u00a0\u00a0\u00a0 _dtest<\/code><\/p>\n
cmp\u00a0\u00a0\u00a0\u00a0\u00a0 ax, 2<\/code><\/p>\n
sete\u00a0\u00a0\u00a0 al<\/code><\/td>\n
ucomisd xmm0, xmm0<\/code><\/p>\n
setp al<\/code><\/p>\n
movzx eax, al<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
 <\/p>\n
std::div(long, long)<\/h4>\n\n\n\n\n
Reference<\/td>\nWith Intrinsics<\/td>\n<\/tr>\n
mov edx, ebx<\/code><\/p>\n
mov ecx, edi<\/code><\/p>\n
call ldiv<\/code><\/td>\n
mov eax, esi<\/code><\/p>\n
mov rcx, rbx<\/code><\/p>\n
cdq<\/code><\/p>\n
idiv edi<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
 <\/p>\n
How much does effectively inlining these calls impact performance? When benchmarked by calling each operation on every member of a 1×109<\/sup> element array with unknown inputs, the following improvements can be observed:<\/p>\n\n\n\n\n\n
std::isnan(double)<\/td>\nReference<\/td>\nWith Intrinsics<\/td>\n% Improvement<\/td>\n<\/tr>\n
Avg (s)<\/td>\n4.03<\/td>\n1.25<\/td>\n69%<\/td>\n<\/tr>\n
Std Dev (s)<\/td>\n0.05<\/td>\n0.04<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
 <\/p>\n\n\n\n\n\n
std::div(long, long)<\/td>\nReference<\/td>\nWith Intrinsics<\/td>\n% Improvement<\/td>\n<\/tr>\n
Avg (s)<\/td>\n6.52<\/td>\n6.06<\/td>\n7%<\/td>\n<\/tr>\n
Std Dev (s)<\/td>\n0.11<\/td>\n0.04<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
 <\/p>\n
You can view the benchmark source here <\/a>on Compiler Explorer. Each benchmark was run six times on an Intel Xeon CPU v3 @3.50GHz, with the first warm-up run thrown out.<\/p>\n
Conclusion<\/h3>\n
The aforementioned optimizations will be enabled transparently with an upgrade to the 16.3 toolset in codebases compiled under \/O2. Otherwise, make sure you’re explicitly using \/Oi to enable intrinsic support.<\/p>\n
The C++ team is already looking ahead at improving the performance of standard library functions in future releases, with a similar optimization for std::fma<\/code> targeting the 16.4 release. As always, we welcome your feedback and feature requests for further codegen improvements. If you see cases of inefficient code generation, please reach out via the comments below or by opening an issue on D<\/a>eveloper <\/a>C<\/a>ommunity<\/a>.<\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
In Visual Studio 2019 version 16.2 we improved the codegen of several standard library functions. Guided by your feedback on Developer Community (Inlining std::lldiv and Improved codegen for std::fmin, std::fmax, std::round, std::trunc) we focused on the variants of standard division (std::div, std::ldiv, std::lldiv) and std::isnan. Originally function calls to the standard library, rather than inline […]<\/p>\n","protected":false},"author":5984,"featured_media":24545,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[218],"tags":[],"class_list":["post-24544","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-performance"],"acf":[],"blog_post_summary":"
In Visual Studio 2019 version 16.2 we improved the codegen of several standard library functions. Guided by your feedback on Developer Community (Inlining std::lldiv and Improved codegen for std::fmin, std::fmax, std::round, std::trunc) we focused on the variants of standard division (std::div, std::ldiv, std::lldiv) and std::isnan. Originally function calls to the standard library, rather than inline […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/24544","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/5984"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=24544"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/24544\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/24545"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=24544"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=24544"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=24544"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}