Chunk large ResizeArrays in TcResultsSinkImpl so that they aren't promoted to the Large Object Heap

[baronfel]

Following on from #6084 we should handle the cases where the unbounded ResizeArrays in TcResultsSinkImpl (and potentially elsewhere?) are changed to be a list-like data structure that self-chunks its elements into arrays that are below the LOH threshold.

Then we need to use that structure in place of at least the capturedNameResolutions member of TcResultsSinkImpl, potentially more.

Per @TIHan in #6089 the structure doesn't have to be threadsafe as the compiler service thread is the only accessor.

[gerardtoconnor]

Hey @baronfel, I was looking at this and was just confused on few things, not withstanding the point that arrays should probably not be getting this big, can you explain the chunking benefit on an already large array?

Reason I am asking it that the initial Resize array ... that is presumably already too big (and therefore on the LOH) is a problem, most of the operation on the resize arrays in TcResultsSinkImpl are mutating the existing array, not copying, (copy in GetSymbolUses() and maybe few others), but construction of TcResolutions in GetResolutions() are re-using the same LOH resize array refs anyway?

Is this just a less optimal application of the post-built array chunking or have I missed something critical? I would have thought using an unrolled linked list here would have maybe been better as it chunks automatically as it grows, does not need to be copied (potentially), and is nearly as performant as array?

[baronfel]

The thing that worried me was that capturedNameResolutions (and other ResizeArrays in the same code unit) were unbounded and thus could end up on the LOH. The chunking structure is a solution to this, but rapidly gets complex with the requirements to support removal by a predicate, maintain insertion order, and compress after removal. A linked list would likely do just fine here as well.

[gerardtoconnor]

I get that it's a way to do it for copies, but in the example where it's implemented, the capturedNameResolutions is (potentially) already on the LOH, and then we are chunking it in allUsesOfSymbols so that when GetUsesOfSymbol runs, (which is ironically a filter action which will reduce the size and reduce likelihood of LOH), we are not hitting LOH … in an ideal world would
1- capturedNameResolutions be a unrolled linked list (to never be put on LOH)
2 - allUsesOfSymbols be a generated seq from capturedNameResolutions, not even a data structure as it is being used in the context of a filter action and can avoid being allocated reading straight from source via transform/mapping?

Thanks for help understanding this … the code structure here looks strange to me so I may need some educating or the code may need fixing, its a win-win either way for me 👍

[baronfel]

I think we're speaking past each other: the intent was to change the declaration of capturedNameResolutions in TcResultsSinkImpl to not be a ResizeArray, and instead be some other structure (linked list, whatever) that would allow for a usage pattern that didn't hit the LOH (ie no unbounded growth of internal arrays). If capturedNameResolutions was a proper linked list then that would be fine IMO, assuming that the invariants above hold:
a) support some kind of remove-via-predicate operation
b) support an Add operation that maintains insertion order (there's some other logic that depends on insertion order that's not in TcResultsSinkImpl from what I recall)

So all in all I agree with you, capturedNameResolutions needs to be something other than a ResizeArray. Then all the derived usages of it (the seq expressions and whatnot) should be correct by construction.

[gerardtoconnor]

Thanks for clarifying, I was referencing usage in PR TcSymbolUseData cleanup per #6084 #6084 and how the ResizeArray chunking was used there, whereas this focusing on capturedNameResolutions although a common pattern/structure would be useful also.

Unlike linked list, an unrolled linked list can more dynamically handle additions and removable, ironically making it a better candidate for these operations then linked list or array, each array node can be made a variable length, unaffecting nodes around it so that predicate removal is faster … allowing this feature prevents blind index hopping down the array nodes. Additions are simply just adding to the array in the head node until overflow size hit for chunking so straight forward also.

I was wondering if having the elements sorted by range in the array would help given the predicate is range based, but as it appears to happen infrequently, it will only add time sorting the insertions.

[baronfel]

oh yeah, #6084 was really just a very short-term get-something-done fix. This issue is the right place to do a proper long-term fix, and it sounds like that would be a good candidate. Then once the source data was converted, the changes would flow naturally to the TcSymbolUseData and other consumers 👍

[gerardtoconnor]

Cool … time is running out so I'll try hack out before the weekend, so we can use in most places LOH is being hit, where it's an option ... these changes kinds of changes tend to propagate breaks like a weed so hopefully it's not too much of a mess.

[cartermp]

I haven't seen this pop up elsewhere, but given that this is kind of a game of whack a mole, it's likely that we have more LOH allocations sourced from this same data. Finding a way to use it uniformly throughout the codebase is likely to be a boon.

[dsyme]

I'm going to close out this specific issue, as @TIHan did so much work in this area in 2020-21.