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

[Julián Albo]

Jacek Dziedzic wrote:

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.

--
Salu2

[Frederick Gotham]

Jacek Dziedzic posted:

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
// ...
}

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

[Frederick Gotham]

Heinz Ozwirk posted:

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

Yes, unless you cast to a reference type.

--

Frederick Gotham

[Jacek Dziedzic]

Kaz Kylheku wrote:

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

Julián Albo wrote:

Jacek Dziedzic wrote:

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

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]

Andrew Koenig wrote:

[snip]

Yes, you were right.

thanks,
- J.

[Jacek Dziedzic]

Frederick Gotham wrote:

Jacek Dziedzic posted:

>>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
// ...
}

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.

[Julián Albo]

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.

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.

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.

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

--
Salu2

[Thomas Matthews]

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
// ...
}

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

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(&hashtab le[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.l earn.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