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
I 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
IIRC 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
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.
Your post will probably unfortunately get flagged, but I have observed an increase in my discussions with friends about politics overall, specifically DEI
deleting instagram isn't feasible for me. I like to use it to connect with most of my friends, but then also get distracted by their short form content scrolling
just use it on pc. It gets most of the benefits for contact maintenance. You can still watch the reels you are sent. But no reels, and the feed scroll gets very boring suddenly.
