Queue-like loop / data structure

[srush]

There are a bunch of classical NLP approaches that are generalizations of queue-style algorithms, think roughly like Dijkstra. I have been thinking recently a bit about what these might look like in Dex, but I'm a bit stumped. Naively you could probably have a while loop over elements in the queue, but then you would not have parallelism over expansion. Alternatively you could pop a batch of elements at a time, but that feels a bit arbitrary.

Curious if you guys have thoughts. I think the simplest model is that you pop a node, expand neighbors, enqueue them and repeat.

[apaszke]

Yeah, growable stacks/queues are not easy to use today and would require a bunch of low level hacks. And we're not happy about it! We've been briefly brainstorming some solutions, but we don't have anything we'd happily implement right now.

But in any case, algorithms such as Dijkstra are inherently sequential in their definition, so I don't think there's any parallelism to be extracted? But I'd be curious to hear more if you have ideas for improving that.

[srush]

Yeah, it's a good question. Let me think through more precisely what I'm after.