HN user

Saltor

23 karma
Posts0
Comments5
View on HN
No posts found.
[GET] "/api/user/Saltor/stories?hitsPerPage=30&page=0": 500 Failed to fetch user stories
Thread-Safe Lock Free Priority Queues in Golang 10 years ago

I don't think that the implementation here performs correctly...

For example, the following:

    q := NewPrioq()
    q.In <- timestamp(20)
    q.In <- timestamp(10)
    q.In <- timestamp(30)
    o := <-q.Out
    fmt.Println("Read", o)
Prints "Read 20" rather than "Read 30".

Furthermore, this input:

    q := NewPrioq()
    for i := 0; i < 202; i++ {
        q.In <- timestamp(i)
    }
    o := <-q.Out
    fmt.Println("Read", o)
will result in a deadlock.

As far as I can tell, this code behaves like a FIFO queue with capacity 201. Each iteration of the loop in Prioq.run() will read once from the input channel, insert into the empty tree, remove the "max" element from the single item tree, and then insert into the output channel.

Reading from the input channel and writing to the output channel are performed in lockstep rather than as needed. A correct implementation of this pattern would need to use a select block and to avoid the deadlock and would need a way for writes to the output channel to be signaled as needed so to avoid the stale max value problem.

0ThreadHN
Ubuntu on Windows 10 years ago

I'm hopeful that this will lead towards greater unification and innovation, but I can see why people are more likely to bring up "Embrace, Extend, Extinguish" when Microsoft does something compared to when other companies do. The difference is that Microsoft is the one who internally coined the term and used it to describe their strategies. It was a conscious and explicitly stated strategy rather than an unspoken side benefit.

You could certainly say that none of that matters and what we should care about is the actual actions that each company makes, but I can definitely see how people would read more intent into things like this when Microsoft does it compared to other companies.

0ThreadHN