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_double0;
hashtable[index].d1=some_double1;
hashtable[index].d2=some_double2;
}

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_cast<int*> &(hashtable[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*>(hashtable_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]

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_double0;
hashtable[index].d1=some_double1;
hashtable[index].d2=some_double2;
}

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_cast<int*> &(hashtable[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]

> [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]

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_double0;
hashtable[index].d1=some_double1;
hashtable[index].d2=some_double2;
}

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_cast<int*> &(hashtable[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*>(hashtable_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_cast<double*>(hashtable_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
"improvement" 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]

<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]

[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]

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_cast<double*>(hashtable_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 "improvement" 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]

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_double0;
hashtable[index].d1=some_double1;
hashtable[index].d2=some_double2;
}

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_cast<int*> &(hashtable[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.

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

Now... I'm trying to save a few cycles by doing something
along the lines of
(...)
bytes. On my system sizeof(int) is 4, sizeof(double) is 8
and portability is not an issue.

Save a few cycles and sacrify portability? Write it in assembler. It will be
safer than ugly code, at least everyone that takes an eye in the code will
notice that is not portable.

 

[Andrew Koenig]

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_double0;
hashtable[index].d1=some_double1;
hashtable[index].d2=some_double2;
}

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_cast<int*> &(hashtable[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_cast, 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.

 

[Frederick Gotham]

Jacek Dziedzic posted:

if(...) {
// point to the first member
int *hashtable_ptr = reinterpret_cast<int*> &(hashtable[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
// ...
}

You're probably going the wrong way about this, but nonetheless...

char *p = (char*)hastable[index].id;

* (int*)p = some_int; p += sizeof some_int;
* (int*)p = some_int2; p += sizeof some_int2;
*(double*)p = some_double0; p += sizeof some_double0;

 

[Frederick Gotham]

Heinz Ozwirk posted:

The result of a cast is an rvalue, not an lvalue.

Yes, unless you cast to a reference type.

 

[Jacek Dziedzic]

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.

Yes, you were right, I only got the overhead.

It's weird then that the same (or similar) trick worked for
me a few hundred lines earlier, got to be a compiler quirk.

thanks,
- J.

 

[Jacek Dziedzic]

Jacek Dziedzic wrote:




Save a few cycles and sacrify portability?

I think you're a little hasty in your conclusions. I don't
"sacrifice" portability, it's just not needed here. The program
is destined to run on a massively parallel machine, and
basically only on _this_ one machine, at least for the next
five years. The few cycles may mean days of computational
time of several tens of nodes saved, as this loop iterates
_trillions_ of times. Sure, perhaps in a few years this
computer will have become outdated and the program
will have to run on another machine with sizeof(int)==32
and sizeof(double)==32, but this will be caught by an
assert in the init module that will ask somebody to fix
this. Fixing this would, in fact, be as easy as changing
an offset here or there in a clearly marked place.

> Write it in assembler. It will be safer than ugly code

Recoding it in another assembly language in case of
a change of architecture won't be easy.
Furthermore I have to admit I can't code IA-64 assembly.

> at least everyone that takes an eye in the code will
> notice that is not portable.

Well, I think the two lines

// Warning: the following function is not portable.
// mind the offsets marked in *)

does the same job.

- J.

 

[Jacek Dziedzic]

> [snip]

Yes, you were right.

thanks,
- J.

 

[Jacek Dziedzic]

Jacek Dziedzic posted:

if(...) {
// point to the first member
int *hashtable_ptr = reinterpret_cast<int*> &(hashtable[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
// ...
}

You're probably going the wrong way about this, but nonetheless...

char *p = (char*)hastable[index].id;

* (int*)p = some_int; p += sizeof some_int;
* (int*)p = some_int2; p += sizeof some_int2;
*(double*)p = some_double0; p += sizeof some_double0;

Thanks. That's the way I tried and, as others have warned me,
I only got the overhead.

- J.

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

I think you're a little hasty in your conclusions. I don't
"sacrifice" portability, it's just not needed here. The program
is destined to run on a massively parallel machine, and
basically only on _this_ one machine, at least for the next
five years.

Then tell me in 2012 if you sacrificed something or not.

The few cycles may mean days of computational
time of several tens of nodes saved, as this loop iterates
_trillions_ of times.

I think you're a little hasty in your conclusions. I did not say that the
few cycles implied a little gain.

Recoding it in another assembly language in case of
a change of architecture won't be easy.

I doubt that recoding obfuscated nonportable C++ will be.

 

[Thomas Matthews]

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_double0;
hashtable[index].d1=some_double1;
hashtable[index].d2=some_double2;
}

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_cast<int*> &(hashtable[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*>(hashtable_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...

1. Try keeping everything in units of "struct hash_t".
Fill in an instance before hashing. If you need to
insert into the table, just copy the item:
struct hash_t new_item;
// ...
hashtable[index] = new_item;
This has the benefit of letting the compiler figure
out the best way to copy the data. The best method
may be item per item, block / string copy, or DMA
to cite a few. Worst case, you could call an
implementation specific function:
implementation_memcpy(&hashtable[index],
&new_item,
sizeof(new_item));

2. Are all the items in "struct hash_t" needed to make
the hash table work?
Perhaps just the key and a pointer to data located
elsewhere. Thus only a small amount of data (the
key and pointer) are moved around in the table.
Most computer time is spent searching and sorting,
not by deferencing to get at value of a <key, value>
pair.

3. Remove operations not needed. Does the hash table
need to be used as often?

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library