Fast by Default: Algorithmic Optimization in Practice (dotJS 2019)

Transcript

1. Vladimir Agafonkin ⚡fast by default: algorithmic optimization in practice
6. ⚡fast or GTFO
7. Leaflet earcut pixelmatch delaunator rbush flatbush kdbush geokdbush geoflatbush geojson-vt potpack supercluster martini delatin cheap-ruler polylabel icomesh concaveman dobbyscan linematch lineclip simplify-js robust-predicates tinyqueue flatqueue which-polygon quickselect webgl-wind suncalc flamebearer tiny-sdf simpleheat … github.com/mourner/projects
8. mapbox/earcut (JS) mapbox/earcut.hpp (C++)
9. github.com/mapbox/potpack
10. github.com/mourner/ rbush kdbush flatbush rbush-knn geokdbush geoflatbush
11. mapbox/pixelmatch (JS) mapbox/pixelmatch-cpp (C++)
12. github.com/mapbox/delatin
14. delaunay: 150s delaunay-fast: 117s faster-delaunay: 5s delaunator: 1s delaunator-cpp: 0.9s delaunator-rs: 0.9s Delaunay triangulation of 1 million points in JavaScript:
16. 1. find a bottleneck 2. find out why it’s slow 3. make it faster optimization:
18. 1. find a bottleneck 2. find out why it’s slow 3. make it faster optimization: algorithm s!
19. slow code: code that does unnecessary work
20. Rollup
21. rollup/rollup#2062 rollup: map = magicString.generateMap() obj = decode(map) ";;;;EAEEA,EAAE,EAAC,CAAE;ECQY,UACC…"
22. rollup/rollup#2062 rollup: map = magicString.generateMap() magic-string: ... map = encode(obj) rollup: obj = decode(map)
23. map = encode(obj) obj = decode(map)
24. rollup/rollup#2062 rollup: map = magicString.generateDecodedMap() magic-string: map = encode(obj) rollup: obj = decode(map) source maps got 40% faster
25. algorithmic complexity: a measure of how performance scales with input size
26. O(1) O(log n) O(n) O(n log n) O(n2) O(n3)
27. array[0] + array[1]; O(1) — instant
28. for (const item of array) { sum += item; } O(n) — suspicious
29. O(n2) — ridiculously slow for (let i = 0, n = array.length; i < n; i++) { for (let j = i + 1; j < n; j++) { sum += array[i] + array[j]; } }
30. function foo(array) { for (const item of array) { array[array.indexOf(item)] = item + 10; } } O(n2) — ridiculously slow
31. function foo(array) { for (const item of array) { bar(array, item); } } function bar(array, item) { array[array.indexOf(item)] = item + 10; } O(n2) — ridiculously slow
32. accidentallyquadratic.tumblr.com
33. O(n3) — rewrite from scratch for (let i = 0, n = array.length; i < n; i++) { for (let j = i + 1; j < n; j++) { for (let k = j + 1; k < n; k++) { sum += array[i] + array[j]; } } }
34. if (j < 0) { if (triangles.length === 0) triangles.push([i]); return; } for (let n = triangles.length, a = 0; a < n; ++a) { let sa = triangles[a]; if (sa[0] === j) { for (let b = a + 1; b < n; ++b) { let sb = triangles[b]; if (sb[sb.length - 1] === i) { triangles.splice(b, 1); triangles[a] = sa = sb.concat(sa); return; } } sa.unshift(i); return; } d3/d3-delaunay#23
35. array.indexOf array.lastIndexOf array.splice array.includes array.reverse array.every Object.values array.find array.some array.findIndex array.reduce array.reduceRight array.some Object.keys O(n) — suspicious
37. array.slice array.concat array.map array.filter str.split suspicious allocations
38. a.slice().concat(b).map(foo) .filter(bar).reduce(bla, 0); allocate memory and throw it out immediately (4 times)
39. function foo() { ... return [x, y]; } const [x, y] = foo();
40. const lines = input.split(';'); for (const line of lines) { const segments = line.split(','); for (const segment of segments) { const decoded = decode(segment); for (const i of decoded) { ... } } } Rich-Harris/sourcemap-codec#71
41. for (let i = 0; i < input.length; i++) { const c = input.charCodeAt(i); if (c === 44) { // "," ... } else if (c === 59) { // ";" ... Rich-Harris/sourcemap-codec#71 3 times faster
42. O(log n) logarithmic complexity
43. O(log n) O(1) O(n) O(log n) — blazing fast
44. 1 1,000,000 20 O(log n) — blazing fast
45. binary search o(log n)
52. rollup/rollup#2228 … 40x faster
53. 1. O(n) → O(log n) 2. O(n log n) → O(n) 3. O(n2) → O(n log n) 4. O(n3) — throw out algorithmic optimization
54. slow slow slow algorithmic optimization
55. organize data algorithmic optimization
56. algorithmic optimization: do more at the beginning to do less every next time
57. • hash map • hash set • binary search tree • priority heap • linked list • interval tree • r-tree • quadtree • kd-tree • … data structures
58. sorted array o(n log n) ❤ favorite data structure
59. github.com/mourner/kdbush
60. HashTable Array [10, 20, 30]; { '1': 10, '2': 20, '3': 30 }; { '0': 10, '1': 20, ‘2': 30 };
61. istanbuljs/istanbul-lib-instrument#22 { '1': 10, '2': 20, '3': 30 }; 15 times faster { '0': 10, '1': 20, ‘2': 30 };
62. people take established code for granted
63. established !== best there is always room for improvement
64. 1. learn how things work under the hood 2. don’t be afraid to reinvent the wheel 3. simplify your code constantly 4. practice optimization, and you’ll learn how to write fast code by default
65. agafonkin.com thank you