floki
floki copied to clipboard
philss
Remove stack usage on Finder
On https://github.com/philss/floki/pull/518 I added the stack concept on the on Finder to make it easier to implement the search without HTMLTree. Since we ended up with separated functions to do the traversal with or without the tree, the stack ends up being an unnecessary performance overhead, and makes the code harder to read.
This PR replaces all stack usages and uses recursion to do the traverse the nodes.
##### With input big #####
Name ips average deviation median 99th %
id (PR) 736.59 1.36 ms ±8.70% 1.31 ms 1.87 ms
tag name (type) (PR) 623.02 1.61 ms ±9.32% 1.57 ms 2.19 ms
id (v0.36.2-4-gc3417a5) 546.58 1.83 ms ±8.47% 1.79 ms 2.48 ms
class (PR) 520.63 1.92 ms ±7.31% 1.88 ms 2.53 ms
tag name (type) (v0.36.2-4-gc3417a5) 470.92 2.12 ms ±10.80% 2.07 ms 3.07 ms
class (v0.36.2-4-gc3417a5) 424.90 2.35 ms ±9.94% 2.29 ms 3.50 ms
class multiple (PR) 40.74 24.55 ms ±49.78% 22.65 ms 100.20 ms
class multiple (v0.36.2-4-gc3417a5) 31.39 31.85 ms ±49.38% 28.18 ms 105.79 ms
Comparison:
id (PR) 736.59
tag name (type) (PR) 623.02 - 1.18x slower +0.25 ms
id (v0.36.2-4-gc3417a5) 546.58 - 1.35x slower +0.47 ms
class (PR) 520.63 - 1.41x slower +0.56 ms
tag name (type) (v0.36.2-4-gc3417a5) 470.92 - 1.56x slower +0.77 ms
class (v0.36.2-4-gc3417a5) 424.90 - 1.73x slower +1.00 ms
class multiple (PR) 40.74 - 18.08x slower +23.19 ms
class multiple (v0.36.2-4-gc3417a5) 31.39 - 23.46x slower +30.50 ms
Memory usage statistics:
Name Memory usage
id (PR) 0.00156 MB
tag name (type) (PR) 0.51 MB - 328.64x memory usage +0.51 MB
id (v0.36.2-4-gc3417a5) 1.87 MB - 1203.73x memory usage +1.87 MB
class (PR) 0.0170 MB - 10.93x memory usage +0.0155 MB
tag name (type) (v0.36.2-4-gc3417a5) 2.38 MB - 1531.39x memory usage +2.38 MB
class (v0.36.2-4-gc3417a5) 1.89 MB - 1213.66x memory usage +1.89 MB
class multiple (PR) 8.11 MB - 5208.64x memory usage +8.11 MB
class multiple (v0.36.2-4-gc3417a5) 11.06 MB - 7104.29x memory usage +11.06 MB
**All measurements for memory usage were the same**
##### With input medium #####
Name ips average deviation median 99th %
id (PR) 2.15 K 0.47 ms ±10.02% 0.45 ms 0.70 ms
tag name (type) (PR) 1.89 K 0.53 ms ±9.37% 0.52 ms 0.78 ms
id (v0.36.2-4-gc3417a5) 1.72 K 0.58 ms ±8.00% 0.57 ms 0.80 ms
tag name (type) (v0.36.2-4-gc3417a5) 1.50 K 0.66 ms ±8.62% 0.65 ms 0.93 ms
class (PR) 0.88 K 1.14 ms ±7.65% 1.11 ms 1.53 ms
class (v0.36.2-4-gc3417a5) 0.81 K 1.23 ms ±7.91% 1.20 ms 1.69 ms
class multiple (PR) 0.157 K 6.38 ms ±7.07% 6.25 ms 8.38 ms
class multiple (v0.36.2-4-gc3417a5) 0.126 K 7.92 ms ±20.86% 7.65 ms 16.02 ms
Comparison:
id (PR) 2.15 K
tag name (type) (PR) 1.89 K - 1.14x slower +0.0650 ms
id (v0.36.2-4-gc3417a5) 1.72 K - 1.25x slower +0.116 ms
tag name (type) (v0.36.2-4-gc3417a5) 1.50 K - 1.43x slower +0.199 ms
class (PR) 0.88 K - 2.45x slower +0.68 ms
class (v0.36.2-4-gc3417a5) 0.81 K - 2.64x slower +0.76 ms
class multiple (PR) 0.157 K - 13.71x slower +5.92 ms
class multiple (v0.36.2-4-gc3417a5) 0.126 K - 17.02x slower +7.46 ms
Memory usage statistics:
Name average deviation median 99th %
id (PR) 1.59 KB ±0.00% 1.59 KB 1.59 KB
tag name (type) (PR) 201.81 KB ±0.00% 201.81 KB 201.81 KB
id (v0.36.2-4-gc3417a5) 621.45 KB ±0.00% 621.45 KB 621.45 KB
tag name (type) (v0.36.2-4-gc3417a5) 828.10 KB ±0.00% 828.10 KB 828.10 KB
class (PR) 50.80 KB ±0.00% 50.80 KB 50.80 KB
class (v0.36.2-4-gc3417a5) 670.41 KB ±0.00% 670.41 KB 670.41 KB
class multiple (PR) 2742.65 KB ±0.00% 2742.66 KB 2742.76 KB
class multiple (v0.36.2-4-gc3417a5) 3666.98 KB ±0.00% 3666.96 KB 3667.21 KB
Comparison:
id (PR) 1.59 KB
tag name (type) (PR) 201.81 KB - 126.63x memory usage +200.22 KB
id (v0.36.2-4-gc3417a5) 621.45 KB - 389.93x memory usage +619.85 KB
tag name (type) (v0.36.2-4-gc3417a5) 828.10 KB - 519.59x memory usage +826.51 KB
class (PR) 50.80 KB - 31.87x memory usage +49.20 KB
class (v0.36.2-4-gc3417a5) 670.41 KB - 420.65x memory usage +668.81 KB
class multiple (PR) 2742.65 KB - 1720.88x memory usage +2741.06 KB
class multiple (v0.36.2-4-gc3417a5) 3666.98 KB - 2300.85x memory usage +3665.39 KB
##### With input small #####
Name ips average deviation median 99th %
id (PR) 9.65 K 103.64 μs ±13.69% 100.24 μs 174.14 μs
tag name (type) (PR) 8.82 K 113.42 μs ±19.63% 108.07 μs 232.30 μs
id (v0.36.2-4-gc3417a5) 7.68 K 130.25 μs ±15.35% 125.29 μs 230.68 μs
tag name (type) (v0.36.2-4-gc3417a5) 7.21 K 138.68 μs ±13.88% 132.89 μs 232.46 μs
class (PR) 4.41 K 226.90 μs ±20.70% 211.84 μs 461.20 μs
class (v0.36.2-4-gc3417a5) 4.18 K 239.45 μs ±11.48% 232.35 μs 378.30 μs
class multiple (PR) 0.88 K 1142.82 μs ±8.20% 1113.90 μs 1579.43 μs
class multiple (v0.36.2-4-gc3417a5) 0.73 K 1378.83 μs ±13.63% 1328.57 μs 2030.63 μs
Comparison:
id (PR) 9.65 K
tag name (type) (PR) 8.82 K - 1.09x slower +9.78 μs
id (v0.36.2-4-gc3417a5) 7.68 K - 1.26x slower +26.60 μs
tag name (type) (v0.36.2-4-gc3417a5) 7.21 K - 1.34x slower +35.04 μs
class (PR) 4.41 K - 2.19x slower +123.25 μs
class (v0.36.2-4-gc3417a5) 4.18 K - 2.31x slower +135.81 μs
class multiple (PR) 0.88 K - 11.03x slower +1039.17 μs
class multiple (v0.36.2-4-gc3417a5) 0.73 K - 13.30x slower +1275.19 μs
Memory usage statistics:
Name average deviation median 99th %
id (PR) 1.59 KB ±0.00% 1.59 KB 1.59 KB
tag name (type) (PR) 39.44 KB ±0.00% 39.44 KB 39.44 KB
id (v0.36.2-4-gc3417a5) 127.27 KB ±0.00% 127.27 KB 127.27 KB
tag name (type) (v0.36.2-4-gc3417a5) 165.11 KB ±0.00% 165.11 KB 165.11 KB
class (PR) 9.46 KB ±0.00% 9.46 KB 9.46 KB
class (v0.36.2-4-gc3417a5) 135.13 KB ±0.00% 135.13 KB 135.13 KB
class multiple (PR) 560.28 KB ±0.00% 560.27 KB 560.32 KB
class multiple (v0.36.2-4-gc3417a5) 747.37 KB ±0.00% 747.37 KB 747.41 KB
Comparison:
id (PR) 1.59 KB
tag name (type) (PR) 39.44 KB - 24.75x memory usage +37.84 KB
id (v0.36.2-4-gc3417a5) 127.27 KB - 79.85x memory usage +125.67 KB
tag name (type) (v0.36.2-4-gc3417a5) 165.11 KB - 103.60x memory usage +163.52 KB
class (PR) 9.46 KB - 5.94x memory usage +7.87 KB
class (v0.36.2-4-gc3417a5) 135.13 KB - 84.79x memory usage +133.54 KB
class multiple (PR) 560.28 KB - 351.55x memory usage +558.68 KB
class multiple (v0.36.2-4-gc3417a5) 747.37 KB - 468.94x memory usage +745.78 KB
