Should/can array element deinitialization be parallelized?

[bradcray]

While looking through module code today, I noticed that an array of elements requiring deinitialization (e.g., an array of records with a deinit() procedure) deinitializes those elements serially rather than in parallel:

chapel/modules/internal/DefaultRectangular.chpl

Lines 1043 to 1048 in 10b7011

	proc dsiDestroyDataHelper(dd, ddiNumIndices) {
	compilerAssert(chpl_isDdata(dd.type));
	for i in 0..ddiNumIndices-1 {
	chpl__autoDestroy(dd[i]);
	}
	}

This issue asks whether this can legally be changed into a forall loop (seems like it) and whether that would ever bite us. @ronawho points out that our current registration/deregistration bottlenecks when a large number of arrays share the same domain could be a case that might hurt (though we have longstanding intentions to address that bottleneck in which case this seems like more of a no-brainer).

For most of our performance benchmarks and critical code, this seems unlikely to have an impact since they're arrays of raw data. But who knows what users will do and we are a parallel language, so deinitializing in parallel seems like a no-brainer.

Related issues:
#6689
#9414
#11333
#10911

[ronawho]

This issue asks whether this can legally be changed into a forall loop (seems like it) and whether that would ever bite us. @ronawho points out that our current registration/deregistration bottlenecks when a large number of arrays share the same domain could be a case that might hurt (though we have longstanding intentions to address that bottleneck in which case this seems like more of a no-brainer).

This bottleneck was addressed in #15895

For most of our performance benchmarks and critical code, this seems unlikely to have an impact since they're arrays of raw data. But who knows what users will do and we are a parallel language, so deinitializing in parallel seems like a no-brainer.

I agree that for the most part this won't be too important for performance, but could still save some time for large enough arrays for types with a non-trivial deinit. I wanted to explore that overhead so I wrote a microbenchmark to look at deinit times for array-of-arrays, array-of-strings, and array-of-records:

use Time, CPtr;
config const nAoA = 5_000_000;
config const innerN = 50;
config const nAoS = nAoA * 50;
config const nAoR = nAoA * 50;

proc timeit(type T, desc: string) {
  var t: Timer;
  {
    t.start();
    var A: T;
    writef("%s create : %.3drs\n", desc, t.elapsed()); t.clear();
  }
  writef("%s destroy: %.3drs\n", desc, t.elapsed()); t.clear();
}

record RAlloc {
  var p: c_ptr(int);
  proc init() { p = c_malloc(int, innerN); }
  proc deinit() { c_free(p); }
}

record RNoop {
  var p: c_ptr(int);
  proc init() { }
  proc deinit() { }
}

timeit([1..nAoA][1..innerN] int, "AoA     ");
timeit([1..nAoS] string,         "AoStr   ");
timeit([1..nAoR] RAlloc,         "AoRalloc");
timeit([1..nAoR] RNoop,          "AoRnoop ");

And the following diff to toggle parallel init/deinit with a config const:

diff --git a/modules/internal/ChapelArray.chpl b/modules/internal/ChapelArray.chpl
index f87b81f331..14d46c74c3 100644
--- a/modules/internal/ChapelArray.chpl
+++ b/modules/internal/ChapelArray.chpl
@@ -3298,10 +3298,8 @@ module ChapelArray {
     _do_destroy_arr(array._unowned, array._instance, deinitElts);
   }

-  proc _deinitElementsIsParallel(type eltType) param {
-    // TODO: Would anything be hurt if this always returned true?
-    // one guess: arrays of arrays where all inner arrays share a domain?
-    return false;
+  proc _deinitElementsIsParallel(type eltType) {
+    return parallelInitDeinit && rootLocaleInitialized;
   }

   proc _deinitElements(array: _array) {
diff --git a/modules/internal/ChapelBase.chpl b/modules/internal/ChapelBase.chpl
index 9fb27d3e89..cdc619f9c9 100644
--- a/modules/internal/ChapelBase.chpl
+++ b/modules/internal/ChapelBase.chpl
@@ -27,6 +27,8 @@ module ChapelBase {
   pragma "locale private"
   var rootLocaleInitialized: bool = false;

+  config const parallelInitDeinit = false;
+
   use ChapelStandard;
   private use ChapelEnv, SysCTypes;

@@ -905,7 +907,7 @@ module ChapelBase {
       param heuristicThresh = 2 * 1024 * 1024;
       const heuristicWantsPar = arrsizeInBytes > heuristicThresh;

-      if heuristicWantsPar {
+      if heuristicWantsPar && parallelInitDeinit {
         initMethod = ArrayInit.parallelInit;
       } else {
         initMethod = ArrayInit.serialInit;

deinit times:

type	serial	parallel
AoA	1.164s	2.660s
AoStr	0.843s	0.098s
AoRalloc	6.317s	0.395s
AoRnoop	0.000s	0.005s

Generally what I see is that you really need the deinit to be free'ing some memory in order for parallel deinit to be worthwhile. And even then parallel deinit still hurts the array-of-array case, though it's not nearly as impacted as it was before #15895.

My preference for now is probably to just leave deinit serial so we're not hurting the AoA case and revisit that after #10911.

[mppf]

The AoA case probably has some nested parallelism. Perhaps that is presenting an issue here?

Could we turn on parallel deinit for all types except for arrays of arrays? I'm worried that if it is not parallel for user records that users will write programs with bugs that will be revealed when we turn it on later.

[ronawho]

We squash nested parallelism so that shouldn't be an issue. I think it's contention/serialization from acquiring the domain's lock.

If there is a way to identify array-of-arrays (and really array-of-records/classes-with-arrays) we could conditionally select parallel init.

I'm not as personally motivated to get this case parallel since it doesn't have major impacts on application performance. Parallel init matters a lot because it affects numa-affinity and init can be really slow in cases, but deinit speed doesn't impact much beyond deinit itself and for most types I can think of deinit will be much faster than init. (e.g. allocating is much slower than freeing)

[bradcray]

The magnitude of difference between these cases (e.g., AofRnoop and AofAofInt) seems concerning and worth investigating more. Or... Elliot, reading between the lines, are you positing that it's due to contention in the shared inner domain's hash table of linked arrays? (I don't think you said it directly, or else I missed it).

If so, since Engin's actively working the issue relating to const domains (I think?), I'm fine waiting a few weeks to see if that lands before doing more here.

For the given results, I feel curious what the behavior of AofAofString or AofAofRAlloc or AofAofRnoop or AofI would be. I.e., how much is the AofA vs. the element type / complexity?

My first thought was: What if we were to parallel deinit arrays whose element types were non-pod (by some definition of pod)? E.g., I'm guessing if we timed parallel dealloc AofAofString or AofAofRAlloc we'd see a benefit? (i.e., that it's less an AofA issue than what the element type is?) But I think we should only do this if Engin doesn't land his const domain change soon in a way that we can leverage that.

[ronawho]

During the perf meeting we decided to hold off on this until the const domain change is in, and then revisit.

[ronawho]

The const domain optimization was merged in #16218, but I'm still seeing a regression for the AoA case (#15215 (comment))

The serial AoA deinit times seem to have gotten much faster since the last measurements, but the parallel case is only marginally better than before.

Running with 9ef62f4 on chapcs:

type	serial	parallel
AoA	0.309s	2.133s
AoStr	0.983s	0.081s
AoRalloc	6.141s	0.585s
AoRnoop	0.000s	0.005s

FYI @bradcray and @e-kayrakli since this came up in the perf meeting.

This makes me suspect we're still modifying the arrays list of domains for the AoA case, but it is certainly faster than before so I'm not sure.

[e-kayrakli]

Can it be because we still lock, decrement counter, unlock; instead of using an atomic int for keeping the count?

We can do even more specialization for cases where a const domain is only used as an array-of-array's outer dimension. There may be some complications that I am not seeing there, though.

(We can use an atomic int pretty easily for const domains, however, domain constness is a dynamic information, so we'd still have to have a lock but just not use it while removing an array from a domain)

[ronawho]

Yeah good point, the locking isn't helping. Just removing the locks but not making the counter atomic (racy) takes parallel deinit down to 0.6 seconds. Still 2x slower than serial, but not bad.

[bradcray]

Is there a good reason that we use a lock rather than an atomic? Is it because in the event that we are tracking membership, we use the lock to guard the hash table?

Still 2x slower than serial

That seems...weird...

[e-kayrakli]

Is there a good reason that we use a lock rather than an atomic? Is it because in the event that we are tracking membership, we use the lock to guard the hash table?

No good reason beyond what you suggest.

I didn't want to tinker too much with the array tracking implementation especially with the thinking that this new definedConst field can be param in the near future, and we may be able to revise that part again. But paramness (even constness) of that field turned out a bit harder than we thought initially.

That being said, it is perplexing that parallel deinit is slower even with regular int.

[bradcray]

No good reason beyond what you suggest.

If the const bit was a param, we could potentially do something really clever like use a lock when we're maintaining the hash table and an atomic counter when we're not. But even with the const field it seems like there's a path forward: What if we stored an atomic, and used it as an atomic counter in the event that we're not using the hash table; but used it as a lock (via testAndSet, having it store 1/0 for full/empty, say) when we are?

[ronawho]

I don't have any concrete timings yet, but deinit for array's of bigints seem quite slow. I'm hoping to revisit this soon.

[ronawho]

During the most recent perf meeting we decided to move forward with this and accept the regression to array-of-arrays. Then longer term we can move to an atomic reference count, at least when we don't have to track domains. This is tracked in https://github.com/Cray/chapel-private/issues/1378. We also discussed just bumping the reference count once instead of once per element. I opened https://github.com/Cray/chapel-private/issues/4362 for that.

In the short term the plan is:

• Commit a perf test
• Switch to always using parallel deinit, accepting the hit for AoA

And eventually or as there's demand for it optimize the AoA case.