Re: 2-dimensional DW array access without MULs?
- From: "robertwessel2@xxxxxxxxx" <spamtrap@xxxxxxxxxx>
- Date: 20 Mar 2006 16:43:42 -0800
Jim Leonard wrote:
I'm still trying to teach myself, so forgive me for getting something
wrong... I'm trying to optimize something for 8088 that is fairly MUL
heavy, and I thought a good way to do that was, for one particular
operation, precalculate a table and then just do (x,y) lookups into the
table. Only problem is, I can't figure out to do this without a MUL to
get to the right row/column in the array.
The only thing I can think of is to make my word array's column size
aligned by a power of 2 so that I can use shifts to get to the right
(x,y)... Or, if my word array is 128 columns or less I could use
something like "mov bh,y; shl bh,1; mov bl,x, mov result,[offset
myarray+bx]"... Is this the right line of thinking?
I'm just curious how people usually work with 2-dimensional arrays that
are not byte arrays, or have dimensions not aligned to a power of 2, or
over 64K, preferably with examples... Is LEA usually used for this? I
checked a few resouces but most of them list the different addressing
modes but not provide example usage (although I confess I haven't
checked Hyde's book yet).
Thanks in advance for any advice!
Well, if you're going to be doing random accesses into a two (or more)
dimensional array, you're going to have to do a multiplication
operation in the general case. As you've already noticed, that doesn't
mean a multiplication *instruction* in all cases. You mentioned using
shifts when the dimension was a power-of-2. Other simple products can
often be computed faster than a multiplication as well. For example,
on an 8086, you can multiply by 14 faster with:
mov bx,ax
shl ax,1 ;*2
shl ax,1 ;*4
shl ax,1 ;*8
sub ax,bx ;*7
shl ax,1 *14
Than with a multiplication instruction.
If you've got a 386, you can use scaled addressing to generate many
interesting small multiplications with an lea or two.
You can help this process by adjusting the size of the dimensions to
many the required products easier to compute - and leaving the padding
space unused.
If the accesses are not purely random, there are often opportunities to
reduce the index calculations to simple adds to get to the next
element. A classic example is a dot-product loop where you'd be doing
something like:
for (i=0; i<n; i++)
s+=a[r][i]*b[i][c]; //where r and c are invariant for the loop
The stepping through those two arrays should reduce to a simple add
each (one the size of an element, the other the size of a row).
.
- Follow-Ups:
- Re: 2-dimensional DW array access without MULs?
- From: Jim Leonard
- Re: 2-dimensional DW array access without MULs?
- References:
- 2-dimensional DW array access without MULs?
- From: Jim Leonard
- 2-dimensional DW array access without MULs?
- Prev by Date: Re: newbie questiom about %rip in x86-64 and var
- Next by Date: Re: 2-dimensional DW array access without MULs?
- Previous by thread: 2-dimensional DW array access without MULs?
- Next by thread: Re: 2-dimensional DW array access without MULs?
- Index(es):
Relevant Pages
|
