473,847 Members | 1,457 Online

# Indexing an array

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!

Jul 17 '07 #1
6 1410
di****@gmail.co m wrote:
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[i]` 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.

--
Bleagh Hedgehog
Notmuchhere: http://www.electrichedgehog.net/

Jul 17 '07 #2

<di****@gmail.c omwrote in message
news:11******** **************@ g37g2000prf.goo glegroups.com.. .
>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.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm
Jul 17 '07 #3
On Jul 17, 7:22 pm, Chris Dollin <e...@electrich edgehog.netwrot e:
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[i]` is defined to be/mean the same as `*(p+i)`.
yeah, but p[i] should be faster (in Intel) than *(p+i),
because p[i] 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 ;)

Jul 19 '07 #4
On Jul 17, 10:28 pm, "Malcolm McLean" <regniz...@btin ternet.com>
wrote:
>
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"?

Jul 19 '07 #5
di****@gmail.co m wrote:
On Jul 17, 7:22 pm, Chris Dollin <e...@electrich edgehog.netwrot e:
>They're all horrible, whatever their speed.

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.
>(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 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[i]` is defined to be/mean the same as `*(p+i)`.

yeah, but p[i] should be faster (in Intel) than *(p+i),
because p[i] 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.

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.)
>Unless, given the context, something even better suggested
itself.

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.
You're welcome.

--
Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

Jul 19 '07 #6
On Jul 18, 5:47 am, Barry Schwarz <schwa...@doezl .netwrote:
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
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.
Jul 19 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.