Aliasing performance problem.

[Łukasz Lew]

Hi,

I have a container similar to this one.

template <typename Nat, typename Elt>
class NatMap {
 public:
  Elt& operator[] (Nat nat) {
    return tab [nat.GetRaw()];
  }
 private:
  Elt tab [Nat::kBound];
};

I wanted to drop the requirement for Elt to have a default constructor:

template <typename Nat, typename Elt>
class NatMap {
 public:
  Elt& operator[] (Nat nat) {
    return ((Elt*)tab) [nat.GetRaw()];
  }
 private:
  char tab [Nat::kBound * sizeof(Elt)];
};

I use g++-4.3 and this code works 25% slower in my application than
the previous one. Unfortunately the slowdown does not manifest in a
synthetic benchmark. I guess it is something about compiler
optimizations, aliasing, aligning, or similar stuff.

Just now I tried new g++-4.4 and it gave me a following warning for
the latter code:
dereferencing pointer '<anonymous>' does break strict-aliasing rules

What should I do to get my performance back? (while not needing the
default constructor)

Thanks for any suggestion.
Lukasz
PS
If this is lack optimizations because of aliasing info, this has to be
doable somehow as STL have the same problem, doesn'it ?

[tom fogal-2]

I forgot to CC the list.  Sorry.

------- Forwarded Message

From: tom fogal <tfogal@...>
To: Łukasz Lew <lukasz.lew@...>
Subject: Re: Aliasing performance problem.
In-Reply-To: Your message of "Sun, 01 Nov 2009 19:35:37 +0100."
             <c55009e70911011035o1f206eadq36ade953b48543a@...>
References: <c55009e70911011035o1f206eadq36ade953b48543a@...>
Date: Sun, 01 Nov 2009 12:17:08 -0700

Łukasz Lew <lukasz.lew@...> writes:
> I wanted to drop the requirement for Elt to have a default constructor:
>
> template <typename Nat, typename Elt>
> class NatMap {
>  public:
>   Elt& operator[] (Nat nat) {
>     return ((Elt*)tab) [nat.GetRaw()];
>   }

use reinterpret_cast here.

How big is a `Nat'?  Could you instead pass it by reference?

>  private:
>   char tab [Nat::kBound * sizeof(Elt)];
> };
>
> I use g++-4.3 and this code works 25% slower in my application than
> the previous one. Unfortunately the slowdown does not manifest in a
> synthetic benchmark. I guess it is something about compiler
> optimizations, aliasing, aligning, or similar stuff.
>
> Just now I tried new g++-4.4 and it gave me a following warning for
> the latter code:
> dereferencing pointer '<anonymous>' does break strict-aliasing rules
>
> What should I do to get my performance back? (while not needing the
> default constructor)

first, compile with -fno-strict-aliasing to get your correctness back.

Then -- does it help if you force inlining of the method?  You might
also consider playing with the attributes on the function:

  http://gcc.gnu.org/onlinedocs/gcc-4.4.2/gcc/Function-Attributes.html

e.g. `hot', `pure' or `const' if applicable, `nothrow' though I bet
it won't help and I'm not sure if that's equivalent to `throw()', the
latter generally being a bad idea.

If that doesn't work, I would say compile it both ways and look at the
generated asm.

> If this is lack optimizations because of aliasing info, this has to
> be doable somehow as STL have the same problem, doesn'it ?

The STL `Container' concept requires the contained type to be
`DefaultConstructible', which has the semantics you would think.  I'm
going off the SGI STL docs, so that knowledge is a bit dated, though I
would imagine still generally accurate.

HTH,

- -tom

------- End of Forwarded Message

[Łukasz Lew]

On Sun, Nov 1, 2009 at 20:17, tom fogal <tfogal@...> wrote:

> Łukasz Lew <lukasz.lew@...> writes:
>> I wanted to drop the requirement for Elt to have a default constructor:
>>
>> template <typename Nat, typename Elt>
>> class NatMap {
>>  public:
>>   Elt& operator[] (Nat nat) {
>>     return ((Elt*)tab) [nat.GetRaw()];
>>   }
>
> use reinterpret_cast here.
>
> How big is a `Nat'?  Could you instead pass it by reference?

Nat is just one int.

>
>>  private:
>>   char tab [Nat::kBound * sizeof(Elt)];
>> };
>>
>> I use g++-4.3 and this code works 25% slower in my application than
>> the previous one. Unfortunately the slowdown does not manifest in a
>> synthetic benchmark. I guess it is something about compiler
>> optimizations, aliasing, aligning, or similar stuff.
>>
>> Just now I tried new g++-4.4 and it gave me a following warning for
>> the latter code:
>> dereferencing pointer '<anonymous>' does break strict-aliasing rules
>>
>> What should I do to get my performance back? (while not needing the
>> default constructor)
>
> first, compile with -fno-strict-aliasing to get your correctness back.
>:)

Adding -fno-strict-aliasing also reduces the loss of performance from
25% to 12%.


> Then -- does it help if you force inlining of the method?  You might
> also consider playing with the attributes on the function:
>
>  http://gcc.gnu.org/onlinedocs/gcc-4.4.2/gcc/Function-Attributes.html
>
> e.g. `hot', `pure' or `const' if applicable, `nothrow' though I bet
> it won't help and I'm not sure if that's equivalent to `throw()', the
> latter generally being a bad idea.

None helps.

>
> If that doesn't work, I would say compile it both ways and look at the
> generated asm.

That's hard.
I use this class in plenty of places.
Hot spot of the program is many 100's of lines of C++.
Moreover one change in line somewhere in code changes a whole assembly
beyond analyzing.

>
>> If this is lack optimizations because of aliasing info, this has to
>> be doable somehow as STL have the same problem, doesn'it ?
>
> The STL `Container' concept requires the contained type to be
> `DefaultConstructible', which has the semantics you would think.  I'm
> going off the SGI STL docs, so that knowledge is a bit dated, though I
> would imagine still generally accurate.

I'm not sure you are correct here.
Maybe that's true if you want to use functions like resize?

>
> HTH,
>
> -tom
>

[John S. Fine]

My first guess would be an alignment problem.  But that is just a guess
especially since you didn't say anything about how Elt aligns.

Also, an alignment problem is a little less likely in the code you
actually posted than it would be in the real code that you cut this out
of.  Do you really have the performance problem with this code?  Or have
you simplified the code to the point that you can't measure the performance?

I understand the strict-aliasing issue, but in this case it shouldn't
actually be a problem.  You always access the data as Elt and never as
char, so the fact that you allocate as char should only be an alignment
issue, not an aliasing issue.

Łukasz Lew wrote:

> Hi,
>
> I have a container similar to this one.
>
> template <typename Nat, typename Elt>
> class NatMap {
>  public:
>   Elt& operator[] (Nat nat) {
>     return tab [nat.GetRaw()];
>   }
>  private:
>   Elt tab [Nat::kBound];
> };
>
> I wanted to drop the requirement for Elt to have a default constructor:
>
> template <typename Nat, typename Elt>
> class NatMap {
>  public:
>   Elt& operator[] (Nat nat) {
>     return ((Elt*)tab) [nat.GetRaw()];
>   }
>  private:
>   char tab [Nat::kBound * sizeof(Elt)];
> };
>
> I use g++-4.3 and this code works 25% slower in my application than
> the previous one. Unfortunately the slowdown does not manifest in a
> synthetic benchmark. I guess it is something about compiler
> optimizations, aliasing, aligning, or similar stuff.
>
> Just now I tried new g++-4.4 and it gave me a following warning for
> the latter code:
> dereferencing pointer '<anonymous>' does break strict-aliasing rules
>
> What should I do to get my performance back? (while not needing the
> default constructor)
>
> Thanks for any suggestion.
> Lukasz
> PS
> If this is lack optimizations because of aliasing info, this has to be
> doable somehow as STL have the same problem, doesn'it ?
>
>  

[Łukasz Lew]

On Mon, Nov 2, 2009 at 02:24, John Fine <johnsfine@...> wrote:
> My first guess would be an alignment problem.

I tried to add __attribute__ ((align)) to the tab array, didn't help a bit.
Any other way I can try?

> But that is just a guess
> especially since you didn't say anything about how Elt aligns.

Elt usually is an int as well, but ocasionally a struct made of bunch of ints.

>
> Also, an alignment problem is a little less likely in the code you actually
> posted than it would be in the real code that you cut this out of.  Do you
> really have the performance problem with this code?

I optimized this code very much: consistent 1-2% perfomance improvemnt
was enough to accept the change to repository.
This way I learned a lot (especially how costly branches are). So yes,
25% loss is a big problem for me.


> Or have you simplified
> the code to the point that you can't measure the performance?

The code iself is not simplified. But the calling patters are compicated.
For instance I use
NatMap <Vertex, Vertex> next;
to represent set of disjont cyclic lists with:
act = next [act];   // act is of type Vertex
going to next element. I loop over this lists, merge them, etc
There is more but I think this example is enough to ilustrate the usage.



>
> I understand the strict-aliasing issue, but in this case it shouldn't
> actually be a problem.

>  You always access the data as Elt and never as char,
> so the fact that you allocate as char should only be an alignment issue, not
> an aliasing issue.
>
> Łukasz Lew wrote:
>>
>> Hi,
>>
>> I have a container similar to this one.
>>
>> template <typename Nat, typename Elt>
>> class NatMap {
>>  public:
>>  Elt& operator[] (Nat nat) {
>>    return tab [nat.GetRaw()];
>>  }
>>  private:
>>  Elt tab [Nat::kBound];
>> };
>>
>> I wanted to drop the requirement for Elt to have a default constructor:
>>
>> template <typename Nat, typename Elt>
>> class NatMap {
>>  public:
>>  Elt& operator[] (Nat nat) {
>>    return ((Elt*)tab) [nat.GetRaw()];
>>  }
>>  private:
>>  char tab [Nat::kBound * sizeof(Elt)];
>> };
>>
>> I use g++-4.3 and this code works 25% slower in my application than
>> the previous one. Unfortunately the slowdown does not manifest in a
>> synthetic benchmark. I guess it is something about compiler
>> optimizations, aliasing, aligning, or similar stuff.
>>
>> Just now I tried new g++-4.4 and it gave me a following warning for
>> the latter code:
>> dereferencing pointer '<anonymous>' does break strict-aliasing rules
>>
>> What should I do to get my performance back? (while not needing the
>> default constructor)
>>
>> Thanks for any suggestion.
>> Lukasz
>> PS
>> If this is lack optimizations because of aliasing info, this has to be
>> doable somehow as STL have the same problem, doesn'it ?
>>
>>
>

[Andrew Haley]

?ukasz Lew wrote:

> I have a container similar to this one.
>
> template <typename Nat, typename Elt>
> class NatMap {
>  public:
>   Elt& operator[] (Nat nat) {
>     return tab [nat.GetRaw()];
>   }
>  private:
>   Elt tab [Nat::kBound];
> };
>
> I wanted to drop the requirement for Elt to have a default constructor:
>
> template <typename Nat, typename Elt>
> class NatMap {
>  public:
>   Elt& operator[] (Nat nat) {
>     return ((Elt*)tab) [nat.GetRaw()];
>   }
>  private:
>   char tab [Nat::kBound * sizeof(Elt)];
> };
>
> I use g++-4.3 and this code works 25% slower in my application than
> the previous one. Unfortunately the slowdown does not manifest in a
> synthetic benchmark. I guess it is something about compiler
> optimizations, aliasing, aligning, or similar stuff.
>
> Just now I tried new g++-4.4 and it gave me a following warning for
> the latter code:
> dereferencing pointer '<anonymous>' does break strict-aliasing rules
>
> What should I do to get my performance back? (while not needing the
> default constructor)

The first thing you should do is fix the aliasing bug, and then repeat the
measurement.  It's hard for gcc to do a decent job optimizing code that
is incorrect.

Andrew.