On Fri, Aug 2, 2013 at 11:12 AM, Jonathan S. Shapiro <[email protected]>wrote:
> It seems that I often have large, durable DAGs with internal pointers. > Often, there is some "master" pointer (or small set of such pointers) that > keeps the structure alive. > I do typically see this pattern, but not for frozen DAGs. They change over time (sometimes a little, sometimes a lot), which means they need collection themselves or they could consume all memory with non-referenced elements. Once collections of these regions is allowed while sub-regions exist, the "borrowed" pointer no longer works, because holding the master-pointer no longer implies liveliness for dynamic data within the region. --- I'm considering possibilities which are not strictly LIFO/subtyped regions.... For example, consider borrowed internal references between large value types, made safe by master-pointers... If I make a large array-of-structs, any of the structs can point to any other struct in the same array using borrowed pointers without GC tracing, because if the whole array becomes unreachable, so do all of the elements of the array. This could not only dramatically reduce the number of GC traced pointers, but would also eliminate indirection and bounds checking costs because the borrowed pointers were validated when they were created. However, the utility of this alone is a bit suspect, as our array is fixed size. When we run out of entries, there is no means to get more, other than pausing to copy/rebuild the entire array into a new larger array. It would be nice if we could at least make a second array, and mutually link the lifetimes of the arrays. So now we have two value-type arrays-of-structs, and we join them by having their boxes hold pointers to each-other. Now borrowed pointers in either value-type-region can point to the other. None of them need to be GC traced, because the master-pointers guarantee liveliness of the other array. Further, both arrays don't need to be of the same type. This seems to have some advantages over general garbage-collected heap-allocation, because we are able to replicate C's ability to do cache-efficient packed arrays, with long-lived internal pointers to elements -- without the overhead of generally handling internal references in our GC. This also seems to have some advantages over value-type-arrays with array-index references, since we don't need to dereference or bounds-check the pointers between elements. Effectively, this is a mechanism to implement typesafe-managed-manual memory techniques within a GC system while hinting to the GC that doesn't need to frequently concern itself with the details inside the boxes (see below). In order for this to be truly useful, I think we still need a way to free one of the sub-arrays. There are two interesting possibilities. (1) is simply to use a GC tracing method on the borrowed pointers of connected boxes, to find out which boxes have no more borrowed pointers.. and then free that box. However, because the main point of this entire mechanism is to enable low-overhead alternate memory-management techniques, I think there is a more interesting option... (2) to allow forced free of a box, which causes the system to prevent any more borrowed pointers and actively null-out any existing references to the inside of that box. This is similar to 1, but it's guaranteed to free the memory in a single pass. Recapping, the intent of all of the above is to try to establish a pattern for typesafe managed memory usage which: (a) enables approaching C-like performance of cache-efficient packed arrays, and direct internal element pointer references, without the constant overhead of GC tracing those pointers, or dereferencing and bounds-checking (b) enables implementing typesafe-yet-manual memory management scheme within the context of a managed-GC, including ARC, linear-types, or even just malloc/free. (c) enables using and reclaiming these blocks of memory without the GC tracing their pointers as part of it's normal generational collection work. ---- Did I sell anyone, or is it full of holes?
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
