davidtgoldblatt

Just to emphasize the truly remarkable thing here: the winning (SIMD) solution takes about 1ns per word sorted -- just over 3 machine cycles to sort 16 nibbles. Note that even extracting a nibble from a word in the naive manner would take about the same amount of time. The speedup from using SIMD registers is tremendous, and should be a lesson to anyone who spends their time micro-optimizing hot functions.

Looks good to me; that's essentially the solution I had in mind (though, I think you have a race on NintBucket::waiters in modify and append_cv). Using a custom two-mutex lock class and condition_variable_any is particularly clever, I hadn't thought of that.

I just published my solution, which uses a similar strategy: http://dgoldblatt.com/a-threading-riddle-solution.html

I don't think of this as violating the N^2 primitives rule; the solution is still linear in the size of the problem its facing (it only uses K condition variables for K threads, so even if K is bigger than N^2, it's still morally in the scope of the problem).

I think his solution is a little bit tongue in cheek - it shows how much easier it is to solve using transactional memory compared to low-level concurrency primitives. So it cheats by using very powerful techniques instead of the very weak ones that the post says to use. You couldn't use his solution in C++ for instance, because C++ doesn't come with garbage collection or transactional memory.

My bad; Strilanc's interpretation is correct. I updated the wording to hopefully be a little clearer.

Many processors have undefined behavior. The x86 manuals, for instance, specify (or rather, explicitly decline to specify) lots of it:

- Values of certain flags after certain instructions

- The result of bsf or bsr on 0.

- I think there are some floating point operations that can be undefined when the results fall off the edge of representability, but I don't remember off the top of my head.

These have behavior that differs from processor to processor.

This isn't to mention the various kinds of processor errata that pop up: loads being reordered with LOCK'd x86 instructions, or ARM memory reads that go backwards in time, both of which happen in real processors despite being architecturally forbidden.

The longer I work on performance teams, the more I agree with the "performance always matters" point of view[1]. In large binaries (or at least, in the large binaries I've worked on), we don't see a few tight loops taking the bulk of the time. Instead, there's a death by a thousand cuts in which many small inefficiencies add up, and have to be clawed back slowly and painfully, often by people with less understanding of the semantics of the code in question than the original authors. Most performance work I see isn't stuff like "write the tight loop in assembly; save 30% on execution time", it's stuff like "reuse the locale object to avoid construction penalties; save 0.4%".

For reasons like this I'm skeptical of e.g. python advocates who say the speed difference doesn't matter since you can always rewrite "the hot code" in C. That works when you're truly using python as a scripting language; the glue that ties you matrix multiplication routines or whatever together. But when you're going to have a large, flat, performance profile, you're better off just writing your program in C++ (or its friends) to begin with.

[1] So I suppose, you can take this entire comment as "person in specialty thinks everyone else should change to make his life easier". Maybe I just have a warped view of priorities.

Nice work! I have some suggestions for future improvements:

- Your CPUCycle class doesn't actually do backoff. atomic_thread_fence(m_o_relaxed) is a no-op, and at least one compiler (recent clang versions) will optimize the loop away entirely. You can fix by reading from a volatile variable inside the loop.

- Similarly, nanosleep on linux will busy-loop instead of returning to the scheduler for small delays; this seems not to be the goal for some of the backoff schemes

- The BoundedQueue assumes that a futex call functions as a "full memory fence". I'm not terribly familiar with the linux kernel internals, but I don't believe this to be the case. On Power, for instance, it appears to not always generate a sync instruction, instead using lwsync or isync. I haven't looked at the queue closely enough to tell if this poses a correctness issue, but it definitely looks weaker than atomic_thread_fence(m_o_seq_cst).

- The SpinLock uses a test-and-set loop; test-and-test-and-set will often scale much better because of the reduced cache coherency traffic required.

- Similarly, using NoBackoff as the default backoff strategy seems to impose a likely performance penalty on users who aren't familiar with the need for backoff.

- The FutexLock code looks a little screwy to me. Why backoff if you're likely going to do a futex operation anyway? Why is the Lock()'s unconditional discarding of the exchanged value safe? It seems like you have the potential for missed wakeups. But it's late and I'm tired, so I'm probably just missing something.

I don't mean to be critical, it's just that code reviews only ever contain nits. I'm excited that somebody is working on locking primitives that are more efficient than glibc pthreads (whose performance I'm not a huge fan of).

BTW, the problems with thread registration you mention can be solved using cpu-local storage instead of thread-local. This can also save space usage and collection time since, assuming short lifetimes for guard objects, the total maximum number of guard objects that ever come into existence simultaneously is smaller.

In lots of practical scenarios though, hazard pointers aren't great for performance, since they require a Store|Load fence during every load operation (e.g. traversing linked list requires O(n) mfences). Alternatives like Fraser's epoch-based reclamation or quiescent state based reclamation often perform better in "real life". (Not to imply you're not familiar with this, haberman, but it's useful to document for other readers).

This isn't really a great solution though, since it pushes the problem of ensuring FIFO ordering outside of the queue and onto the user; but being FIFO is entirely the point of the queue data structure. If your queue doesn't provide ordering across multiple threads, it can't meaningfully be called a multi-threaded queue, so it's not very fair to compare it to genuine multi-threaded queues. Unless I've misread the documentation, this is just a collection of SPMC queues, together with a read operation that checks all the queues for an item to dequeue, right? But there is no synchronization that occurs to tie any of these SPMC queues together. Even if you wrapped every single access to this data structure in a lock, for instance, you would not be able to ensure FIFO ordering of elements inserted into it.

I think the estimation that having inter-thread ordering requirements is uncommon is incorrect. Probably the most common use of MPMC queues is as a concurrency primitive in systems using a CSP-like abstraction, where such requirements are extremely common. But you can't implement, say, Go's channels in terms of this data structure.

This doesn't seem to correctly implement a queue to me?

Suppose thread A enqueues an item, signals somehow to thread B that thread B may proceed, and then thread B enqueues an item. There's no guarantee that thread A's item will be dequeued before thread B's.

Of course, non-linearizable doesn't necessarily mean useless (this is in fact an active research area), but it makes me think the performance comparisons aren't really fair; you're comparing genuinely linearizable queues with one that isn't bound by that performance-hampering requirement.

By the way, in case anyone was curious about the comment in the article:

> Since fences are so expensive, couldn’t you add a dummy assembly instruction that prevents the X86 from re-ordering? So the pseudo assembly for thread 0 might become:

    > store(zeroWants, 1)
    > store(victim, 0)
    > r0 = load(victim) ; NEW DUMMY INSTRUCTION
    > r0 = load(oneWants)
    > r1 = load(victim)

> Since the dummy instruction is a load, the X86 can’t reorder the other loads before it. Also, since it loads from “victim”, the X86 can’t move it before the store to “victim”.

> If you do this to both threads, does that solve the problem?

This doesn't work. Intel specifically calls out these sorts of attempts to get a fake memory barrier: "The memory-ordering model allows concurrent stores by two processors to be seen in different orders by those two processors; specifically, each processor may perceive its own store occurring before that of the other." This is true in practice as well as in theory.

A related trick that does work in practice (though it is also banned by Intel) is to write to the low-order bytes of a word, read the entire word, and get the high-order bytes. It's sort of a single-word StoreLoad barrier. There's a paper from Sun that documents it further: http://home.comcast.net/~pjbishop/Dave/QRL-OpLocks-BiasedLoc... .

The relative performance of a lock'd instruction and an mfence will vary across processors and workloads. On my machine, simple peterson locking is ~10% faster when using an mfence as opposed to an xchgl. Maybe if the non-locked code benefited more from pipelining, the results would be different.

As an aside, g++ uses mfence for its C++11 atomics while clang uses xchgl; Does anyone know if Intel/AMD has ever guaranteed that all the usual ordering guarantees apply when mixing these? (Of course given their implementations it almost certainly will, but it would be nice to know this for a fact).

To clarify: the strategy in the post doesn't actually work (or at least, is not guaranteed to work in every conforming implementation): the "volatile" only applies to the read of the function pointer, not to the execution of the function in question.

You don't even need to assume some sort of crazy evil compiler to have to worry about this - speculative inlining of function pointers guarded by a safety check is something that FDO builds will actually do.

Even if you're read mostly, R/W locks often do a very bad job. If your critical sections are short (say, in a hash map, or fine-grained locks in a linked list or tree, or even a whole structure lock on a small tree or array), then contention on the R/W lock internals will be a bottleneck, since readers still have to update the reader count, so the count field is a shared location all the readers are doing writes to. You could have this by e.g. having a "fat" R/W lock that's made up of num_cpus primitive R/W locks (and each reader only reader-locks the lock associated with its CPU), but none of the common R/W locks actually do this (and it's not always even the right call if you're worried about node size).

Then again, lots of lock-free structures often try to handle memory management using reference counts or hazard pointers, which have their own performance issues.

This isn't true for either of the common high performance mallocs. tcmalloc doesn't support mremap at all, and jemalloc disables it in its recommended build configuration. glibc will remap, but any performance gains that get realized from realloc tricks would probably be small compared to the benefits of switching to a better malloc implementation.

Sorry for being unclear; this is the comparison I was trying to draw. The new techniques look like "magic" the way SVMs did when they first became popular. It triggers excitement the way it did when people realized that they could get near state of the art performance on the MNIST digits just by dumping raw pixel values into an SVM.

I'm don't have a ton of expertise in the area, but I chat sometimes with people who do, so take this as a reasonably informed but lay opinion.

By and large, most uses of machine learning don't get much value from better machine learning in the sense that, given finite time and resources, you'll probably get better results on your problem by spending time on feature engineering instead of on machine learning improvements.

Some of the new deep learning techniques though have achieved good results on a large variety of problems in more of a "just plug it in" sense. My favorite example of this is this paper: http://machinelearning.wustl.edu/mlpapers/paper_files/ICML20... , which handles both sentence parsing and scene decomposition. They get competitive results on wide-ranging problem domains which have traditionally required lots of fine-tuning to do well on.

So the hope is that deep neural networks will provide improvements in the same way that SVMs did 20 years ago; that people will be able to just dump numbers into a more or less black box algorithm and get better results than they currently do. And indeed, I'm guessing people were as excited about SVMs in the 90s they are about deep neural networks today.

Something I've been wondering since the Forbes article - is inappropriate investor behavior illegal? The things described there would unambiguously be sexual harassment if someone's manager did them; it seems unfortunate if the only tool to fight investor/founder harassment is social pressure.

For those interested in additional technical details of high-performance garbage collection, the book cited (The Garbage Collection Handbook: The Art of Automatic Memory Management) is a fantastic reference. It's one of the best-written technical books I own, and distills much of the modern literature. If you need to do GC performance tuning or reason about memory management issues in the JVM, having this book around will be very useful.

If you're wondering why you've heard of him for non-entrepreneurial reasons, Cheriton has made major academic contributions in distributed systems; he's an author on the leases paper, the V operating system, and the "Understanding the Limitations of CATOCS" paper, among many others.

getcontext and setcontext also keep track of signal state, which involves a syscall.

Charles Schwab (which, security practices aside, is a fantastic place to bank) doesn't (as far as I can tell) store your password unhashed.

However, they manage to make this irrelevant, because passwords are restricted to between 6 and 8 characters and can contain only numbers or letters. I can only hope the passwords are bcrypted to high heaven.

I've yet to find one of these types of services that you can't access by spoofing the MAC address of a real customer.

A while back, Intel removed MAC address spoofing from some of its wireless cards through a driver update, citing vague "security" concerns. I felt very up in arms about it for a while (why on Earth would you hobble your customer's products so you can make sure they can't violate your moral code!), but eventually decided I couldn't really complain, since the only reason I could think of that I might want such an ability would be to steal internet access.

This is only tangentially related to the article, but if you'd like to see a nice interactive visualization similar to the ones it includes, http://cs.stanford.edu/~karpathy/svmjs/demo/ is a great one. There are similar visualizations for neural networks and random forests linked there.

It's a testament to the speed at which technology moves that, despite being not very much older than the author (he's 16, I'm 23), I feel separated by a significant age gap. I'm still often shocked that Youtube can afford all the bandwidth required for streaming video; he barely remembers the world where unlimited streaming video wasn't the norm.

This is really neither here nor there, but I never understood why factorial is always used as an example of a naturally recursive function, as opposed to, say, sum. It's not as though "product of the numbers from 1 to n" and "sum of the numbers from 1 to n" are somehow inherently different in how recursive they are.

Something I find amusing is that the ability the author demonstrates here, to notice that a task is repetitive and has a programmatic solution, is itself a skill that has to be learned, and one that's different than programming.

Once, when I was working on a group project in an operating systems class, we modified our kernel malloc and free routines to print the relevant address every time they were called, to do some simple leak-checking. The result was a file of a few thousand lines like "malloc 0x94583900", "free 0x34739A4", etc. One of my partners looked at the file and said some variant of "oh no - this is going to take hours to match up". Apparently it hadn't occurred to him, someone who'd been programming professionally for years and who only minutes before had been tweaking the internals of a process management function in a multithreaded x86 operating system, that there was an easier avenue available to him.

It's relatively well-documented that sleep deprivation has effects similar to those of alcohol intoxication, but coming in to work drunk is a firing offense, while working to the point of sleep deprivation is regarded as heroic. Of course, these aren't quite the same, but I still wish the idea that your dedication is measured by your level of self-destructive sleep habits weren't so prevalent in the tech industry.

Rvalue references allow you to "steal" the resources from an object when it's safe to do so. One use for this is to optimize functions returning large complicated data structures, but that's just because memory is a particular type of resource.

With rvalue references, you can move around objects that should be moveable but not copyable. Consider an object representing a database connection - copying it isn't meaningful, but moving it ought to be.

There's the following algorithms class CS 261 (upper-level undergraduate/masters) and CS 361b (mostly aimed at phd students, though undergraduates take it). 161 covers all the material you would expect to see in an undergrad algorithms class. I'd be surprised if 261 or 361b are put online, since they're not usually recorded and (at least when I took them) have between 10 and 20 students.