Skip to content

Instantly share code, notes, and snippets.

@EugeneLoy
Forked from jboner/latency.txt
Last active February 7, 2018 21:38
Show Gist options
  • Save EugeneLoy/fa9b58358f643b2b59e8c4e1031847c6 to your computer and use it in GitHub Desktop.
Save EugeneLoy/fa9b58358f643b2b59e8c4e1031847c6 to your computer and use it in GitHub Desktop.
Performance analysis numbers
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment