9 ms·
Cool article! I was wondering how high k goes in production? You can easily get call stacks that are 20-100 depth so the theoretical maximum is around 100 but I
by hahnchen 2y ago
Cool article! I was wondering how high k goes in production? You can easily get call stacks that are 20-100 depth so the theoretical maximum is around 100 but I imagine that would be very very slow
- tekknolagi 2y agoI don't know how deep call stacks go (and also separately don't know if I am allowed to quote stats like that) but people tend to not do points-to with k higher than 2 or 3 because it explodes the whole graph
- ashton314 2y agoIIRC the complexity of k-CFA is exponential in k, which is not great. There’s another version called m-CFA; I don’t remember exactly what it does differently, but it doesn’t blow up exponentially
- DannyBee 2y agoYes, the time complexity of m-cfa is polynomial. See https://arxiv.org/pdf/1311.4231 https://arxiv.org/pdf/1311.4231 I'll borrow a few choice pieces from the paper to try to explain why. The main difference is that: k-cfa is sensitive to the last k calls. m-cfa is sensitive to the top m stack frames. This turns out not equivalent: with k=1 vs m=1: a program where main calls a calls b. in k-cfa, the context will be the call to b. in m-cfa, the context will be the call to a. How m-cfa came about and why it works: k-CFA is EXPTIME-complete (so no polynomial algorithm can exist). However, it was observed that there are plenty of provably k-cfa equivalent points-to for OO languages that ran in provably polynomial time (and none for functional languages). Diving into this caused folks to discover the difference between objects and closures matters a lot to the time-bounds, and led to the formulation of m-cfa. Space complexity was never as much an issue as time complexity was, due to BDD's and other things.