Indexing an array

[ditiem]

I hope this is the correct group. It came out a doubt about speed
when indexing an array in the following way:

for a given pointer p, p[0] contains an address and p[1] an offset.
I must return the content of the address plus the offset.. Which way
is faster and more portable?

1.- *( ((unsigned int*)*p) + *(p+1) ) ;
2.- ((unsigned int*)*p)[ *(p+1) ] ;
3.- *((unsigned int*)(*p ++ + *p)) ;

thanks!

 

[Chris Dollin]

I hope this is the correct group. It came out a doubt about speed
when indexing an array in the following way:

for a given pointer p, p[0] contains an address and p[1] an offset.

Bleagh. That means you're going to have to play casting games.
Why not have `p` point to a struct with a pointer and an offset
in it, nicely typed? What's the problem context?

I must return the content of the address plus the offset.. Which way
is faster and more portable?

1.- *( ((unsigned int*)*p) + *(p+1) ) ;
2.- ((unsigned int*)*p)[ *(p+1) ] ;
3.- *((unsigned int*)(*p ++ + *p)) ;

They're all horrible, whatever their speed.

(3) is the worst, since it falls foul of undefined behaviour:
you modify `p` /and/ independently read it. Don't do that.

(1) and (2) are exactly equivalent in terms of C semantics,
since if `p` is a pointer and `i` is an int[eger] the
expression `p` is defined to be/mean the same as `*(p+i)`.
Indeed we can have

2.5- ((unsigned int*) *p)[p[1]]

(I leave out the semicolon because this presumably isn't
supposed to be a statement; if it were, you could replace
it with `{}` with the same effect.)

But, as I say above, I wouldn't use a pointer that you're
going to pretend points to different types. I'd use a
(pointer to) struct and write something like:

0.- p->base[p->offset]

Unless, given the context, something even better suggested
itself.

 

[Malcolm McLean]

I hope this is the correct group. It came out a doubt about speed
when indexing an array in the following way:

for a given pointer p, p[0] contains an address and p[1] an offset.
I must return the content of the address plus the offset.. Which way
is faster and more portable?

1.- *( ((unsigned int*)*p) + *(p+1) ) ;
2.- ((unsigned int*)*p)[ *(p+1) ] ;
3.- *((unsigned int*)(*p ++ + *p)) ;

If you've go something quirky like that, make explicit what you are doing.

unsigned int *ptr = p[0];
int index = (int) p[1];
unsigned int x = ptr[index];

any modern compiler can microptimise expressions very easily to eliminate
the intermediates which are needed for readability, not storage.

 

[Barry Schwarz]

I hope this is the correct group. It came out a doubt about speed
when indexing an array in the following way:

for a given pointer p, p[0] contains an address and p[1] an offset.
I must return the content of the address plus the offset.. Which way

Speed is irrelevant if the result is incorrect.

What are the units for offset? If it is bytes, your code is
incorrect because it computes the wrong address.

Is the value to be extracted truly an unsigned int? Is the
value of p[0] correctly aligned for an unsigned int?

What is the type of p? Since you don't cast the expression
*(p+1), I expect it is something similar to int*.

Are you absolutely positive that the pointer value in p[0] and
the offset in p[1] have the same size? Does you implementation
guarantee that converting an int (*p) to a pointer will have the
desired effect (it is something the implementation must document).

Just out of curiosity, how did you end up with such a sorry state?

is faster and more portable?

Converting an int to a pointer is guaranteed non-portable.

1.- *( ((unsigned int*)*p) + *(p+1) ) ;
2.- ((unsigned int*)*p)[ *(p+1) ] ;
3.- *((unsigned int*)(*p ++ + *p)) ;

thanks!

Remove del for email

 

[ditiem]

They're all horrible, whatever their speed.

Lol... you put an smile with your expresion

(3) is the worst, since it falls foul of undefined behaviour:
you modify `p` /and/ independently read it. Don't do that.

I agree with you in all. I am trying to meassure the program to
see which one is faster. Even the one you suggested about using
a nice casting to an struct. I will comment the results.

(1) and (2) are exactly equivalent in terms of C semantics,
since if `p` is a pointer and `i` is an int[eger] the
expression `p` is defined to be/mean the same as `*(p+i)`.

yeah, but p should be faster (in Intel) than *(p+i),
because p is a machine instruction which can use preload,
while p + i needs from 2 instructions at least (all this
is assuming compiler does ZERO optimizations).

0.- p->base[p->offset]

My fear is that taking structs everywhere (just for a casting!)
will make code even more terrible!. The expresions I wrote are
expanded inline, etc etc, which complex the tasks of looking
how they are translated in each use.

Unless, given the context, something even better suggested
itself.

Imagine it was an exam question

Thanks for your answer, I appreciate it.

 

[ditiem]

(e-mail address removed) wrote:
They're all horrible, whatever their speed.

LOL, you put and smile on my face . I agree with you, they are
all horrible.

(3) is the worst, since it falls foul of undefined behaviour:
you modify `p` /and/ independently read it. Don't do that.

I am trying to make several benchmarks in order to measure which
one is faster. I suspect maybe (3) is the fastest one, but I think
some gcc optimizations will break it.

0.- p->base[p->offset]

I will add this in the list. I though about this solution, but
the casting is done in one small point of the program that is
expanded inline (or using MACROS, even more terrible), so
declaring structs for each one of the castings I must do could
make things even funnier .

Unless, given the context, something even better suggested
itself.

Imagine it was an exam question . Thanks for your answer,
I really appreciate it!. I hope soon I will post some results!

 

[ditiem]

If you've go something quirky like that, make explicit what you are doing.

unsigned int *ptr = p[0];
int index = (int) p[1];
unsigned int x = ptr[index];

I did not know compiler will work so fine. But if the compiler does
not
support inlined functions, how will you write it in a "#define"?

 

[Chris Dollin]

Lol... you put an smile with your expresion

I'm serious that they're all horrible, if it's supposed to be
code that people read & write.

I agree with you in all. I am trying to meassure the program to
see which one is faster. Even the one you suggested about using
a nice casting to an struct.

I did /not/ suggest any /casting/ to a struct. I suggested /using/
a struct.

I will comment the results.

(1) and (2) are exactly equivalent in terms of C semantics,
since if `p` is a pointer and `i` is an int[eger] the
expression `p` is defined to be/mean the same as `*(p+i)`.

yeah, but p should be faster (in Intel) than *(p+i),
because p is a machine instruction which can use preload,
while p + i needs from 2 instructions at least (all this
is assuming compiler does ZERO optimizations).

Compilers don't do ZERO optimisations nowadays. Turning the
code sequence for p, i, +, * into the same code sequence as
p, i, [] is the kind of thing that peephole optimisers could
do thirty years ago on 16-bit processors.

If you're interested in your code executing fast, you /will/ ask
the compiler to turn its optimisers on (up).

0.- p->base[p->offset]

My fear is that taking structs everywhere (just for a casting!)

There. Is. No. Casting. Here.

will make code even more terrible!. The expresions I wrote are
expanded inline, etc etc, which complex the tasks of looking
how they are translated in each use.

Ahhhh -- let me guess; this is supposed to be the compiled output
of something? `p` is a pointer into a fake machine store, hence
the type games? If so, then might be better off using a union:

typedef union machine_word Word;

union machine_word
{
Word *pointer;
int integer;
... other possibilities ...
};

...

Word *p;

...

p[0].pointer[p[1].integer]

But it depends. /Please/ tell us the context of the question:
it makes a difference. (In a compiler/interpreter I wrote
some time ago, I too had to play silly games moving between
types. I believe the games were justfied -- in context. But
they might not have been; several years later, I hope my
coding has continued to improve.)

Imagine it was an exam question

Imagine the examiner having an epiphany and, instead of setting
the exam, taking a holiday in the Lake District.

Thanks for your answer, I appreciate it.

You're welcome.

 

[ditiem]

Speed is irrelevant if the result is incorrect.

So fully agree!

What are the units for offset? If it is bytes, your code is
incorrect because it computes the wrong address.

p is unsigned int *. The units of the offest are in unsigned int.

Is the value to be extracted truly an unsigned int? Is the
value of p[0] correctly aligned for an unsigned int?

yes to all

What is the type of p? Since you don't cast the expression
*(p+1), I expect it is something similar to int*.

mmm I dont cast it but the result is and unsigned int*. Sorry, I
forgot
to say the pointer type (

Are you absolutely positive that the pointer value in p[0] and
the offset in p[1] have the same size?

Absolutely. In fact the invention works, there is not better
demostration

Does you implementation guarantee that converting an int (*p)
to a pointer will have the

Yeah, that is precisely the trick hehe

Just out of curiosity, how did you end up with such a sorry state?

Implemeting an Abstract Machine (for Prolog, nor for Java) that
takes only 2 pages (of 4Kb) of memory and goes between 8 and 100
times faster (in the set of benchmarks I have, but we will see
in the rest of programs) than conventional abstract machines

In AM all memory is plain and the program executed has no
types at all (they are created on run-time). Even internal
structs of the AM are not too typed. You only know that in a
certain address of memory there is another address of memory
that cointains the data you want... etc etc, and you only know
that in run-time, that is because an "int" can be a pointer,
a number, a char...

Converting an int to a pointer is guaranteed non-portable.

I dont guess any reason for that... but I believe you. Thanks
for the info, I hope not to run into a wall too hard when
porting it to other architectures.

Remove del for email

emmm, is this your quote? Else I did not get the meaning
of this sentence.