Efficiency with Algorithms, Performance with Data Structures, cppcon

2015/2/8 18:47

A nice talk from Chandler Carruth at cppcon last year:

Which features this nice table which helps to highlight why data structures are so important.

One cycle on a 3 GHz processor1
L1 cache reference0.5
Branch mispredict5
L2 cache reference714x L1 cache
Mutex lock/unlock25
Main memory reference10020x L2, 200x L1
Compress 1K bytes with Snappy3,000
Send 1K bytes over 1 Gbps network10,0000.01
Read 4K randomly from SSD*150,0000.15
Read 1 MB sequentially from memory250,0000.25
Round trip within same datacenter500,0000.5
Read 1 MB sequentially from SSD*1,000,00014X memory
Disk seek10,000,0001020x datacenter RT
Read 1 MB sequentially from disk20,000,0002080x memory, 20X SSD
Send packet CA->Netherlands->CA150,000,000150

Good hash table design : 00:49:00