RE: array handling -- MIDRANGE-L

Very interesting.  I had never really thought about
'optimizing' an array, but it certainly makes good
sense.  I appreciate the pointers.

Thanks again.

--- Joe Pluta <joepluta@PlutaBrothers.com> wrote:
> No, you're right on-base here, Rich.  You can
> significantly reduce your
> overhead this way; I use caching a lot for small
> tables.  Since the number
> of entries is so small, I don't think we'll be able
> to significantly reduce
> your processing time by the backloading technique,
> but let me explain it and
> see if you're interested in implementing it.
>
> A LOOKUP operation has to do "N" compare operations.
>  The worst case is an
> unsorted array where there is no hit; in this case,
> "N" is the number of
> entries in the array.  (Of course, if you're getting
> REALLY pedantic, it's
> actually doing twice that many compares, along with
> a number of increments
> equal to the size of the array, but I think you get
> the picture.)
>
> As your array gets larger, this can add up to a lot
> of cycles.  There are
> two ways to reduce the number of compares.  First is
> to order the array -
> that is, make sure the array is in sequence.
> Knowing that, the compiler can
> generate a much more efficient LOOKUP algorithm
> (using a binary scan), where
> the maximum number of compares is actually ((number
> of entries) log 2).  For
> a 20 element array, that's five compares, or a
> potential savings of 75%.  On
> larger arrays, the savings is even more significant.
>  The only downside is
> making sure that all the unused entries at the end
> of your array have "high
> values", such as X'FF'.
>
> Now you run into the problem of unused elements.
> Let's say you make your
> array 1000 elements long, but you only use 20.  In
> that case, most of the
> time is spent chceking unused elements.  Even with
> an ascending array, you
> still have to do 10 compares, twice the number
> required to handle 32
> entries.  One of the nice things about the LOOKUP
> operation in RPG is that
> you can specify a starting position in the array; it
> will only scan the
> elements from that index forward.  So, what you do
> is you load the array
> BACKWARD, starting with the last position in the
> array.  Then, whenever you
> do a LOOKUP, you start with the last position that
> you loaded.  Depending on
> the number of entries and the size of your array,
> you can probably see that
> this can significantly reduce your processing.
>
> So what's the best for you?  In your case, since the
> number of elements
> doesn't fluctuate very much, you should be able to
> tune your array size to
> be close to the number of entries you need.  You may
> occasionally have to
> resize your array, and you MAY want to put a check
> in your maintenance
> program to notify you if someone tries to add more
> records to the file than
> your cache program expects.  But the backloading
> technique is probably
> overkill - it's more relevant when you have to
> define a really BIG array
> that may only have a small number of elements in it.
>
> On the other hand, since you ARE doing this for
> performance reasons, making
> your array ascending may be a smart move.
> Regardless of the size, ascending
> arrays allows the compiler to generate the far more
> efficient binary search
> algorithm, which should reduce processing even in
> your case.  Simply add the
> ASCEND keyword to the D-spec defining the array.
> Then, before you load your
> array, do a MOVEA *HIVAL to preload the array with
> X'FF':
>
> D ARY1            S              2    DIM(20) ASCEND
> (...)
> C                   MOVEA     *HIVAL        ARY1
>
> Hope this helps a little.
>
> Joe Pluta
> www.plutabrothers.com
>
>
> > -----Original Message-----
> > From: midrange-l-admin@midrange.com
> > [mailto:midrange-l-admin@midrange.com]On Behalf Of
> Richard Reeve
> > Sent: Sunday, December 02, 2001 5:33 AM
> > To: midrange-l@midrange.com
> > Subject: RE: array handling
> >
> >
> > Joe,
> >
> >      You hit the nail on the head.  I am doing
> this
> > for performance reasons.  There are currently less
> > than 20 hold codes (much less actually, currently
> > using 4 so I defined the array(s) as 20.  Without
> > doing something along the lines that I described
> then
> > I would have to go out and read the table file for
> > each hold transaction rather than loading the
> array
> > one time and doing a lookup for each hold
> transaction
> > (to get corresponding code).  I should always get
> a
> > hit on the table (after loading).
> >
> > Please let me know if you think that I am missing
> > something.....
> >
> > --- Joe Pluta <joepluta@PlutaBrothers.com> wrote:
> > > Richard, one quick question: are you doing this
> for
> > > performance reasons?
> > > That is, are you caching data in order to avoid
> > > doing reads on the file?
> > >
> > > If not, I'd be interested to know why you are
> doing
> > > this, since it can cause
> > > maintenance headaches down the road - you must
> > > change the program if the
> > > number of entries ever exceeds the size of your
> > > array.
> > >
> > > If you *are* doing this for performance, will
> there
> > > be a significant number
> > > of times when you get a "miss" rather than a
> "hit"?
> > > If the answer is yes,
> > > you might want to "backload" the arrays; this
> can
> > > substantially reduce your
> > > processing time.  Let me know and I'll go into
> this
> > > a little further.
> > >
> > > Joe
> > >
> > > > -----Original Message-----
> > > > From: Richard Reeve
> > > >
> > > > Thanks to all who responded.  This list is
> > > certainly a
> > > > life saver.
> > > >
> > > > Happy Holidays to all.
> > > >
> > > > Rich
> > >
> > > _______________________________________________
> > > This is the Midrange Systems Technical
> Discussion
> > > (MIDRANGE-L) mailing list
> > > To post a message email: MIDRANGE-L@midrange.com
> > > To subscribe, unsubscribe, or change list
> options,
> > > visit:
> > >
> >
>
http://lists.midrange.com/cgi-bin/listinfo/midrange-l
> > > or email: MIDRANGE-L-request@midrange.com
> > > Before posting, please take a moment to review
> the
> > > archives
> > > at http://archive.midrange.com/midrange-l.
> > >
> >
> >
> > =====
> >
> >
> > __________________________________________________
> > Do You Yahoo!?
> > Buy the perfect holiday gifts at Yahoo! Shopping.
> > http://shopping.yahoo.com
> > _______________________________________________
> > This is the Midrange Systems Technical Discussion
> (MIDRANGE-L)
> > mailing list
> > To post a message email: MIDRANGE-L@midrange.com
> > To subscribe, unsubscribe, or change list options,
> > visit:
>
http://lists.midrange.com/cgi-bin/listinfo/midrange-l
> > or email: MIDRANGE-L-request@midrange.com
> > Before posting, please take a moment to review the
> archives
> > at http://archive.midrange.com/midrange-l.
>
> _______________________________________________
> This is the Midrange Systems Technical Discussion
> (MIDRANGE-L) mailing list
> To post a message email: MIDRANGE-L@midrange.com
> To subscribe, unsubscribe, or change list options,
> visit:
>
http://lists.midrange.com/cgi-bin/listinfo/midrange-l
> or email: MIDRANGE-L-request@midrange.com
> Before posting, please take a moment to review the
> archives
> at http://archive.midrange.com/midrange-l.
>


=====


__________________________________________________
Do You Yahoo!?
Buy the perfect holiday gifts at Yahoo! Shopping.
http://shopping.yahoo.com