No way to represent a set of tasks

[canndrew]

I want to implement a future which can be cloned so that multiple tasks can be blocked waiting for the same external event. This doesn't seem to be possible to implement. Task doesn't implement Hash or Eq so I can't keep the set of pending tasks in a HashSet or even a Vec because there's no way to de-duplicate the tasks. If someone keeps poll()ing my future, or keeps cloning new ones, the Vec would grow indefinitely.

Could we give Task an implementation of Hash or Ord + Eq or something? Alternatively, could we add a TaskSet type for this use-case?

[tailhook]

Does Future::shared solve your task?

[canndrew]

No, but looking at how it's implemented did. So thanks for that.

I might leave this open though since any of my suggestions would have made this easier to solve.

[carllerche]

I’m not sure how providing a task set would help. I can’t really comment more without knowing what api you are trying to provide, but my initial impression is that using something like a TaskSet would result in a buggy impl.

[canndrew]

@carllerche It might result in some spurious wakeups if an object that needs to be notified keeps moving between different tasks. I think it would still be more efficient (in the general case) than the allocation and duplication involved in keeping tasks in a hash map and giving every object it's own key (aka what Future::shared does). And I don't see how it could actually be buggy.

[carllerche]

@CAndrew what happens if there are two clones being used on the same task and one drops? Would it not deregister all handles on that same task?

[alexcrichton]

@canndrew for the original question (something like hash/eq/ord for Task) I don't think we'll be able to do that as we don't really have an underlying id and it's often quite difficult to equate two handles (as they've got trait objects and such behind the hood). In that sense I'd recommend tracking ids manually in what you're working on and use that for deduplication of task handles. Would that work for you?

[carllerche]

I'm going to close this as I don't think that there is anything to do. Please let me know if I am wrong.

[AljoschaMeyer]

Came here for exactly the same question (hash, ord, or at least eq for tasks). Literally the first thing I saw after clicking on the "src" button for the Task struct was pub struct Task {id: usize, ...}. Which does not look like "[...] we don't really have an underlying id" 😸.

Tasks should be opaque, but I don't see how a concrete implementation could look like that has no concept of equality. Even though the current implementation doesn't make it explicit (ie does not implement Eq), it still has to have some concept of checking whether two different tasks correspond to the same thing, right? And I can't imagine any implementation that truly does not rely on such a concept. So if every implementation needs this anyways, why not make it part of the API?

Since you have spent a lot of time on the whole codebase, there's probably something I'm missing. So please don't read this as "I want Feature X!", but rather as "Someone is curious about the design of the library". I'd really appreciate if you could share some background on this.

[carllerche]

To clarify, the id field of Task is going to be removed in the (near hopefully) future.

[carllerche]

@AljoschaMeyer If there is a compelling reason to add Eq + Hash then we can consider it. As I mentioned above, my hunch is anytime you want to store a Task in a set, you are heading towards writing something buggy.

[AljoschaMeyer]

I stumbled upon this while writing multi-producer sink. By taking ownership of a sink, you get a handle which you can clone, using an RC and a RefCell for interior mutability. The start_send and poll_complete implementations check a queue of tasks. If the queue is empty or the first entry matches the current task, you can send/poll the underlying sink and then notify the next task. Else, enqueue the task and return NotReady.

This can easily be done by assigning my own ids to the handle, but comparing Task equality is more elegant.

And hopefully this is not heading towards buggyness, since I don't see how one could implement sink multiplexing without such an abstraction.

Edit: The above description of the multiplexing assumes that poll is not called more than once per NotReady return, which is not true. But by using a set instead of a queue, the multiplexing works.

[carllerche]

@AljoschaMeyer

The design that you are describing makes me think that you would hit the bug that I referenced above.

If, for each SinkHandle, you store a task in a set, when that SinkHandle is dropped, you need to remove its associated task from the set. If you do not do this, you will leak memory.

Now, if you have two SinkHandle instances, and both are used on the same task. Then one drops, it will remove its task from the set. However, the other instance has the same associated task and that task is now removed from the task set. In this case, the second SinkHandle will never get notified and is now dead locked.

The solution to this problem is that you store an entry in your set for each SinkHandle instance and not each Task. To do this, you want to generate IDs.

[carllerche]

I attempted to clarify the problem here: #689

[AljoschaMeyer]

Thank you, that clarified a lot!

For other stumbling upon this while looking for stream/sink (de)multiplexing, here are my attempts: multi-producer-sink and multi-consumer-stream.