New Issue: CG: Challenges in converting sort() to CG

Notifications Issues
1

17005, “vasslitvinov”, “CG: Challenges in converting sort() to CG”, “2021-01-26T02:43:55Z”

main issue: #8629     mixed CG+UG? #16985

Here are a couple of challenges that arise in order to convert the sort() function to constrained-generic style. Currently this function is:

proc sort(Data: [?Dom] ?eltType, comparator:?rec=defaultComparator) {
  ......

  if radixSortOk(Data, comparator) {
    MSBRadixSort.msbRadixSort(Data, comparator=comparator);
  } else {
    QuickSort.quickSort(Data, comparator=comparator);
  }
}

Consider switching the Data formal to be constrained-generic. For example, let it have the interface type ArrayIFC. To focus on Data, this issue drops the comparator argument throughout. So:

interface ArrayIFC(Self) {
  ... required functions ...
}

proc sort(Data: ?T) where T implements ArrayIFC {
  if radixSortOk(Data) {
    MSBRadixSort.msbRadixSort(Data);
  } else {
    QuickSort.quickSort(Data);
  }
}

radixSortOk()

Here is a simplified CG-version of radixSortOk():

proc radixSortOk(Data: ArrayIFC) param {
  if !Data.domain.stridable {
    return true;
  }
  return false;
}

We cannot resolve this function “early” i.e. without knowing the particular type of Data. Because the stridability of Data.domain needs to be known at compilation time and it depends on the array type.

What do we do instead?

msbRadixSortParamLastStartBit()

Here is a simplified CG-version of msbRadixSortParamLastStartBit(), along with its helper:

proc msbRadixSortParamLastStartBit(Data: ArrayIFC) param {
  if fixedWidth(Data.eltType) > 0
    return fixedWidth(Data.eltType) - RADIX_BITS;

  return -1;
}

proc fixedWidth(type eltTy) param {
  if (isUintType(eltTy) || isIntType(eltTy) ||
      isRealType(eltTy) || isImagType(eltTy)) then
    return numBits(eltTy);

  if (isHomogeneousTuple(eltTy)) {
    var tmp:eltTy;
    return tmp.size * numBits(tmp(0).type);
  }

  return -1;
}

The library author wrote fixedWidth() to work on any argument type. However, it is an UG function, which we invoke on the type eltType coming from the interface ArrayIFC. Since the concrete eltType type varies between implementations of the interface, we cannot resolve fixedWidth() “early”. Similarly to the case of passing a CG argument to an UG function, this prevents early resolution of msbRadixSortParamLastStartBit().

How do we handle this?