Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The NSA Instruction (2019)

vaibhavsagar.com

Post reply on HN
Print view View original

91–98 of 98 posts

Re: The NSA Instruction (2019)

#91

Post by djmips »

PhantomGremlin wrote: post #89
CalChris wrote: post #53

Earlier quoted context omitted.

Gimme dem modern wide supercalar OOO cached chickens, please. Cray was right back then but he is no longer right now. If he were, the market would say so.

Cray is still right. Today we know how to put 16 4 GHz CPUs on a single die. If we want, we can hook chips together to build a computer with 16,384 CPUs. But we can't build a single chip running usefully at 16x4 GHz. We can't build a single system running at 16384x4 GHz. If we could build that fast chip or system, all else being equal, the market would choose the single fast CPU over the pile of slow CPUs. Right now…

Thanks for the post but you can't in all fairness keep your "Cray is still right" opening statement when you go on to agree that in reality, which is what is important, we have to settle for lots of chickens.

Re: The NSA Instruction (2019)

#92

Post by ncmncm »

jart wrote: post #90
ncmncm wrote: post #78

Earlier quoted context omitted.

Yet, practically all software running on 64-bit x86 machines is compiled without, because the original amd64 released in 2003 lacked it, and distributions still target that. Likewise, MSVC. There would be good reasons for Apple XCode not to, but that doesn't mean they don't. If you tell MSVC to issue a popcount instruction with "__popcnt64()" (etc.), it will. If you ask Gcc to issue a popcount instruction with "__bui…

Try the Cosmopolitan Libc implementation of popcnt(). It uses CPUID checks for compatibility which get hoisted out of a tight loop by the optimizer so there's no performance loss when building for -march=k8. If you build for -march=native then they get DCE'd entirely. See https://github.com/jart/cosmopolitan/blob/master/libc/bits/p...

Because of a bug in a bunch of Intel chips, something like the following is probably better.

      asm(
  "mov\t%1,%0\n"
  "popcnt\t%1,%1"
    : "=r"(Res) : "r"(Pop) : "cc");
(assuming intel syntax)

Re: The NSA Instruction (2019)

#93

Post by PhantomGremlin »

djmips wrote: post #91
PhantomGremlin wrote: post #89

Earlier quoted context omitted.

Cray is still right. Today we know how to put 16 4 GHz CPUs on a single die. If we want, we can hook chips together to build a computer with 16,384 CPUs. But we can't build a single chip running usefully at 16x4 GHz. We can't build a single system running at 16384x4 GHz. If we could build that fast chip or system, all else being equal, the market would choose the single fast CPU over the pile of slow CPUs. Right now…

Thanks for the post but you can't in all fairness keep your "Cray is still right" opening statement when you go on to agree that in reality, which is what is important, we have to settle for lots of chickens.

That's a good point. The "strong oxen" Cray was originally talking about are now totally unachievable, compared to settling for lots of chickens.

Re: The NSA Instruction (2019)

#94

Post by 4gotunameagain »

solarexplorer wrote: post #36
4gotunameagain wrote: post #12

Earlier quoted context omitted.

Looks like we've done similar things :) Horror story: I was once developing a TRN system for a spacecraft instrument which uses an ancient x86 processor that does not have popcnt, ended up using a look-up table instead...

Did you know about HAKMEM 169? I guess it was/is not widely known since many people mention lookup tables as the only fast alternative to the popcnt instruction. http://www.hakmem.org/#item169

That's interesting, thanks.

It seems that look up tables are still faster when memory allows it though (http://www.dalkescientific.com/writings/diary/archive/2008/0...)

Re: The NSA Instruction (2019)

#95

Post by ynik »

ncmncm wrote: post #78
dragontamer wrote: post #47

Earlier quoted context omitted.

> But if you need to implement popcount or many other bit manipulation algorithms in software Power9, ARM, x86 BMI, Nvidia PTX, AMD GCN, and AMD RDNA all have a popcount instruction. Yeah, all mainstream CPUs and GPUs made in the past decade... Unfortunately, there's no system I can think of where you'd need the software solution anymore... Maybe if you wanted popcount on an Arduino??

Yet, practically all software running on 64-bit x86 machines is compiled without, because the original amd64 released in 2003 lacked it, and distributions still target that. Likewise, MSVC. There would be good reasons for Apple XCode not to, but that doesn't mean they don't. If you tell MSVC to issue a popcount instruction with "__popcnt64()" (etc.), it will. If you ask Gcc to issue a popcount instruction with "__bui…

C++20 added std::popcount() in the new header

If you haven't told it that the target ISA has the POPCNT instruction, std::popcount() on MSVC will use runtime feature detection: https://godbolt.org/z/qab4Mjv1v

Re: The NSA Instruction (2019)

#96

Post by ncmncm »

ynik wrote: post #95
ncmncm wrote: post #78

Earlier quoted context omitted.

Yet, practically all software running on 64-bit x86 machines is compiled without, because the original amd64 released in 2003 lacked it, and distributions still target that. Likewise, MSVC. There would be good reasons for Apple XCode not to, but that doesn't mean they don't. If you tell MSVC to issue a popcount instruction with "__popcnt64()" (etc.), it will. If you ask Gcc to issue a popcount instruction with "__bui…

C++20 added std::popcount() in the new header If you haven't told it that the target ISA has the POPCNT instruction, std::popcount() on MSVC will use runtime feature detection: https://godbolt.org/z/qab4Mjv1v

Curiously, for std::bitset(i).count(), MSVC (VS 16.9) still generates a loop, regardless.

Re: The NSA Instruction (2019)

#97

Post by avianes »

ncmncm wrote: post #77

It is appalling that, after every other general-computing architecture in common use either started out with a popcount instruction, or had one added later at substantial expense, RISC-V came out without one. It still doesn't have any. The proposed B, "bitmanip" extension has it (along with a raft of trivial variations: count leading zeroes, count trailing ones, yada yada) but that is not ratified and not implemented…

> It should have been in the base instruction set.

No, it should not. Popcount is not necessary for all the microcontrollers and it does not fully share its circuitry with the other instructions of the basic ISA.

Popcount must be in an extension (like bitmanip) and it will be ratified and integrated into chips soon. The 1.0 version of the B extension is currently under review and is much simpler than the previous versions.

Re: The NSA Instruction (2019)

#98

Post by jart »

ncmncm wrote: post #92
jart wrote: post #90

Earlier quoted context omitted.

Try the Cosmopolitan Libc implementation of popcnt(). It uses CPUID checks for compatibility which get hoisted out of a tight loop by the optimizer so there's no performance loss when building for -march=k8. If you build for -march=native then they get DCE'd entirely. See https://github.com/jart/cosmopolitan/blob/master/libc/bits/p...

Because of a bug in a bunch of Intel chips, something like the following is probably better. asm( "mov\t%1,%0\n" "popcnt\t%1,%1" : "=r"(Res) : "r"(Pop) : "cc"); (assuming intel syntax)

Thanks you just helped tons of my code go faster. Turns out false output dependency is a much bigger issue for bsr and bsf with 32-bit operands since it impacts all models and GCC builtins like __builtin_clz(x)^31 won't xor the output unless you use -march=native. So once again I find myself replacing compiler apis with stallman notation. For what it's worth:

    asm("popcnt\t%0,%0" : "=r"(res) : "0"(pop) : "cc");
Can generate the mov statement automatically.
Post reply on HN