Suspend-friendly collections

Thanks to the advice of several tireless members here, I’m now converting a codebase to be mostly suspending. For the most part, this has been rather straightforward.

However, I have come across two issues where I haven’t been able to easily convert the code to be suspending.

The first issue is where the equals method needs to call a suspending function. I can’t move the functionality to a different function as instances of this specific class is used as a key in a HashMap. I obviously don’t want to add a runBlocking in the equals method, and I can’t see an easy solution to this.

The other issue is where the Comparator class where the comparison function is not suspending. This means that if the comparison function needs to call a suspending function, there is no way to use the built-in sorting function.

What is the correct way to deal with this?

What’s the use case for equals to be suspending?
Usually classes for which equality makes sense are classes which just “store data” in memory and nothing else. (like references to external resources or such where suspending functions are very useful in dealing with).

Usually, yes. But in this case the issue is more complicated. A lot of background can be found in this post: Coroutines and deadlocks

A very short summary is that the project is a programming language interpreter where most values are lazily evaluated. Resolving the actual content of a value can be done in parallel (which is why everything is suspending). These values can be used as keys in a HashMap.

The use case for the sorting is similar. The language provides a function to sort elements, but since the elements are lazily evaluated, they need to call into the underlying evaluation function which is suspending.

If you need to run some lazy code to compute equals then I imagine you need to run that just to do anything.
So you could run that just after construction and make equals not lazy.

It’s not that simple. I wouldn’t mind explaining, but I’ll only do it if you’re really interesting in the answer, since I’d need to explain a lot of details.

I ended up solving the sorting problem by implementing a simple quicksort, which solves the problem for now. However, quicksort is less efficient than the built-in sort function so it would be nice to be able to use it.

Highlighting a specific example might help. Perhaps you could explain how using the lazy value as a key where insertion requires evaluation:

hashMap[lazyValue] = someValue

could be any different than evaluating and then using the real value as the key.

val realValue = lazyValue.awaitRealValue()
hashMap[realValue] = someValue

The insertion cannot possibly complete in either case until the real value is known.

Is it a different use case that’s really troubling you?

Or is the issue simply that making such a change to existing code would be an expensive undertaking?

The problem is that lazy values does not have a different type compared to computed values (“collapsed” in the terminology of my application). If a value is not lazy, its collapse method simply returns itself.

Now, even if this was possible, it would still not be ideal, since for sorting (i.e. the implementation of Comparable) all the values usually don’t need to be computed. For example, take two arrays, each a million elements long, but that differ in their first element. To order these, only the first element needs to be evaluated. In other words, it’s impossible to know how much to calculate before you actually perform a comparison.

For cases where you are checking equality like HashMap keys, waiting for the values to collapse still feels like the right approach in my mind.

I don’t have any suggestions better than a custom algorithm for the sorting case, but consider testing the performance of waiting for the values to collapse completely before you discount that approach for sorting. If the values aren’t used until they collapse, then maybe they don’t need to be sorted until they collapse.

Keep in mind, the sorting algorithm may not have such an impact compared to waiting for the values to collapse, even only partially, enough to do the comparison.