Click here to Skip to main content
15,878,231 members
Articles / Programming Languages / C#
Tip/Trick

No Code is the Fastest Code

Rate me:
Please Sign up or sign in to vote.
4.75/5 (4 votes)
8 Jan 2020CPOL2 min read 9.6K   44   2   15
Optimization of finding a point with shortest distance w.r.t. a point of interest

Table of Contents

Introduction

When it comes to optimization, majority of developers turn to parallelism but per CPU core isn't cheap. We could look to eliminate some operations to increase the per-thread performance first. That doesn't mean accuracy has to be sacrificed. With all other things being equal, the code with lesser operations shall be more performant, hence the tip title: no code is fastest code since no code needs to be executed.

Shortest Distance

We'll use the task of finding the shortest distance as an example. The formula of the length of a line is used to find the distance between 2 points, as shown below:

length of line formula

We have to compare and store the shorter distance. The interesting property of relationship of 2 numbers and their square roots is shown below: Given square root of D1 is lesser than that of D2, it should also be true that D1 is lesser than D2. We will make use of that property to forgo square root calculation.

Math property of lesser numbers and their square root

Below is the C# code using length of line formula, meaning with Math.Sqrt() to find the nearest distance with respect to dest. The C++ code is identical, except for the sqrt() call, so it is not shown here to avoid repetition.

C#
double shortest = 10000000.0;
int shortest_index = 0;

for (int j = 0; j < list.Count; ++j)
{
    Point pt = list[j];
    double x = (pt.x - dest.x);
    double y = (pt.y - dest.y);
    x *= x;
    y *= y;
    double distance = Math.Sqrt(x + y); // calling sqrt
    if (distance < shortest)
    {
        shortest = distance;
        shortest_index = j;
    }
}

This is the C# code to find the shortest distance without using Math.Sqrt() in the tight loop but Math.Sqrt() is still used to compute the distance outside the loop at the end when the shortest distance is found.

C#
double shortest2 = 10000000.0;
int shortest_index2 = 0;

for (int j = 0; j < list.Count; ++j)
{
    Point pt = list[j];
    double x = (pt.x - dest.x);
    double y = (pt.y - dest.y);
    x *= x;
    y *= y;
    double distance = x + y; // no calling sqrt
    if (distance < shortest2)
    {
        shortest2 = distance;
        shortest_index2 = j;
    }
}
shortest2 = Math.Sqrt(shortest2);

Benchmark Results

The benchmark is done on the computer with these specs: Intel(R) Core i7-8700 @ 3.2GHz CPU with 16GB RAM. The executable is built in Release x64 mode. Only one thread is utilized. The outer loop is done 1 million times while the inner loop is done on the List (or vector in C++) with one thousand elements.

C++
VC++ 2019 16.4 update, /Ox
============================
   With sqrt timing: 4855ms
Without sqrt timing: 1264ms

In Visual C++, we get a 74% speedup over the sqrt version. G++ and Clang++ benchmark are built and run in Windows Subsystem for Linux (Ubuntu 1804). It does seem like G++ and Clang++ has a more optimized sqrt() implementation over VC++'s. Both compilers generate faster code than VC++, despite having WSL overhead running on Windows.

C++
Clang++ 6.0.0, -O3
============================
   With sqrt timing: 1830ms
Without sqrt timing: 1047ms

With Clang++, we get 42% speedup.

C++
G++ 7.4.0, -O3
============================
   With sqrt timing: 2388ms
Without sqrt timing: 1211ms

With G++, we get almost 50% speedup, but its timing isn't as good as Clang++'s.

C++
C# 7, .NET Framework 4.6.1
============================
   With sqrt timing: 1938ms
Without sqrt timing: 1840ms

The result is surprising with C# 7. Only about 100 milliseconds shaved off the total time. So don't bother with this optimization in C# since the speed improvement is negligible (only 5% better).

History

  • 18th January, 2020: Add bailout before squaring code suggested by scjurgen to C++ and C# benchmark
  • 9th January, 2020: Initial release

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Singapore Singapore
Shao Voon is from Singapore. His interest lies primarily in computer graphics, software optimization, concurrency, security, and Agile methodologies.

In recent years, he shifted focus to software safety research. His hobby is writing a free C++ DirectX photo slideshow application which can be viewed here.

Comments and Discussions

 
SuggestionBailout before calculating the square Pin
scjurgen13-Jan-20 3:06
professionalscjurgen13-Jan-20 3:06 
GeneralRe: Bailout before calculating the square Pin
YvesDaoust13-Jan-20 23:36
YvesDaoust13-Jan-20 23:36 
GeneralRe: Bailout before calculating the square Pin
scjurgen13-Jan-20 23:51
professionalscjurgen13-Jan-20 23:51 
GeneralRe: Bailout before calculating the square Pin
YvesDaoust14-Jan-20 0:04
YvesDaoust14-Jan-20 0:04 
GeneralRe: Bailout before calculating the square Pin
Shao Voon Wong17-Jan-20 21:27
mvaShao Voon Wong17-Jan-20 21:27 
GeneralRe: Bailout before calculating the square Pin
Shao Voon Wong17-Jan-20 23:18
mvaShao Voon Wong17-Jan-20 23:18 
GeneralRe: Bailout before calculating the square Pin
Shao Voon Wong28-Jan-20 2:08
mvaShao Voon Wong28-Jan-20 2:08 
GeneralRe: Bailout before calculating the square Pin
scjurgen28-Jan-20 3:40
professionalscjurgen28-Jan-20 3:40 
QuestionICC Pin
E. Papulovskiy10-Jan-20 1:23
E. Papulovskiy10-Jan-20 1:23 
ICC on an old good Intel 4770 gives:

       With sqrt timing: 1024ms
    Without sqrt timing:  501ms
shortest: 9.25283, 9.25283
shortest index: 483, 483
Done!


MSVC was designed to produce GUI applications, it was never meant for speed.
QuestionFor VC++ use "/fp:fast" Pin
logica9-Jan-20 4:40
logica9-Jan-20 4:40 
QuestionMakefile Pin
Member 41335848-Jan-20 23:58
Member 41335848-Jan-20 23:58 
AnswerRe: Makefile Pin
Shao Voon Wong9-Jan-20 0:07
mvaShao Voon Wong9-Jan-20 0:07 
GeneralDebate PinPopular
Rick York8-Jan-20 19:48
mveRick York8-Jan-20 19:48 
GeneralRe: Debate Pin
Shao Voon Wong9-Jan-20 13:52
mvaShao Voon Wong9-Jan-20 13:52 
GeneralRe: Debate Pin
Rick York9-Jan-20 18:01
mveRick York9-Jan-20 18:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.