On Sat, Aug 2, 2014 at 11:09 PM, Matt Oliveri <[email protected]> wrote:
> If not, then the question is how do you keep track of the borrowing > structures to call releaseObject on? > Every container (an object with references to other objects) would contain a release-event-delivery system which borrowers would register into. Think of it as a "borrowersOfOurElements" list -- though an optimized version could be more complicated. In the ListA/ComplexB example, ListA is designated as an owner of it's elements; ComplexB is designed as a borrower of it's elements. The moment ComplexB retains a pointer to something from LisaA, it's event-handler is added to ListA as a borrower. data-structures which "index" all of another structure are very common. In fact, dealing with them in the faces of changes and threading is also a significant headache which lots of code is written to handle. Integrating STM and an explicit concept of an "indexing structure" could simplify that whole mess and make it feel more like a consistent database-trigger in code. However, in cases were only a few entries were borrowed, other techniques could be used. Borrowing just a few items might put the releaseObject delegate into an itemToBorrower hashmap. Borrowing more items might make a bloom filter that would track subsets of items. When the percentage was high enough, the borrower would be notified on all object releases. Regarding the broader issue of stack/heap/register roots, I have not thought about this enough in detail. I was thinking the releaseObject() concept would be used inside a hybrid system (perhaps Ulterior Reference Counting) to remove many pointers and sources of cycles from the view of either RC or tracing -- but not to eliminate either. For example -- We don't need to ever trace internal pointers of ComplexB if we know it only references live elements in ListA. In a way, this feels like a form of region-analysis. However, instead of treating the entire region as a chunk which must be freed at once, it's trying to provide a non-tracing lifetime solution for elements in the region. > > HOWEVER, the language to write releaseObject can be severely constrained, > > possibly not even turing complete -- for the purpose of making it > provable. > > Hmm, I'm not sure that would be easy. If you want releaseObject to take > full advantage of the data structure in order to update it, then the > algorithms could get arbitrarily fancy for fancier data structures. It > seems like the proof would need to be derived from the structure of the > code, probably using some extra annotations. It might turn out to be the > same as, or similar to existing ideas to use types > for memory management. > Only code which needs to be provable is the "construction and traversal" -- which I'm hoping is simpler than the full data-structure logic. However, I admit I don't know enough about how this type of proof would work. > > If an entire data-structure is released (such as releasing ListA), then > any > > borrowers can get a "releaseAllFrom(ListA)". If they only hold > references > > from ListA, then they can be fully released quickly. If they borrow > > references from other sources, then the ListA entries will need to be > > removed one by one. > > Maybe I over-generalized in what I thought you were proposing. ListA was > just an example; the owning data structure could be anything, not just a > List. How would you take advantage of releaseAllFrom-like operations > generically for any data type? Well I guess the data structure implementer > only needs to handle owning structures they > actually borrow from, but the runtime needs to handle anything borrowing > from anything. > Every data-structure implementor would need to provide a set of provable subprograms, including TraverseAll, relaseObject, and insertObject. Given these three programs, the system can provably implement releaseAllFrom(). Either as ComplexB.releaseObject(ListA.TraverseAll), or as a hash-join, where the system builds a hashmap out of a ListA.TraverseAll, and then does a TraverseAll on ComplexB, removing matches.
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
