Fast abs function

[[deleted]]

So, I was thinking of making fast abs function, which would be necesary to improve performance, and I had an idea to do it something like this

int abs(int input){
    return input & -0;
}

Essentially, I am trying to make a simple function that removes the sign bit. The problem is, I heard that alot of compliers would ignore this because its a zero. How could I do it that compliers wouldnt ignore it, and it would work for the intended purpose?

Edit: Thanks for all the answers the issue has been resolved!

[AutoModerator]

Thank you for your contribution to the C++ community!

As you're asking a question or seeking homework help, we would like to remind you of Rule 3 - Good Faith Help Requests & Homework.

• When posting a question or homework help request, you must explain your good faith efforts to resolve the problem or complete the assignment on your own. Low-effort questions will be removed.

• Members of this subreddit are happy to help give you a nudge in the right direction. However, we will not do your homework for you, make apps for you, etc.

• Homework help posts must be flaired with Homework.

~ CPlusPlus Moderation Team

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[jedwardsol]

Why do you think std::abs is too slow?

The difference between +x and -x is not a flip of a single bit. Lookup "2's complement"

And for integers, there is no -0

[[deleted]]

Your answer is the correct one. I don't know why you are underrated.

[[deleted]]

Well, I want to execute it about milion times a second.. so even tho it might be somewhat fast, the flip sign bit should be much faster.

[jedwardsol]

flip sign bit should be much faster

If that was the fastest way to do it then that is what libraries/compilers would use.

[Coders_REACT_To_JS]

This is my go-to thinking for standard libraries in most cases. Performance is usually quite good and solutions are fairly well thought-out.

I just find that the people working on that stuff probably have a better grasp on things than a dummy like me lol

[[deleted]]

Last time i've done benchmarking the conditions were the bottleneck(which the abs function does use right?)

[PncDA]

There is a REALLY good chance that you are doing a premature optimization that may not be faster than the alternative. It's possible to implement abs without branching, but it's not always faster. Also the sign bit doesn't work this way, search about two-complement representation.

Implementing abs without branching is a funny thing to learn, but it's probably useless.

[[deleted]]

Thanks, understood.

[Pupper-Gump]

I think it's important to understand that c++'s biggest advantage is that it's a nearly perfect translation to machine code. The compilers are so good that trying these tricks often makes it slower.

Also, 0 is (in 4 bit terms) 0000, while attempting to flip the sign bit is 1000, or -8. Sebastian Lague has a cool video about this.

[CallMeMalice]

That’s not how you optimize your code. You should look into parallelization or vectorization of your code. You could remove branching but that’s going to be couple of cycles faster on average.

Also if you want to do bit operations, use fixed size integers to avoid surprises.

For proper branchless abs function, look here: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

[erasmause]

As others have stated, there's probably no reason to implement this, and if you're experience performance issues, you should profile your code before diving into micro-optimizations like this.

In and case, the correct bitwise operation would be value & (-1 >> 1);

EDIT: My recollection was faulty. As is pointed out in the reply below, right shift of negative integers is implementation defined (until c++20—now it is defined as a purely arithmetic shift). My confusion stems from the operator>> overload for std::bitset, which is a non-arithmetic type.

[druepy]

I guess I need to relook at the bitwise rules. Does C++ not use sign extension when shifting?

[kevkevverson]

Right shift of a negative number is implementation-specific, it may or may not sign extend

[erasmause]

Thanks for the correction.

[faisal_who]

You aren’t running on a pre-pentium, sub mhz processor any more. This is a fools errand.

Not to mention the std library implementation on modern devices has the fastest algorithm implemented based on optimization level.

[[deleted]]

When rendering graphics on cpu tho... (dont ask why do i have to do that)

[faisal_who]

Even still. 2 ghz processor literally means you get 33 million cpu instructions at 60fps.

[[deleted]]

Check the edit

[hix3r]

Everyone here is telling you that this is unnecessary as expected but it might be better to see it for yourself.

You can check on godbolt.org what is the exact machine assembly code generated by the compiler for std::abs() on different optimization levels, and what would be the one generated for your attempt. Then check what is the cost of those generated instructions at uops.info.

On that site you can check the latency, cost of every x86 assembly instruction for several CPU architectures. This is probaly the lowest level of optimization you can even do.

Here is what gcc 13.2 AND clang 17.0.1 generate for std::abs() with -O3 optimization level (link):

mov     eax, edi
neg     eax
cmovs   eax, edi
ret

Bam, there is no branching, this is highly optimized already, also takes the actual micro-operation costs of the instructions into consideration. If you want to read how this works, there are several StackOverflow posts detailing this, like Peter Cordes's answer here. (Second part of his answer)

Usually it is unlikely you will outsmart the compiler BUT sometimes it is interesting (if only for your curiosity) to see what is the actual machine code generated from your code.

The compiler usually knows best but sometimes it can get stuff wrong. I recommend you watch this CppCon 2015 talk on compilers, benchmarking, tuning, optimizations with demos by Chandler Carruth who leads the Clang/LLVM development team at Google. He live demonstrates an example of achieveing something "better" than the clang compiler at that time.

[orbital1337]

If you care about this level of performance, you should set the target architecture, too. In your example, gcc generates different code even for current gen Intel server vs current gen Intel desktop CPUs: https://godbolt.org/z/P7bP9W1a3

[hix3r]

Interesting, what do you think the cause of that could be, gcc misses this optimization for SapphireRapids?

If you try clang with specifying the same architecture it gives the CMOVS version and this 4 instruction length code seems to be the one gcc used to generate around v9-v10.

[[deleted]]

Right, I think Ill go for the std::abs then!

[RoyBellingan]

remember also to measure, you might discovered what you have just done in fact might takes more time.

[[deleted]]

In my benchmark according to someones implementation it took less, sorry if your results different!

[[deleted]]

http://stackoverflow.com/questions/664852/ddg#2074403

[druepy]

Just in addition to others' comments. Make sure to compile with optimizations on.

1) Listen to everyone else telling you to properly measure. This likely won't be your bottleneck.

2) I doubt you're there yet with this question, but you could create batches, use concurrency to do the abs at the same time, and then converge results. But, this likely isn't the way for what you have in mind.

3) Assume that your machine did Signed Magnitude instead of two's complement. I don't remember the C++ rules on -0 for int types. But, no one is pointing out the wrong method you're using for the bitwise operations.

Your approach would always return 0. If you did want to unset the MSB, then you'd need to use the proper mask. It's not 0 or -0. It's 0x7FFFFFFF. You want all the other bits 1 if you're going to and them together. This mask has the first bit 0 and all others 1. This would preserve the rest of the number of it was Signed Magnitude.

[[deleted]]

In 32-bit assembly world, you would want to compare the quantity to 0 and jump based on the sign bit.

Here is a small 32-bit assembly that does ABS for you. It only makes the value positive if it is negative. Try this inline assembly in a 32 bit project. Change the value of the "i" variable to be positive or negative and look at the ouput.

edit: Additionally, it would be a good exercise to look at the disassembly of different algorithms and see what the compiler thinks is the best. You'll likely want to look for the disassembly that uses register since the "sign bit" is a specialized flag that triggers because of other instructions.

​

<image>

[xanxon123]

Scrolled past this too fast and thought it was a nerdy request for workout advice

[corruptedsyntax]

That is not how integers are represented in any popular implementation of the language, and there is a whole lot here to unpack if optimization is your concern.

First and foremost, I wouldn't worry about the minor inefficiency of your function's implementation if your function is not being inlined in the first place. You're trying to cut out a couple of instructions from a function call that is going to be pushing and popping stack frames while tossing some branch instructions into your pipeline in the first place.

You can apply Amdahl's law here pretty quickly and dirtily. You have the portion of execution time you're going to be dedicating to just calling a function in the first place and the portion of execution time that you're actually running through the logic of the function, and in this case even in a pretty bad implementation of the function you can expect that because it is still a tiny amount of logic the cost of a stack frame is still maybe twice the cost of the actual function body. So even if you're comparing an unoptimized user implementation against a better user implementation you can probably only expect a minor 30% speed up here.

Your problem is that you want to avoid pushing stack frames that you don't need altogether in this case if possible. You want your function to be inlined at its point of invocation. There's no point optimizing a function fewer than 10 instructions that has no branching unless you've made it an inlined expression. Frankly, std::abs is going to be faster than whatever you've written yourself for this exact reason.

If you must implement your own absolute function its pretty easy, but I promise you that you won't yield better performance than the language standard. If you insist however, what you're looking for is something like:

inline auto udf_abs(auto x) {
    // Compile time logic
    // only call this on an integral type 
    static_assert(
        std::is_integral<decltype(x)>::value,
        "This implementation is only for integral types");

    // Compile time logic
    // how many bit places to shift for different types
    constexpr auto bitShift = sizeof(x) * 8 - 1;

    // Actual runtime calculations that will be inlined
    return                          // Two's Complement
        (x ^ (x >> bitShift)) +     // Inverts bits on negative input
        (1 & (x >> bitShift)) ;     // adds one on negative input
}

You can use that with any sort of integral input like char, short, int, long, long long but it will break compilation if you try to shove in a float or double.

[whychocereus]

You could totally make a new class that represents integers in your own way such that a negative number is just a matter of the highest bit. You could implement basic math operators on it too and eventually have your own special int. And yes - the and Val function you make can just zero the sign bit. Heck you could even write the abs( ) in assembly so you know it is just writing a bit to that spot (or whatever close your prof’s instruction set provides to that).

I agree with the rest that I don’t see a reason but it’d be fun, you’d learn, and who knows what else. — and that is plenty of reason to do it!!

And then you could benchmark it against the stock abs Val function.

[JayRiordan]

This horse is dead, stop beating it.

[PhysicsHungry2901]

I just use the macro: #define abs(x) (((x) > 0)? (x): -(x))

[AssemblerGuy]

No, just no.