| You are right. But the purpose of that code was just to indicate the rough performance that was possible using much less sophisticated parts, compared to a lock-free linked list with sorting built in. But, thinking about it further it does seem like solving the 'stale max value' problem would be non-trivial. If I was implementing this for a real system I would side-step that problem by redefining the requirements (which could be seen as cheating). We can agree that the Out channel is full of stale max values and isn't really well sorted. But it will only have len(out) many stale values, and the values which replace them as Out drains are reasonably well ordered. At any time we have at most len(out) out of order tasks. I am thinking of the queue in two different scenarios. 1: Workers are keeping up with new tasks - this queue provides FIFOish semantics and no effective priority ordering. But it doesn't matter, workers are keeping up prio is irrelevant. 2: Workers are falling behind. The red-black tree fills up as Out is filled to max capacity. As Out drains new tasks are in priority order (roughly). Because of the vagueness of the guarantees given above you'd need to think hard about whether that provides enough. But I would strongly prefer something along these lines (i.e. avoid lock-free linked list with built in sorting) if I thought I could live with it. What do you think? |