arraytiming.java

金融资产定价,随机过程,MONTE CARLO 模拟 JAVA 程序和文档资料

/* WARANTY NOTICE AND COPYRIGHT
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

Copyright (C) Michael J. Meyer

[e-mail]
[e-mail]

*/


/*
 * ArrayTiming.java
 *
 * Created on August 27, 2002, 7:32 AM
 */

package Examples.Array;

import ArrayClasses.*;
import LinAlg.*;
import cern.colt.matrix.impl.DenseDoubleMatrix2D;



/** <p>Checks if contiguous triangular arrays are faster than standard 2D
 *  Java arrays, ColtMatrices and DenseDouble2DMatrices when used in a situation 
 *  similar to Libor path simulation. Only access to entries is tested.
 *  Note that contiguous arrays make a tradeoff between contiguous memory
 *  allocation and more complicated index computations. The main questions 
 *  are:</p>
 *  <ul>
 *     <li>Does contiguous (linear) allocation in main memory streamline data 
 *         traffic between memory and L2-cache? Note that we have to pay a price
 *         because we have to perform index calculations. Here these are done by
 *         accessor functions adding more overhead but it is the only realistic
 *         solution keeping the code from becoming very akward.</li>
 *     <li>What sort of overhead do accessor functions add?</li>
 *     <li>How do <code>ColtMatrices</code> and <code>cern.colt.matrices</code>
 *         perform?</li>
 *  </ul>
 *  <p>Run the program with <code>T=20</code> to remain in the L2-cache. 
 *  The current setting of <code>T=60</code> puts us into main memory.</p>
 *
 * <p>FINDINGS: nothing beats the standard java array. Colt matrices perform 
 * worst once the cache is too small. Accessor methods add significantly to
 * the overhead even more than index calculations. Having the array stored 
 * contiguously in memory is not worth the effort.</p>
 *
 * <p>Each sub-loop moves along a 1D array possibly consisting of references
 * to other 1D arrays. One could have the idea to store a reference to
 * the current 1D array at the beginning of each loop to reduce address
 * calculations and repeated bounds checking. This is possible for
 * standard java arrays at every level since nothing is hidden by accessor
 * methods. If this is done too often it decreases performance.
 * Done in the outermost loop there is a small performance gain.
 * See the improved loop for the <code>javaArray</code>.</p>
 *
 * <p><b>Summary:</b> the standard java array is fastest and straightforward 
 * unimproved loops work very well. Accessor methods exact a heavy toll.
 * Our loops traverse the arrays in a row by row fashion. This follows the way
 * arrays are allocated in main memory.</p>
 * 
 * <p>See also {@link MemoryTraffic} which shows that traversing a java array 
 * in main memory row by row is significantly (10 times) faster than traversing 
 * it column by column. Column by column
 * access is just as bad as complete random access.</p>
 *
 * @author Michael J. Meyer
 */
public class ArrayTiming {
    
    public static void main(String[] args)
    {
        int T=60, p=7, nLoops=2000;
        double x=3;
        
        // allocate the sequence of upper triangular contiguous arrays
        UTRContiguousArray[] UTCA=new UTRContiguousArray[T];
        for(int t=0;t<T;t++)UTCA[t]=new UTRContiguousArray(p,t+p);
        
        // allocate the sequence of lower triangular contiguous arrays
        LTRContiguousArray[] LTCA=new LTRContiguousArray[T];
        for(int t=0;t<T;t++)LTCA[t]=new LTRContiguousArray(p,t+p);
        
        // allocate the sequence of upper triangular arrays
        UTRArray[] UTA=new UTRArray[T];
        for(int t=0;t<T;t++)UTA[t]=new UTRArray(p,t+p);
        
        // allocate the sequence of standard java arrays
        double[][][] javaArray=new double[T][][];
        for(int t=0;t<T;t++)
        {
            javaArray[t]=new double[t][];
            for(int i=0;i<t;i++)javaArray[t][i]=new double[t-i];
        }
        
        // allocate the sequence of square ColtMatrices
        ColtMatrix[] CM=new ColtMatrix[T];
        for(int t=0;t<T;t++)CM[t]=new ColtMatrix(t+1,t+1);
        
        // allocate the sequence of square DenseDouble2DMatrices
        DenseDoubleMatrix2D[] DDM=new DenseDoubleMatrix2D[T];
        for(int t=0;t<T;t++)DDM[t]=new DenseDoubleMatrix2D(t+1,t+1);

        double before, after, time;
        
        String message="TIMING THREE DIMENSIONAL LOOP THROUGH ARRAY\n"+
                       "OF TWO DIMENSIONAL ARRAYS:\n\n";
        System.out.println(message);
 
        
        // CONTIGUOUS TRIANGULAR ARRAYS
        
        // begin timing upper triangular contiguous arrays
        
        // standard loop
        before=System.currentTimeMillis();
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++)
        for(int i=p;i<t+p;i++)
        for(int j=i;j<t+p;j++){ x=(UTCA[t]._(i,j)+x)/2; }
        
        after=System.currentTimeMillis();
        time=after-before;
        message="Upper triangular contiguous arrays, time: "+time;
        System.out.println(message);
        
        // improved loop
        before=System.currentTimeMillis();
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++){
            
            UTRContiguousArray utca=UTCA[t];
            for(int i=p;i<t+p;i++)
            for(int j=i;j<t+p;j++){ x=(utca._(i,j)+x)/2; }
        }
        
        after=System.currentTimeMillis();
        time=after-before;
        message=
        "Upper triangular contiguous arrays, improved loop, time: "+time;
        System.out.println(message);
        
 
        // begin timing lower triangular contiguous arrays
        before=System.currentTimeMillis();
        
        // the loop
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++)
        for(int i=p;i<t+p;i++)
        for(int j=p;j<=i;j++){ x=(LTCA[t]._(i,j)+x)/2; }
        
        after=System.currentTimeMillis();
        time=after-before;
        message="\nLower triangular contiguous arrays, time: "+time;
        System.out.println(message);
        

        
        // TRIANGULAR ARRAY WITH ARBITRARY INDEX BASE AND ACCESSOR METHODS
        
        // begin timing upper triangular array
        before=System.currentTimeMillis();
        
        // the loop
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++)
        for(int i=p;i<t+p;i++)
        for(int j=i;j<t+p;j++){ x=(UTA[t]._(i,j)+x)/2; }
        
        after=System.currentTimeMillis();
        time=after-before;
        message="\nUpper triangular noncontiguous arrays "+
                "with accessor methods, time: "+time;
        System.out.println(message);
        

        // STANDARD JAVA ARRAYS
        
        //begin timing java arrays
        
        // the standard loop
        before=System.currentTimeMillis();
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++)
        for(int i=0;i<t;i++)
        for(int j=0;j<t-i;j++){ x=(javaArray[t][i][j]+x)/2; }

        after=System.currentTimeMillis();
        time=after-before;
        message="\nStandard java arrays, time: "+time;
        System.out.println(message);
        
        // the improved loop
        before=System.currentTimeMillis();
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++)
        {
             double[][] A_t=javaArray[t];
             for(int i=0;i<t;i++)
             for(int j=0;j<t-i;j++){ x=(A_t[i][j]+x)/2; }
        }

        after=System.currentTimeMillis();
        time=after-before;
        message="Standard java arrays, improved loop, time: "+time;
        System.out.println(message);
        

        
        // COLT MATRICES
        
        // begin timing square ColtMatrices
        before=System.currentTimeMillis();
        
        // the loop
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++)
        for(int i=0;i<t;i++)
        for(int j=0;j<=i;j++){ x=(CM[t].getQuick(i,j)+x)/2; }
        
        after=System.currentTimeMillis();
        time=after-before;
        message="\nColtMatrices, time: "+time;
        System.out.println(message);
        
        // begin timing square DenseDouble2DMatrices
        before=System.currentTimeMillis();
        
        // the loop
        for(int loops=0;loops<nLoops;loops++)
        for(int t=0;t<T;t++)
        for(int i=0;i<t;i++)
        for(int j=0;j<=i;j++){ x=(DDM[t].getQuick(i,j)+x)/2; }
        
        after=System.currentTimeMillis();
        time=after-before;
        message="cern.colt.matrix.impl.DenseDoubleMatrix2D, time: "+time;
        System.out.println(message);
        
        
        
    } // end main
        
    
    
    
    
    
} // end ArrayTiming