Prev: Review of a safer memory management approach for C++?
Next: Static variable in template function
From: Daniel Krügler on 7 Jun 2010 18:37
On 7 Jun., 17:09, Saeed Amrollahi <amrollahi.sa...(a)gmail.com> wrote:
[..]
> You are right. Of course we take advantage of inline expansion of
> operator(). In this case we have %25 performance improvement.
> For non-inline defintion (I mean defining function outside
> structure), the results are identical.
> The interesting question is:
> In case #1, when I declare bigger() with inline specifier, there is
> no performance improvement. Why?

This is the effect of an "indirect call". It is irrelevant,
whether the function is inline or not, but calling std::count_if
with the function bigger will have the effect, that a function
pointer is used as argument. This happens, even, if the actual
function is inline. Of-course, an implementation could still
inline such an indirect call, but that typically requires
much more analysis efforts of the compiler. For me details
on this topic I recommend to read chapters 22.1/2 in "C++
Templates" written by Vandevoorde/Josuttis.

HTH & Greetings from Bremen,

Daniel Kr�gler


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Alf P. Steinbach on 7 Jun 2010 18:36
* Saeed Amrollahi, on 07.06.2010 17:09:
> On Jun 7, 11:14 am, Keith H Duggar<dug...(a)alum.mit.edu> wrote:
>> On Jun 6, 6:15 pm, Saeed Amrollahi<amrollahi.sa...(a)gmail.com> wrote:
>>
>>> On Jun 5, 11:50 pm, albert kao<albertk...(a)gmail.com> wrote:
>>> 3. There is no performance gain by rewriting bigger() with function
>>> object. Calling member function is almost as efficient as
>>> calling global function.
>>
>> That is wrong. For most implementations of the STL you will find
>> that function objects can be /faster/ than passing free function
>> references/pointers. In the ops case
>>
>> struct Bigger
>> {
>> bool operator ( ) ( int i ) const { return abs(i)>= D ; }
>> } ;
>> ...
>> count += count_if(diff + 1, diff + N, Bigger());
>>
>> is likely to be much faster than
>>
>> bool bigger(int i) { return abs(i)>= D; }
>> ...
>> count += count_if(diff + 1, diff + N, bigger);
>>
>> Also, on many platforms
>>
>> struct Bigger
>> {
>> bool operator ( ) ( int i ) const { return i>= D || i<= -
>> D ; }
>> } ;
>>
>> will be faster still. Give it a try and you will see. By the way,
>> if you put the count_if into a loop you will get better sampling
>> and higher signal to noise. For example:
>>
>> int count = 0 ;
>> for ( int k = 0 ; k< 1024 ; ++k ) {
>> count += count_if(diff + 1, diff + N, Bigger()) ;
>> }
>>
>> KHD
>
> Hi Keith
>
> You are right. Of course we take advantage of inline expansion of
> operator(). In this case we have %25 performance improvement.
> For non-inline defintion (I mean defining function outside
> structure), the results are identical.
> The interesting question is:
> In case #1, when I declare bigger() with inline specifier, there is
> no performance improvement. Why?

The formal argument type 'Bigger' (it doesn't matter if it really turns out as
'Bigger const&', say) uniquely identifies the function to be executed, while a
formal argument of type 'bool (*)(int)' might be any function of that type.

For a simple optimizer how much information the argument type carries may
influence how and what it optimizes.

But while that at least sounds plausible, it is in the end a Quality of
Implementation issue.


Cheers & hth.,

- Alf

--
blog at <url: http://alfps.wordpress.com>

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: albert kao on 10 Jun 2010 05:39
On Jun 7, 4:14 am, Keith H Duggar <dug...(a)alum.mit.edu> wrote:
> On Jun 6, 6:15 pm, Saeed Amrollahi <amrollahi.sa...(a)gmail.com> wrote:
>
> > On Jun 5, 11:50 pm, albert kao <albertk...(a)gmail.com> wrote:
> > 3. There is no performance gain by rewriting bigger() with function
> > object. Calling member function is almost as efficient as
> > calling global function.
>
> That is wrong. For most implementations of the STL you will find
> that function objects can be /faster/ than passing free function
> references/pointers. In the ops case
>
> struct Bigger
> {
> bool operator ( ) ( int i ) const { return abs(i) >= D ; }
> } ;
> ...
> count += count_if(diff + 1, diff + N, Bigger());
>
> is likely to be much faster than
>
> bool bigger(int i) { return abs(i) >= D; }
> ...
> count += count_if(diff + 1, diff + N, bigger);
>
> Also, on many platforms
>
> struct Bigger
> {
> bool operator ( ) ( int i ) const { return i >= D || i <= -
> D ; }
> } ;
>
> will be faster still. Give it a try and you will see. By the way,
> if you put the count_if into a loop you will get better sampling
> and higher signal to noise. For example:
>
> int count = 0 ;
> for ( int k = 0 ; k < 1024 ; ++k ) {
> count += count_if(diff + 1, diff + N, Bigger()) ;
> }
>
> KHD
>

I write the function object as follows.
Feel free to comment.
class Bigger {
private:
int d;
public:
Bigger(int diff) : d(diff) {}
bool operator()(int i) {return i >= d || i <= -d;}
};

const int N = 50;
const int D1 = 40;
const int D2 = 41;
const int D3 = 42;

// I do not use a loop from 40 to 42 because of performance concern
int count = count_if(diff + 1, diff + N, Bigger(D1));
// use count
// ...
count = count_if(diff + 1, diff + N, Bigger(D2));
// use count
// ...
count = count_if(diff + 1, diff + N, Bigger(D3));
// use count
// ...


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: tcma on 10 Jun 2010 05:39
On Jun 7, 11:02 am, Ulrich Eckhardt <eckha...(a)satorlaser.com> wrote:
> Note up front: This has _very_ little to do with C++, as such things always
> depend on the actual implementation etc.
>
>
>
> albert kao wrote:
> > I want to optimize the following small integer program in speed.
> [...]
> > // initialize seq
> > // ...
> > adjacent_difference(seq, seq + N, diff);
> > int count = count_if(diff + 1, diff + N, bigger);
>
> You are computing a sequence of values from another sequence and then count
> the number of values in the generated sequence fitting certain criteria. If
> the sequences are large, a significant amount of time will be used by the
> CPU/MMU to transfer the values between RAM and the various cache levels. If
> you generate and count in one loop, the pressure on the memory IO system
> will be lower. In particular you then don't generate data, push it to RAM
> only to later load it again from RAM.
>
> Uli
>

What is the program to generate and count in one loop?
Please help.
Thanks.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ulrich Eckhardt on 10 Jun 2010 20:34
tcma wrote:
> On Jun 7, 11:02 am, Ulrich Eckhardt <eckha...(a)satorlaser.com> wrote:
[...]
>> albert kao wrote:
>> [...]
>> > adjacent_difference(seq, seq + N, diff);
>> > int count = count_if(diff + 1, diff + N, bigger);
[...]
> What is the program to generate and count in one loop?

In pseudo code it looks like this:

count = 0
for each pair(a, b) in sequence:
if bigger(b - a):
count += 1

Be sure to handle the special cases of a sequence containing zero or one
element.

Uli

--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Review of a safer memory management approach for C++?
Next: Static variable in template function