Current State
The dispatcher queue is implemented as two linked lists, one for IO tasks and one for compute tasks.
These lists are sorted by composition Ids which are attached to each function that gets pushed into the queue.
We use linked lists, because we need to be able to skip work and take it from the middle of a queue.
Taking from the middle of a queue can happen, for example when we want to prioritize work because of data locality or need to skip work because the engine type does not match the requested one.
This is a bit inefficient, as we are maintaining a two lists with O(n) insertion time, if we are not lucky and can't insert in the front or back.
Options to Improve
Currently we think there are two possible ways to improve this design.
The first one is switching the lists for Map data structures.
This would allow us to keep each function separately in a single level data structure.
It would reduce insertion and removal time to O(log n) and remove the need to manually keep track of the order in the list.
The issue is, that we currently only need the composition Id for sorting, which are not unique.
In a Map keys usually need to be unique. (Specifically for the standard library one)
This could be solved by adding a second key, like a per invocation key within each invocation.
The upside of this approach is, that the number of objects we need to manage stays the same, the downside is that we also need to add code to create those Ids and keep track of them throughout the lifetime of the invocation.
The second option would be a two level queue.
The top level has a single entry for each composition, and then each entry holds a second queue specific to the composition.
The upside of this is, that it is more clearly structured and we may even get rid of the composition keys, since we could give the dispatcher a way to directly enqueue on the per composition queue by giving it a reference.
The downside is, that this would make taking things from the queue and iterating over the queue more complicated and we may need to add more bookkeeping to the top level to keep track of total number of tasks in the queue etc.
Current State
The dispatcher queue is implemented as two linked lists, one for IO tasks and one for compute tasks.
These lists are sorted by composition Ids which are attached to each function that gets pushed into the queue.
We use linked lists, because we need to be able to skip work and take it from the middle of a queue.
Taking from the middle of a queue can happen, for example when we want to prioritize work because of data locality or need to skip work because the engine type does not match the requested one.
This is a bit inefficient, as we are maintaining a two lists with O(n) insertion time, if we are not lucky and can't insert in the front or back.
Options to Improve
Currently we think there are two possible ways to improve this design.
The first one is switching the lists for Map data structures.
This would allow us to keep each function separately in a single level data structure.
It would reduce insertion and removal time to O(log n) and remove the need to manually keep track of the order in the list.
The issue is, that we currently only need the composition Id for sorting, which are not unique.
In a Map keys usually need to be unique. (Specifically for the standard library one)
This could be solved by adding a second key, like a per invocation key within each invocation.
The upside of this approach is, that the number of objects we need to manage stays the same, the downside is that we also need to add code to create those Ids and keep track of them throughout the lifetime of the invocation.
The second option would be a two level queue.
The top level has a single entry for each composition, and then each entry holds a second queue specific to the composition.
The upside of this is, that it is more clearly structured and we may even get rid of the composition keys, since we could give the dispatcher a way to directly enqueue on the per composition queue by giving it a reference.
The downside is, that this would make taking things from the queue and iterating over the queue more complicated and we may need to add more bookkeeping to the top level to keep track of total number of tasks in the queue etc.