fmstephe

Another concern (big or little depending on your circumstances) many common things stored in maps, strings, primitives, incur an allocation on conversion to interface{}.

Coupled with a fairly inefficient GC it means I would need to think twice before using this.

Unfortunately this miscompilation probably is within spec, given that the atomic package has no documented ordering.

But it's coming.

https://github.com/golang/go/issues/5045

There is no official ordering provided by the atomic package. An atomic package isn't very useful without ordering semantics. And ordering actually _is_ provided, it's just not part of the documentation.

The background is that the Go team were initially reluctant to even make the atomic package public. It's mostly there to support the runtime and the sync package which needs fiddly low level concurrency things. But, it exists and it is public. Some people on the Go team regret this (I believe).

Giving clear and precise semantics to the atomic package was delayed because, it's a lot of difficult work and you only get to do it once. There was discussion around trying to find a clear and simple semantics.

In the mean time the atomic package actually had ordering, because you would have a hard time writing runtime or the sync package without this. Also the race detector assumes some kind of ordering for operations in the atomic package. It was confirmed by Dmitry Vyukov that the race detector assumed C/C++11 acquire/release semantics for atomic operations.

After some discussion it was decided that C/C++11 semantics should be adopted. But the documentation has not been updated to reflect this. Updating the documentation doesn't appear to planned right now. Which is a shame.

https://github.com/golang/go/issues/5045

Above I have sort of put words into the mouths of the Go team (or some members of it). It's not my intention and bad mouth anyone, and I think everyone was making decisions for good reasons. Whether I agree or not :)

With respect to adding ordering arguments, Go most likely won't get those for a very long time.

The best article I know if

http://tofspot.blogspot.com/2013/10/the-great-ptolemaic-smac...

As mentioned by another user below. The story in that link is really a great read. However, I'm unable to tell you how accurate or complete that account is.

mappu, do you have a need for 64-bit aligned data?

I would be interested if you did. I have a repo that provides a set of packages for doing things like that. If that is a real need I would be interested to add it to the library.

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?

If you want to push the performance of that approach (a single goroutine prioritising your messages for you a queue in and a queue out) I have built a set of lock-free queues on a ringbuffer.

https://github.com/fmstephe/flib/tree/master/queues/spscq

Those are only single producer single consumer (spsc) so not flexible enough for your needs right now, but I am working on expanding into multiproducer/multiconsumer variants which could be a good fit.

The single producer/consumer queues get up to 100 million messages per second (on microbenchmarks) and I expect the multi variants to be above 10-20 million per second.

I also have a handbuilt redblack tree which does around 10 million inserts/pops per second

https://github.com/fmstephe/matching_engine/tree/master/matc...

Although that is very specialised for another purpose, I would be happy to try stripping it down if you wanted that. But, start with the LLRB in that gist.

It is interesting to me how popular linked lists are for non-blocking data structures. They are often slow and always so hard to reason about and implement safely.

Here's a very quick alternative

    push all messages into a channel IN.
    A goroutine reads from IN inserts into a sorted TREE.
    same goroutine reads max from TREE and pushes to channel OUT.
    workers read from OUT.

This is a pretty mediocre implementation. But I post it because the numbers posted in this article were so low. I think we can do better with something far less sophisticated.

https://gist.github.com/fmstephe/4fdc930ff180be3e92c693ad5a2...

I timed that to write 600,000 messages concurrently and read 600,000 sequentially in 1.5 seconds. Not a perfect measurement but I'm on a train and I'm about to get to my stop.

If we need really high performance we can start substituting faster, and simpler, queues than Go's channels and we can very likely improve that red-black tree that is doing the sorting. Each of these components is simpler, more likely correct, and from what I can see substantially faster than the sophisticated lock-free queue described in the article.

I don't want to come across as snarky. But I am surprised by the popularity of linked-list based lock-free data structures like this.

EDIT: So the tone of my post came across nastier than I really intend. I quite enjoyed the article, I'd be interested how far the performance can be improved.

If, like me, you wondered how it maintains cache coherence with that many core. It uses something called 'directory based coherence'.

https://en.wikipedia.org/wiki/Cache_coherence

From what I have read it appears that the cores we typically run today, use snooping, constantly listening for interesting changes to other core's caches. Clearly this doesn't scale, you don't want to listen to cache traffic of 200,000 cores. So they have a centralised 'directory' to manage cache coherency. The directory system has higher latency, presumably every load/store has to send a message to the potentially distant cache directory manager.

Does anyone really know this stuff, I would be interested to hear a more knowledgeable take on it :)

Golang

Great, thanks for the clarification.

Can you expand on the last sentence. I'm not sure I understand what you were trying to express. (not trolling, genuinely curious)

That is the case. I personally love Crouton for development on a pretty old chromebook.

link to essay? I can't pick it from that description.

Although it isn't equivalent to wireshark, linux's perf command (no doubt osx/win/bsd have their own) is close enough and very easy to use.

It exposes a very large number of CPU counters, including cache misses etc.

Not quite as thorough as simulating. But probably more useful in practice.

That was genuinely charming. I really enjoyed it. It is good to be reminded how good things are now.

Russ Cox gave a really good answer to this question. I have to paraphrase because I can't find the original comment.

It was done for implementation speed. They had a compiler backend which they, the early Go team, were all familiar with. It was small so they could quickly change it to suit Go, rather than the other way around.

Russ Cox expressed the sentiment that if they had tried to use LLVM there would have been a lot of up front work that would have taken a long time and the Go project probably would have fizzled out. Using the plan 9 tool chain they were up and running very quickly allowing them to focus on the most important work, designing the language itself.

(Probably shouldn't attribute this to Russ Cox, I've probably read into his (rather briefer than what I wrote above) comments)

In my opinion this was the right choice. If LLVM turns out to be the best backend for Go it's easy to use it later. However, the language itself is largely fixed after 1.0. Better to focus on the language than the compiler backend which can be swapped out later.

I enjoyed this article, but one thing jumped out at me. He said that he hadn't redone the analysis behind the blog post he cited. Even though the data and analysis was made explicitly available.

This seems like it would be a good thing to do habitually. I appreciate that data if often not available for checking. But in this case it feels like it would have really strengthened the process.

Can anyone add practical experience with the API spec tools. This is a new name for me.

I had a look at the websites for each of the three tools the article specifically mentions

    http://raml.org/
    http://swagger.io/
    https://apiblueprint.org/

I get the impression that these are code generating tools built from a specification file.

I have real world experience with two tools which fit that rough description. SOAP and google app-engine end-points.

I would unambiguously describe both as awful. Really horrible experiences with both. They tie your systems to large, and difficult to understand tool sets. SOAP wasn't obviously buggy, but app engine endpoints are unpredictable and the generated code produces some serious awkwardness.

I don't want to slap a label on these tools and dismiss them off-hand.

Anyone used them 'for the win'?

Thanks Nick.

Thanks Tony, I'll look into that link.

I am looking at options for building custom electric guitars. This is just for a hobby, so no mass production at the end.

Can anyone with experience in doing this tell me if it is feasible to get CNCed products made as one offs?

It seems likely that this step is part of a longer and highly involved process resulting in mass production, which wouldn't be appropriate for me.

Can anyone offer experience/tips for getting this kind of CNC work done as a one off. I live in Germany.

Thanks in advance.

I would love to get a report from someone with a lot of Erlang experience.

Erlang is a great example of an industry oriented dynamically typed programming language.

But... they recently, maybe more 5 years ago now, went to a lot of trouble to integrate a really nice static type system into it. They also had a type analyser, dialyser, for a long time before that.

The impression I had was that some significant number of people experienced some dynamic typing pain and a lot of effort was put into reducing this by strengthening the type system.

I am just a part time Erlang hacker, so I will keep out of this debate. But I would love to hear from anyone who experienced this in a professional development environment.

"I'm relieved to hear that at least it doesn't pollute beyond module boundaries."

This isn't true, it is easy to come up with an example where lack of safety spreads past module boundaries.

    impl Vec<T> {
        pub fn evil(&mut self, len: i32, cap: i32) {
            self.len = len;
            self.cap = cap;
        }
    }

If we want to know our program is broken now, we need to look across all of the source code to see if evil is called in breaking ways.

The point was that Rust provides abstraction facilities which allow us to contain these invariants. If we are careful.

This is good advice. I am totally confused by the Rust vs Go debate. They occupy such different spaces.

Can you clarify those statements. I have seen that segment and would be interested to know about misinformation in it.

Or are you talking about a different segment?

Go supports this, I think. I am not quite sure what is meant by object relative layout.

In Go:

A struct is laid out as you declared it, with possible compiler added padding. A struct value field (not a pointer) in another struct is laid out contiguously in memory as you declared it. An array (or a slice) of values (no pointers) are laid out contiguously in memory.

You can happily take pointers into any of these larger structures. If you had a data structure where you really wanted to control the layout, you can create a slab allocator as a big array of values, and take pointers into that array to allocate pieces of your data structure. I did this exact thing to write a red-black tree in Go.

It is true that Go's GC isn't compacting. But it will be in the future (or it is planned to be).

But, if I hadn't programmed in Go I would have agreed with your comment above.

(A great thing about HN is getting to talk with the authors directly)

I didn't recognise that you were talking chiefly about javascript. It is true that my example doesn't apply here.

Ok, then I would make one comment (and edit my first comment).

I would avoid the discussion of simultaneity at the start

    'Events in parentheses happen “simultaneously”.
     In practice they happen at slightly different times,     
     but separated by only a couple of nanoseconds, so
     people understand them to be simultaneous. Events (c1c2) 
     are called glitches and sometimes considered a problem
     because one would expect only c2 to happen.'

Because you are working in a single threaded simultaneous events just don't exist. The glitches you describe occur completely independently of timing, nanoseconds or otherwise. Drawing up diagrams where events occur at the same time is adding complexity which doesn't exist.

    errors            ---e1-------e2---------------
    userActions       -u1------u2------------u3----
    analyticsMessages ---e1u1--(e1u2 e2u2)---e2u3--



    errors            ---e1----e2------------------
    userActions       -u1----------u2--------u3----
    analyticsMessages ---e1u1--(e2u1 e2u2)---e2u3--

Both of these scenarios produce glitches (as I understand it). So we don't need any notion of 'simultaneous events' to create them.

Anyway - that is nitpicking. I enjoyed your article. I agree that the scenario described at top does not apply in javascript.

I too strongly dislike callbacks :)

EDIT: The article is about javascript. Everything below does not apply to javascript. You need more than one thread, at least, for any of these problems.

I strongly suspect that combining async streams will prove to be a problem in practice, whether we resolve glitches or not. This article requires quite subtle reasoning about async systems. In my experience this type of reasoning is rarely done effectively on real life projects.

I am not criticising Rx, I am interested in Rx. But I am always concerned when a project/community starts producing articles on very subtle topics and claims 'x isn't a problem if you just understand it properly'. Here properly probably means deeply, and deep knowledge in software is scarce. There are too many things to know, to know many things deeply.

Let me look at one example (and please comment if I'm really not understanding something).

So we consume, asynchronously, two streams. Because they are asynchronous we might hit some point where it's a bit uncertain where two outputs are related.

    errors            ---e1----e2------------------
    userActions       -u1------u2------------u3----
    analyticsMessages ---e1u1--(e1u2 e2u2)---e2u3--

That's a good example, and we fixed that problem with 'errors.withLatestFrom(...'. But, since we are asynchronous don't we also have to worry about this scenario.

    errors            ---e1-------------------e2--
    userActions       -u1--u2--u3-u4-u5-u6-u7-u8--
    analyticsMessages ---e1u1---------------e2u8--

Now, let me clarify what happened here. The error occurred after u2, but the errors thread got descheduled and the userActions thread kept on processing. I am not certain exactly what to expect from 'errors.withLatestFrom(userActions,...' here but I suspect that 'e2u8' may be the expected output.

So this error reporting system is fundamentally unreliable. If this is correct then I would say that combining Rx streams is not appropriate for this use case. This also suggests that although we managed to get rid of our glitches we still produced a terrible piece of software.

Do I have to wrong end of the stick? (The answer was yes, but it was good anyway)

My understanding is that it is both.

This really is a real breakthrough in quantum computing. Specifically for an approach called 'quantum annealing' which is one of many (there is at least one other) possible approaches to quantum computing.

This result is a breakthrough in two ways.

1: It demonstrates real quantum effects in the D-Wave computer. It had been hotly debated, by experts in quantum computing, whether the D-Wave actually used quantum effects in its computations. 2: It shows a real speedup for a very specific instance of a very specific algorithm. This is great news, and a very good result, for the people working on the D-Wave.

This is just a news story because

1: The D-Wave is much, 100 million times!, faster than the same algorithm running on a conventional computer. But there are algorithms you can run on a conventional computer which are equivalent (If someone could clarify how equivalent they are that would be great) which are as fast as the D-Wave. So they chose an algorithm which is good for the D-Wave and terrible on a classical computer. 2: The problem instance they chose is very artificial and it isn't clear that the speed up wouldn't disappear if they tried to run actual real world instances of the problem.

I would conclude that this is a great result. It increases the understanding of quantum computing. That is very exciting. The D-Wave doesn't appear to be practically useful. Yet.

(I am not even the beginning of an expert in this, everything I wrote above comes from the link below)

http://www.scottaaronson.com/blog/?p=2555