Usage of `sort` in internal modules and its impact on compilation performance

[e-kayrakli]

On 5/28, we took a hit on compilation time , likely because code added to the Sort module in #27277.

That's a really unfortunate side effect of using sorting in some of our internal modules, mostly around non-DR domains. Can we do something to avoid that hit?

Right now, sort is used in:

• dsiSorted et al: the only usage of dsiSorted and sorted seems to be in the Sort module, at least in the module code. Can we make sorted on associative domains a tertiary method in the Sort module instead?
• ChapelArray: this seems to have a workaround code for exposing the default comparator. I haven't pulled on that thread to see what would break if we were to try something else. Besides, as long as we are not calling sort, maybe it is to use Sort?
• bulkAdd_prepareInds: This has to sort indices before adding for faster operation. I am not sure if there is a good way around this. A potential solution is to create a utility module for sparse operations and move bulk addition there, but note that += on sparse domains also needs this.

[jabraham17]

I think this is a duplicate of #27309?

Related to this, note that the .sorted method should be removed with an edition. See https://github.com/Cray/chapel-private/issues/5976. The docs already guide users in this direction, we cannot remove or change the behavior of this iterator without it being a breaking change

[mppf]

The new sort code brings in more standard modules that we weren't using by default before (most notably BlockDist, Random, and Time). With effort, we might be able to pull some of these out, but it was more than I felt able to do before feature freeze. That said, it makes more sense to me to allow Sort to continue to use these but to make Sort itself no longer included by default.

ChapelArray: this seems to have a workaround code for exposing the default comparator.

Whatever this is about, having a separate module defining the default and reverse comparators, would allow it to be included by default without the rest of Sort.

bulkAdd_prepareInds: This has to sort indices before adding for faster operation. I am not sure if there is a good way around this. A potential solution is to create a utility module for sparse operations and move bulk addition there, but note that += on sparse domains also needs this.

IMO this shouldn't be compiled be default; the sparse functionality should be left out unless sparse operations are used. I don't know how specifically we can/should achieve that.

[jabraham17]

I think the stuff in ChapelArray is just for supporting the associative array .sorted, so once that goes away it should resolve that problem.

[mppf]

Also note: --print-module-resolution can show you not only which modules were resolved but what caused them to be resolved. Dead module removal happens after this information is printed.

[jabraham17]

Even removing Sort from all 3 of the places mentioned in this issue are not enough to solve the problem, according to --print-module-resolution. Because Sort is used from Search, and Search is used by modules/internal/DefaultSparse.chpl

[jabraham17]

I think to make this work, we would need to extract out large chunks of functionality from Sort like the comparators and internal functions like chpl_compare into something like modules/internal/SortHelpers.chpl. Then use them from Sort and in other places where needed.

We would also need to do something similar for Search, which also uses the comparators and chpl_compare

[e-kayrakli]

I wonder if there's something we can do with the usage of --fast. The sparse code that needs sorting can be hidden behind --fast. However, in today's if boundsChecking approach, we would still have to start compiling huge amounts of code before dropping them because of the boundsChecking param. Where my mind went is something like:

// In the internal Sparse code:
use if boundsChecking then SlowSparseHelpers else FastSparseHelpers;

where the compiler would completely ignore one of the modules.

[lydia-duncan]

I wonder if there's something we can do with the usage of --fast. The sparse code that needs sorting can be hidden behind --fast.

For some reason this gives me the heebie-jeebies and I'm not sure if that's reasonable. It feels like it blurs the line between optimization and making changes to the generated code that could impact correctness in ways that aren't under the user's control. It would definitely widen the distinction between --fast and --no-checks, but that isn't necessarily a bad thing. And arguably, if a user cares enough about sorting to have explicitly included it in other ways, they won't see a difference in compilation speed with this approach - but would they see a correctness difference? Would there be assumptions they're making about their code that aren't always true? And if so, would those assumptions be valid for them to make, or would they be considered implementation details?

[mppf]

FWIW, I'd sooner head to making the sparse functionality require some opt in (use Sparse or whatever) than to make which modules are compiled depend on --fast.