Implement a cache based on the least recently used replacement.

If you've been following the "API Corner," you know that the articles are intended to introduce you to what's available in system APIs, tell you how to code to the APIs, and demonstrate calling the APIs within the context of a complete program that can be compiled and run. The articles generally do not, however, discuss considerations of how you might integrate the API into your existing or new applications. Considerations such as validation of input parameters, error recovery, performance, and the like are typically left to you.

One example of this would be the article "Dynamically Editing a Numeric Value" published in May of last year. In that article, you were introduced to the Convert Edit Code (QECCVTEC) and Edit (QECEDT) APIs by way of implementing an SQL user-defined function (UDF) named EDITC. EDITC enabled the dynamic editing of numeric values based on a user-specified edit code. The focus of that article was on how to use the APIs rather than how to necessarily get the best performance out of the UDF in an application setting. In this article, we'll look at a few ways that the performance of the EDITC UDF might be improved and, along the way, also introduce you to the Machine Interface (MI) instruction Materialize Machine Data (MATMDATA); this is, after all, the "API Corner," so we've got to introduce at least one new programming interface. This article assumes that you have read the previous article and are familiar with the operation of the EDITC procedure provided in the article. Today, I won't discuss the QECCVTEC and QECEDT APIs in any detail as the previously referenced article provides that information.

Last year's EDITC procedure provides the intended function of editing a numeric value of arbitrary size with an equally arbitrary edit code selected by the user. The procedure is not, however, written in a manner likely to get the best performance in typical usage—namely, processing tables containing more than one row. Let's say, for instance, that you are using the following SQL statement on the table SOMETABLE and that SOMETABLE contains 100,000 rows.

Select editc(Amount, 9, 2, 'A') from SomeTable

As part of processing the 100,000 rows of SOMETABLE, EDITC will unconditionally call the QECCVTEC API 100,000 times. As each of these calls will be requesting the edit mask appropriate for editing a numeric value with a precision of 9, a scale of 2, and an edit code of 'A', EDITC will be receiving back the same edit mask, length of edit mask, and length of edited value values with each of these 100,000 API calls.

One easy optimization would be for EDITC to retain the variant parameter values associated with the most recent call to QECCVTEC—that is, the API input parameters Precision, Scale, and EditCode along with the returned API output parameters of EdtMsk, LenEdtMsk, and LenEdtVal. By storing these values in global storage, rather than the local storage used in the original article, EDITC can then compare the current Precision, Scale, and EditCode values to the previous Precision, Scale, and EditCode values. If all three are the same, then EDITC can immediately call the QECEDT API using the previously returned (and stored) QECCVTEC values of EdtMsk, LenEdtMsk, and LenEdtVal. Only if one or more of the three input values have changed does EDITC need to call QECCVTEC in order to get an updated edit mask. In the case of our earlier example, this simple comparison of current input values to previous input values would, when processing SOMETABLE, change 100,000 QECCVTEC API calls to one QECCVTEC API call and 99,999 comparisons of the current Precision, Scale, and EditCode to the previous Precision, Scale, and EditCode—a definite savings in processing.

This "easy" optimization, however, is not very "real world." The problem is that EDITC is only retaining knowledge of the edit mask most recently used. Let's change the previous SQL statement to the following statement.

Select editc(Amount, 9, 2, 'A'), editc(NbrDays, 4, 0, '2') from SomeTable

In this case, the EDITC UDF will be called twice for each row processed of SOMETABLE: once for Amount and once for NbrDays. Assuming that the first call to EDITC is to process Amount with the second call being for NbrDays, then the comparison of current Precision, Scale, and EditCode to previous Precision, Scale, and EditCode will fail (be not equal) with every EDITC call as the precision, scale, and edit code is different across Amount and NbrDays. Due to this comparison failure, EDITC will end up calling the QECCVTEC API 200,000 times plus doing 200,000 comparisons of current input values to previous input values. Now the original (non-optimized) EDITC would be faster; it would still need to call QECCVTEC 200,000 times, but it would not be performing 200,000 input variable comparisons that always result in the "optimized" EDITC calling QECCVTEC.

To avoid this problem, EDITC needs to maintain a larger history (or cache) of recently used Precision, Scale, and EditCode input values—along with the EdtMsk, LenEdtMsk, and LenEdtVal values associated with these input values. The following module (with the changes from the original EDITC module highlighted in bold) shows one of the ways you could maintain this larger history.

h nomain                                                      

dEditC           pr           256a   varying                

d NbrIn                         31p 9 const                  

d Precision                     10i 0 const                  

d Scale                         10i 0 const                  

d EditCode                       1a   const varying          

dEdit             pr                 extpgm('QECEDT')        

d RcvVar                       256a                          

d LenRcvVar                     10i 0 const                  

d NbrToEdt                     31a   const options(*varsize)

d NbrClass                     10a   const                  

d Precision                     10i 0 const                  

d EdtMsk                       256a   const                  

d LenEdtMsk                     10i 0 const                  

d ZeroSupr                       1a   const                  

d QUSEC                               likeds(QUSEC)          

dMatUTC           pr                 extproc('_MATMDATA')    

d UTC                           8a                          

d Option                         2a   value                  

dCurr             ds                 qualified              

d Precision                     10i 0 overlay(Curr :1)        

d Scale                         10i 0 overlay(Curr :5)        

d EditCode                       1a   overlay(Curr :9)        

dX               s             5u 0                        

dY               s             5u 0                        

dNbr             s             31a                          

dNbrEdited       s           256                            

dZeroSupr         s             1a                          

dLoTime           s             8a                            

dCacheSize       c                   const(20)                

d                 ds                                            

dIDs                             9a   dim(CacheSize)            

d PrecisionIn                   10i 0 overlay(IDs :1)          

d ScaleIn                       10i 0 overlay(IDs :5)          

d EditCodeIn                    1a   overlay(IDs :9)          

d                 ds                                            

dValues                       264a   dim(CacheSize)            

d LenEdtMskOut                  10i 0 overlay(Values :1)        

d LenEdtValOut                 10i 0 overlay(Values :5)        

d EdtMskOut                   256a   overlay(Values :9)        

dUsageTime        s             8a   dim(CacheSize)            

d                                     inz(x'0000000000000000')

dZonedOutput     ds                 qualified                

d Zoned                         1   inz(x'02')              

d Scale                         3u 0                          

d Precision                     3u 0                          

d                               10i 0 inz(0)                  

/copy qsysinc/qrpglesrc,qusec                                

pEditC           b                   export                  

dEditC           pi           256a   varying                  

d NbrIn                         31p 9 const                    

d Precision                     10i 0 const                    

d Scale                         10i 0 const                    

d EditCode                       1a   const varying            

dCvtEdtCd         pr                 extpgm('QECCVTEC')      

d EdtMsk                       256a                            

d LenEdtMsk                     10i 0                          

d LenEdtVal                     10i 0                          

d ZeroSupr                       1a                            

d EditCode                       1a   const                    

d FillChr                       1a   const                    

d Precision                     10i 0 const                    

d Scale                         10i 0 const                    

d QUSEC                               likeds(QUSEC)            

dCpyNv           pr                 extproc('_LBCPYNV')      

d Rcv                                like(Nbr)                

d RcvAtr                             const like(ZonedOutput)  

d Src                                 const like(NbrIn)        

d SrcAtr                             const like(PackedInput)  

dPackedInput     ds                 qualified                

d Packed                         1   inz(x'03')            

d Scale                         3u 0 inz(%decpos(NbrIn))  

d Precision                    3u 0 inz(%len(NbrIn))      

d                               10i 0 inz(0)                

/free                                                      

QUSBPrv = 0;                                              

monitor;                                                  

Curr.Precision = Precision;                              

Curr.Scale = Scale;                                      

Curr.EditCode = EditCode;                                

X = %lookup(Curr :IDs);                                  

if X = 0;                                                

     LoTime = *hival;                                                

     for Y = 1 to CacheSize;                                          

         if UsageTime(Y) < LoTime;                                    

           LoTime = UsageTime(Y);                                    

           X = Y;                                                    

         endif;                                                      

     endfor;                                                          

     IDs(X) = Curr;                                                  

     CvtEdtCd(EdtMskOut(X) :LenEdtMskOut(X) :LenEdtValOut(X) :ZeroSupr

             :EditCode :' ' :Precision :Scale :QUSEC);              

endif;                                                              

MatUTC(UsageTime(X) :x'0004');                                      

ZonedOutput.Precision = Precision;                                  

ZonedOutput.Scale = Scale;                              

CpyNv(Nbr :ZonedOutput :NbrIn :PackedInput);            

Edit(NbrEdited :LenEdtValOut(X) :Nbr :'*ZONED'          

       :PrecisionIn(X) :EdtMskOut(X) :LenEdtMskOut(X)    

       :ZeroSupr :QUSEC);                                

return %subst(NbrEdited :1 :LenEdtValOut(X));          

on-error;                                              

   return '*** Error ***';                              

endmon;                                                

/end-free                                                

pEditC           e                                      

As with the previous article, to create the EDITC module and EDITS service program, you can run the following commands.

CRTRPGMOD MODULE(EDITC)

CRTSRVPGM SRVPGM(EDITS) MODULE(EDITC) EXPORT(*ALL)

Quite a few of the changes are related to the definition of working variables used by the EDITC function. Moving several variables from local storage in function EDITC to the persistent global storage of service program EDITS, and then consolidating these previously standalone variables into arrays, enables EDITC to maintain a cache of recent edit mask usage.

In EDITS, there are three arrays defined: IDs to contain the most recently requested Precision, Scale, and EditCode values; Values to contain the LenEdtMsk, LenEdtVal, and EdtMsk associated with the IDs values; and UsageTime to contain the time of last usage associated with the IDs value. The use of three separate arrays is done solely for the purpose of distinguishing to you the distinction of QECCVTEC inputs, QECCVTEC outputs, and aging controls. In practice, I would most likely use one array with all of the inputs, outputs, and aging controls as subfields of the one array.

All three arrays are defined with dim(CacheSize) where CacheSize is a named constant set to the value of 20. If, in your application mix, a different cache size would be appropriate, then changing the value of CacheSize, recreating the EDITC module, and recreating the EDITS service program would be all that is necessary in order to start utilizing that new cache size (for new jobs on the system anyway). Having a sufficiently large value used for CacheSize is critical. Too small of a value will cause unproductive thrashing of the cache. Too large of a value will cause more storage to be used than is necessary and lead to some unproductive processing of cache entries when performing cache lookups and cache maintenance. By far, though, it will be better to have a cache defined too large rather than one defined too small. We'll return to this discussion of CacheSize a bit later in this article.

With that brief discussion of the arrays being used, let's now take a look at EDITC's processing. When entering the function, EDITC first aggregates the input values of Precision, Scale, and EditCode into the data structure Curr. Curr is then used to look,up an entry in the IDs array that matches the current input values.

If a match is not found (that is X is 0, which will be the case when EDITC is used the first time within a job or when a non-cached set of input values is encountered), then the UsageTime array is searched to find the first entry with the lowest UsageTime value. UsageTime array entries (as you'll see shortly) represent the time that the entry was last used to edit a numeric value, with the lowest time value identifying the entry that was least recently used. Having found this UsageTime entry, the corresponding entry of the IDs array is updated to reflect the value of Curr, the QECCVTEC API is called, and the returned values of the API call are stored in the corresponding entry of the Values array. The previously least recently used entry has now been discarded as part of cache maintenance. This entry now reflects the most recently used cache entry.

At this point, X identifies the entries of UsageTime, IDs, and Values that are to be used when calling the QECEDT API, regardless of whether or not the initial lookup into IDs was successful. EDITC now runs the MATMDATA MI instruction to access the current Coordinated Universal Time (UTC) time and stores this value in the UsageTime(X) array entry.

The MATMDATA instruction provides very high-speed access to system information such as the current local time and the current UTC time. The time value (whether local or UTC) is returned in an 8-byte format that is often referred to as a "Standard Time Format" (where "standard" refers to the i and not necessarily the industry in general). This standard time format provides a consistent measure of elapsed time (since a specific time on August 23, 1928, for the curious among you) with varying degrees of granularity based on the release your system is running on. In the case of V5R4, bit 48 (base 0) of the standard time format is incremented every 8 microseconds; in the case of 6.1 and 7.1, bit 51 of the standard time format is incremented every 1 microsecond. Storing the UTC time in UsageTime provides EDITC with a very clear timestamp of when a given set of IDs values was used, allowing EDITC to quickly identify (in the DoFor loop previously reviewed) which entry in IDs and Values has not been used in the longest time and therefore is the "best" candidate for replacement when our cache is "full." Note that I have "best" in quotes. In the current EDITC, we are implementing a cache replacement algorithm based on least recently used, so not used in the longest time is how "best" is defined. There are many other possible replacement algorithms, where "best" can very well not be least recently used. Some algorithms in fact define "best" as most recently used (based on how you anticipate data access).

Having stored the UTC time in UsageTime(X), EDITC then runs essentially the same instructions as the earlier version of EDITC. The only difference is that EDITC now references the appropriate entry in the IDs and Values arrays when calling QECEDT rather than the previous standalone variables. EDITC could, if desired, eliminate the two instructions, modifying the ZonedOutput data structure by adding the ZonedOutput structure as another subfield of the Values array, but that's left for you to do.

Having reviewed the logic flow of EDITC, let's now look at our use of MATMDATA and our storing of UTC time in UsageTime. As mentioned earlier, MATMDATA can return either local or UTC time (and if you're on 6.1 or 7.1, either unique or non-unique standard time format values for local and UTC time). UTC time is chosen due to many geographies setting local time backward during certain points of the year. If EDITC were to be using local time, and any job utilizing EDITC was unfortunate enough to be running when the local time is set back one hour, then EDITC would be selecting the most recently used entry as the "oldest" as a "fallen-back." A 1:01 a.m. entry would appear to be older than the 1:55 a.m. entries time-stamped prior to local time falling back. This problem would be corrected within an hour, but during that hour the EDITC cache might experience some real thrashing.

A second point is that we don't really need to be storing a time value at all, but using time gave me a reasonable way of introducing the MATMDATA instruction. All we really need is a method of determining which cache entry was least recently used, and a simple counter approach, such as shown below, would meet that requirement.

dLoUsage         s             20u 0

dCounter         s             20u 0

dUsage          s             20u 0 dim(CacheSize)    

d                                     inz(0)            

if X = 0;                                                          

     LoUsage = *hival;                                                

     for Y = 1 to CacheSize;                                          

         if Usage(Y) < LoUsage;                                      

           LoUsage = Usage(Y);                                      

           X = Y;                                                    

         endif;                                                      

     endfor;                                                          

     IDs(X) = Curr;                                                  

     CvtEdtCd(EdtMskOut(X) :LenEdtMskOut(X) :LenEdtValOut(X) :ZeroSupr

             :EditCode :' ' :Precision :Scale :QUSEC);              

endif;                                                              

Counter += 1;                                                      

Usage(X) = Counter;            

And returning to the topic of CacheSize, to determine a "good" cache size will require knowledge of your applications. If the application most utilizing EDITC effectively cycles through the three SQL statements shown below (with presumably a Where clause limiting the rows accessed by the statement), then a minimum cache size of 5 would be called for (and to play it safe, I would just leave CacheSize at 20, a value sufficiently larger than the base minimum).

Select editc(Amount, 9, 2, 'A'), editc(NbrDays, 4, 0, '2') from SomeTable

Select editc(Column1, 4, 0, '2'), editc(Column2, 8, 0, 'Y') from Table1

Select editc(Column3, 5, 0, 'J'), editc(Column4, 6, 0, 'Q') from Table2

Though the EDITC UDF is being used six times in the previous SQL statements, you may notice that two of the calls (those referencing NbrDays and Column1) are using the same input values of 4, 0, and '2' for Precision, Scale, and EditCode, respectively. Though the columns being edited are different, and undoubtedly the values associated with the columns are also different, the same EdtMsk will be applied to both EDITC calls. When looking to set CacheSize, don't inadvertently look at just a single SQL statements usage of EDITC; look at the working set usage of EDITC—that is, the amount of unique EDITC inputs within a job step, which may very well span multiple programs and statements. And when in doubt, go high.

Before ending this article, I would like to point out two additional items.

First, while through the use of caching we have hopefully (depending on an appropriate value for CacheSize) eliminated some of the calls to QECCVTEC, you may or may not perceive any actual improvement in the wall-clock time required to run the applications using the EDITC UDF. The perceived time for the application to run is the sum of several components: the time to access 100,000 SOMETABLE rows, the time to determine the appropriate edit mask, the time to edit the current value of the Amount column, and of course the time to perform whatever logic the application program is doing outside of the EDITC UDF. In this article, we have only addressed the performance of determining the appropriate edit mask—one small piece of the total application. The other components of the application (with accessing the 100,000 rows of SOMETABLE most likely being the largest contributor to the time required to run the application) have not changed. So if accessing the edit mask was originally accountable for only 1 percent of the overall run time, then reducing that 1 percent by 50 percent may not be noticeable to the casual user. We'll know, though, that any typical application usage of EDITC is running faster and more efficiently (again assuming that CacheSize is set appropriately).

Second, and as alluded to at the start of this article, further performance optimizations to the maintenance of the edit mask cache, though not shown or discussed, are possible. These additional optimizations, though, have absolutely nothing to do with APIs, and this is, after all, the "API Corner," not the "RPG Performance Corner." It was a stretch to even get MATMDATA into EDI, which was needed to justify (in my mind anyway) this article in the "API Corner." And I wanted to get this article out as I have discovered that quite a few companies are using the original EDITC as is.

As usual, if you have any API questions, send them to me at This email address is being protected from spambots. You need JavaScript enabled to view it.. I'll see what I can do about answering your burning questions in future columns.

Bruce Vining is president and co-founder of Bruce Vining Services, LLC, a firm providing contract programming and consulting services to the System i community. He began his career in 1979 as an IBM Systems Engineer in St. Louis, Missouri, and then transferred to Rochester, Minnesota, in 1985, where he continues to reside. From 1992 until leaving IBM in 2007, Bruce was a member of the System Design Control Group responsible for OS/400 and i5/OS areas such as System APIs, Globalization, and Software Serviceability. He is also the designer of Control Language for Files (CLF).A frequent speaker and writer, Bruce can be reached at This email address is being protected from spambots. You need JavaScript enabled to view it.. 

---

MC Press books written by Bruce Vining available now on the MC Press Bookstore.

		IBM System i APIs at Work Leverage the power of APIs with this definitive resource. List Price $89.95 Now On Sale

Also Read

The API Corner: Moving Jobs Within and Across Job Queues

The API Corner: What Time Zone Do You Want That Date and Time In?

The API Corner: How Do You Want That Date and Time?