ARM64 Popcount in Golang and Assembler | Hacker News Reader

ARM64 Popcount in Golang and Assembler

barakmich.dev

93 pointsfanf244 comments

FWIW, I learned a little bit about how to check for supported features in x86_64 from the linked code (I added the comments):

    TEXT ·hasPOPCNT(SB),NOSPLIT,$0
     XORQ AX, AX     ; AX <- 0
     INCL AX         ; AX <- 1
     CPUID           ; check cpu caps
     SHRQ $23, CX    ; shift bit 23 to bit 0 (bit 23 => POPCNT support)
     ANDQ $1, CX     ; examine bit 0
     MOVB CX, ret+0(FP)  ; return 1 iff POPCNT instruction supported
     RET

It seems Intel CPU's have such a bloated and varied instruction set you have to query to see what flavor of CPU you have to create portable code. Writing compilers for this must be a real pain.

Full disclosure : I work for Intel

> It seems Intel CPU's have such a bloated and varied instruction set you have to query to see what flavor of CPU you have to create portable code. Writing compilers for this must be a real pain.

This is equally applicable to other x86 vendors.

The alternatives are either (a) never introducing new instructions, or (b) making portable binaries impossible. Neither alternative seems better? It doesn't look quite as tortured in C:

  bool has_popcnt() {
    unsigned regs[4];
    cpuid(1, regs);
    // You could name 23 CPUID_POPCOUNT_SHIFT or something.
    return ((regs[2] >> 23) & 1);
  }

In normal C compilers (GCC, Clang) you can use ifuncs to do this resolution once at module load time, and then the correct function for the current CPU is dispatched cheaply afterwards.

Yes, adding features to a CPU is not a vendor specific problem. I wonder if this can be handled at the link / binary loader level so it is more transparent to the programmer. Almost like a patch using diff. You have a base binary that runs on any machine, but there are added diffs (added by the static linker) for different CPU versions and the OS loader patches and loads the code appropriately.

https://gcc.gnu.org/wiki/FunctionMultiVersioning helps make this somewhat ergonomic, although it's still manual.

These SIMD instructions are low-level micro-optimizations. Abstract an instruction behind a function call, and even for the very best case when all source data is already in correct registers and no need to save or restore anything, that indirect jump is likely to take the time comparable to the instructions being used there.

One way to do it in C++, implement dispatching at higher level, where the function being dispatched takes much more time than a call overhead. Sometimes C++ templates or even C preprocessor can help reduce copy-pasting.

Another way to do it is JIT from byte code. .NET tries to do that, I don’t think it’s too efficient currently, but I believe couple major versions in the future it might actually become good. It doesn’t have performance budget for expensive optimization modern C++ compilers do in optimized release builds. OTOH there’re other optimizations unavailable in C++: JIT may use whatever max AVX version is present, may compile immutable or rarely changing input data into code.

> This is equally applicable to other x86 vendors.

I think it's equally applicable to any processor vendor, x86 has just been around the longest.

It's actually particularly shitty on x86, because, unlike SSE2, it has been added after AMD64 came around, and thus you can't necessarily assume its existence on a random 64-bit CPU.

Meanwhile any ARM64 CPU will have CNT.

While CPUID itself is far from elegant, I don't think ARM is fundamentally different. e.g., the ID_AA64ISAR1_EL1 register (ARM wins no naming awards here) indicates the presence of certain instructions.

https://developer.arm.com/docs/ddi0595/h/aarch64-system-regi...

aarch64 is actually worse as far as I can tell because reading from that register is restricted and cannot be done from userspace (hence "EL1") and thus doing this portably is a huge pain. On Linux I think some of this is exported via /proc/cpuinfo and auxval, so that's what most people use…

Edit: Also there's a ton of them, this lists a couple: https://www.kernel.org/doc/html/latest/arm64/cpu-feature-reg...

It makes good sense for the OS to abstract this for a few reasons:

- You'll get into trouble when migrating a process between cores in heterogeneous environments (having cores that support different ISA extensions is relatively uncommon today, but Intel has already announced some, and people have gotten into trouble in the past with e.g. reading cacheline sizes when big and little cores used different values).

- This can be a pretty slow operation on some platforms, and the system can make it more efficient by caching it (and can provide additional capabilities information that may not have existed on older CPUs so that there's a uniform interface).

I remember when that came up–I still don't understand how you are supposed to support a process that has queried the kernel for some feature ("can I use SVE2?"), gets an affirmative response, starts using that, and midway gets migrated to another core that doesn't support those instructions? Either you're going to either have the same extensions on all the cores, or lie about it by presenting the lowest common denominator to each of them…although I guess if you did want to do that, you'd want the kernel to be able to fake this from the start.

One approach could be that the OS pins the process or threads to cores that support the features that were queried for.

i.e: If a process asks "can I use SVE2" and gets a yes, the OS doesn't move it to any core for which that isn't true.

Right, but as I mentioned here: https://news.ycombinator.com/item?id=23835764 (and last month: https://news.ycombinator.com/item?id=23481049) every process is going to ask this…

Ah, that's very a good point.

Alternatively, an invalid instruction fault is signaled, handled by the OS, which activates the core capable of that instruction and migrates the process there. Not cheap, but I would expect that to happen rarely, if the lesser core is only used during low-power operation.

Yeah, but that means that every process is going to forced to run on the big core the moment that you call into libc's vectorized string functions…

There are similar issues for any suspend-able and/or hot-swappable system. An extension to process signals should be created to inform them that a system-context change has occurred. Clock timestamps, features, all assumptions should be invalidated.

Yeah, but then programs have to know about that. Up until now the general assumption has been that context switches are largely transparent…

I think Intel is going the lie about it route for their first “hybrid” chip.

Nah, they just disable all the features that aren't shared by the little cores.

That's the "lie about it" route I mentioned above.

Usually what a compiler will do is target some "reasonable" CPU from the past, for your choice of "reasonable". For example, the C compiler on my system defaults to Penryn.

Unrelated: what does Intel Sports do?

Immersive viewing of sporting events: https://www.intel.com/content/www/us/en/sports/sports-overvi...

Why does it use SHRQ, ANDQ & MOVB, instead of a BT & SETB ?

Good question. The instruction set is so large and is not orthogonal and it difficult to know the "best way" to do things. I am always perplexed at the instruction selection compilers make, but the compiler writers are often pretty clever.

> Take whichever side you want in the Intel vs GNU syntax debate, creating a third option means relearning all the quirks from scratch, and ignoring any documentation that already exists.

Isn't the "Intel vs GNU syntax debate" only on x86? For ARM, AFAIK there's only one assembly syntax.

ARM assembly and GNU assembly for ARM are subtly different in terms of syntax. I think the labels and indenting is different but everything else is broadly the same. I can happily read either.

Slight tangent, but writing custom assembler code to make this go faster on the ARM chip makes me wonder how much optimization the Apple team has put into the Swift compiler for the A-series, work that has been going on for years for iOS. I suspect the answer is "a lot more than we realize" and it would be interesting to see this Golang comparison re-run on macOS/ARM (when available) and then compared to the same program written in Swift.

Apple has (or will be) submitting ARM patches for the Go project.

https://twitter.com/wongmjane/status/1275177255681982464?lan...

Compulsory popcount resources from Wojciech Mula http://0x80.pl/articles/sse-popcount.html

Nice link, thanks!

My interest in popcount is for radix trie node compression https://dotat.at/prog/qp/ so these bulk popcount hacks are interesting but not directly useful for my purposes :-)

There is also a C library based on it: https://github.com/kimwalisch/libpopcnt

Erm, math/bits package OnesCount() family of functions?

https://golang.org/pkg/math/bits/#OnesCount

go compiler output...

0x0020 00032 ($GOROOT/src/math/bits/bits.go:115) FMOVD R0, F0

0x0024 00036 ($GOROOT/src/math/bits/bits.go:115) VCNT V0.B8, V0.B8

0x0028 00040 ($GOROOT/src/math/bits/bits.go:115) VUADDLV V0.B8, V0

I would have expected the Go compiler to emit the POPCNT instruction on it's own. Most current C compilers will even detect if you implement a popcount in software and replace it with a single POPCNT instruction - why does Go not do something like that as well?

Go's compiler is not particularly sophisticated.

(By design.)

Because Go Gc amd64 target supports CPUs that do not have support for the popcnt instruction and runtime detection + checking a bool around each popcnt instruction is a big overhead. There is no mtune or march for Go Gc amd64 like (Go) gcc does.

Huh, TIL. I always assumed this to be a rather old instruction, but turns out it was only added fairly recently on x86

https://vaibhavsagar.com/blog/2019/09/08/popcount/

Go's compiler values being fast over potential optimizations, I believe, so this might be something that they don't think is something the compiler should do.

Wow. This is the first time I have seen Go Assembler Syntax, and it confused me at first, as I thought it was the standard Intel syntax.

  __builtin_popcount()

... which gcc and clang will replace with best available.

'nuff said.

Edit: or OnesCount() in Go.

Any clues on what they author is using it for?

There’s a few potential uses these days - more than just the famous crypto folklore one! Some examples on https://vaibhavsagar.com/blog/2019/09/08/popcount/

https://news.ycombinator.com/item?id=23832978

Reply on news.ycombinator.com