4 ms·

Great comment and thanks for the reading material. Now I'm wondering if there's a Rust library for a generational copying arena--one that compacts strings/blob

• steveklabnik 7y ago
  Generational arenas yes, but copying, I'm not aware of one. It's very hard to get the semantics correct, since you can't auto-re-write pointers/indices.
  • ithkuil 7y ago
    Perhaps such a library could help you record the location of the variables that contain pointers to the strings and keep that pointer up to data as the ownership of the string moves from variable to variable? I'm other words, doing some of the work a moving compacting collector would do during compaction but continuously during normal program execution.
    • steveklabnik 7y ago
      There's no way to hook into the move, so I don't see how it would be possible, or at least, not with techniques similar to compacting GCs.
      • masklinn 7y ago
        Maybe by reifying the indirection? The compacting arena would hand out smart pointers which would either always bounce through something (to get from an indentity to the actual memory location, at a cost) or it'd keep track and patch the pointers it handed out somehow. Possibly half and half, I don't remember what language it was (possibly obj-c?) which would hand out pointers, and on needing to move the allocations it'd transform the existing site into a "redirection table". Accessing pointers would check if they were being redirected, and update themselves to the new location if necessary. edit: might have been the global refcount table? Not sure.
        • steveklabnik 7y ago
          Yeah so I was vaguely wondering about some sort of double indirection; the structure keeps track of "this is a pointer I've handed out", those pointers point into that, which then points into the main structure. I have no idea if this actually a good idea, seems like you get rid of a lot of the cache locality advantages.
          • masklinn 7y ago
            I don't know that the cache locality would be a big issue (your indirection table would be a small-ish array), however you'd eat the cost of doubling the indirections, each pointer access would be two of them.
          • mypalmike 7y ago
            This sounds a lot like classic MacOS (pre-Darwin) memory allocation. You were allocated a handle, which you called Lock on to get a real pointer. After accessing the memory, you called Unlock to release it. There was definitely a performance hit for that indirection.
            • cesarb 7y ago
              It's the same on classic Windows (pre-Windows 95) memory allocation. GlobalAlloc with GMEM_MOVEABLE or LocalAlloc with LMEM_MOVEABLE returned a handle, which you called GlobalLock or LocalLock on to get a real pointer. After accessing the memory, you called GlobalUnlock or LocalUnlock to release it. Of course, this being Microsoft, you can still call these functions inherited from 16-bit Windows even on today's 64-bit Windows. (See Raymond Chen's "A history of GlobalLock" at https://devblogs.microsoft.com/oldnewthing/20041104-00/?p=37393 https://devblogs.microsoft.com/oldnewthing/20041104-00/?p=37...).
        • e_y_ 7y ago
          On top of the cost of the extra pointer lookup, you also run into cache coherency issues when dealing with threading. So then you need to use atomic ops or locks or cache flushing which makes it even more expensive. Rust is better suited to deal with it since there's a similar issue with refcounting across threads, so you might be able to get away with doing it for objects that are exclusive to one thread.
      • Jweb_Guru 7y ago
        It would be possible (and not that hard) for Copy types, but you'd need some custom derive traits if you had any pointers to managed objects.