cfallin

Sure -- for a good example, GPUs go partway there by not speculating (they still have cache hierarchies though). It works because GPU workloads have massive data parallelism, so while one group of threads (a "warp") is stalled waiting for data, the cores can just execute other threads. Sun/Oracle had built a number of Sparc chips along this line too, e.g. the Niagara (Sun UltraSPARC T1) tolerates memory latency by having a bunch of SMT threads (8 per core, IIRC?) rather than OoO scheduling.

The problem is that single-thread performance is really important for a lot of workloads, because (i) parallelization is hard, (ii) even for parallelized workloads, serial bottlenecks (critical sections, etc.) still exist, and (iii) latency is often important too (one web request on one core of a server, or compiling one straggler extra-large file in a parallel build, for example).

> It is possible to have OoO without speculative execution

That's technically correct (the best type of correct!), but without speculation, the CPU can't see beyond a branch, so the window in which the machine can reorder instructions is very small. (For x86 code, the usual rule of thumb is that branches occur once per 5 instructions.) So in practical terms, an OoO design (in the restricted-dataflow paradigm, i.e., all modern general-purpose OoO cores) always at least does branch prediction, to keep the machine adequately full of ops.

An interesting question, though, given that we're going to do speculation, is what types of speculation the core can do. The practical minimum is just branch prediction, but modern cores do all sorts of other speculation in memory disambiguation, instruction scheduling, and the like, some of which has enabled real side-channel attacks (e.g., Meltdown).

Also, FWIW, Pentium was 2-way superscalar, but not OoO in the fully general dataflow-driven sense; the Pentium Pro (aka P6), in 1995, was the first OoO. (Superscalar can technically be seen as OoO, I suppose, in that the machine checks dependencies and can execute independent instructions simultaneously, but it's not usually considered as such, as the "reordering" window is just 2 instructions.)

Yes, but it typically means a significantly smaller speculative window -- rather than a ROB that can fill with several hundred instructions beyond a mispredicted branch, there is just the pipeline depth from fetch to commit worth of speculative work.

Yes, that's true, several of the vulnerabilities involve checks that are performed late (not at time of speculative access, but at some point before instruction commit). Not excusing the design choice at all, but it's conceivable that an engineer could make this choice if (i) side-channel effects of the speculation are not considered at all, and (ii) the postponement of the check allows the load latency to be reduced. Again, not justifying, and the vulnerabilities are terrible, but there does seem to be a rational-given-some-assumptions way to reach such a decision.

The stream of critical CPU vulnerabilities starting with Spectre/Meltdown last year are related to speculative execution, not just Intel. (AMD and ARM CPUs are also vulnerable to Spectre, for example.) Intel CPUs are sometimes vulnerable to additional attacks because they speculate in more scenarios than other designs. But fundamentally, as long as multiple different trust domains are sharing one CPU that speculates at all, or has any microarchitectural state (e.g., caches), there are likely to be some side-channel attacks that are possible.

The important thing to realize is that speculation and caching and such were invented for performance reasons, and without them, modern computers would be 10x-100x slower. There's a fundamental tradeoff where the CPU could wait for all TLB/permissions checks (increased load latency!), deterministically return data with the same latency for all loads (no caching!), never execute past a branch (no branch prediction!), etc., but it historically has done all these things because the realistic possibility of side-channel attacks never occurred to most microarchitects. Everyone considered designs correct because the architectural result obeyed the restrictions (the final architectural state contained no trace of the bad speculation). Spectre/Meltdown, which leak the speculative information via the cache side-channel, completely blindsided the architecture community; it wasn't just one incompetent company.

The safest bet now for the best security is probably to stick to in-order CPUs (e.g., older ARM SoCs) -- then there's still a side-channel via cache interference, but this is less bad than all the intra-core side channels.

There's still some research on this general idea -- e.g., a fellow grad student's work on in-memory bulk data operations:

- https://archive.org/details/arxiv-1611.09988 (AND/OR/NOT in RAM)

- https://www.pdl.cmu.edu/PDL-FTP/NVM/rowclone_micro13.pdf (cloning data in RAM; full disclosure, I'm a co-author on this one)

And IIRC at least one start-up (Emu Technology) that has built actual processing-in-memory (PIM) hardware.

For anyone with a bit of an academic bent, the ideas behind GraalVM are really really cool -- basically, they compile by partially evaluating an interpreter for X with a program in language X. Simple idea at a high level but they actually made it work well, with some clever tricks like annotated partial-eval boundaries in the interpreter and an API for first-class speculative assumption objects.

Their paper is a good read: https://dl.acm.org/citation.cfm?id=3062381

Yes, definitely! I just bought a few Wingsung 3008s from eBay (a few dollars each, I think) and they're super-smooth. Couldn't believe I got a TWSBI-like piston filler for that cheap. Only downside to the cheap eBay pens is the shipping time...

The idea of straight-line traces goes back even further, to Josh Fisher's work on trace scheduling in compilers in the early 80s (linearizing one control-flow path gives a much wider scope for optimizations):

https://en.wikipedia.org/wiki/Josh_Fisher#Trace_Scheduling

He combined this with a VLIW processor architecture to build Multiflow, a hardware startup. (Interesting history tidbit: Robert Colwell, who architected the P6, the first out-of-order Intel core, started his career at Multiflow before joining Intel. The P6 didn't have any trace-cache influences, but the P4, a few years later, infamously did...)

Re: complexity, read up on "semi-naïve evaluation" for the usual execution strategy, which basically involves keeping lists of newly-added tuples in each iteration of the fixpoint loop and only processing deltas related to those new additions. This, combined with good index inference for each relation (predicate), so that e.g. the node-neighbor lookup is O(log |V|), should result in efficient execution...

Doop is a fantastic base system to extend for anyone wanting to do program analysis generally! I built my thesis work on top of it (recently defended but unfortunately not published yet) and Datalog is incredibly productive to prototype ideas.

(Performance is another matter -- one has to pay careful attention to clause ordering, and watch out for O(n^2) / O(n^3) / ... loop nests, but at least it's easier to try options than refactoring an ad-hoc analysis engine.)

One solution, not practical for most folks but works well for me: live in a different area code than phone number. (My cell number is in the area code I grew up in.)

It seems most spam calls either fake a source number that's in my phone's area code, or use a completely random source. Almost any inbound call I actually expect without an address-book entry would come from my (new) local area code, so I can pick up a call if (in current area code) OR (in address book). So in essence, my current area code is a 3-digit passcode.

Perhaps a nice trick if one is allocating a new VoIP number -- at the cost of looking like a non-local when giving it out, you can effectively screen for actual local calls...

I heartily second the recommendation for "The Idea Factory"! I'm currently reading this book and aside from the seriously impressive run of successes, the characters are really quite amusing at times too. E.g., Shannon built a desktop calculator that operated using Roman numerals only ("THROBAC") in order to amuse himself. And some of the whimsical creations were pretty impressive in their own right. E.g., his maze-solving mouse "Theseus" learned the maze layout on progressive runs through the maze by using relay-based logic.

Ah, yes, that makes perfect sense! So many word roots hiding in plain sight...

Some of the compound words are really quite funny, too... two of my favorites, randomly encountered recently: gloves/mittens are "Handschuhe" (hand shoes), and a porcupine is "Stachelschwein" (spike/quill pig).

Very intuitive actually!

Why not, though? Energy is energy -- we (humans) oxidize food, basically burning it slowly, to power our bodies. Whether the energy is carried by glucose/ATP or electric current is just an implementation detail.

Comparisons are frequently made in other domains as well -- e.g., cyclists measure power outputs in watts.

The rule of thumb I've understood is that the brain runs on about 20 watts (peak power), and a human on average runs on about 100 watts. That's 8.64 MJ/day, which converts to 2064 food calories (kcal), at 4184 J/kcal.

Yup, the Pennsylvanian is actually pretty nice. The route is the old Penn Railroad mainline and zigzags through some really scenic parts of the Appalachians!

The only downside is that it's on a once-per-day schedule (Pgh->NYC at 7:30am and NYC->Pgh at 10:50am). It's 8-9 hr downtown-to-downtown (vs. ~5-6 when flying) so you'd really want to do Fri/Mon for a weekend. FWIW, there are three or four Megabuses per day too, including an overnight bus in each direction, for when the train schedule doesn't work.

Also, flying to NYC from Pgh is oddly expensive, like $400 roundtrip expensive. Amtrak is about $150 RT if far enough in advance.

Anyway, welcome to Pittsburgh! I hope you're surviving the snow...

> [Amtrak] was really pleasant. It just takes forever.

Absolutely -- IMHO for mid-distance (200 mi to 500 mi or so) trips, Amtrak is a really underrated option. I travel semi-often from Pittsburgh to NYC (450 mi) and choose train over flights because it's actually not that much slower (consider to/from airport, security, and (de)boarding, as you say) and it's much more comfortable: I can walk up and down the whole train, with no fasten-seatbelt sign to stop me; there's a cafe car; I have about 2 feet of legroom; there is reliable AC power and functional wifi. I just make it a work-from-train day and all's well.

Yeah, the only downside of heap storage is the alloc/dealloc cost -- once you have the memory, it's all just bytes in RAM, whether heap or stack.

It's not even a clear tradeoff for large arrays, because using value types on the stack implies lots of copies -- when you have a large block of data you want to refer to it by reference.

Also, stack size is finite and relatively small -- 2MB-ish default per thread on Linux, or is it 8MB? -- so placing large matrices there will work until it doesn't. Heap allocation has all of virtual memory at its disposal.

> Unacceptable. It's now 5+ years since major improvements.

It's disappointing that the curve doesn't go up-and-to-the-right more, but "unacceptable" reads a little harsh to me -- I doubt the lack of big IPC gains for single-core workloads was a voluntary choice. Intel (and ARM, and Apple, and AMD, and ...) are full of engineers trying to come up with clever tricks in the instruction scheduler, or branch predictor, or prefetcher, or cache replacement policy or whatever, that obtain fractions of a percent IPC improvement. It's really hard to improve on something that's been optimized to death for the past ~25 years (since the first CPUs with out-of-order execution), and they'll take whatever they can get.

I do agree that the competition with AMD will certainly be interesting to watch, certainly...

The tricky bit isn't making sure you don't free pointed-to objects; the tricky bit is knowing which objects can be pointed-to. A consequence of GP's point is that because there can be an arbitrary delay between reading a pointer and dereferencing it, any pointer ever exposed to other threads must be considered in-use indefinitely (the reader could sleep indefinitely then wake up and deref) unless one can prove that the pointer is no longer held by any potential readers.

There are a few common ways to do that. Hazard pointers are one: every thread updates some per-thread pointer indicating what object it is reading, and other threads check this (for every live thread) before freeing an object. GC also solves the problem because any multithreaded GC must somehow examine live roots in every thread -- so it will see the still-live reference in the sleeping reader.

The main point, though, is that it's harder than the lock-synchronized case because one no longer has the guarantee that a reader will hold the lock as long as it's examining the pointed-to object.

Another cool feature, on top of steveklabnik's comment: rustc is actually smart enough to collapse `Option<T>` where `T` is a borrowed reference (pointer) to a single word. Basically, the compiler knows that the pointer can never be null (borrows are always valid when in scope), so it can use the non-null values for `Some(...)` and the null value for `None`.

In other words, the compiler can turn an Option into a null-pointer convention by reasoning from first principles.

(I think this optimization works for enums in general, and is somehow related to the `nonzero::NonZero` type, but I could be wrong about that.)

Example (look at the calls to f1 and f2 in example::main): https://godbolt.org/g/SSs6X2

Yup, bleeding-edge laptop support is still a toss-up, but it's getting better, IMHO!

I think that's where this sentiment often comes from: people who cut their teeth on XF86Config tweaking and compiling NVidia kernel modules from source and shopping for just the right PCMCIA wireless adapter are now amazed when a fresh Ubuntu install has working 3D-accelerated graphics, 802.11n (with GUI for configuration), Bluetooth, etc. (And yes, we have Freedesktop.org/systemd/NetworkManager and friends to thank for a lot of this.)

Maybe the bar was just really low, and you've got a strong argument if you say it shouldn't be anymore, but we are making progress...

People have replicated silicon fab processes at home -- see e.g. [0] where Jeri Ellsworth makes homemade transistors. Of course the effort she took to do that (while seriously really impressive) probably isn't worthwhile compared to the use of an FPGA if you just want to see your CPU pipeline in Verilog come alive :-)

[0] http://hackaday.com/2010/05/13/transistor-fabrication-so-sim...

> It only works when your function returns error of the same type as expression inside 'try!' or '?' macros.

The language has actually thought of this case -- it turns out you can map lower-level errors into your higher-level error type by implementing the `From<E>` trait. E.g.:

    use std::io;
    pub enum MyErr { Io(io::Error), Custom(String) }

    impl From<io::Error> for MyErr {
        fn from(err: io::Error) -> MyErr { MyErr::Io(err) }
    }

    fn do_stuff() -> Result<(), MyErr> {
        let f = try!(File::open(...));
        // ...
    }

Well, you can't solve it in the general case. But parallelizing compilers can and have been written that perform a conservative analysis -- they can prove some subset of all parallelizable loops as parallelizable, and for the ones they can't prove as such, they err toward 'remain serialized'.

For a simple example, code that performs regular array-based accesses, where index computations are simple affine functions (a*i + b) of a single iteration variable 'i', is a case that's received a lot of attention. See e.g. Polly for LLVM.

+1 to Pittsburgh! My girlfriend is a resident at UPMC and from everything I hear/see, they're treated well. The cost of living here is cheap enough that if you're making 50-60k you can afford one of the nicest 1-bedrooms in the East End (area around the universities); I'm very comfortable on half that as a PhD student. The town is filled with nerds of both the tech and medicine variety (we have Google, Uber, etc offices too). Anyway, best of luck!

I'm just a grad student (but I've seen plenty of paper reviews and heard plenty of discussions at conferences), but at least in my corner of academia, the older and more established folks tend to be more visionary: they're more distant from the publish-or-perish scramble of assistant professorship and they've seen cycles of fads come and go. Of course a lot of younger profs bring fresh approaches too but IMHO the tendency to conform to 'accepted' topics to survive is much stronger on the early end of a career.

I agree partially w.r.t. testability of branchless code, but there's a flipside too: often the root cause of an edge case is in data-structure shape, so full coverage isn't necessarily sufficient. In other words, if an edge case is "folded into" the normal path via something like Linus' trick, you still need to actually test the case where (in this example) `head` is being removed, or else you aren't certain that the folding of cases is valid. And if you're testing that case, then you'll have full coverage of the original (branchy) code too.

Totally agree w.r.t. performance, though. Even if the branch is never taken, control flow can reduce the scope of other compiler optimizations.

> the cognitive load of what I no longer had to worry about exceeded what I had to worry about.

Yup, this has been my experience too. I started using Rust for my primary project last March and was worried a little at first about the risk of wasting too much time, but at this point I'm ~1.5x to 2x as productive as in C++11:

* essentially no more "head-scratching action-at-a-distance bugs" (I've spent N years in C++ and I still sometimes invalidate an iterator) -- as you say, any errors that still exist are higher-level logic errors, which are (in my experience) much more straightforward to track down.

* enums and match/destructuring and all the builtin types (e.g. Option, Result) have me thinking in a much more strongly-typed and principled way. So even logic errors tend to be less frequent because I break down the problem the 'right' way immediately. Algebraic datatypes let one describe a state space really succinctly.

Rust is one of those languages that really, strongly wants you to be idiomatic, but it pays off!