low-level, ugly pointer arithmetics

[Jacek Dziedzic]

Hi!

I'm trying to squeeze a few clock cycles from a tight
loop that profiling shows to be a bottleneck in my program.
I'm at a point where the only thing that matters is
execution speed, not style (within the loop, obviously).

The loop deals with an array:

// this is aligned at cache line boundaries
struct hash_t {
int id;
int next;
double d0;
double d1;
double d2;
} hashtable[HASH_MAX];

within the loop, whenever there is a hashtable miss I
need to store new values into hashtable[index].
Originally this looked like

if(...) {
hashtable[index].id=some_int;
hashtable[index].next=some_int2 ;
hashtable[index].d0=some_double 0;
hashtable[index].d1=some_double 1;
hashtable[index].d2=some_double 2;
}

Now... I'm trying to save a few cycles by doing something
along the lines of

if(...) {
// point to the first member
int *hashtable_ptr = reinterpret_cas t<int*&(hashtab le[index].id)
*(hashtable_ptr ++) = some_int; // store into id and move on
*(hashtable_ptr ++) = some_int2; // store into next and move on
*(hashtable_ptr ++) = some_double0; // << --- trouble
// ...
}

the trouble is that I'm working with a pointer to int
and I want to store a double and, later on, advance the
pointer not by sizeof(int) bytes, but by sizeof(double)
bytes. On my system sizeof(int) is 4, sizeof(double) is 8
and portability is not an issue.

I tried

*((reinterpret_ cast<double*>(h ashtable_ptr))+ +) = some_double0;

but I got an error:

"the result of this cast cannot be used as an lvalue".

Why's that? I really need to force the compiler to treat
this pointer as a double* for a moment... I realize I can
have two pointers to the same hashtable entry, one an int*
and one a double*, but I need to save every clock cycle I
can as this loop is executed trillions of times.

What's the usual procedure to iterate a pointer through
members of varying types? Perhaps it would be easier with
a char*, but that means advancing by 4 and 8 which,
I suppose, would be slower than plain ++? Or does it boil
to moving by 4 or 8 offsets at the assembly level too?

thanks in advance,
- J.

PS. Are pointers to different datatypes guaranteed to
be of the same size? If not, than perhaps I need
an assert here and there...

[Bart]

Jacek Dziedzic wrote:

Hi!

I'm trying to squeeze a few clock cycles from a tight
loop that profiling shows to be a bottleneck in my program.
I'm at a point where the only thing that matters is
execution speed, not style (within the loop, obviously).

The loop deals with an array:

// this is aligned at cache line boundaries
struct hash_t {
int id;
int next;
double d0;
double d1;
double d2;
} hashtable[HASH_MAX];

within the loop, whenever there is a hashtable miss I
need to store new values into hashtable[index].
Originally this looked like

if(...) {
hashtable[index].id=some_int;
hashtable[index].next=some_int2 ;
hashtable[index].d0=some_double 0;
hashtable[index].d1=some_double 1;
hashtable[index].d2=some_double 2;
}

Now... I'm trying to save a few cycles by doing something
along the lines of

if(...) {
// point to the first member
int *hashtable_ptr = reinterpret_cas t<int*&(hashtab le[index].id)
*(hashtable_ptr ++) = some_int; // store into id and move on
*(hashtable_ptr ++) = some_int2; // store into next and move on
*(hashtable_ptr ++) = some_double0; // << --- trouble
// ...
}

Accessing a double through a pointer to int causes undefined behavior.
In any case, unless you have a 10+ year old compiler it is almost
certain the compiler has done this optimization already (or a better
one even). If you're at this level of optimization then you should
probably look at the disasembly of the code to see what the compiler
generates and/or write your own assembly routine. Many processors have
vector instructions or similar stuff that could help you here.

Regards,
Bart.

[Bart]

<snip>

Oh and one more thing. Since you just seem to be copying members of a
POD structure then memcpy() is also acceptable, and it is probably
implemented optimally for your system as well.

Regards,
Bart.

[Jacek Dziedzic]

Bart wrote:

[snip]
Accessing a double through a pointer to int causes undefined behavior.

But doesn't a cast alleviate this? I thought the compiler
would understand that I want to treat the binary representation
of a pointer to int like it was a pointer to double, so that
it would store the value correctly and then increment it
correctly. Won't this work?

In any case, unless you have a 10+ year old compiler it is almost
certain the compiler has done this optimization already (or a better
one even). If you're at this level of optimization then you should
probably look at the disasembly of the code to see what the compiler
generates and/or write your own assembly routine.

Yes and no. The compiler is a month-old intel compiler,
tuned to this particular architecture (Itanium 2), so you'd
expect it to be extremely aggresive, more so since this
architecture relies heavily on the compiler doing the
optimizations.

However, even with -O3 and other aggressive optimization
options I was able to outsmart the compiler in two places
by merely converting

array[index][0]=double0;
array[index][1]=double1;
array[index][2]=double2;

into

array_ptr = array[index];
*(array_ptr++)= ...;
*(array_ptr++)= ...;
*(array_ptr )=...;

as proven by profiler output. Writing my own assembly
routine is out of question -- this IA64 assembly output
is absolutely unreadable (at least to me, I only have
experience with x86 assembly) and looks like it is
quite heavily optimized already. Still, experience of the
past three days shows that translating indexing into
pointer arithmetics somehow makes the compiler perform
better still.

Many processors have
vector instructions or similar stuff that could help you here.

Yes, this processor in particular. My teammate managed
to vectorize the pow() and sqrt() operations which were
the previous bottleneck. What appears as the next bottleneck
is cache penalties for accessing elements of a large
(~1e6 doubles) array in an almost random order, many many
times. Hence I am trying to code a hashtable that would
store the values of most recently used elements in a
smaller table that would fit within the L2 cache.

Anyway, is there _really_ no way to access elements of
a struct using a single, advancing pointer? I suspect
some controller-programming C gurus would know a way?

TIA,
- J.

[Heinz Ozwirk]

"Jacek Dziedzic" <jacek@no_spam. tygrys.no_spam. netschrieb im Newsbeitrag
news:3f******** *************** ****@news.chell o.pl...

>
Hi!

I'm trying to squeeze a few clock cycles from a tight
loop that profiling shows to be a bottleneck in my program.
I'm at a point where the only thing that matters is
execution speed, not style (within the loop, obviously).

The loop deals with an array:

// this is aligned at cache line boundaries
struct hash_t {
int id;
int next;
double d0;
double d1;
double d2;
} hashtable[HASH_MAX];

within the loop, whenever there is a hashtable miss I
need to store new values into hashtable[index].
Originally this looked like

if(...) {
hashtable[index].id=some_int;
hashtable[index].next=some_int2 ;
hashtable[index].d0=some_double 0;
hashtable[index].d1=some_double 1;
hashtable[index].d2=some_double 2;
}

Now... I'm trying to save a few cycles by doing something
along the lines of

if(...) {
// point to the first member
int *hashtable_ptr = reinterpret_cas t<int*&(hashtab le[index].id)
*(hashtable_ptr ++) = some_int; // store into id and move on
*(hashtable_ptr ++) = some_int2; // store into next and move on
*(hashtable_ptr ++) = some_double0; // << --- trouble
// ...
}

the trouble is that I'm working with a pointer to int
and I want to store a double and, later on, advance the
pointer not by sizeof(int) bytes, but by sizeof(double)
bytes. On my system sizeof(int) is 4, sizeof(double) is 8
and portability is not an issue.

I tried

*((reinterpret_ cast<double*>(h ashtable_ptr))+ +) = some_double0;

but I got an error:

"the result of this cast cannot be used as an lvalue".

Why's that?

The result of a cast is an rvalue, not an lvalue. Think of it as a temporary
variable. Then your statement becomes something like

double* temp = reinterpret_cas t<double*>(hash table_ptr);
*temp = some_double0;
temp++;

The problem is the final increment. It increments the temporary, not the
hashtable_ptr. To do that, you have to add an extra level of indirection

*((*reinterpret _cast<double**> (&hashtable_ptr ))++) = some_double0;

But before you try such nasty code, you should try something more readable:

if (...)
{
hash_t* ptr = &hashtable[index];
ptr->id = some_int;
ptr->next = some_int2;
ptr->d0 = some_double0;
...
}

If some_int, some_int2 etc. are local variables, which are computed as part
of the function, it might also improve speed if you replace all those
variables with a single, local instance of a hash_t struct. For most
compilers, code like

hash_t data;
data.id = ...
...

should be as fast as

int id, next;
double d0, d1, ...;
id = ...
...

But you could then copy the structure as a whole, like

if (...) hashtable[index] = data;

of even use memcpy, which still is much more readable than your pointer
tricks. Such tricks often even have negative effects on speed. Measure such
"improvemen t" very carefully and do it for every update of your compiler.
Even a compiler will understand (and optimize) simple code mush better than
tricky casts and pointer arithmetic.

I really need to force the compiler to treat
this pointer as a double* for a moment...

When you force a compiler to do something the way you want, you also force
it, not to do something it could do better than you do.

I realize I can
have two pointers to the same hashtable entry, one an int*
and one a double*, but I need to save every clock cycle I
can as this loop is executed trillions of times.

What's the usual procedure to iterate a pointer through
members of varying types? Perhaps it would be easier with
a char*, but that means advancing by 4 and 8 which,
I suppose, would be slower than plain ++? Or does it boil
to moving by 4 or 8 offsets at the assembly level too?

That depends on the hardware, your program is running on. Test it! And
remember, such tests are only valid for a single version of a compiler. You
have to test it again for each and every combination of hardware, operating
system and compiler. And the results may still depend on your code.

Heinz

[Jacek Dziedzic]

Bart wrote:

<snip>

Oh and one more thing. Since you just seem to be copying members of a
POD structure then memcpy() is also acceptable, and it is probably
implemented optimally for your system as well.

Again, yes and no. The two things are that:
a) the source values that need to be stored into members
of the hash_t struct do not lie at subsequent addresses,
and if things work as expected they are in registers.
b) even though I believe memcpy() to be optimized to a single
cycle, the structure is so small (32 bytes) that I doubt
it would perform well, even if it is inlined.
Unfortunately this is not a case of copying multiple
entries of an array.

I guess b) may be disputed, but a) makes this a no-no.

thanks anyway,
- J.

[Bart]

Jacek Dziedzic wrote:

Bart wrote:

[snip]
Accessing a double through a pointer to int causes undefined behavior.

But doesn't a cast alleviate this? I thought the compiler
would understand that I want to treat the binary representation
of a pointer to int like it was a pointer to double, so that
it would store the value correctly and then increment it
correctly. Won't this work?

The cast only shuts up the compiler. It may work on your
implementation, but I was giving a general answer.

Anyway, is there _really_ no way to access elements of
a struct using a single, advancing pointer? I suspect
some controller-programming C gurus would know a way?

You can try using a char pointer that gets incremented by sizeof(int)
and sizeof(double). That would be pretty much equivalent to an
advancing pointer, although I can't say whether it's going to yield
faster code. Try it and see.

Regards,
Bart.

[Jacek Dziedzic]

Heinz Ozwirk wrote:

>
The result of a cast is an rvalue, not an lvalue. Think of it as a
temporary variable. Then your statement becomes something like

double* temp = reinterpret_cas t<double*>(hash table_ptr);
*temp = some_double0;
temp++;

The problem is the final increment. It increments the temporary, not the
hashtable_ptr. To do that, you have to add an extra level of indirection

Right!

>
*((*reinterpret _cast<double**> (&hashtable_ptr ))++) = some_double0;

Yuck :)

But before you try such nasty code, you should try something more readable:

if (...)
{
hash_t* ptr = &hashtable[index];
ptr->id = some_int;
ptr->next = some_int2;
ptr->d0 = some_double0;
...
}

Yes, you were right! My incrementing a pointer combined with
heavy casting only made the matter worse (speedwise).
Your idea is slightly better (in terms of speed) than the
original code I posted.

If some_int, some_int2 etc. are local variables, which are computed as
part of the function, it might also improve speed if you replace all
those variables with a single, local instance of a hash_t struct. For
most compilers, code like

hash_t data;
data.id = ...
...

should be as fast as

int id, next;
double d0, d1, ...;
id = ...
...

But you could then copy the structure as a whole, like

if (...) hashtable[index] = data;

of even use memcpy, which still is much more readable than your pointer
tricks.

Unfortunately, the source part of the data copied is
in registers, so I guess memcpy is out of question,
especially since this struct is rather small (32 bytes)
and I don't work at contiguous batches of hash_t's
in one iteration.

Such tricks often even have negative effects on speed. Measure
such "improvemen t" very carefully and do it for every update of your
compiler. Even a compiler will understand (and optimize) simple code
mush better than tricky casts and pointer arithmetic.

It turns out you were right!

[snip]

thanks a lot,
- J.

[Kaz Kylheku]

Jacek Dziedzic wrote:

Hi!

I'm trying to squeeze a few clock cycles from a tight
loop that profiling shows to be a bottleneck in my program.
I'm at a point where the only thing that matters is
execution speed, not style (within the loop, obviously).

The loop deals with an array:

// this is aligned at cache line boundaries
struct hash_t {
int id;
int next;
double d0;
double d1;
double d2;
} hashtable[HASH_MAX];

within the loop, whenever there is a hashtable miss I
need to store new values into hashtable[index].
Originally this looked like

if(...) {
hashtable[index].id=some_int;
hashtable[index].next=some_int2 ;
hashtable[index].d0=some_double 0;
hashtable[index].d1=some_double 1;
hashtable[index].d2=some_double 2;
}

The compiler should do a good job of eliminating the common
subexpression hashtable[index], reducing it to a cached pointer value.
If you're worried that that doesn't happen, you can try doing that
reduction manually:

{
hash_t *tmp = &hashtable[index];
tmp->id = some_int;
tmp->next = some_int2;
...
}

That's about the best you can do.

if(...) {
// point to the first member
int *hashtable_ptr = reinterpret_cas t<int*&(hashtab le[index].id)
*(hashtable_ptr ++) = some_int; // store into id and move on
*(hashtable_ptr ++) = some_int2; // store into next and move on
*(hashtable_ptr ++) = some_double0; // << --- trouble
// ...
}

If the processor has an indexed addressing mode with displacement for
structure access, then doing this kind of thing won't help at all. All
it means is that you can use indirect addressing to fetch the data,
with no displacement.

In some instruction sets, it might even be the same instruction, with a
value of zero in the displacement field. So all you are doing is adding
the overhead of incrementing the base address.

[Andrew Koenig]

"Jacek Dziedzic" <jacek@no_spam. tygrys.no_spam. netwrote in message
news:3f******** *************** ****@news.chell o.pl...

The loop deals with an array:

// this is aligned at cache line boundaries
struct hash_t {
int id;
int next;
double d0;
double d1;
double d2;
} hashtable[HASH_MAX];

within the loop, whenever there is a hashtable miss I
need to store new values into hashtable[index].
Originally this looked like

if(...) {
hashtable[index].id=some_int;
hashtable[index].next=some_int2 ;
hashtable[index].d0=some_double 0;
hashtable[index].d1=some_double 1;
hashtable[index].d2=some_double 2;
}

Now... I'm trying to save a few cycles by doing something
along the lines of

if(...) {
// point to the first member
int *hashtable_ptr = reinterpret_cas t<int*&(hashtab le[index].id)
*(hashtable_ptr ++) = some_int; // store into id and move on
*(hashtable_ptr ++) = some_int2; // store into next and move on
*(hashtable_ptr ++) = some_double0; // << --- trouble
// ...
}

the trouble is that I'm working with a pointer to int
and I want to store a double and, later on, advance the
pointer not by sizeof(int) bytes, but by sizeof(double)
bytes.

Do you have any evidence that successively incrementing hashtable_ptr will
be significantly faster than doing direct (constant offset) indexing? In
other words:

hash_t* hptr = &hashtable[index]; // or, equivalently,
hashtable+index
hptr->id = some_int;
hptr->next = some_int2;
hptr->d0 = some_double0;

and so on.

On most computers this will generate successive instructions that put hptr
in a register and specify appropriate offsets as part of each instruction,
and the processor will probably add those offsets to the register at least
as quickly as you can recompute an appropriate value for hashtable_ptr.
Plus you don't have to use reinterpret_cas t, which is almost never portable,
and you don't have to hope that the compiler won't put padding into your
structure that you didn't expect.

The main difference between my suggestion and your original version is that
I'm computing the address of hashtable[index] once, then reusing that
address. In fact, most optimizing compilers will do that for me, so it is
possible that the change will have no effect. Indeed, on many computers,
the execution time of the program fragment will depend more than anything
else on the number of memory references you make, which means that there may
not actually be anything you can do to speed up the program.