Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #14417 > unrolled thread

min/max by value - 25% faster

Back to article view | Back to comp.lang.c++

Contents

  min/max by value - 25% faster Eirik <eirik.olimstad@gmail.com> - 2012-02-22 04:56 -0800
    Re: min/max by value - 25% faster Mike McCarty <mcmccarty@gmail.com> - 2012-02-22 06:56 -0800
      Re: min/max by value - 25% faster gwowen <gwowen@gmail.com> - 2012-02-22 07:56 -0800
      Re: min/max by value - 25% faster Eirik <eirik.olimstad@gmail.com> - 2012-02-22 10:00 -0800
        Re: min/max by value - 25% faster Mike McCarty <mcmccarty@gmail.com> - 2012-02-22 14:06 -0800
          Re: min/max by value - 25% faster BGB <cr88192@hotmail.com> - 2012-02-22 16:37 -0700
    Re: min/max by value - 25% faster Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-22 14:16 -0800
    Re: min/max by value - 25% faster Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-02-22 22:23 +0000
      Re: min/max by value - 25% faster Eirik <eirik.olimstad@gmail.com> - 2012-02-23 04:47 -0800
        Re: min/max by value - 25% faster Miles Bader <miles@gnu.org> - 2012-02-23 22:43 +0900
        Re: min/max by value - 25% faster Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-02-23 15:39 +0000

#14417 — min/max by value - 25% faster

I see a ~25% increase in performance (VC2010 SP1) when adding an
overload that takes integers by value instead of const references.
Why are these not implemented as a part of STL for int, double, etc..?

#define MIN(a, b) a<b?a:b
#define MAX(a, b) a>b?a:b

namespace std
{
	inline const int min(int const a, int const b)
	{
		return MIN(a, b);
	}
	inline const int max(int const a, int const b)
	{
		return MAX(a, b);
	}
}

caller:
{
	std::vector<int> v(2);
	v[0] = get_some_random_number();
	v[1] = get_some_random_number();
	int m = std::min(v[0], v[1]); // ~25% faster when the overload above
is chosen
}

/Eirik

[toc] | [next] | [standalone]

#14422

~25% faster than what?  

0.3ns vs. 0.4ns?  

I.e. how did you measure this and how can you be sure what you're seeing isn't just noise?

[toc] | [prev] | [next] | [standalone]

#14425

On Feb 22, 2:56 pm, Mike McCarty <mcmcca...@gmail.com> wrote:
> ~25% faster than what?
>
> 0.3ns vs. 0.4ns?
>
> I.e. how did you measure this and how can you be sure what you're seeing isn't just noise?

Quite. And with what compiler options? Is the function even being
inlined, let alone having the reference/dereference elided?

[toc] | [prev] | [next] | [standalone]

#14429

On Feb 22, 3:56 pm, Mike McCarty <mcmcca...@gmail.com> wrote:
> ~25% faster than what?
>
> 0.3ns vs. 0.4ns?
>
> I.e. how did you measure this and how can you be sure what you're seeing isn't just noise?

~25% faster than just using std::min(int const&, int const&) as
specified by the standard.
How many nano seconds faster is not really relevant. But it ran for
about 20 seconds with about 420.000 iterations (see test iterations
below) per second.

test setup:
  int some_dummy_test_value = 0;
  size_t vector_size = 1000;
  vector<int> x = fill_vector_with_random_numbers(vector_size);
  vector<int> y = fill_vector_with_random_numbers(vector_size);

test iteration:
for(size_t i(0); i != vector_size; ++i)
{
  some_dummy_test_value += std::min(x[i], y[i]);
  some_dummy_test_value += std::max(x[i], y[i]);
}

[toc] | [prev] | [next] | [standalone]

#14435

420K iterations/second?  That's ~2us per iteration == very slow (as in unbelievably so).  It should take on order of nanoseconds, not microseconds.

In any case, it is possible that the optimizer realized that min(x,y)+max(x,y) == x+y and elided the conditional branches entirely.  It may not have been able to make that elision via references.  You might want to try making your benchmark less trivial.

[toc] | [prev] | [next] | [standalone]

#14441

On 2/22/2012 3:06 PM, Mike McCarty wrote:
> 420K iterations/second?  That's ~2us per iteration == very slow (as in unbelievably so).  It should take on order of nanoseconds, not microseconds.
>

yes. 2us is about 2x as long as it takes Windows to do a lock/unlock 
mutex pair on my system (via the "CreateMutex()" / 
"WaitForSingleObject()" route), which is itself absurdly slow (an 
"EnterCriticalSection()" / "LeaveCriticalSection()" pair is 15ns IIRC, 
or about 67x faster).

if so, yes, that is pretty damn slow.
unless of course someone is using an interpreter, HW emulator, or 
dragged some old-as-hell PC out of the closet ("how fast does it go on 
my early generation 386?").

far more likely, there is some sort of measurement issue, such as giving 
the wrong number of iterations or something...


> In any case, it is possible that the optimizer realized that min(x,y)+max(x,y) == x+y and elided the conditional branches entirely.  It may not have been able to make that elision via references.  You might want to try making your benchmark less trivial.

it depends.

it the compiler can figure out that the references aren't needed, it can 
optimize things away.

otherwise, it could be wasting a little bit of time getting/setting via 
references (which involve an additional indirection internally).


granted, in general, I would advise against putting too much weight into 
benchmarks of this sort without good reason though (very rarely are 
these the sorts of issues which impact the overall performance of a 
program).

generally, it is a good idea not to try to micro-optimize stuff unless 
it is really needed (not that one can't be aware of this stuff, or 
believe that it is all unknowable magic or something, but rather it is 
more that trying to optimize too much early on tends to result in 
overall worse code, and often not in areas which are actually 
particularly relevant to the overall running time).

this is also part of why there are profilers: they can help point out 
where optimization effort would be most useful.


or such...

[toc] | [prev] | [next] | [standalone]

#14437

On Feb 22, 4:56 am, Eirik <eirik.olims...@gmail.com> wrote:
> I see a ~25% increase in performance (VC2010 SP1) when adding an
> overload that takes integers by value instead of const references.
> Why are these not implemented as a part of STL for int, double, etc..?
>
> #define MIN(a, b) a<b?a:b
> #define MAX(a, b) a>b?a:b
>
> namespace std
> {
>         inline const int min(int const a, int const b)
>         {
>                 return MIN(a, b);
>         }
>         inline const int max(int const a, int const b)
>         {
>                 return MAX(a, b);
>         }
>
> }
>
> caller:
> {
>         std::vector<int> v(2);
>         v[0] = get_some_random_number();
>         v[1] = get_some_random_number();
>         int m = std::min(v[0], v[1]); // ~25% faster when the overload above
> is chosen
>
> }

As others have asked, what compiler, what platform, what compiler
options - specifically is optimization enabled?

[toc] | [prev] | [next] | [standalone]

#14439

On Wed, 2012-02-22, Eirik wrote:
> I see a ~25% increase in performance (VC2010 SP1) when adding an
> overload that takes integers by value instead of const references.
> Why are these not implemented as a part of STL for int, double, etc..?
>
...
> namespace std
> {
> 	inline const int min(int const a, int const b)
> 	{
> 		return MIN(a, b);
> 	}

With my compiler (g++ -O3 for amd64) I get the same assembly code when
using the overload -- which is exactly what I'd expect for something
this easy to optimize.

int foo(int a, int b)
{
    return std::min(a, b);
}

_Z3fooii:
        cmpl    %edi, %esi
        movl    %edi, %eax
        cmovle  %esi, %eax
        ret

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#14453

On Feb 22, 11:23 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
> On Wed, 2012-02-22, Eirik wrote:
> > I see a ~25% increase in performance (VC2010 SP1) when adding an
> > overload that takes integers by value instead of const references.
> > Why are these not implemented as a part of STL for int, double, etc..?
>
> ...
> > namespace std
> > {
> >    inline const int min(int const a, int const b)
> >    {
> >            return MIN(a, b);
> >    }
>
> With my compiler (g++ -O3 for amd64) I get the same assembly code when
> using the overload -- which is exactly what I'd expect for something
> this easy to optimize.
>
> int foo(int a, int b)
> {
>     return std::min(a, b);
>
> }
>
> _Z3fooii:
>         cmpl    %edi, %esi
>         movl    %edi, %eax
>         cmovle  %esi, %eax
>         ret
>
> /Jorgen
>
> --
>   // Jorgen Grahn <grahn@  Oo  o.   .     .
> \X/     snipabacken.se>   O  o   .

That example will of course result int the same, as foo takes
arguments by value...

[toc] | [prev] | [next] | [standalone]

#14455

Eirik <eirik.olimstad@gmail.com> writes:
> That example will of course result int the same, as foo takes
> arguments by value...

Er, isn't that the whole point -- that std::min yields _exactly the
same code_ as your hand-rolled not-using-references MIN thingy
(meaning there's no reason to not use std::min)?

-miles

-- 
Innards, n. pl. The stomach, heart, soul, and other bowels.

[toc] | [prev] | [next] | [standalone]

#14457

On Thu, 2012-02-23, Eirik wrote:
> On Feb 22, 11:23 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
>> On Wed, 2012-02-22, Eirik wrote:
>> > I see a ~25% increase in performance (VC2010 SP1) when adding an
>> > overload that takes integers by value instead of const references.
>> > Why are these not implemented as a part of STL for int, double, etc..?
>>
>> ...
>> > namespace std
>> > {
>> >    inline const int min(int const a, int const b)
>> >    {
>> >            return MIN(a, b);
>> >    }
>>
>> With my compiler (g++ -O3 for amd64) I get the same assembly code when
>> using the overload -- which is exactly what I'd expect for something
>> this easy to optimize.
>>
>> int foo(int a, int b)
>> {
>>     return std::min(a, b);
>>
>> }
>>
>> _Z3fooii:
>>         cmpl    %edi, %esi
>>         movl    %edi, %eax
>>         cmovle  %esi, %eax
>>         ret

> That example will of course result int the same, as foo takes
> arguments by value...

It was the simplest case I could come up with quickly without having
it all optimized away.

Then please come up with a better example. "int foo(const int& a,
const int& b)" perhaps? The burden of proof must ultimately be on you.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web