Wednesday, September 16, 2015

When %LOOKUP *NE LOOKUP

lookup %lookup

I am sure most of us RPG developers have thought when a Built In Function, BIF, is introduced to replace an Operation code it would work the same way. Earlier this week I encountered a situation where it did not, where the %LOOKUP BIF can give different results to using the LOOKUP operation code.

The Look Up Operation and BIF are used to find a value in an array. I had a program where I was adding elements to an array and using %LOOKUP to determine the first unused element in the array, which I could then use to determine the number of used elements in the array. The program passed testing and was deployed on to the production IBM i server. When being used in the production environment the program stopped being able to determine where the first unused element was. After plenty of head scratching and debugging the code I finally determined the cause of the problem, the %LOOKUP.

Before I describe what the problem was let me give a sample program I can use to illustrate this issue:

01    ctl-opt option(*nodebugio:*srcstmt:*nounref) ;

02    dcl-s Array char(15) dim(30) ascend ;
03    dcl-s i packed(3) ;
04    dcl-s TestVar char(15) ;

05    Array(1) = 'AARDVARK' ;
06    Array(2) = 'BEAR' ;
07    Array(3) = 'CHERRY' ;
08    Array(4) = 'DEER' ;
09    Array(5) = 'EAGLE' ;
10    Array(6) = 'FINCH' ;
11    Array(7) = 'GRAPE' ;
12    Array(8) = 'HAMSTER' ;
13    Array(9) = 'IGLOO' ;
14    Array(10) = 'JEWEL' ;
15    Array(11) = 'KITE' ;
16    Array(12) = 'LION' ;
17    Array(13) = 'MOUSE' ;
18    Array(14) = 'NUT' ;
19    Array(15) = 'OSCAR' ;
20    Array(16) = 'PINE' ;

21    i = %lookup(' ':Array:1) ;
22    dsply ('Blank = ' + %char(i)) ;
23    i = 1 ;
24    TestVar = ' ' ;
25  C     TestVar       LOOKUP    ARRAY(i)                               99
26    dsply ('Fixed = ' + %char(i)) ;

The array, called Array and defined on line 2, contains 30 elements and is in ascending sequence.

On line 3 and 4 I define the field to contain the returned value from the %LOOKUP, i, and a variable I will use with the %LOOKUPGE and %LOOKUPLE.

I load the array in lines 5 – 20, filling 16 of the 30 elements. The rest are left at their default value, blank.

The first test I performed, lines 21 – 26, was to check for the first array element that is blank, which should return 17. I have used the %LOOKUP BIF on line 21, and displayed the result on line 22. If there is no element that is equal to blank I would expect it to return zero in the variable i. I use the DSPLY Operation to display the value of i, line 22.

In lines 23 – 26 is the code I used for using the LOOKUP Operation code. On line 25 the indicator 99 is in the equal position (75-76) to indicate that this is a lookup equal. Again I display the value returned by the LOOKUP using the DSPLY Operation code, line 26.

Notice that as I am using the latest version of RPG I can intermingle free form and fixed lines of code without the need for /FREE and /END-FREE.

What happened?

  DSPLY  Blank = 0 
  DSPLY  Fixed = 17

What! The %LOOKUP could not find the blank element, number 17, while LOOKUP could. I have to admit this freaked me out.

I changed the program inserting the %LOOKUP after every time I added a value to the array like this:

    Array(1) = 'AARDVARK' ;
    i = %lookup(' ':Array:1) ;
    dsply ('1 = ' + %char(i)) ;

    Array(2) = 'BEAR' ;
    i = %lookup(' ':Array:1) ;
    dsply ('2 = ' + %char(i)) ;

    Array(3) = 'CHERRY' ;
    i = %lookup(' ':Array:1) ;
    dsply ('3 = ' + %char(i)) ;


    Array(15) = 'OSCAR' ;
    i = %lookup(' ':Array:1) ;
    dsply ('15 = ' + %char(i)) ;

    Array(16) = 'PINE' ;
    i = %lookup(' ':Array:1) ;
    dsply ('16 = ' + %char(i)) ;

The output showed something interesting:

  DSPLY  1 = 2 
  DSPLY  2 = 3
  DSPLY  3 = 4
  DSPLY  4 = 5
  DSPLY  5 = 6
  DSPLY  6 = 7
  DSPLY  7 = 8
  DSPLY  8 = 9
  DSPLY  9 = 10
  DSPLY  10 = 11
  DSPLY  11 = 12
  DSPLY  12 = 13
  DSPLY  13 = 14
  DSPLY  14 = 15
  DSPLY  15 = 0
  DSPLY  16 = 0

It appeared that when I reached the midpoint of the array, in this case element 15, the %LOOKUP could no longer find the next blank element.

If I reduced the array to 17 elements, see below, the %LOOKUP failed at the ninth element.

    dcl-s Array char(15) dim(17) ascend ;

If I increased the array to 99 elements, see below, the having only 16 elements filled did not cause the problem as less than half the elements are filled.

    dcl-s Array char(15) dim(99) ascend ;

Just in case this was an error caused by using the latest RPG, all free, I created a program with fixed definitions and compiled it for release V5R4M0. I cannot compile for an earlier release as I only have access to IBM i with version 7.1 and 7.2. I found the same with that program too. Code for this program is here.

Referring to IBM's KnowledgeCenter I found a link at the bottom of the %LOKUPxx page that took me to a page called: Sequenced arrays that are not in the correct sequence, the link is at the bottom of this post. One interesting passage on this page states:

... the %LOOKUPxx built-in functions and the LOOKUP operation code may find different values. The %LOOKUPxx built-in functions may not find a data value even if it is present in the array.

Since a binary search is used by the %LOOKUPxx built-in functions for a sequenced array, and the correct function of a binary search depends on the data being in order, the search may only look at a few elements of the array. When the array is out of order, the result of a binary search is unpredictable.

I am still shocked by this revalation.

How did I fix this problem? I initialized the array with the largest hexadecimal value, x'FF', and as the next unused element would contain x'FF' I would check for that rather than blank.

  Array(*) = x'FF' ;
  Array(1) = 'AARDVARK' ;


  i = %lookup(x'FF':Array:1) ;
  dsply ('xFF = ' + %char(i)) ;

Now when I run the program the %LOOKUP works as I expect it to.

  DSPLY  xFF = 17
  DSPLY  Fixed = 17

 

You can learn more about this on the IBM website:

 

This article was written for IBM i 7.2, and should work for earlier releases too.


Version of code for V5R4M0

     * Compiled at TGTRLS(V5R4M0)
01  H option(*nodebugio:*srcstmt)

02  D Array           S             15    dim(30) ascend
03  D i               S              3P 0
04  D TestVar         S             15
     /free
05     Array(1) = 'AARDVARK' ;
06     Array(2) = 'BEAR' ;
07     Array(3) = 'CHERRY' ;
08     Array(4) = 'DEER' ;
09     Array(5) = 'EAGLE' ;
10     Array(6) = 'FINCH' ;
11     Array(7) = 'GRAPE' ;
12     Array(8) = 'HAMSTER' ;
13     Array(9) = 'IGLOO' ;
14     Array(10) = 'JEWEL' ;
15     Array(11) = 'KITE' ;
16     Array(12) = 'LION' ;
17     Array(13) = 'MOUSE' ;
18     Array(14) = 'NUT' ;
19     Array(15) = 'OSCAR' ;
20     Array(16) = 'PINE' ;

21     i = %lookup(' ':Array:1) ;
22     dsply ('Blank = ' + %char(i)) ;
23     i = 1 ;
24     TestVar = ' ' ;
25   /end-free
26  C     TestVar       LOOKUP    ARRAY(i)                               99
27   /free
28     dsply ('Fixed = ' + %char(i)) ;

Return

20 comments:

  1. Your basic problem Simon was that you lied to the compiler and when you do that all bets are off . Simply put, you told it the array was in sequence when it wasn't.

    In the case of a small array such as this one the speed gained by using %Lookup when the array specifies "Ascend" will be so negligible as to not be worth the effort. In such cases you can simply remove the "Ascend" keyword and you will get the same results as with LOOKUP. Another reason for doing this is that if there are duplicates in the array (as you effectively have with blanks in this example) even if you sort the array after adding a new value you will not necessarily get the same result. I actually haven't tried this (can't VPN into my system at my current location) but I'm pretty darn certain your X'FF' solution will not always work. When a binary search is executed you cannot guarantee which of a series of duplicates will be returned - you lucked out and got the first one, but normally you have to walk backwards through the array from the returned index to determine the first one.

    We did a write up on %Lookup back in 2009 (http://www.itjungle.com/fhg/fhg020409-printer01.html) and I'm sure I've described the backwards walk requirement somewhere but can't find the reference.

    ReplyDelete
    Replies
    1. I admit the example I gave in this post was very simple.

      I discovered this in a program I wrote where I had FETCH-ed 3,500 records from a file into a data structure array. I was loading a subfile from the array. I have a “Position to” field and when a value is entered into this field I want to start the subfile with the closest match to the value entered, equivalent of a SETLL. I used the %LOOKUPGE and could not get array index to the right record. So I tried a %LOOKUP, and then the LOOKUP operation code, trying to determine if it was something I was doing wrong or was it really doing what I observed. What I found became the basis for this post.

      Delete
    2. These operate differently if the sort option is selected in the D spec. You have to do a %sorta before the lookup. Simple solution is to go out of free, use the C spec op code Lookup, and go back into free. This is if you have to maintain an existing program.

      V7 can allow the sort based on a field in a DS. You may want to consider embedded SQL using cursors if you have the data in a database over a SQL view if it can be created.

      Delete
    3. I know this is a bit late, but I've had to deal with this recently and I tracked down an example of what I did back in 2006...
      The best way I found was to set the Array for Ascending, then Sort only the loaded portion of that array, then only %lookup that loaded portion of the array.
      This removed the problem with sorting an array with a bunch of blanks, as well as the binary search tracking through all those blank array elements.

      dcl-s Array Char(10) DIM(100) Ascend;
      dcl-s Elements int(3) inz(3);
      dcl-s Element# int(3);

      Array(1) = 'CHERRY' ;
      Array(2) = 'AARDVARK' ;
      Array(3) = 'BEAR' ;

      // Check only loaded portion of array sorted ascending:
      SortA %SubArr(Array:1:Elements);
      Element# =
      %Lookup('BEAR':Array:1:Elements);

      At this point, Element = 2.


      Delete
  2. This also means that, I cannot blindly convert any Fixed Format to Free format code, right?

    ReplyDelete
    Replies
    1. Yes, it does mean you should test.

      But this should not be used as an excuse not to more to free format.

      Delete
  3. We need to understand that % BIF are not a beautification of operation code. They are a complete different write / rewrite, and that is why BIFs are more efficient than op codes. It also means BIFs are not going to behave exactly like op codes. If we have played a trick with some op code, we better revisit before converting it into a % BIF. I learned my lesson the hard way :)

    ReplyDelete
  4. My test worked if I limited the %Lookup to the number of elements populated, 16 in your case.

    // Count is number of elements populated
    i = %Lookup(TestVar:Array:1:Count) ;

    If the array is not sorted, you can sort if first, then %Lookup.
    SortA %SubArr(Array:1:Count) ;

    I rarely use ASCEND in an array definition. If the array gets that 'big', I'll use a work table instead.

    Chris Ringer

    ReplyDelete
  5. Interessant, wie die %Lookup() Funktion arbeitet. Es ist gut zu wissen, dass es hier unterschiedlich läuft. So etwas sollte schon in der IBM Hilfe dokumentiert sein.

    ReplyDelete
    Replies
    1. Translatation: Interesting how the %lookup() function works. It's good to know that it works differently here. Something like this should already be documented in the IBM Help.

      Delete
  6. I had read this behavior of the %lookup back when I first used it, many releases ago. The solution is to count the number of entries you enter as you pop them in. Then you only search the portion of the array that is used.

    I think you could have issues with LOOKUP with an array that isn't really sorted when it says it is as well. That's why in the old days, we'd load the end of the array forward or initialize it to high values.Of course, I haven't done stuff with LOOKUP in years except for legacy code, and most of that doesn't say the array is sorted.

    The best solution is to count the elements in the array, and only work with the used portion.

    Location=%lookup(test:array:1:NbrElement)
    If location=0;
    NbrElement+=1;
    Array(NbrElement)=Test;
    Endif;

    This is faster both in searching and in locating the unused element, especially if you have a lot of unused elements. (Up to you how to handle a full array; I've left that out.

    ReplyDelete
  7. This is purely a coder error. Why but "ascend" on an array that did not have data in "ascend" order? So to fix it, he initalized all to xFF? Another fix would be to *sort* the data after each insert. Then he would find the first element each time, but the order would be ascending and all would be well.

    To repeat, this is a coder error, not a language or bif error. You placed unordered data in an ordered list strange things happen. And always remember rpg does not have an out-of-bound null or empty field like VB does, so an array with 16 elements will default to some thing and normally that is blank as in x40 EBCDIC.

    ReplyDelete
  8. Rather than using arrays, why not ( dynamicallly ) create a DB table and work with that. There is no limit on size and what you can do. Remember, we have an integrated database and single level store !

    ReplyDelete
    Replies
    1. And the speed of %Lookup and an in memory table is orders of magnitude faster Antoon. We tested this with a client some years back and it helped to take hours off the nightly jobs.

      Delete
  9. I don't understand why you would declare the array with ASCEND or DESCEND in the first place. If you want it sorted, do it after you have populated the array simply by SORTing it. Removing the ASCEND keyword let's your sample work fine!!
    The funny thing though, and predictable from the behaviour described, is that the array obviously starts getting "messed up" after (%elem(n)/2)+1 elements are "touched". In a 30 element array, you can populate 1 and 16 and %LOOKUP will still work fine. After populating the elements in between 1 and 16, %LOOKUP screws up. Hence it is obvious, that after populating more than 50% of sorted(!) arrays, an internal sort is triggered. Yet, displaying the array in a debug session does not show the array in sorted order. Then again, that 50% threshold value is not surprising having traditional sort algos in mind!

    Eventually, as Jack already stated, this is in no way a matter of LOOKUP or %LOOKUP, rather than a matter of array treatment - and I would guess by the runtime and not even the compiler.

    I personally consider stuff like ASCEND/DESCEND and some other interim solutions to the language as legacy leftovers kept for compatibility reasons. Just avoid that stuff and you're all good.

    ReplyDelete
    Replies
    1. I am pretty sure you cannot do a %LOOKUPGE without either the ASCEND or DESCEND.

      Delete
    2. Joachim - no internal sort is triggered. Ever. If you code the option RPG assumes that you have sorted the array. Period. It will never sort the data.

      %Lookup with an Ascend/Descend option performs a binary search. If you have 16 elements then the first element checked will be 8 (or 9 depending on the algorithm) if the empty elements are space filled then the key being sought will be higher and eventually the 16th element will be found. But if you were searching for the value you placed in element 1 you would never get a hit.

      Now if you populate the rest of the elements you might be lucky and get a hit - but most likely not. If it was not found in 8 then (say) 12 would be checked. If that is too high them next would be 10, and so on. But if 10 were higher than the search key, a matching key in position 11 would nor be found by %lookup.

      Delete
  10. IBM documentation is precise but unclear.
    But if we know how the %LOOKUP works we understand this behaviour.

    1. For arrays that are not sequenced, %LOOKUP makes a linear search which is what the LOOKUP opcode does.

    2.For sequenced arrays, with ASCEND or DESCEND coded, the BIF does a binary search and the end result may be different from the one returned by the LOOKUP opcode.

    This means that if we're using a sequenced array it also must be sorted for the %LOOKUP BIF to work properly.

    So, do not code ASCEND or DESCEND in the array definition or apply the SORTA opcode to the array before using %LOOKUP.

    ReplyDelete
  11. Without the ASCEND, I do not believe you can force the binary search (assuming you don't use the C search routine) , which is more work.) Binary searches are much faster than full table scans. You just have to know when using the binary search makes sense; if you do use it, you need to have the blank elements at the beginning if you are going to search for them rather than just knowing where they are, which I prefer.. Efficiency is never my first priority, but proper table handling can make a serious difference.

    Data base tables can be used instead of some (not all) arrays, but will generally give you a big hit in run time. .

    ReplyDelete
    Replies
    1. Lynne, that thing with the binary search is correct!

      Delete

To prevent "comment spam" all comments are moderated.
Learn about this website's comments policy here.

Some people have reported that they cannot post a comment using certain computers and browsers. If this is you feel free to use the Contact Form to send me the comment and I will post it for you, please include the title of the post so I know which one to post the comment to.