3 ms·

GC is intractable with pointer arithmetic. Edit: to be clear, this is the classic difference between a reference (a value without arithmetic) vs a pointer.

• ori_b 11y ago
  This isn't quite true, although you need some sort of guarantee on the arithmetic to ensure that each pointer is bounded within an object. C, in theory, allows this restriction, since computing a pointer to another object and dereferencing it is undefined behavior, but most implementations seem to relax this restriction.
  • DonaldFisk 11y ago
    I think that Symbolics C did have this restriction.
  • duaneb 11y ago
    > This isn't quite true, although you need some sort of guarantee on the arithmetic to ensure that each pointer is bounded within an object. I mean, this isn't pointer arithmetic, this is constrained offset lookup implementing a subset of pointer arithmetic (only addition of numbers >= 0?). I'd argue they're still not pointers unless you can derefence an arbitrary integer.
    • ori_b 11y ago
      Then you're arguing that strictly conforming C code does not have pointers.
      • duaneb 11y ago
        The semantics of the english here is a little lacking, but I think strictly conforming C code has pointers that behave like references. To my current understanding, this is highly unrealistic, hence ameliorating tooling like address sanitization. To be clear, they would still be called pointers. But when people talk about the complications of pointers, they are referring to non-standard behavior which is necessary with today's C code (and pretty much all historic C code).
• parenthephobia 11y ago
  That's not really true, at least not with C. C doesn't permit arbitrary pointer arithmetic. e.g. If you take a pointer to the first element of an array and decrement it, the behaviour is undefined. It's permissible for the GC to crash your program in that situation. You don't need to dereference it: just having that pointer, even ephemerally, is undefined behaviour. If you deallocate an object, then all pointers to that object are, technically, rendered as-though uninitialized: it is undefined what happens if you even attempt to determine the address of a previously-deleted object. This permits implementations to set dangling pointers to NULL. Finally, a pointer to e.g. an int can't be used to access e.g. a float at that location. It is valid to convert an int pointer to a float pointer, but the consequences of dereferencing it are undefined. An exception exists for characters: any pointer can be converted to a char pointer and used to read the bytes of the object. The upshot is that every pointer in C always points at a valid object of a known type - or just-allocated memory which hasn't had a value put in it yet - or the GC is allowed to crash the program. Of course, most (all?) compilers don't actually generate code where it's always possible to find out what type of object a pointer is pointing at, or even whether the pointer has actually gone out of range. The real issue in C - other than a lot of code depends on the above rules not being enforced - is that it's valid to convert a pointer to an integer, store it for long enough for an eager GC to remove the object, and then convert that integer back to a pointer. Now you have an invalid pointer, but the standard doesn't allow the pointer to become invalid. That means the only valid GC must assume any integer might be a pointer in disguise (unless it can prove it could never be converted into a pointer), and it can't move objects around either, because it can't just go modifying integers which might be pointers to those objects.
  • haimez 11y ago
    Notably, this also prevents being able to implement functionality required for performant GC, like generational collection (as moving references is virtually impossible without controlling the runtime).