A good way to process an array?

[alexshpilkin]

The full binary tree example in the README is good and perhaps representative of some places where one’d want to use automatic parallelization. But there’s also another simple case of a very different flavour: arrays.

Suppose there’s a large linear array of stuff we need to go through in some semblance of an order (a map, a reduce with an associative but not necessarily commutative operation, or something in that vein). Enqueueing every processing job from 0 to N–1 and then gathering up all the results from N–1 to 0 is likely not a good idea for a multitude of reasons (even for a map), one among them being that all the work for enqueueing the items is stuck on the initial thread.

Pretending the array is actually a tree (with the first level dividing the items into [0, N/2) and [N/2, N), and so on down) is probably better, but once the parallelism runs out it has a fairly cache-unfriendly access pattern compared to the linear one we’d have had if we hadn’t went for parallel processing. It sounds like what we’d actually need is to lay out the array non-linearly from the start. I recall a paper (arXiv, ACM DL) considered array layouts for in-RAM binary search and measured things like a BFS layout (like you’d use for implementing a binary heap; their winner) and a Van Emde Boas one (theoretical cache-oblivious winner, but in practice a loser for RAM datasets because of the indexing overhead). Their problem is not quite like ours, though.

Thoughts? Experiences?

(I really hope I’m overcomplicating things and there’s a simple solution I overlooked...)

[judofyr]

I agree that "pretending the array is an tree" should be possible, but that will also lead log(n) additional stack space which doesn't seem so nice.

I had envisioned something like this:

1. On the stack, we place a task which stores (1) the array and (2) from: usize, to: usize. We set from=0, to=N on the initial one.
2. We start iterating over the array and then we keep incrementing from so that it always represents the "not-yet-executed" parts of the array.
3. When the heartbeat kicks we might discover this task. We can then split it: We pick a k update the original task to have to=k (so that it stops) and then we create a new task with from=k, to=original.to.

This kinda creates that tree "on-demand".

However, it's not entire clear to me how the ownership of the data ought to be, nor how we pick a good k (or if that matters at all?)

[alexshpilkin]

I wanted to complain that the solution you describe is unimplementable on top of the standard fork/join API, but then I realized that in spite of that it might in fact be implementable on top of your fork/try-join API, where the try-join call does not take it upon itself to complete a task synchronously if it hasn’t been taken up by another thread. That is an advantage I did not expect.

For example, here’s a version of your idea with k = (from + to) / 2, ignoring edge cases:

1. Have from and to passed to us (0 and N respectively in the root task) and introduce k = (from + to) / 2.
2. Fork a copy of ourselves passing it k and to.
3. Process the first two elements, from and from + 1, and advance from by 2.
4. Try to join the task from step 2.
5. If it has been picked up, do a synchronous recursive call passing it from and k, then wait for the task to complete and return.
6. Otherwise, we have withdrawn the task. Advance k by 1 and loop around to step 2.

I think this might be what I wanted. (Now I’ll just figure out why my C port doesn’t scale and then I’ll see if this actually works...)

[judofyr]

That sounds possible, yes. Excited to hear how this pans out!