Hacker News Reader

Comment by mabbo | Hacker News Reader

> each sorting step is fast, bubbling down to N identical and independent questions asked in parallel at every clock cycle.

> The first empty cell could take the new data since it’s empty, but since 4 just got kicked out from the cell above, this empty cell gets the 4 instead

These are incompatible. The result in cell 3 is dependent on the result of cell 2 (and so on up the chain of cells).

Therefore, the steps have to run in order, making this O(n) just for adding one item to the set.

The end goal might still be possible, but I don't see how this can work.

View on HN

I initially thought this as well, but reading the code showed me it's actually O(1) to add each item to the set.

Each cell computes in parallel (new_data < cell_data) & (cell_state == OCCUPIED). If this is true, then the cell will be pushed down, either be the new data or by the data from the cell above. Each cell can also grab this value from the cell above. If the cell above's value is true, then the cell grabs the value from the cell above. If the value in the cell above is false, then the cell grabs the data being inserted. This is O(1) because there's no cascading value shift. I personally found this pretty clever, and I'm looking forward to implementing some of these bounded size hardware sorts on GPU.

> Each cell can also grab this value from the cell above

Therein lies the problem I see. Grabbing this value from the above cell implies that this value has already been calculated- but it hasn't, as these cells run in parallel. The results of a cell in a single round of calculations is not accessible to the other cells during the same round.

In short- how does a cell know whether its new value is the value being inserted or the value being pushed down without knowing the result of the cell above it?

And having asked that, I can actually think of one answer: it can calculate whether it's neighbor will be pushing or not independently. So each cell is really doing the calculation of "given these two numbers (my cell's value and the above cell's), where does this new number fit in sorted order with them- before, between, or after".

arguably it's O(N^2) in spacetime, because it's O(N) steps on O(N) hardware (N parallel units).

You can imagine different hardware architectures taking O(1) steps on O(N^2) parallel units or O(N^2) steps on O(1) unit(s), or anything in between.

Reply on news.ycombinator.com