CompletableFuture dependent ordering

[JSR166 Concurrency mailing list]

Hi everyone,

CompletableFuture maintains a Treiber stack for processing dependents, such as "thenAccept" and "whenComplete" actions. I couldn't find a previous discussion on this design decision. Can you please educate me on why a LIFO stack was preferred over a FIFO queue?

The current behavior seems less intuitive and a lack of awareness can cause subtle surprises. While chaining against the dependent can resolve these gotchas most of the time, there are scenarios where it is more correct to work with the original future instance and to chain dependents on the side. This has come up a few times regarding an asynchronous cache and while I have educated users on this behavior, a workaround within the cache would merely shift the pain by no longer returning the user's supplied future instance. While I can understand the stack might have been preferred as a more elegant implementation, I do not yet see why it would be better by its external behavior.

Thanks and happy new year.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[JSR166 Concurrency mailing list]

I think you can only safely assume the happens-before between the computation of the value consumed and the computation consuming that value.

That is, dependencies are ordered only through explicit chaining. CompletionStage doesn't seem to guarantee any other order.

Alex

On Mon, 4 Jan 2021, 22:32 Benjamin Manes via Concurrency-interest, <[hidden email]> wrote:

Hi everyone,

CompletableFuture maintains a Treiber stack for processing dependents, such as "thenAccept" and "whenComplete" actions. I couldn't find a previous discussion on this design decision. Can you please educate me on why a LIFO stack was preferred over a FIFO queue?

The current behavior seems less intuitive and a lack of awareness can cause subtle surprises. While chaining against the dependent can resolve these gotchas most of the time, there are scenarios where it is more correct to work with the original future instance and to chain dependents on the side. This has come up a few times regarding an asynchronous cache and while I have educated users on this behavior, a workaround within the cache would merely shift the pain by no longer returning the user's supplied future instance. While I can understand the stack might have been preferred as a more elegant implementation, I do not yet see why it would be better by its external behavior.

Thanks and happy new year.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[JSR166 Concurrency mailing list]

It's similar for Scala Futures—happens-before can only be assumed for chained effects, as "callbacks" registered to the same Future can potentially run in parallel.

On Mon, Jan 4, 2021 at 11:31 PM Alex Otenko via Concurrency-interest <[hidden email]> wrote:

I think you can only safely assume the happens-before between the computation of the value consumed and the computation consuming that value.

That is, dependencies are ordered only through explicit chaining. CompletionStage doesn't seem to guarantee any other order.

Alex

On Mon, 4 Jan 2021, 22:32 Benjamin Manes via Concurrency-interest, <[hidden email]> wrote:

Hi everyone,

CompletableFuture maintains a Treiber stack for processing dependents, such as "thenAccept" and "whenComplete" actions. I couldn't find a previous discussion on this design decision. Can you please educate me on why a LIFO stack was preferred over a FIFO queue?

The current behavior seems less intuitive and a lack of awareness can cause subtle surprises. While chaining against the dependent can resolve these gotchas most of the time, there are scenarios where it is more correct to work with the original future instance and to chain dependents on the side. This has come up a few times regarding an asynchronous cache and while I have educated users on this behavior, a workaround within the cache would merely shift the pain by no longer returning the user's supplied future instance. While I can understand the stack might have been preferred as a more elegant implementation, I do not yet see why it would be better by its external behavior.

Thanks and happy new year.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

--

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[JSR166 Concurrency mailing list]

On 1/4/21 5:28 PM, Benjamin Manes via Concurrency-interest wrote:
>
> CompletableFuture maintains a Treiber stack for processing dependents,
> such as "thenAccept" and "whenComplete" actions. I couldn't find a
> previous discussion on this design decision. Can you please educate me
> on why a LIFO stack was preferred over a FIFO queue?

There was some implicit discussion of this when people discovered that
the initial trial versions tended to blow call stacks and retain
unneeded heap pointers in recursive usages. As others have noted,
there's no guarantee about triggering order, so choosing one that tends
to use fewer resources (in the trampoline-like postComplete() method)
seems to be the best option. In some applications, the triggering order
can be surprising, but his would be true no matter what choice was made.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[JSR166 Concurrency mailing list]

Thank you.  I recall some of those early issues so that makes sense. I agree no ordering should be relied upon but lacked a good explanation for the implementation preference.

On Tue, Jan 5, 2021 at 3:59 AM Doug Lea via Concurrency-interest <[hidden email]> wrote:

On 1/4/21 5:28 PM, Benjamin Manes via Concurrency-interest wrote:
>
> CompletableFuture maintains a Treiber stack for processing dependents,
> such as "thenAccept" and "whenComplete" actions. I couldn't find a
> previous discussion on this design decision. Can you please educate me
> on why a LIFO stack was preferred over a FIFO queue?

There was some implicit discussion of this when people discovered that
the initial trial versions tended to blow call stacks and retain
unneeded heap pointers in recursive usages. As others have noted,
there's no guarantee about triggering order, so choosing one that tends
to use fewer resources (in the trampoline-like postComplete() method)
seems to be the best option. In some applications, the triggering order
can be surprising, but his would be true no matter what choice was made.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[JSR166 Concurrency mailing list]

During my work maintaining CompletableFuture, ordering of dependent actions was never a goal.

But efficiency was.

On Tue, Jan 5, 2021 at 4:05 AM Benjamin Manes via Concurrency-interest <[hidden email]> wrote:

Thank you.  I recall some of those early issues so that makes sense. I agree no ordering should be relied upon but lacked a good explanation for the implementation preference.

On Tue, Jan 5, 2021 at 3:59 AM Doug Lea via Concurrency-interest <[hidden email]> wrote:

On 1/4/21 5:28 PM, Benjamin Manes via Concurrency-interest wrote:
>
> CompletableFuture maintains a Treiber stack for processing dependents,
> such as "thenAccept" and "whenComplete" actions. I couldn't find a
> previous discussion on this design decision. Can you please educate me
> on why a LIFO stack was preferred over a FIFO queue?

There was some implicit discussion of this when people discovered that
the initial trial versions tended to blow call stacks and retain
unneeded heap pointers in recursive usages. As others have noted,
there's no guarantee about triggering order, so choosing one that tends
to use fewer resources (in the trampoline-like postComplete() method)
seems to be the best option. In some applications, the triggering order
can be surprising, but his would be true no matter what choice was made.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest