Skip to main content

Browse the archive

https://github.com/halide/Halide
21 March 2024, 02:33:35 UTC
Revision 0112da4664f3410b27b5fb9ff2d381a50cdb981c authored by Andrew Adams on 19 July 2023, 18:27:35 UTC, committed by GitHub on 19 July 2023, 18:27:35 UTC 
Fix quadratic algorithm in simplify_correlated_differences (#7686)
 
This pass called expr_uses_var in a loop while building up a potentially
long let chain. This does a quadratic amount of work in the size of the
let chain, which stalled compilation for a particular pathological
pipeline I encountered.

This changes it to an eager algorithm that tracks the set of free
variables and incrementally grows it instead of revisiting the entire
expr for each new let added. It is n log(n) in the number of lets
instead of n^2

Co-authored-by: Steven Johnson <srj@google.com>
1 parent 18fbc15
History
Tip revision: 0112da4664f3410b27b5fb9ff2d381a50cdb981c authored by Andrew Adams on 19 July 2023, 18:27:35 UTC
Fix quadratic algorithm in simplify_correlated_differences (#7686)
Tip revision: 0112da4
File Mode Size
.github
apps
cmake
dependencies
doc
packaging
python_bindings
src
test
tools
tutorial
util
.clang-format -rw-r--r-- 1.4 KB
.clang-format-ignore -rw-r--r-- 375 bytes
.clang-tidy -rw-r--r-- 6.9 KB
.gitattributes -rw-r--r-- 342 bytes
.gitignore -rw-r--r-- 4.9 KB
.gitmodules -rw-r--r-- 0 bytes
CMakeLists.txt -rw-r--r-- 6.6 KB
CMakePresets.json -rw-r--r-- 6.8 KB
CODE_OF_CONDUCT.md -rw-r--r-- 3.5 KB
LICENSE.txt -rw-r--r-- 14.4 KB
MANIFEST.in -rw-r--r-- 159 bytes
Makefile -rw-r--r-- 105.3 KB
README.md -rw-r--r-- 16.5 KB
README_cmake.md -rw-r--r-- 77.9 KB
README_fuzz_testing.md -rw-r--r-- 3.9 KB
README_python.md -rw-r--r-- 31.8 KB
README_rungen.md -rw-r--r-- 12.1 KB
README_vulkan.md -rw-r--r-- 11.4 KB
README_webassembly.md -rw-r--r-- 10.5 KB
README_webgpu.md -rw-r--r-- 4.4 KB
pyproject.toml -rw-r--r-- 196 bytes
requirements.txt -rw-r--r-- 130 bytes
run-clang-format.sh -rwxr-xr-x 1.4 KB
run-clang-tidy.sh -rwxr-xr-x 3.2 KB
setup.py -rw-r--r-- 1.2 KB

README.md

back to top