performance measurements

Each table row shows performance measurements for this Java program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
2,0001.541.5736,2441826  1% 0% 1% 99%
6,0003.913.9238,3481826  1% 1% 1% 100%
10,0007.607.6149,0921826  1% 1% 1% 100%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read pidigits benchmark to see what this program should do.

 notes

java version "1.8.0_25"
Java(TM) SE Runtime Environment (build 1.8.0_25-b17)
Java HotSpot(TM) Server VM (build 25.25-b02, mixed mode)

 pidigits Java #3 program source code

/**
 * The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/

   contributed by Mike Pall
   java port by Stefan Krause
   Data Parallel adaptation by Sassa NF
*/

import java.util.concurrent.*;

public class pidigits {
   final static int 
      // plain int values
      FOUR = 0, BQ = 1, BR = 2, BT = 3, 
      // GMP integers
      V = 4, ER1 = 5, Q1 = 6, R1 = 7, T1 = 8, U1 = 9, ES1 = 10, ER = 11, 
      // these are always available
      Q = 12, R = 13, T = 14, U = 15; 

   final static int SPIN = 1000;

   long [] values = new long[ 16 ];
   Semaphore [] sema = new Semaphore[ values.length ];
   Semaphore allDone = new Semaphore( 0 );
   Semaphore moreWork = new Semaphore( 0 );
   final static int ADD = 0, MUL = 1, DIV_Q_R = 2;

   ExecutorService executor = Executors.newFixedThreadPool( 3 );

   int i;
   StringBuilder strBuf = new StringBuilder(1000000);
   final int n;

   private pidigits(int n)
   {
      this.n=n;
   }

   public static void acquire( Semaphore s, int permits )
   {
     int i = SPIN;
     while( !s.tryAcquire( permits ) ) if ( --i <= 0 ) break;

     // now, if i <= 0, then the semaphore is definitely not acquired
     if ( i <= 0 )
     {
       try
       {
         s.acquire( permits );
       }
       catch( Exception e )
       {}
     }
   }

   public class exec implements Runnable
   {
     exec [] seq_tasks;
     int instr, dest, op1, op2, op3 = -1;

     public exec( exec[] tasks )
     {
       seq_tasks = tasks;
     }

     public exec( int ins, int d, int o1, int o2 )
     {
       instr = ins; dest = d; op1 = o1; op2 = o2;
     }

     public exec( int ins, int d, int o1, int o2, int o3 )
     {
       this( ins, d, o2, o3 ); op3 = o1;
     }

     public void run()
     {
       _run();
       acquire( moreWork, 1 ); // leave the thread spinning until more work arrives
                               // - unparking takes ages on some boxes
     }

     public void _run()
     {
       if ( seq_tasks != null )
       {
         for( exec r: seq_tasks ) r._run();
         allDone.release();
         return;
       }

       // the while loop makes sure the thread doesn't get preempted
       // - don't care about the CPU going wild; it would be idle otherwise anyway
       acquire( sema[ op1 ], 1 ); sema[ op1 ].release();
       acquire( sema[ op2 ], 1 ); sema[ op2 ].release();

       if ( instr == MUL )
       {
         GmpUtil.mpz_mul_si( values[ dest ], values[ op1 ], (int)values[ op2 ] );
       }
       else if ( instr == ADD )
       {
         GmpUtil.mpz_add( values[ dest ], values[ op1 ], values[ op2 ] );
       }
       else if ( instr == DIV_Q_R )
       {
         GmpUtil.mpz_tdiv_qr( values[ dest ], values[ op3 ], values[ op1 ], values[ op2 ] );
         sema[ op3 ].release();
       }

       sema[ dest ].release();
     }
   };

   // compose_r = ( q,r; s,t ) = ( bq, br; bs, bt ) x (q,r; s,t)
   // bs == 0, hence s == 0 and multiplications involving bs and s aren't here (br*s, bt*s)
   // bt == 1 hence multiplications involving bt aren't here (s*bt, t*bt)

   // compose_l = ( q,r; s,t ) = (q,r; s,t) x ( bq, br; bs, bt )
   // extract = ( q*3 + r )/( s*3 + t ) compared to ( q*4 + r )/( s*4 + t )
   // the latter is the same as computing quotient and remainder of ( q*4 + r )/( s*4 + t );
   // if the remainder is greater or equal to q,
   // then the quotient is the same as of ( 3*q + r )/( s*3 + t ) since s==0
   final exec[] COMPOSE_R = new exec[]{ 
      new exec( new exec[]{ new exec( MUL, Q1, Q, BQ ),
            new exec( MUL, U1, Q1, FOUR ) } ), // now U is always Q*4
      new exec( new exec[]{ new exec( MUL, V, T, BR ),
         new exec( ADD, R1, R1, V ) } ),
      new exec( new exec[]{ new exec( MUL, R1, R, BQ ) } )
      };

   final exec[] COMPOSE_L = new exec[]{ 
      // digit extraction logic here
      new exec( new exec[]{ new exec( ADD, ES1, U, R ),
         // DIV_Q_R is approx the same cost as two muls
         // so this splits the work roughly equally
         new exec( DIV_Q_R, ER, ER1, ES1, T ) } ), 
                                                   
         // compose_l
      new exec( new exec[]{ new exec( MUL, R1, R, BT ),
         new exec( ADD, R1, R1, V ) } ),
      new exec( new exec[]{ new exec( MUL, V, Q, BR ),
         new exec( MUL, T1, T, BT ) } ),
      new exec( new exec[]{ new exec( MUL, Q1, Q, BQ ),
         new exec( MUL, U1, Q1, FOUR ) } ) // now U is always Q*4
      };


   private boolean multi_threaded_compute( exec[] code, int bq, int br, int bt, boolean compare )
   {
     allDone.drainPermits();

     for( int i = BQ; i < Q; ++i ) sema[ i ].drainPermits();

     values[ BQ ] = bq;
     sema[ BQ ].release();
     values[ BR ] = br;
     sema[ BR ].release();
     values[ BT ] = bt;
     sema[ BT ].release();

     for( int i = compare ? 1: 0; i < code.length; ++i )
     {
       executor.execute( code[ i ] ); // we are one thread, so skip code[ 0 ], 
                                      // if comparing the remainder is needed
       moreWork.release();
     }

     if ( !compare ) return false;

     code[ 0 ]._run();

     // ER1 >= Q means the remainder of (4*q+r)/t contains q,
     // and the quotient is the same as (3*q+r)/t
     boolean r = GmpUtil.mpz_cmp( values[ ER1 ], values[ Q ] ) >= 0; 
                                                                
     acquire( allDone, code.length );

     return r;
   }

   /* Print one digit. Returns 1 for the last digit. */
   private boolean printDigit(int y)
   {
      strBuf.append((char)(y+'0'));
      if (++i % 10 == 0 || i == n) {
         if (i%10!=0) for (int j=10-(i%10);j>0;j--) { strBuf.append(" "); }
         strBuf.append("\t:").append(i).append("\n");
      }
      return i == n;
   }

   /* Generate successive digits of PI. */
   void printAll()
   {
     int k = 1;
     for( int i = V; i < values.length; ++i ) values[ i ] = GmpUtil.mpz_init();

     GmpUtil.mpz_set_si( values[ Q ], 1 );
     GmpUtil.mpz_set_si( values[ T ], 1 );
     GmpUtil.mpz_set_si( values[ R ], 0 );
     GmpUtil.mpz_set_si( values[ U ], 4 ); // U = Q*4 - invariant
     values[ FOUR ] = 4;

     // these are initially unavailable
     for( int i = 0; i < sema.length; ++i ) sema[ i ] = new Semaphore( 0 );

     sema[ Q ].release(); // these are always avalable
     sema[ R ].release();
     sema[ FOUR ].release();
     sema[ T ].release();
     sema[ U ].release();
     i = 0;
     for (;;) {
       if ( multi_threaded_compute( COMPOSE_L, k, 4*k+2, 2*k+1, true ) ) {
         int y = GmpUtil.mpz_get_si( values[ ER ] );
       
         // compare == false - computation is in background; foreground thread can print
         multi_threaded_compute( COMPOSE_R, 10, -10*y, 1, false ); 
 
         boolean r = printDigit(y);
         acquire( allDone,  COMPOSE_R.length ); // wait for the COMPOSE_R to complete

         if ( r ) {
           System.out.print( strBuf );
           System.out.flush();
           // don't have to be this nice in a one-shot run
           for( int i = V; i < values.length; ++i ) GmpUtil.mpz_clear( values[ i ] ); 
           return;
         }
       } else {
         long g = values[ T ];
         values[ T ] = values[ T1 ];
         values[ T1 ] = g; // to save on init/GC costs
         k++;
       }
       long g = values[ Q ];
       values[ Q ] = values[ Q1 ];
       values[ Q1 ] = g;
       g = values[ R ];
       values[ R ] = values[ R1 ];
       values[ R1 ] = g;
       g = values[ U1 ];
       values[ U1 ] = values[ U ];
       values[ U ] = g;
     }
   }

   public static void main(String[] args){
      pidigits spigot = new pidigits(Integer.parseInt(args[0]));
      spigot.printAll();
      System.exit(0);
   }
}

class GmpUtil {
   static {
      System.loadLibrary("jpargmp");
   }

   static native long mpz_init();

   static native void mpz_clear(long src);

   static native void mpz_mul_si(long dest, long src,
         int val);

   static native void mpz_add(long dest, long src,
         long src2);

   static native void mpz_set_si(long src, int value);

   static native int mpz_get_si(long src);

   static native int mpz_cmp(long dest, long src);

   static native void mpz_tdiv_qr(long q, long r, long n,
         long d);
}

 make, command-line, and program output logs

Wed, 19 Nov 2014 08:17:47 GMT

MAKE:
mv pidigits.java-3.java pidigits.java
/usr/local/src/jdk1.8.0_25/bin/javac pidigits.java
0.80s to complete and log all make actions

COMMAND LINE:
/usr/local/src/jdk1.8.0_25/bin/java -Djava.library.path=Include/java -server -XX:+TieredCompilation -XX:+AggressiveOpts pidigits 10000

(TRUNCATED) PROGRAM OUTPUT:
3141592653	:10
5897932384	:20
6264338327	:30
9502884197	:40
1693993751	:50
0582097494	:60
4592307816	:70
4062862089	:80
9862803482	:90
5342117067	:100
9821480865	:110
1328230664	:120
7093844609	:130
5505822317	:140
2535940812	:150
8481117450	:160
2841027019	:170
3852110555	:180
9644622948	:190
9549303819	:200
6442881097	:210
5665933446	:220
1284756482	:230
3378678316	:240
5271201909	:250
1456485669	:260
2346034861	:270
0454326648	:280
2133936072	:290
6024914127	:300
3724587006	:310
6063155881	:320
7488152092	:330
0962829254	:340
0917153643	:350
6789259036	:360
0011330530	:370
5488204665	:380
2138414695	:390
1941511609	:400
4330572703	:410
6575959195	:420
3092186117	:430
3819326117	:440
9310511854	:450
8074462379	:460
9627495673	:470
5188575272	:480
4891227938	:490
1830119491	:500
2983367336	:510
2440656643	:520
0860213949	:530
4639522473	:540
7190702179	:550
8609437027	:560
7053921717	:570
6293176752	:580
3846748184	:590
6766940513	:600
2000568127	:610
1452635608	:620
2778577134	:630
2757789609	:640
1736371787	:650
2146844090	:660
1224953430	:670
1465495853	:680
7105079227	:690
9689258923	:700
5420199561	:710
1212902196	:720
0864034418	:730
1598136297	:740
7477130996	:750
0518707211	:760
3499999983	:770
7297804995	:780
1059731732	:790
8160963185	:800
9502445945	:810
5346908302	:820
6425223082	:830
5334468503	:840
5261931188	:850
1710100031	:860
3783875288	:870
6587533208	:880
3814206171	:890
7766914730	:900
3598253490	:910
4287554687	:920
3115956286	:930
3882353787	:940
5937519577	:950
8185778053	:960
2171226806	:970
6130019278	:980
7661119590	:990
9216420198	:1000
9380952572	:1010
0106548586	:1020
3278865936	:1030
1533818279	:1040
6823030195	:1050
2035301852	:1060
9689957736	:1070
2259941389	:1080
1249721775	:1090
2834791315	:1100
1557485724	:1110
2454150695	:1120
9508295331	:1130
1686172785	:1140
5889075098	:1150
3817546374	:1160
6493931925	:1170
5060400927	:1180
7016711390	:1190
0984882401	:1200
2858361603	:1210
5637076601	:1220
0471018194	:1230
2955596198	:1240
9467678374	:1250
4944825537	:1260
9774726847	:1270
1040475346	:1280
4620804668	:1290
4259069491	:1300
2933136770	:1310
2898915210	:1320
4752162056	:1330
9660240580	:1340
3815019351	:1350
1253382430	:1360
0355876402	:1370
4749647326	:1380
3914199272	:1390
6042699227	:1400
9678235478	:1410
1636009341	:1420
7216412199	:1430
2458631503	:1440
0286182974	:1450
5557067498	:1460
3850549458	:1470
8586926995	:1480
6909272107	:1490
9750930295	:1500
5321165344	:1510
9872027559	:1520
6023648066	:1530
5499119881	:1540
8347977535	:1550
6636980742	:1560
6542527862	:1570
5518184175	:1580
7467289097	:1590
7772793800	:1600
0816470600	:1610
1614524919	:1620
2173217214	:1630
7723501414	:1640
4197356854	:1650
8161361157	:1660
3525521334	:1670
7574184946	:1680
8438523323	:1690
9073941433	:1700
3454776241	:1710
6862518983	:1720
5694855620	:1730
9921922218	:1740
4272550254	:1750
2568876717	:1760
9049460165	:1770
3466804988	:1780
6272327917	:1790
8608578438	:1800
3827967976	:1810
6814541009	:1820
5388378636	:1830
0950680064	:1840
2251252051	:1850
1739298489	:1860
6084128488	:1870
6269456042	:1880
4196528502	:1890
2210661186	:1900
3067442786	:1910
2203919494	:1920
5047123713	:1930
7869609563	:1940
6437191728	:1950
7467764657	:1960
5739624138	:1970
9086583264	:1980
5995813390	:1990
4780275900	:2000
9946576407	:2010
8951269468	:2020
3983525957	:2030
0982582262	:2040
0522489407	:2050
7267194782	:2060
6848260147	:2070
6990902640	:2080
1363944374	:2090
5530506820	:2100
3496252451	:2110
7493996514	:2120
3142980919	:2130
0659250937	:2140
2216964615	:2150
1570985838	:2160
7410597885	:2170
9597729754	:2180
9893016175	:2190
3928468138	:2200
2686838689	:2210
4277415599	:2220
1855925245	:2230
9539594310	:2240
4997252468	:2250
0845987273	:2260
6446958486	:2270
5383673622	:2280
2626099124	:2290
6080512438	:2300
8439045124	:2310
4136549762	:2320
7807977156	:2330
9143599770	:2340
0129616089	:2350
4416948685	:2360
5584840635	:2370
3422072225	:2380
8284886481	:2390
5845602850	:2400
6016842739	:2410
4522674676	:2420
7889525213	:2430
8522549954	:2440
6667278239	:2450
8645659611	:2460
6354886230	:2470
5774564980	:2480
3559363456	:2490
8174324112	:2500
5150760694	:2510
7945109659	:2520
6094025228	:2530
8797108931	:2540
4566913686	:2550
7228748940	:2560
5601015033	:2570
0861792868	:2580
0920874760	:2590
9178249385	:2600
8900971490	:2610
9675985261	:2620
3655497818	:2630
9312978482	:2640
1682998948	:2650
7226588048	:2660
5756401427	:2670
0477555132	:2680
3796414515	:2690
2374623436	:2700
4542858444	:2710
7952658678	:2720
2105114135	:2730
4735739523	:2740
1134271661	:2750
0213596953	:2760
6231442952	:2770
4849371871	:2780
1014576540	:2790
3590279934	:2800
4037420073	:2810
1057853906	:2820
2198387447	:2830
8084784896	:2840
8332144571	:2850
3868751943	:2860
5064302184	:2870
5319104848	:2880
1005370614	:2890
6806749192	:2900
7819119793	:2910
9952061419	:2920
6634287544	:2930
4064374512	:2940
3718192179	:2950
9983910159	:2960
1956181467	:2970
5142691239	:2980
7489409071	:2990
8649423196	:3000
1567945208	:3010
0951465502	:3020
2523160388	:3030
1930142093	:3040
7621378559	:3050
5663893778	:3060
7083039069	:3070
7920773467	:3080
2218256259	:3090
9661501421	:3100
5030680384	:3110
4773454920	:3120
2605414665	:3130
9252014974	:3140
4285073251	:3150
8666002132	:3160
4340881907	:3170
1048633173	:3180
4649651453	:3190
9057962685	:3200
6100550810	:3210
6658796998	:3220
1635747363	:3230
8405257145	:3240
9102897064	:3250
1401109712	:3260
0628043903	:3270
9759515677	:3280
1577004203	:3290
3786993600	:3300
7230558763	:3310
1763594218	:3320
7312514712	:3330
0532928191	:3340
8261861258	:3350
6732157919	:3360
8414848829	:3370
1644706095	:3380
7527069572	:3390
2091756711	:3400
6722910981	:3410
6909152801	:3420
7350671274	:3430
8583222871	:3440
8352093539	:3450
6572512108	:3460
3579151369	:3470
8820914442	:3480
1006751033	:3490
4671103141	:3500
2671113699	:3510
0865851639	:3520
8315019701	:3530
6515116851	:3540
7143765761	:3550
8351556508	:3560
8490998985	:3570
9982387345	:3580
5283316355	:3590
0764791853	:3600
5893226185	:3610
4896321329	:3620
3308985706	:3630
4204675259	:3640
0709154814	:3650
1654985946	:3660
1637180270	:3670
9819943099	:3680
2448895757	:3690
1282890592	:3700
3233260972	:3710
9971208443	:3720
3573265489	:3730
3823911932	:3740
5974636673	:3750
0583604142	:3760
8138830320	:3770
3824903758	:3780
9852437441	:3790
7029132765	:3800
6180937734	:3810
4403070746	:3820
9211201913	:3830
0203303801	:3840
9762110110	:3850
0449293215	:3860
1608424448	:3870
5963766983	:3880
8952286847	:3890
8312355265	:3900
8213144957	:3910
6857262433	:3920
4418930396	:3930
8642624341	:3940
0773226978	:3950
0280731891	:3960
5441101044	:3970
6823252716	:3980
2010526522	:3990
7211166039	:4000
6665573092	:4010
5471105578	:4020
5376346682	:4030
0653109896	:4040
5269186205	:4050
6476931257	:4060
0586356620	:4070
1855810072	:4080
9360659876	:4090
4861179104	:4100
5334885034	:4110
6113657686	:4120
7532494416	:4130
6803962657	:4140
9787718556	:4150
0845529654	:4160
1266540853	:4170
0614344431	:4180
8586769751	:4190
4566140680	:4200
0700237877	:4210
6591344017	:4220
1274947042	:4230
0562230538	:4240
9945613140	:4250
7112700040	:4260
7854733269	:4270
9390814546	:4280
6464588079	:4290
7270826683	:4300
0634328587	:4310
8569830523	:4320
5808933065	:4330
7574067954	:4340
5716377525	:4350
4202114955	:4360
7615814002	:4370
5012622859	:4380
4130216471	:4390
5509792592	:4400
3099079654	:4410
7376125517	:4420
6567513575	:4430
1782966645	:4440
4779174501	:4450
1299614890	:4460
3046399471	:4470
3296210734	:4480
0437518957	:4490
3596145890	:4500
1938971311	:4510
1790429782	:4520
8564750320	:4530
3198691514	:4540
0287080859	:4550
9048010941	:4560
2147221317	:4570
9476477726	:4580
2241425485	:4590
4540332157	:4600
1853061422	:4610
8813758504	:4620
3063321751	:4630
8297986622	:4640
3717215916	:4650
0771669254	:4660
7487389866	:4670
5494945011	:4680
4654062843	:4690
3663937900	:4700
3976926567	:4710
2146385306	:4720
7360965712	:4730
0918076383	:4740
2716641627	:4750
4888800786	:4760
9256029022	:4770
8472104031	:4780
7211860820	:4790
4190004229	:4800
6617119637	:4810
7921337575	:4820
1149595015	:4830
6604963186	:4840
2947265473	:4850
6425230817	:4860
7036751590	:4870
6735023507	:4880
2835405670	:4890
4038674351	:4900
3622224771	:4910
5891504953	:4920
0984448933	:4930
3096340878	:4940
0769325993	:4950
9780541934	:4960
1447377441	:4970
8426312986	:4980
0809988868	:4990
7413260472	:5000
1569516239	:5010
6586457302	:5020
1631598193	:5030
1951673538	:5040
1297416772	:5050
9478672422	:5060
9246543668	:5070
0098067692	:5080
8238280689	:5090
9640048243	:5100
5403701416	:5110
3149658979	:5120
4092432378	:5130
9690706977	:5140
9422362508	:5150
2216889573	:5160
8379862300	:5170
1593776471	:5180
6512289357	:5190
8601588161	:5200
7557829735	:5210
2334460428	:5220
1512627203	:5230
7343146531	:5240
9777741603	:5250
1990665541	:5260
8763979293	:5270
3441952154	:5280
1341899485	:5290
4447345673	:5300
8316249934	:5310
1913181480	:5320
9277771038	:5330
6387734317	:5340
7207545654	:5350
5322077709	:5360
2120190516	:5370
6096280490	:5380
9263601975	:5390
9882816133	:5400
2316663652	:5410
8619326686	:5420
3360627356	:5430
7630354477	:5440
6280350450	:5450
7772355471	:5460
0585954870	:5470
2790814356	:5480
2401451718	:5490
0624643626	:5500
7945612753	:5510
1813407833	:5520
0336254232	:5530
7839449753	:5540
8243720583	:5550
5311477119	:5560
9260638133	:5570
4677687969	:5580
5970309833	:5590
9130771098	:5600
7040859133	:5610
7464144282	:5620
2772634659	:5630
4704745878	:5640
4778720192	:5650
7715280731	:5660
7679077071	:5670
5721344473	:5680
0605700733	:5690
4924369311	:5700
3835049316	:5710
3128404251	:5720
2192565179	:5730
8069411352	:5740
8013147013	:5750
0478164378	:5760
8518529092	:5770
8545201165	:5780
8393419656	:5790
2134914341	:5800
5956258658	:5810
6557055269	:5820
0496520985	:5830
8033850722	:5840
4264829397	:5850
2858478316	:5860
3057777560	:5870
6888764462	:5880
4824685792	:5890
6039535277	:5900
3480304802	:5910
9005876075	:5920
8251047470	:5930
9164396136	:5940
2676044925	:5950
6274204208	:5960
3208566119	:5970
0625454337	:5980
2131535958	:5990
4506877246	:6000
0290161876	:6010
6795240616	:6020
3425225771	:6030
9542916299	:6040
1930645537	:6050
7991403734	:6060
0432875262	:6070
8889639958	:6080
7947572917	:

Revised BSD license

  Home   Conclusions   License   Play