[Feature Request]: add a method to list that pops but only if the list isn't empty?

[lydia-duncan]

Summary of Feature

Description:
This request came about as a result of a conversation with Oliver on gitter. Basically, popBack() will halt the program today if it is called on an empty list (or segfault if compiled without bounds checking). But in a parallel context, it's difficult to ensure that a list is still full before calling popBack(), as there aren't user-facing ways to lock the list and then call isEmpty(), size, or popBack() (both because we don't provide a public locking mechanism for list and because these operations all lock internally themselves).

Oliver mentioned that it would be helpful for an error to be thrown in this case, but we don't typically throw errors for "out of bounds" issues, due to wanting to be consistent with other types and not wanting to require array accesses be surrounded by try statements or expressions. We could potentially provide an alternative method that explicitly does throw an error in that case.

A suggested solution is adding a method along the lines of a popIfNotEmpty() that basically ensures the entirety of the operation (checking if the list is empty and returning the result of a pop if it is not) happens within a protected segment of code. This will avoid causing the program to halt, though I think there's an open question about how it should behave if the list is empty (e.g. should it throw with a deferred unlock call? Or should it return a sentinel value?). And of course, there may be cases where it fails to pop something but from the user's perspective the list is no longer empty (if the pop call happened to enter the locking segment before whatever operation was adding values to the list).

Is this issue currently blocking your progress?
No, Oliver coded up the following for himself:

proc popIfNotEmpty(ref l) {
  l._enter();
  var cluster = new shared Cluster(); // "holder" variable 
  if l._size == 0 then writeln("list is empty");
  else cluster = l._popAtIndex(l._size-1);
  l._leave();
  return cluster;
}

Code Sample

Since the problem is basically a race condition, it's difficult to provide code that reliably would encounter the halt/segfault. But basically what you'd want is to be able to do:

use List;

var myList = ... // create the list
... // spawn some other thread to populate it

var res = myList.popIfNotEmpty();
... // Do something with res

// or

try  {
  var res = myList.popIfNotEmpty();
  ... // do something with res here?  Or after a catch block that repeated the call?
}

[lydia-duncan]

This wouldn't be too hard to do, the hardest part imo is agreeing on what the design should be

[alvaradoo]

As an incentive for implementing this feature, I’d like to share my use case. While working with a Chapel list as a naive queue, I encountered issues with popping from an empty list. Specifically, I was processing the list within a coforall loop, where items were popped for processing, and an inner function—process—was also modifying the list by adding elements to its front. Consequently, the list size could not be known precisely at each iteration, and the coforall loop occasionally attempted to pop from an empty list. Here’s a simplified sketch of the issue:

// workQueue and other variables are defined/initialized earlier in the code
var iteration: int = 0;
while workQueue.size > 0 {
  coforall i in 0..<here.maxTaskPar with (ref workQueue) {
    var cluster = popIfNotEmpty(workQueue);
    if cluster.id != -1 && !cluster.isSingleton then process(cluster);
  }
  iteration += 1;
}

If I used the standard popBack method, this would cause the program to halt upon trying to pop from an empty list. Now, as I write this, I realize that adjusting the number of tasks spawned in the coforall loop based on the workQueue size could eliminate the need for popIfNotEmpty(workQueue) in this instance.

However, imagine a scenario where the number of parallel tasks spawned by the coforall loop is kept static (e.g., NOT set to here.maxTaskPar) to maintain some level of consistency. In such a case, a method like popIfNotEmpty() would indeed be necessary to avoid errors when the list is empty.

To clarify, this is admittedly a simplistic queue implementation, as inserting at the beginning of a Chapel list is O(n). I am currently developing a more efficient queue implementation that doesn’t rely on Chapel lists (though it borrows some internals), so I am no longer using this particular code. However, I think it would be a valuable improvement if Chapel lists did not cause a program to halt when attempting to pop from an empty list inadvertently.