I had a little idea for easily making correct releaseObject implementations: Basically just traverse, but use some RTTI to skip substructures that never contain pointers of the type you're looking for. It's conceptually simple, seems like it could often slightly beat regular traversal, and sometimes seriously beat it. But I haven't tried it, of course. It could turn out that on average it's not good enough to make up for overhead.
This isn't a programmer-provided releaseObject, so I know it's not what you're getting at, but it's a thought for a different way to use all the releaseObject machinery. On Mon, Aug 4, 2014 at 4:24 AM, David Jeske <[email protected]> wrote: > 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
