containers
(Option 2) Fixed O(N^2) performance when handling --bind flags
Issue #384. Same Pull Request as #629 (please read it). But I've been thinking about changes I have made and realized that maybe segment trees with lazy propagation is a little bit overengineering just to set flags. In this branch I've removed the whole segment tree data structure and replaced it with boolean arrays.
When segment tree uses lazy propagation to assign value on the interval and uses recursive algorithm to retrieve actual value on the index, current implementation just memset() the needed part of array to set flags and access needed flag by index. In all other respects, the algorithm remains unchanged.
-
Technically here we revert back to O(N^2) complexity, but compiler optimizations and speed of
memsetperforms also great on even big amounts of mount points. At the same time, if we run some more complex benchmarks, maybe with hundreds of thousands mount points, there's a great possibility that segment trees will perform better. -
At the same time, again, boolean array takes really much less memory than segment tree (4N) of integers. And it's a big advantage. Also, It's just more simple.
-
With this approach we can also try to inline all the check/set flags function. I've tried. Nothing changed. Maybe it became a little slower. Anyway, there's such possibility.
-
It's a way more simple to understand and debug
My benchmark with memset approach:
flatpak run com.microsoft.Edge
Without optimization => memset approach => segtree approach
- 0.013712 => 0.003204 => 0.004324
- 0.040225 => 0.007098 => 0.006671
- 0.004751 => 0.002331 => 0.002611
A test where I pass bwrap 2000 "--bind" flags:
bwrap --dev-bind / / --bind /usr /tmp/1 --bind /usr /tmp/2 ... --bind /usr /tmp/2000 /bin/true
- No optimizations: 14.038314
- Segtree approach: 0.218774
- Memset approach: 0.362339
Maybe we should add parameter like --many-binds to switch the algorithm, but idk, sounds like a delusion. Right now I cannot imagine the use case :D
I'm not a maintainer but it looks like your editor introduced a bunch of whitespace/formatting changes? I imagine they'd like to see the PR without those.
