Optimising Caching Arrays - Part II

If we're using LOOKUP against an unordered array then our search is linear (i.e. O(n) ). If we insert new entries in ascending order (instead of appending to the end) we can use bsearch (from the C run-time library) and reduce our search to O(log(n)). For arrays of less than 50 or so (SWAG), it probably isn't worth the effort. For programs caching hundreds of items, this optimisation can result in significant time savings. I have seen program run times go from hours to minutes when LOOKUP (against an unordered array) is replaced with bsearch (against an ordered array).

Standalone Variable Definitions

d $I              s              5i 0 Inz(1)                           
d $J              s                   Inz(0) Like($I)  
d item            s             10a                   
d @items          s                   Dim(5000) Like(item)                
d szItem          s              5i 0 Inz(%Size(item))        

• $I is a utility variable
• $J is the number of items cached
• item is an item
• @item is an array of items
• szItem is the size of an item

Procedure Definitions

 *                                                                     
 * internal procedures                                                 
 *                                                                     
d insertItem      pr                                                   
d findItem        pr             5i 0                                  
d bSearchComp     pr            10i 0                                  
d                                 *   Value                            
d                                 *   Value                            
 *                                                                     
 * external procedures (from the C run-time library)                   
 *                                                                     
d bsearch         pr              *   ExtProc('bsearch')               
d                                 *   Value                            
d                                 *   Value                            
d                               10i 0 Value                            
d                               10i 0 Value                            
d                                 *   Value ProcPtr                    
d memcmp          pr            10i 0 ExtProc('memcmp')                
d                                 *   Value                            
d                                 *   Value                            
d                               10i 0 Value                            
d memmove         pr                  ExtProc('memmove')                
d                                 *   Value                             
d                                 *   Value                             
d                               10i 0 Value                             

insertItem

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * insert item into array                                            * 
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
p insertItem      b                                                    
d                 pi                                                   
                                                                       
 /free
  //                                                                   
  // if item not found                                                 
  //                                                                   
  If (*NULL = bsearch( %Addr(item)                                    
                     : %Addr(@item)                                    
                     : $J                                              
                     : szItem                                        
                     : %PAddr('BSEARCHCOMP')                           
                     ) );                                              

     $I = 1;
     DoW ( $I    <= $J           And                               
           item  >  @item($I) );                                   
        $I = $I + 1;                                             
     EndDo;                                                         
                                                                    
     If ($I > $J );             // goes on end                                  
        $J           = $I;                                       
        @items($J)   = item;                                       
     Else;                                                            
        //                                                          
        // scooch elements greater than item to the right ...                          
        //                                                          
        memmove( %Addr(@items($I)) + szItem                     
               : %Addr(@items($I))                                
               : ($J - $I + 1) * szItem                        
               );                                                   
        //                                                          
        // ... and insert the new element                          
        //                                                          
                                                                    
         @items($I) = item;                                           
                                                                      
         $J = $J + 1;                                                 
      EndIf;                                                          
   EndIf;                                                             
                                                                      
   Return;                                                            
  /end-free                                                           
 p insertItem      e

findItem

        
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *  
 * ... Find item ...                                                    
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *  
p findItem        b                                                     
d                 pi             5i 0                                   
                                                                        
d @               s               *                                     
 /free                                                                  
                                                                        
  @ = bsearch( %Addr(item)                                             
             : %Addr(@item)                                             
             : $J                                                       
             : szItem                                                 
             : %PAddr('BSEARCHCOMP')                                    
             );                                                         
                                                                        
  If ( @ <> *NULL );                                                    
     Return ((@ - %Addr(@item))/szItem) + 1;  // array element                          
  Else;                                                                 
     Return 0;     
  EndIf;                                                                
 /end-free                                                              
p findItem        e

BSEARCHCOMP

                                                     
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *  
 * ... bsearch compare ...                                              
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *  
p bSearchComp     b                                                     
d                 pi            10i 0                                   
d a@                              *   Value                             
d b@                              *   Value                             
                                                                        
 /free                                                                  
  return memcmp( a@                                                     
               : b@                                                     
               : szItem                                               
               );                                                       
 /end-free                                                              
p bSearchComp     e