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]

di****@gmail.com 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/

[Malcolm McLean]

<di****@gmail.comwrote in message
news:11**********************@g37g2000prf.googlegr oups.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

[ditiem]

On Jul 17, 7:22 pm, Chris Dollin <[e-mail]:

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 ;)

Thanks for your answer, I appreciate it.

[ditiem]

On Jul 17, 10:28 pm, "Malcolm McLean" <[e-mail]>
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"?

[Chris Dollin]

di****@gmail.com wrote:

On Jul 17, 7:22 pm, Chris Dollin <[e-mail]:

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

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

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

Thanks for your answer, I appreciate it.

You're welcome.

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

[ditiem]

On Jul 18, 5:47 am, Barry Schwarz <[e-mail]:

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.