Hacker News Reader

Comment by kazinator | Hacker News Reader

"high level" doesn't refer to how it is implemented.

Even a RISC instruction set can be implemented by, say, either some very slick silicon gates, or by an emulator written in Javascript.

The existence of the Javascript emulator doesn't make the RISC instruction a high level language, on the grounds that an instruction like "ADD R1, R2, R3" triggers a complicated traversal within the Javascript code.

The "level" of a language should refer to the "abstraction level". Years ago, I came to favor the definition of "abstraction level" given in the glossary of the Tunes project:

http://tunes.org/wiki/abstraction_20level.html

View on HN

I think that's the author's point: x86 is now a significant abstraction from the actual details of execution.

But what x86 can express hasn't changed; just how it performs.

An abstraction never includes the details of execution; abstraction is that separation itself! A piece of 80386 code running on an 80386 is no more or less abstract than the same piece of code on a Core i7. They agree in their external effects, like what inputs are loaded from memory, and what result is written.

The fact that EAX is renamed to different internal registers or whatever isn't really "high level": not "high level" in any way that helps the programmer express something. It just changes the performance.

It's not high level the way that, say, "reduce + list" is higher level relative to "for (total = 0; i = 0; i < list.length(); i++) {total += list[i];}"

(Exceptions are situations where programs do certain things; e.g. self-modifying code needs to tackle instruction caches on one implementation, but not another. That's where the abstraction "leaks".)

It used to be that the x86 instruction set was representative of the processor architecture that it programmed. That is no longer the case. Now, it is valid to view the x86 instruction set as an abstraction of the processor architecture. That is, you can mostly pretend that the processor you're programming for is accurately represented by the architecture implied by the x86 instruction set, but it is not. And when it comes to instruction timings, this abstraction leaks.

If the term "abstraction" bothers you, then ignore it. The point of the post is to give people perspective.

I would say that the x86 abstraction is now more distant from the actual design of the hardware, not higher.

>I would say that the x86 abstraction is now more distant from the actual design of the hardware, not higher.

Those are equivalent terms to all but the most obstinate pedants.

That's true of all superscalar machines. That's what killed RISC. The original idea of RISC was one instruction per clock and a very simple CPU control section. Early MIPS CPUs realized that.

Then superscalar came to microprocessors with the Pentium Pro. It took 3000 engineers at Intel to design that CPU, but it did much better than one instruction per clock while still handling all the weird cases in x86 instructions. As the fabs improved, the Pentium Pro technology moved to the mainstream. The Pentium II and III were Pentium Pro architecture.

This killed the basic advantage of RISC. The "all instructions the same length" concept really killed it - it meant 2x code bloat. That meant bigger caches or worse cache performance. It meant more RAM and more RAM bandwidth or worse memory performance. The x86 instruction set, for all its faults, is compact.

For the crypto problem, the trouble is that modern crypto algorithms are not branch free. DES was. Vernam was. Rotor machines were. RSA and elliptic curve stuff, no. This is independent of the CPU architecture.

> Then superscalar came to microprocessors with the Pentium Pro.

Hmm, but wasn't the PowerPC 601 superscalar?

The 601 was comparable to the multiple-issue scoreboard architectures used in 1960s supercomputers, such as the CDC 6600, the IBM 7030, and the UNIVAC LARC. The 601 (I think) was a scoreboard machine, not a rename and retire machine.

A scoreboard machine blocks when two instructions use the same register. A rename and retire machine (most modern out-of-order execution CPUs) can map the same program-visible register to multiple machine registers and parallelize even when there's a register reuse, as long as there isn't real data dependency. The "retirement unit" at the end of the pipeline sorts out conflicts.

Scoreboard machines need lots of program-visible registers, and compilers which avoid reusing them when there are registers free. How much of that needs to be done varies with the CPU implementation, which is why compilers for MIPS machines had flags to optimize compilation for each MIPS implementation. This was a huge pain for software distribution. One problem with having lots of registers visible to the program is that context switches require saving all of them to RAM, which is a drag on CPU dispatching.

RSA is not "modern".

Modern elliptic curves are chosen with side channels in mind. You won't find data-dependent branches or look-ups in straightforward implementations of Curve25519 scalar multiplication, for example.

> You won't find data-dependent branches or look-ups in straightforward implementations of Curve25519

As it was pointed out already starting since Pentium 4, for example, the same assembly instruction "add dest, src" might take a different time depending on the value of dest and src.

Unless those modern elliptic curve compensate for specific models of CPUs they run on, their straight C and assembly code might behave as if it has data dependent branches.

Are you talking about this paper? https://gmplib.org/~tege/x86-timing.pdf

I only saw evidence of data-dependent timing with respect to the div operation, but maybe I missed something.

Of course, I am not suggesting other operations are inherently immune to data-dependent timing leaks.

EDIT: I see there are also some notes on adc and sbb in some situations, i.e. chains of instructions that all light up the carry flag.

Don't worry about the instruction, worry about dest, src. If they:

- Are in cache

- Were touched by a previous instruction (regardless of cache)

- Their cache line was touched by a previous instruction

- Will be read/write (immediately) after that instruction

- You're accessing data shared by multiple cores (lock prefix)

timing will vary

That's the whole point, though - the algorithm is very straightforward to implement without data-dependent look-ups. So while any of those could affect execution time, none should do so in a way that leaks data.

x86 encoding is not that compact, especially if you're using some of the odder addressing modes or instructions. (the packing functions, xmm operations, etc) It wastes a fair number of single byte encodings on infrequently used instructions, like BCD arithmetic. An instruction set designed for space efficiency could be smaller without foregoing too much rational and orthogonal opcode design.

It's definitely more compact than a simplistic orthogonal opcode design with a generous allocation of registers, for sure.

I wrote an article [1] about this back in 2010 when Apple got into the chipmaking business with their A4 - there was a lot of confusion on the internet about RISC vs CISC and not much clarity on how the playing field has changed since the early days.

1: https://neosmart.net/blog/2010/the-arm-the-ppc-the-x86-and-t...

> This killed the basic advantage of RISC. The "all instructions the same length" concept really killed it - it meant 2x code bloat. That meant bigger caches or worse cache performance. It meant more RAM and more RAM bandwidth or worse memory performance. The x86 instruction set, for all its faults, is compact.

I'm not really sure that is a big deal today, however. Maybe it was when caches were much smaller, but AArch64 went back from a variable width encoding scheme (Thumb) to uniform width instructions in 64-bit mode, without any problems that I'm aware of, and the performance is quite good. At the same time, the x86-64 ISA has gotten quite a bit less space-efficient: because of the extension to 16 registers, REX prefixes are everywhere and eat up lots of bytes of the instruction stream.

It's actually pretty straight forward to implement branch free RSA or ECC. Don't use Mod operations, use Montgomery Reduction or ECC curve specific reductions which are branch free.

As a side note, the Pentium II was largely just the PPro with the parallel developed Pentium MMX's MMX instruction set also integrated into the core ISA (as opposed to being a separate execution unit like on the Pentium MMX), with a better bus and a smaller fab size (theres other small issues, but you only need to know about those if you're into writing kernels or writing compilers).

Reply on news.ycombinator.com