bottleneck

bottleneck.md

original

• input: undefined [output (n) commands]
• compiler damage: brute force O(n^2)* -> O(n)
• compiler merge: brute force O(n^2)* -> O(n) [output (m) rectangles]
• compiler optimize: brute force O(mn)
• render: undefined

NOTE:

• the asterisk sign* means, it has a larger opportunity to appear
• worst-case -> best-case

benchmark

// bad input
compiler damage  : 12.2295 ms
compiler merge   : 1055.91 ms	<- a really big bottleneck
compiler optimize: 12.0104 ms
input  : 0.098415 ms
compile: 1080.28 ms
render : 19.8669 ms
total  : 1100.25 ms

// bad input
compiler damage  : 18.734 ms
compiler merge   : 2162.82 ms	<- for worse input
compiler optimize: 18.1344 ms
input  : 0.135607 ms
compile: 2199.83 ms
render : 23.8742 ms
total  : 2223.84 ms

// good input
compiler damage  : 1.83374 ms
compiler merge   : 4.26048 ms	<- still the worst in "compile" phase
compiler optimize: 0.558969 ms
input  : 0.082019 ms
compile: 6.74507 ms
render : 7.51369 ms
total  : 14.3408 ms

optimize 1: downsample

• input: undefined [output (n) commands]
• compiler damage: brute force O(n^2)* -> O(n)
• compiler merge: downsample O(n), then brute force O(n^2) -> O(n)* downsample make it more possible towards best situation, and also have a impact on lowering the output (m) [output (m) rectangles]
• compiler optimize: brute force O(mn)
• render: undefined

benchmark

// bad input
compiler damage  : 37.647 ms	<- bottleneck
compiler merge   : 0.156477 ms	<- much better!
compiler optimize: 0.147764 ms	<- it made this faster too
input  : 0.328209 ms
compile: 38.1118 ms
render : 20.5017 ms
total  : 58.9417 ms


// bad input
compiler damage  : 42.9321 ms	<- bottleneck
compiler merge   : 0.414677 ms	<- this is no longer a bottleneck
compiler optimize: 0.503012 ms
input  : 0.254256 ms
compile: 44.0105 ms
render : 20.7521 ms
total  : 65.0168 ms

optimize 2: hash

• input: undefined [output (n) commands]
• compiler damage: hash O(1), then brute force O(n) hash made the linear search into an O(1) operation
• compiler merge: downsample O(n), then brute force O(n^2) -> O(n)* downsample make it more possible towards best situation, and also have a impact on lowering the output (m) [output (m) rectangles]
• compiler optimize: brute force O(mn)
• render: undefined

benchmark

// bad input
compiler damage  : 0.805781 ms	<- much faster!
compiler merge   : 0.204182 ms
compiler optimize: 0.177139 ms
input  : 0.322715 ms
compile: 1.84876 ms
render : 24.0241 ms				<- maybe a bottleneck there?
total  : 26.1956 ms


// bad input
compiler damage  : 0.798831 ms	<- no longer a bottleneck
compiler merge   : 0.17745 ms
compiler optimize: 0.226347 ms
input  : 0.442356 ms
compile: 1.98787 ms
render : 23.3301 ms
total  : 25.7603 ms


// good input
compiler damage  : 0.315425 ms	<- although still the worst in "compile" phase
compiler merge   : 0.048288 ms
compiler optimize: 0.110788 ms
input  : 0.206091 ms
compile: 0.757227 ms
render : 13.507 ms
total  : 14.4703 ms


// best input
compiler damage  : 0.237234 ms
compiler merge   : 0.000111 ms
compiler optimize: 6.9e-05 ms
input  : 0.10489 ms
compile: 0.400483 ms
render : 0.219961 ms
total  : 0.725334 ms