4
$\begingroup$

In my CS computer organization textbook, there's this blurb on the advantage of assembly over a high-level language.

Another major advantage of assembly language is the ability to exploit specialized instructions - for example, string copy or pattern-matching instructions. Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction. However, the programmer who wrote the loop can replace it easily with a single instruction.

How can a loop be replaced by string copy or pattern matching? Can somebody give an example on specialized instructions that are not available in a high-level language and how a specialized instruction can replace a loop?

$\endgroup$
2
  • 1
    $\begingroup$ For example, the x86 assembly language has a number of prefixes, which allow to repeat commands, like REP MOVS, where the REP prefix repeats the subsequent command while the ECX register is not zero. According to the Intel ref. manual, "a REP STOS instruction is the fastest way to initialize a large block of memory". Although, I'm not sure about those compilers which can't figure out simple cases like that. $\endgroup$ Feb 20 '16 at 19:46
  • 1
    $\begingroup$ @AntonTrunov, compilers do take advantage of such specialized instructions. A hefty part of their complexity is precisely deciding what exact sequence of instructions is the "best" way to do something. This includes at least some canned, human-written (or even found by systematically trying all possible instruction sequences and selecting the best) sequences for some common operations (like copying memory areas). The compiler entries in John Regher's blog are a real eye-opener on real-world compiler building. $\endgroup$
    – vonbrand
    Feb 20 '16 at 20:58
4
$\begingroup$

Some machines have complex processor instructions that can do the same job as a loop with a simple body. For example, x86 processors have an instruction scasb instruction that searches for a byte value; the C strlen function, which searches for a null byte and can be written in C as

while (*p != 0) p++;

can be written in x86 assembly as

repne scasb

Another example is bit counting. Many processors have instructions to do things like finding the number of bits that are set in a word, or finding the index of the lowest-order set bit in a word. However, most programming languages have no operator or function for that, so the programmer has to write a loop like

bit_count = 0;
while (n != 0) {
    if (n & 1) ++bit_count;
    n = n >> 1;
}

whereas recent x86_64 processors have an instruction for that:

popcnt

Some C compilers provide extensions to the standard language that give access to this instruction (and compile to a loop-based form if such an instruction doesn't exist on the target machine).

Yet another example is instructions that accelerate some common cryptographic algorithms (e.g. AES-NI on recent x86 processors). Unlike the previous two, this example is of interest only to the rarefied world of cryptography implementers, so compiler writers are less inclined to provide ways to generate those instructions apart from inline assembly.

Your textbook seems somewhat dated to me. Loop instructions hard-wired in processors are a very CISC feature that most modern processors don't have, the notable exception being the x86 architecture where it is implemented in microcode for backward compatibility. Compilers have become better at understanding what a piece of code including a simple loop does, and converting them to optimized machine instructions. The statement “Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction” is not always true for 21st century compilers. It is sometimes true; for example I can't seem to get GCC to recognize my naive popcnt implementation above.

$\endgroup$
5
  • $\begingroup$ My textbook is this: amazon.com/dp/0124077269. Supposedly it was revised in 2013 $\endgroup$ Feb 22 '16 at 18:32
  • $\begingroup$ As noted in the comments of another answer: you do not need assembly to get popcnt. You can simply use __builtin_popcount and let the C++ compiler worry about how to translate it into efficient assembly code for your platform. $\endgroup$ Feb 22 '16 at 22:24
  • $\begingroup$ @JukkaSuomela Only if you have a compiler that provides this nonstandard extension to the language. If you use multiple compilers on the same hardware, it's less portable. If you use the same compiler over different hardware, it's more portable. But anyway, you're missing the point — the point is that every now and then programmers encounter something that the hardware can do but the compiler isn't aware of. Yesterday is was popcount, today it may be prefetching or crypto acceleration, etc. $\endgroup$ Feb 22 '16 at 22:37
  • $\begingroup$ @Gilles: "every now and then programmers encounter something that the hardware can do but the compiler isn't aware of" — I disagree with this claim. My experience is that GCC implements new instructions before you can actually buy CPUs that support those features. Assembly has its uses, but access to the latest CPU features is not really one of those. Just use an up-to-date C++ compiler. $\endgroup$ Feb 22 '16 at 23:14
  • $\begingroup$ @JukkaSuomela GCC on a PC isn't the whole world. There are other compilers and other processor architectures. There are also build systems where you can't easily — and probably wouldn't want to anyway — use the latest beta version of the compiler. $\endgroup$ Feb 22 '16 at 23:18
4
$\begingroup$

Counting bits set, Brian Kernighan's way

unsigned int v; // count bits set (1)
unsigned int c; // result
for (c = 0; v; ++c)
{
  v &= v - 1;
}

This code becomes popcnt

$\endgroup$
3
  • 1
    $\begingroup$ This is actually available in some compilers. For example, in gcc you have __builtin_popcount. $\endgroup$ Feb 21 '16 at 19:25
  • 2
    $\begingroup$ Yes, but this is non-standard, and adding assembler insertions, intrinsic functions or inline assembly is as far as I know not high level anymore. $\endgroup$
    – Evil
    Feb 21 '16 at 19:36
  • 1
    $\begingroup$ @EvilJS: It works on GCC & Clang, and it is not processor-specific. It is not inline assembly. You can think of __builtin_popcount as a convenient function provided by your programming environment, with a very efficient implementation on modern CPUs and a fairly efficient fallback implementation on any CPU. The name of the function is pretty ugly, but other than that, it is similar to e.g. any other (non-standard but commonly supported) mathematical function. $\endgroup$ Feb 22 '16 at 22:16
0
$\begingroup$

Modern CPUs include specialized instructions (mostly privileged ones, i.e., only the operating system kernel is allowed to use them) to do Input/Output, messing with table pages, flushing the various CPU caches, return from an interrupt. The operations invoked make no sense in regular code (and wouldn't be allowed in the first place), so they aren't in the repertoire of instructions emitted by the compiler. To allow their use, most C compilers (C is often used to write operating system kernels) have ways to include assembly snippets inline.

If you look at the discussions on languages in StackOverflow, you'll see that the compiler is required to emit code that just behaves "as if" it was doing the operations written by the programmer. The instructions used to "fake" what you request can very well be quite different from what you'd expect, computations might be done in wildly different orders, useless computation silently elided, and so on. In the case of C, the compiler is allowed to use knowledge of what standard library functions do, and replace e.g. printf("%s", string) with puts(string), and sin(x) * sin(x) + cos(x) * cos(x) with 1.0. Take some (not too complex) code, and ask to compile with maximal optimization to assembly language (ask for debugging, that'll add some comments that help referencing back to the source). You'll be surprised.

$\endgroup$
5
  • 2
    $\begingroup$ I don't see how this answers the question. The question doesn't ask about instructions that do something that can't be represented in source code, and it doesn't ask about optimizations in general. It specifically asks about optimizations that use special instructions. $\endgroup$
    – svick
    Feb 20 '16 at 22:47
  • $\begingroup$ @svick, the compiler is free to use specialized instructions. And compilers that are smart enough (recent GCC, recent clang, intel's compiler on Linux; the Windows compilers from Microsoft used to be rather dumb, haven't looked in some time though) on a thoroughly CISC machine like the PC will use them, where appropriate. $\endgroup$
    – vonbrand
    Feb 21 '16 at 0:13
  • $\begingroup$ Then I think you should post that as the answer. $\endgroup$
    – svick
    Feb 21 '16 at 1:22
  • $\begingroup$ @svick, see my answer. It does include that (and more). $\endgroup$
    – vonbrand
    Feb 21 '16 at 1:35
  • 1
    $\begingroup$ So what's an example of loops that can be replaced by one assembly instruction? $\endgroup$ Feb 21 '16 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.