3 ms·
It's not equivalent; you can tag every pointer with a special bit. Then statically you know the accessible roots at every instruction pointer value, and you can
by tylerhou 5y ago
It's not equivalent; you can tag every pointer with a special bit. Then statically you know the accessible roots at every instruction pointer value, and you can simply traverse accessible memory regions, following tagged pointers. Free all memory that is not visited.
A decision problem equivalent to the halting problem might be (depending on the language): does this code free all allocated memory correctly (assuming no garbage collector)?
- vlovich123 5y agoCool. That only tells you which memory is no longer actively referenced. It does not tell you whether or not you’ve leaked memory due to stale live references.
- tylerhou 5y agoBut then your definition of leak is arbitrary, because who's to say that memory won't be re-accessed in the future? You're right that that problem is equivalent to the halting problem.
- speedgoose 5y agoIt's a lot more rare problem compared to not correctly freeing memory though. And it's not hard to fix.
- vlovich123 5y agoMy point was that a GC’ed language doesn’t guarantee that this particular instance has to do with anything, especially since they use Swift for a lot of code (which does a form of GC via reference counting). The recommendation to switch to a tracing GC’ed language is naive because there are better solutions to this problem that don’t require a GC (ARC from Apple, managed pointers in c++, rust lifetime ownership etc), solve 90% of the problems with far less cost, which matters for mobile battery powered devices but also matters in high performance servers)