Issue 2: yes, it looks like there are cases where we should perform the op on the copy instead of the original. I'll have to think about how to detect when that is beneficial.
Issue 3: Even before doing things like OR AX, (BX), we also would want OR (BX), AX. The problem is on amd64 there are a ton of possible instructions you could potentially want, including all the ops times all the addressing modes. So although I think it would be easy to handle this particular case, doing it generally would be a large maintenance burden.
Issue 5 : should be an easy rule fix.
Issue 7: I think this is #14761.

@randall77:

Issue 2: yes, it looks like there are cases where we should perform the op on the copy instead of the original. I'll have to think about how to detect when that is beneficial.

I think Issue 1 and 4 are all various symptoms of this: to me it looks like it would be better to keep the original and modify the copy more times than not.

Issue 3: Even before doing things like OR AX, (BX), we also would want OR (BX), AX. The problem is on amd64 there are a ton of possible instructions you could potentially want, including all the ops times all the addressing modes. So although I think it would be easy to handle this particular case, doing it generally would be a large maintenance burden.

x86 doesn't have so many modes, but I think it has the read/modify/write instructions?

Regarding addressing complexity, all the addressing modes are already used by the LEA instruction, although the execution time assessments don't seem quite right yet; it you solve that one, then the read/modify/write is solved except for latency.

Your concern about OR (BX),AX is misplaced I think, as latency is just dependent on whether the memory is in the cache or not, as for all memory accesses; the OR AX,(BX) is more of a concern only if the destination is in the dependency chain, then it is quite long, but almost always shorter or about the same time as separate MOV (BX),AX/XOR DX,AX/MOV AX,(BX) instructions. Note that 1) there is a latency of the first MOV, but the manipulations of the AX register can hide it, and 2) the use of the instructions is usually is this order where there is no dependency on the final (BX) destination.

I'm just saying - GCC can do it in the specific case where the modify/assignment operators are used, why can't we? GCC does not use them when the modify/assignment operators are not used although Clang/LLVM does. We'll never be able to effectively do extreme loop unrolling of some kinds without it (modulos type of things).

Issue 7: I think this is #14761.

Yes, I think you're right.

x86 doesn't have so many modes, but I think it has the read/modify/write instructions?

The SSA backend encodes each addressing mode in a separate opcode. So for integer loads, we already already have:
MOVBload, MOVBQSXload, MOVWload, MOVWQSXload, MOVLload, MOVLQSXload, MOVQload, MOVOload, MOVBloadidx1, MOVWloadidx1, MOVWloadidx2, MOVLloadidx1, MOVLloadidx4, MOVQloadidx1, MOVQloadidx8.
Similarly for stores. And that's not all the loads, for instance we haven't implemented MOVWloadix4 yet.
That's just the MOV opcode. Multiply that by ADD,SUB,AND,OR,XOR,MUL,DIV,NOT,NEG, and probably others. It gets pretty unwieldy pretty quickly.

I'd like to solve this problem at some point. Maybe we bite the bullet and just do all those opcodes (and corresponding rewrite rules). Maybe we autogenerate somehow. It's low priority at the moment because I don't think it buys a whole lot (it's the same microops, just encoded more efficiently) and it's only x86. It's not needed for all the other architectures, and those are higher priority at the moment.

Regarding addressing complexity, all the addressing modes are already used by the LEA instruction, although the execution time assessments don't seem quite right yet; it you solve that one, then the read/modify/write is solved except for latency.

Your concern about OR (BX),AX is misplaced I think, as latency is just dependent on whether the memory is in the cache or not, as for all memory accesses; the OR AX,(BX) is more of a concern only if the destination is in the dependency chain, then it is quite long, but almost always shorter or about the same time as separate MOV (BX),AX/XOR DX,AX/MOV AX,(BX) instructions. Note that 1) there is a latency of the first MOV, but the manipulations of the AX register can hide it, and 2) the use of the instructions is usually is this order where there is no dependency on the final (BX) destination.

@randall77:

The SSA backend encodes each addressing mode in a separate opcode. So for integer loads, we already already have:
MOVBload, MOVBQSXload, MOVWload, MOVWQSXload, MOVLload, MOVLQSXload, MOVQload, MOVOload, MOVBloadidx1, MOVWloadidx1, MOVWloadidx2, MOVLloadidx1, MOVLloadidx4, MOVQloadidx1, MOVQloadidx8.
Similarly for stores. And that's not all the loads, for instance we haven't implemented MOVWloadix4 yet.
That's just the MOV opcode. Multiply that by ADD,SUB,AND,OR,XOR,MUL,DIV,NOT,NEG, and probably others. It gets pretty unwieldy pretty quickly.

I'd like to solve this problem at some point. Maybe we bite the bullet and just do all those opcodes (and corresponding rewrite rules). Maybe we autogenerate somehow. It's low priority at the moment because I don't think it buys a whole lot (it's the same microops, just encoded more efficiently) and it's only x86. It's not needed for all the other architectures, and those are higher priority at the moment.

You are right that in the general case, using the read/modify/write opcodes doesn't make much difference to timing as generally the latency of the first move will be masked by the computations of the modify value so the difference is likely only ten to fifteen percent for a tight loop as here. However, if one is optimizing using loop unrolling techniques (where the modify value is either immediate or a pre-calculated register), it can make a very large difference as in currently using a load followed by the very short modify followed by the store takes 3 clock cycles where it would take only 1 clock cycle for the read/modify/write instruction (both with no latency/dependency on the memory contents of the store/write).

Often, for maximum speed, the base address will be a "unsafe.Pointer", which has the same read/load followed by modify followed by write/store template as currently used here (in fact it has another issue as it produces the simple base address for the MOV's by a LEA instruction when not necessary, which makes the timing even worse; I'll raise an Issue about that once I document it properly).

Regarding addressing complexity, all the addressing modes are already used by the LEA instruction, although the execution time assessments don't seem quite right yet; it you solve that one, then the read/modify/write is solved except for latency.

As I said, it seems you are already handling all of the addressing modes for LEA, although not the load/store variations; couldn't you just apply those rules to all the variations of the other opcodes?

And autogeneration of the code seems to be the way to do it, as it would seem that the rules would be the same for each different load or store for each of the different opcodes.

I can't comment on your priorities, and the current implementation of read then modify then write is "adequate", but we'll never compete with Cee "extreme" optimizations without this.

Just as a further goal to shoot for, Rust/LLVM produces the following assembly code for the same algorithm, although in Rust I had to use an unsafe mutable pointer reference to eliminate the array bounds check; the following code is about as good as it gets without hand optimizing:

    .p2align    4, 0x90     ;; alignment for better efficiency on loop branch destination
.LBB22_73:
    movq    %rcx, %rax  ;; note that the loop variable is kept in rcx for this case: left shift ready
    shrq    $5, %rax            ;; moved for the right shift word calculation here
    movl    $1, %edx            ;; this should be fixed as here as per issue 16092 using immediate load
    shll    %cl, %edx       ;; only works because the and is not necessary when shifting 32-bit reg
    orl %edx, (%r14,%rax,4) ;; note use of combined read/modify/write instruction!
    addq    %rbx, %rcx  ;; note only use of a reg for the prime value added for next loop
.LBB22_68:
    cmpq    %r13, %rcx  ;; loop limit kept in register
    jb  .LBB22_73       ;; note that the array base is kept in a reg (r14), doesn't need load in loop

On my Sky Lake Intel i5-6500, this takes about 3.2 CPU cycles per loop. The CPU is quite likely executing these instructions Out Of Order (OOE) in order to minimize latencies when registers are updated and immediately used in the next instruction.

Note that the above code recognizes that the loop variable can sit in the rcx register and thus be used for the variable left shift when shifting 32-bit registers (also works when shifting 64-bit registers) as the mask of the lower five bits (six bits for 64-bit) is not necessary and has been eliminated. golang version 1.7 eliminates the mask, but does not then recognize that it can also then use rcx as the loop variable eliminating one register move and the use of one extra register. A total of only six registers are used in the above inner loop, meaning it can be just as efficient in x86 code.

Note that is seems that stable golang version 1.7 for at least x86_64 target is very good at eliminating the bounds check in this case, recognizing that topndx is related to the `len(cmpsts), that the bounds check is therefore not necessary, thus eliminating it.

I'll leave it to @randall77 to decide about all the specific recommendations here and whether we want to tackle any of them for 1.9.

A quick update on the overall execution speed, though--things have at least been getting steadily better. For 1.7.5, 1.8.1, and tip at b53acd8:

name \ time/op  p17          p18          ptip
PrimesOdds-8    3.17ns ± 1%  2.56ns ± 1%  2.23ns ± 1%

This uses the same code as before, but converted straightforwardly into a benchmark.

package p

import (
	"math"
	"testing"
)

func primesOdds(top uint32) func() uint32 {
	topndx := int((top - 3) / 2)
	topsqrtndx := (int(math.Sqrt(float64(top))) - 3) / 2
	cmpsts := make([]uint32, (topndx/32)+1)
	for i := 0; i <= topsqrtndx; i++ {
		if cmpsts[i>>5]&(1<<(uint32(i)&0x1F)) == 0 {
			p := i + i + 3
			for j := (p*p - 3) >> 1; j <= topndx; j += p {
				cmpsts[j>>5] |= uint32(1) << (uint32(j) & 0x1F)
			}
		}
	}
	i := -1
	return func() uint32 {
		oi := i
		if i <= topndx {
			i++
		}
		for i <= topndx && cmpsts[i>>5]&(uint32(1)<<(uint32(i)&0x1F)) != 0 {
			i++
		}
		if oi < 0 {
			return 2
		} else {
			return (uint32(oi) << 1) + 3
		}
	}
}

func BenchmarkPrimesOdds(b *testing.B) {
	iter := primesOdds(1000000)
	for i := 0; i < b.N; i++ {
		iter()
	}
}

I'd love to see the Go1 suite expand. (And maybe shrink, too--I think fmt is over-represented.) I'm sure we could find a bunch of candidates (#16122 also comes to mind--recency effects). But we should do a considered, bulk addition. Would you mind filing a new issue, where we could collect a set of proposed additions and then consider them en masse?

@josharian, maybe an issue label would do here?

I think @bradfitz and @spf13 were trying to trim down labels. Let's discuss all this in a new issue so as to leave this one on-topic. I'll file one now.

My problem with the mini benchmark as per @josharian is that the timing includes the determination of the results and not just the culling of the composites as was the intention; thus, the improved results may only indicate better iteration rather than an improved tight composite culling loop that was intended to be tested.

The benchmark timing results should only include the

	iter := primesOdds(1000000)

line and not the

	for i := 0; i < b.N; i++ {
		iter()
	}

lines.

Sorry for misinterpreting. To be clear, is this the correct translation?

var sink func() uint32

func BenchmarkPrimesOdds(b *testing.B) {
	for i := 0; i < b.N; i++ {
		sink = primesOdds(1000000)
	}
}

For that, with tip at c20e545, I see a regression from 1.8 to 1.9:

name \ time/op  17          18          tip
PrimesOdds-8    978µs ± 1%  884µs ± 1%  990µs ± 2%

I see: (where tip == 1caa062)

bradfitz@gdev:~/src/issue_16192$ benchstat 1.6 tip
name          old time/op  new time/op  delta
PrimesOdds-4  4.07ns ± 1%  4.42ns ± 1%  +8.46%  (p=0.000 n=10+9)

bradfitz@gdev:~/src/issue_16192$ benchstat 1.6 1.7
name          old time/op  new time/op  delta
PrimesOdds-4  4.07ns ± 1%  4.40ns ± 1%  +8.18%  (p=0.000 n=10+10)

bradfitz@gdev:~/src/issue_16192$ benchstat 1.7 tip
name          old time/op  new time/op  delta
PrimesOdds-4  4.40ns ± 1%  4.42ns ± 1%   ~     (p=0.227 n=10+9)