4
\$\begingroup\$

In my program I call "granularity" the "minimum step" for a number. For example, if granularity == 4 then I only work with numbers "0, 4, 8, 12 etc" (so normal integer has granularity == 1).

I need a function to round an integer number to a certain granularity. So for example, if granularity == 3, I want this map:

// I don't use negative number so don't care about negative results
0 -> 0
1 -> 0
2 -> 3
3 -> 3
4 -> 3
5 -> 6
6 -> 6
7 -> 6
8 -> 9
and so on

This is my implementation:

#include <iostream>
#include <stdint.h>

using namespace std;

typedef int64_t myDecimal;

myDecimal Round(myDecimal val, myDecimal granularity)
{
    myDecimal rest = val % granularity;
    myDecimal candidat = val / granularity;
    if (2 * rest < granularity) {
        return candidat * granularity;
    } else {
        return (candidat + 1) * granularity;
    }
}

int main()
{
    for (int i = -10; i < 10; i++){
        std::cout << "i = " << i << " " << Round(i, 3) << std::endl;
    }
    return 0;
}

How can you further improve it for better latency as I'm using this in HFT trading?

\$\endgroup\$
3
\$\begingroup\$

Let me start with the usual:

Naming

  • myDecimal: Usually, the prefix "my" does not bear any sensible information. You should think about the information you want to pass by the types name. (For example Decimal is often the name for decimal fractions and the way in which numbers are stored in it!)
  • rest: in the context of a modulus this is called remainder
  • candidat: this is a candidat but where is the other one and which one is it? You should call this something like: flooredValue

Reusability

Everytime that you use this function you have to use the exact type or must cast, which is slow. You should think about making it a template function.

Performance

Most of this is micro optimizations but you seem to be interested in every last bit of time. I don't know how much of this is automatically done by your optimizing compiler:

  • go to assembler: This is very easy code that can be written in assembler. Especially the division and modulus are two functions that are slow (compared to others) and (at least) on x86 architectures the assembler instruction for division gives you the modulus at the same time. (likely optimized by the compiler)
  • multiplication by 2: this can be replaced by a left shift by one (very likely optimized by the compiler)
  • multiplication in return: instead of using a multiplication you can use an addition to return the results (return val - remainder; and return val + granularity - remainder;) (maybe not optimized by the compiler)

Note that all of those "optimizations" could be done automatically by the compiler and even more important might not be optimizations on modern architectures anymore. When it comes to performance you should compare on the assembler level and do extensive profiling.

\$\endgroup\$
2
  • \$\begingroup\$ One can get quotient and remainder without going to assembly language using std::ldiv \$\endgroup\$ – Edward May 9 '14 at 11:03
  • \$\begingroup\$ @Edward: I should have known that. However, the question is if this goes nicely into registers when optimized. \$\endgroup\$ – Nobody moving away from SE May 9 '14 at 11:05
3
\$\begingroup\$

Some minor things:

  • In C++, use <cstdint> instead of <stdint.h>; the latter is a C library.

  • You can somewhat improve performance by using "\n" instead of std::endl. The latter also flushes the buffer, which takes longer and is not what you need here.

  • The return 0 at the end of main() is not needed. Reaching this point always indicates a successful termination, and the compiler will automatically stick in the return 0.

\$\endgroup\$
2
  • \$\begingroup\$ thanks, std::endl is in test code only, i want to optimize performance of Round function which doesn't have any output to console, of course. \$\endgroup\$ – Oleg Vazhnev May 10 '14 at 8:17
  • \$\begingroup\$ @javapowered: Right. The other reviewer has already mentioned much about that, and I just had a few things to add. \$\endgroup\$ – Jamal May 10 '14 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.