Performance analysis numbers

performance

Latency Comparison Numbers
--------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Notes
-----
1 ns = 10^-9 seconds
1 us = 10^-6 seconds = 1,000 ns
1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns

Cost of basic java operations (running OS X on Macbook Pro 2.2GHz with 2GB RAM)
-------------------------------------------------------------------------------
operation                  example            nanoseconds
integer add                a + b              2.1
integer multiply           a * b              2.4
integer divide             a / b              5.4
floating-point add         a + b              4.6
floating-point multiply    a * b              4.2
floating-point divide      a / b              13.5
sine                       Math.sin(theta)    91.3
arctangent                 Math.atan2(y, x)   129.0

Cost (complexity) of basic java operations
------------------------------------------
operation                  example                nanoseconds
variable declaration       int a                  c1
assignment statement       a = b                  c2
integer compare            a < b                  c3
array element access       a[i]                   c4
array length               a.length               c5
1D array allocation        new int[N]             c6 * N
2D array allocation        new int[N][N]          c7 * N^2
string length              s.length()             c8
substring extraction       s.substring(N/2, N)    c9
string concatenation       s + t                  c10 * N

Common order-of-growth classifications
--------------------------------------
order of growth    name           typical code framework                         description           example              T(2N) / T(N) TODO
1                  constant       a = b + c;                                     statement             add two numbers      1
log N              logarithmic    while (N > 1)	{ N = N / 2; ... }               divide in half        binary search        ~ 1
N                  linear         for (int i = 0; i < N; i++) { ... }            loop                  find the maximum     2
N log N            linearithmic   TODO                                           divide and conquer    mergesort            ~ 2
N^2                quadratic      for (int i = 0; i < N; i++)                    double loop           check all pairs      4
                                      for (int j = 0; j < N; j++) { ... }
N^3                cubic          for (int i = 0; i < N; i++)                    triple loop           check all triples    8
                                      for (int j = 0; j < N; j++)
                                          for (int k = 0; k < N; k++) { ... }
2^N                exponential    TODO                                           exhaustive search     check all subsets    T(N)


Java (TODO 32/64) memory usage
------------------------------
type/description                                     bytes
padding                                              multiples of 8
boolean                                              1
byte                                                 1
char                                                 2
int                                                  4
float                                                4
long                                                 8
double                                               8
boolean[]                                            16 + N + padding
byte[]                                               16 + N + padding
char[]                                               16 + 2N + padding
int[]                                                16 + 4N + padding
float[]                                              16 + 4N + padding
long[]                                               16 + 4N + padding
double[]                                             16 + 4N + padding
char[][]                                             ~ 2 M N TODO
int[][]                                              ~ 4 M N TODO
double[][]                                           ~ 8 M N TODO
Boolean                                              16
Byte                                                 16
Character                                            16
Integer                                              16
Float                                                16
Long                                                 24
Double                                               24
String                                               2N + 64 TODO
Object                                               16
reference to object                                  4
object overhead                                      12 + padding
reference to enclosing object (for inner classes)    4