9 ms·
Intel Publishes Fast AVX-512 Sorting Library, 10~17x Faster Sorts in NumPy
- Aardwolf 4y agoThanks Intel for publishing something that's useful on AMD consumer CPU's but not on Intel ones.
- RandomTisk 4y agoAFAIK Consumer Zen4 supports 12 of the 15 AVX-512 extensions, do we know for certain this doesn't target one of the ones AMD is missing?
- aseipp 4y agoThe newest extension it needs is -VBMI2, which is supported by Zen 4. -DQ and -BW are quite old and very common amongst all implementations by this point.
- paulmd 4y agozen4 supports basically everything except the xeon phi SMT4 intrinsics (4VMMW or whatever). As did alder lake before its removal. The support story for AVX extensions is not as complex as people make it out to be anyway. Server is a monotonic sequence, consumer is a monotonic sequence, both of them are converging apart from 1 or 2 that are unique to one or the other. Xeon Phi has the SMT4 intrinsics that are completely its own thing due to the SMT4 there, but you'll know if you're targeting xeon phi. https://i.imgur.com/idAjB1X.png https://i.imgur.com/idAjB1X.png So as you can see, consumer supports everything except BFloat16 for neural net training. Consumer doesn't do that so it's not a problem. And it doesn't support the Xeon Phi stuff because Xeon Phi is its own crazy thing. No uarch family in that chart has ever abandoned an extension once it was adopted. So unless you are taking a consumer application and running it in the server, it's literally not even a problem. And server gets bfloat. That's it, that's literally the only two things you have to know. but letting AMD fanboys draw le funni venn diagram is obviously way catchier than a properly organized chart representing the actual family trees involved... SSE would look bizarre if you represented it that way too, like all AMD's weird one-off SSE4 extension sets released in the middle of more fully-featured implementations... but people working in good faith would never actually be confused by that because they understand it's a different product family and year of release is not the only factor here. -- Really the thing that has been a problem is that server has been stalled out forever... first 10nm problems and now sapphire rapid has more than a dozen known steppings. They can't get the newer architectures out, so consumer has been moving ahead without them... up until alder lake nuked the whole thing. If server had been able to get newer uarchs out, there would be a lot more green bars in server too. supposedly the fab teams are actually ready to go now, and the problem is the design teams aren't used to operating in an environment where they can't go down the hall and have the fab teams fix their shit. Intel put the foot down and aren't letting them do that anymore, since the fab teams need to sell the resulting process/cell libraries to external foundry customers, and the design teams need to be able to make their shit work on external foundries. You can't do this hyper-tuned shit where the process is tweaked to make your bullshit cell designs work. But some of the teams are not mature enough to work in a portable environment where design rules actually have to be obeyed because Intel historically never had to. When you hear the infinite steppings of Sapphire Rapids and the network chip team's continued inability to put out a 2.5gbe chipset that works (I think we are on public release number 6 now?), it's pretty obvious who the worst culprits were. Meteor Lake may also be having packaging/integration problems (although this is supposition by me based on what products are delayed - coincidentally it is a lot of chiplet/tile stuff and intel obviously lacks experience in advanced packaging) but the products that have infinite steppings obviously can't get their own shit together even on their own tiles let alone talking to other people's tiles. But Intel supposedly are not kidding that Intel 4 is ready to go and they've just got nothing to run on it yet. Hence looking for outside partners. Supposedly they've got at least one definite order signed for Intel 3 in 2024, and I think there will be a lot of people happy to diversify and derisk away from the TSMC monoculture that has emerged... if TSMC stumbles, right now there is no alternative. https://www.tomshardware.com/news/intel-ifs-lands-3nm-to-make-3nm-chips-for-major-customer https://www.tomshardware.com/news/intel-ifs-lands-3nm-to-mak... Samsung has all the same conflict-of-interest problems as Intel and also a track record of really mediocre fab execution. Supposedly they are ahead on GAAFET but like... we'll see, it's Samsung, who knows. They've stumbled just as much as Intel, just not on 7nm tier - I remember the iphone "is it TSMC or Samsung" games too. Samsung has put out a lot of garbage nodes and a lot of poorly-yielding nodes of their own.
- paulmd 4y agoedit since I can't edit: "And server gets bfloat" meaning "if you were to bring a ML training server application over to consumer it might not work". Basically what I'm saying is, the only 2 situations that would be a problem is going consumer->server (which I don't see happening often) or going server ML training -> consumer if it doesn't have a non-BFloat16 fallback. And everyone does ML training on GPUs anyway. Otherwise everything supports everything. Going backwards within a family might be a problem, but, that's always a problem, it's not a support matrix problem where there's a mixture of capability, it's just backwards compatibility to older hardware with less features. The real problem, as I said, is that "Cooper Lake" there is Ice Lake-SP which was stalled for years, and by the time it was adopted Milan was already in the market and Cooper Lake was dead on arrival. So nobody actually has Cooper Lake, if you have AVX-512 server it's 99.9% chance it's either Skylake-SP or Cascade Lake-SP. Which is 100% drop-in compatible with any consumer platform that anyone has (since conveniently nobody has Cannon Lake either). The literal only problem is taking consumer applications and running them on server stuff, and there's a well-defined server compatibility set there too. -- Going forward, Sapphire Rapids is Golden Cove cores, so it should have the same support bars as Alder Lake there, ie basically everything, including server bfloat as well. https://www.phoronix.com/image-viewer.php?id=intel-sapphirerapids-avx512&image=avx512_compare_2_lrg https://www.phoronix.com/image-viewer.php?id=intel-sapphirer... (and of course the other problem being Intel has no idea what the fuck they're doing with big.LITTLE on the consumer platform... the support matrix for everything consumer-family going forward is apparently "nothing" because they've dropped AVX-512 entirely.) -- Let me drill this down to the generations you actually need to care about: (that poor PNG...) https://i.imgur.com/2HLrIjr.png https://i.imgur.com/2HLrIjr.png Like literally the AVX-512 support matrix is a complete fucking non-issue, it's an absolute tempest in a teapot by people who have never touched or looked seriously at AVX-512. The AVX-512 rollout is a dumpster fire in many many ways but an overly-complex support matrix is not one of them.
- jeffbee 4y agoNumpy is something you could expect to find running on a workstation and Intel's workstation CPU line has had AVX-512 continuously since 2017.
- mumumu 4y agoAlder Lake and Raptor Lake workstation (W680 Chipset) doesn't have AVX512 enabled.
- jeffbee 4y agoFair. The "entry workstation" thing from Intel is baffling. I was thinking Xeon W, but then of course there was the Xeon W-12xx that lacked AVX-512. In short, I was wrong. It would have been more correct to say that Intel has offered a workstation part with AVX-512 continuously since Skylake.
- bXVsbGVy 4y agoIntel released a couple days ago new Xeon-W CPUs with AVX-512. The wx-24xx uses the same p-cores as alder lake, but with avx-521 enabled. Same for wx-34xx but with raptor lake's p-core. The entry levels xeon are believed to be identical to Core ix, with the e-cores disabled and avx-512 enabled. The extra I/O and ECC support is done by the chipset. In summary, they just went to support avx-512 only on xeon w. This makes sense, since must be hard to schedule between cores with and w/o avx (the e-cores doesn't have avx).
- sliken 4y agoSad, big win for the Ryzen or future Zen 4 threadripper.
- cbsmith 4y agoThere was a longstanding issue where AVX-512 would trigger frequency throttling on a number of Intel CPUs, resulting in a net performance penalty for mixed workloads.
- 4y ago
- sliken 4y agoAssuming Intel didn't add code that's: if (AMD_CPU) { go_slow() } .... again
- mepian 4y agoIt's open-source, as the article says.
- optimalsolver 4y agoI still don't get why people think Intel is obligated to optimize AMD performance. From what I recall, it wasn't a case of slowing down AMD devices, they just didn't apply code optimizations to machines not using Intel.
- sliken 4y agoThe code literally checked for CPU = AMD, and ignore the CPU feature bits what show which accelerations are available. So sure Intel shouldn't tune for AMD, but if the AVX2 is listed as available a compiler should use it. This was proven when via some shared library trickery you could lie about the CPU name, and suddenly the AMD CPU was faster. I stumbled across this on a "Why is matlab much slower than I'd expect" thread. Lying about the CPU greatly improved performance and still showed the correct answers.
- jeroenhd 4y agoWith all the errata compilers need to correct for, I wouldn't blame the compiler for not optimising for foreign chips. Matlab chose to use a library that only works well for Intel (a simple benchmark would've shown that), I don't think Intel's compiler team should be forced to write code for AMD chips. I very much doubt AMD's driver team will optimise their OpenCL tools for Nvidia hardware either. Blame Matlab and friends for slowing down their software on your computer.
- stephencanon 4y agoIf Matlab performance is important for competitive reasons, AMD should hire a few SW engineers to build tuned linear-algebra libraries like Intel does. It’s not rocket science. They could be competitive or faster with a low-millions-per-year investment (and only slightly behind with a much smaller investment in grad students and open source). I worked on these sorts of libraries (not at Intel) for a decade, it’s very, very common to dispatch on CPU family rather than feature flags, because performance details are tied to the microarchitecture, not availability of the feature. Even though Skylake and Haswell both support AVX2 and FMA, there are huge differences in implementation that effect what the best implementation will be, so you can’t just say “oh, FMA is available, use version 37.” Instead you do “if we’re on Skylake, use the Skylake version, if we’re on Haswell, use the Haswell version, otherwise fall back on the generic runs-anywhere version.” Nothing underhanded about it.
- rektide 4y agoFor those not in the know here, Intel's actually had some fairly ok AVX-512 implementations on consumer chips in the past, even if they do cause the whole chip to downclock significantly. But for the new Alder Lake cpu, which has P/E Performance/Efficiency cores, the efficiency cores don't have AVX-512, so code would have to find a way to switch modes it runs in as it is shuffled between cores. So generally, AVX-512 is regarded as not-actually-available on Alder Lake.
- raisin_churn 4y ago> so code would have to find a way to switch modes it runs in as it is shuffled between core It's even worse than that. Initially you could disable E-cores in BIOS to get the system to report AVX-512 being available, but Intel released a microcode update to remove this workaround[0]. Intel also stated that they started fusing off the AVX-512 in silicon on later production Alder Lake chips[1]. Also compare the Ark entries for the Rocket Lake[2], Alder Lake[3], and Raptor Lake[4] flagships. Only the 11900k lists AVX-512 as an available Instruction Set Extension. So it's reasonable to say that AVX-512 on consumer Intel lines is dead for now, whereas AMD has just introduced it in the Ryzen 7000 series. [0] https://www.tomshardware.com/news/intel-reportedly-kills-avx-512-alder-lake-cpus https://www.tomshardware.com/news/intel-reportedly-kills-avx... [1] https://www.intel.com/content/www/us/en/support/articles/000089918/processors.html https://www.intel.com/content/www/us/en/support/articles/000... [2] https://ark.intel.com/content/www/us/en/ark/products/212325/intel-core-i911900k-processor-16m-cache-up-to-5-30-ghz.html https://ark.intel.com/content/www/us/en/ark/products/212325/... [3] https://ark.intel.com/content/www/us/en/ark/products/134599/intel-core-i912900k-processor-30m-cache-up-to-5-20-ghz.html https://ark.intel.com/content/www/us/en/ark/products/134599/... [4] https://ark.intel.com/content/www/us/en/ark/products/230496/intel-core-i913900k-processor-36m-cache-up-to-5-80-ghz.html https://ark.intel.com/content/www/us/en/ark/products/230496/...
- herpderperator 4y agoDoes anyone know why they would do this? If AVX-512 works fine on P-cores, and if certain people disable E-cores because they want to use AVX-512, why would they stop those who want to from being able to use it? Why would they go to such extreme lengths to disable something?
- deleted 4y ago[deleted]
- Waterluvian 4y agoIs sorting one of those things that’s so common that it deserves its own CPU hardware/instructions to aid in performance? Or does AVX-512 provide a lot of what that would theoretically be?
- cbsmith 4y agoHeck yeah. Sorting is a pretty common operation in tons of algorithms, which is why you find some form of a sort function in pretty much every language's standard runtime. Sure, this won't help much for sorting strings, but numerical sorts are still address a significant chunk of problems.
- ygra 4y agoAVX-512 is not a dedicated sorting instruction set, but rather instructions dedicated to doing the same computations in parallel over 512 bit wide registers. So you can do the same operation in the same time for 8 doubles, 16 integers, or 64 bytes at once. Coming up with good usage of those instructions can be tricky. It's not just the typical arithmetic things, but also instructions that shuffle around values in those registers based on values elsewhere and combining all that cleverly then can yield speed-ups for algorithms that deal with lots of data serially. A while ago while trying to understand all that (for the older instruction sets) I've read this CodeProject article: https://www.codeproject.com/Articles/874396/Crunching-Numbers-with-AVX-and-AVX https://www.codeproject.com/Articles/874396/Crunching-Number... – AVX-512 is basically similar, just wider. Although I've heard it has a few more useful instructions as well that have no counterpart in the older instruction sets.
- yonifei 4y agoTo add to this: A really good, digestible talk about using SIMD for sorting: https://www.youtube.com/watch?v=M6HaSvifxwQ https://www.youtube.com/watch?v=M6HaSvifxwQ You can also read the author's blog post series, beginning at https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1 https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1
- jacquesm 4y agoIt's important enough that there are whole books written about it. https://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850 https://www.amazon.com/Art-Computer-Programming-Sorting-Sear...
- mumumu 4y agoNow we only need a consumer CPU from Intel with AVX-512 enabled.
- stephencanon 4y agoRIP Icelake, we hardly knew you.
- kristianp 4y agoFor consumer cpus, you can go back to 11th Gen Intel if you want avx-512 support.[1] Not ideal, I know. [1] https://blog.reyem.dev/post/which-consumer-computers-support-avx-512/ https://blog.reyem.dev/post/which-consumer-computers-support...
- Kon-Peki 4y agoNot listed on that page is the Microsoft Surface Laptop Go, which has the same i5-1135G7 as the X1 Carbon listed. It appears that MS is clearing out their remaining stock with discounts, and they are really nice little machines with outstanding build quality, very good keyboards, and a 3:2 touchscreen. It was never a popular machine, I think it had very unfortunate naming which leads people to confuse it with other MS products. You have to think of it as something like a super-premium Chromebook to understand what it is for. But regardless, you can dump Windows and install Linux just fine.
- posnet 4y agoIt would be interesting to see it benchmarked against the highway qsort[1] Google published last year. [1] https://github.com/google/highway/tree/master/hwy/contrib/sort https://github.com/google/highway/tree/master/hwy/contrib/so...
- janwas 4y agosagarm has posted one result in another thread. I'll also look into adding their code to our benchmark :) It's great to see more vector code, but caveat for anyone using this: the pivot sampling is quite basic, just median of 16 evenly spaced samples. This is will perform poorly on skewed distributions including all-equal and very few unique values. Yes, in the worst case it can resort to std::sort but that's a >10x speed hit and until recently also potentially O(N^2)!. We have drawn larger samples (nine vectors, not one), and subsequently extended the vqsort algorithm beyond what is described in our paper, e.g. special handling for 1..3 unique keys, see https://github.com/google/highway/blob/master/hwy/contrib/sort/vqsort-inl.h#L1311 https://github.com/google/highway/blob/master/hwy/contrib/so....
- janwas 4y agoI've posted bench_sort results in another thread. vqsort is about 1.8 times as fast for uniform random 32/64-bit.
- smcl 4y agoWtf come on I was joking https://news.ycombinator.com/item?id=34803128 https://news.ycombinator.com/item?id=34803128
- garbagecoder 4y agowell, really that's basically the only place left to go at the moment. I don't think we're likely to have 10GHz any time soon or 1,024 cores either. Specialized circuits are probably all that's left before we start hitting asymptotes.
- divbzero 4y agoDedicated hardware for common algorithms is actually not very far fetched. In addition to GPUs, we already have examples of HSMs [1] and TPUs [2] that optimize for specific cryptographic and machine learning operations. [1]: https://en.wikipedia.org/wiki/Hardware_security_module https://en.wikipedia.org/wiki/Hardware_security_module [2]: https://en.wikipedia.org/wiki/Tensor_Processing_Unit https://en.wikipedia.org/wiki/Tensor_Processing_Unit
- orangeoxidation 4y agoThere's video de- and encoding as well.
- formerly_proven 4y agoIntel has dedicated gzip hardware in QAT among a few other hardware blocks.
- contravariant 4y agoPretty sure the internet exists by virtue of algorithm specialized hardware.
- erk__ 4y agoWell it does already exist https://www.ibm.com/docs/en/zos/2.5.0?topic=works-integrated-accelerator-z-sort https://www.ibm.com/docs/en/zos/2.5.0?topic=works-integrated...
- Blackthorn 4y agoThanks Intel! Now maybe you can release some processors for those of us at home, that actually have AVX-512!
- hummus_bae 4y agoPlease.
- fancyfredbot 4y agoAVX-512 is wide enough to process 8 64 bit floats at once. To get a 10x speedup with an 8 wide SIMD unit is a little difficult to explain. Some of this speedup is presumably coming from fewer branch instructions in addition to the vector width. It's extremely impressive. Also, it has taken Intel a surprisingly long time!
- adgjlsfhk1 4y agoavx512 also gives you 2x more register space which can be very useful.
- dragontamer 4y agoL1 cache on Intel machines reads/writes in 512-bit chunks. So you get a 2x faster L1 cache when working with AVX512 on Intel IIRC. Or perhaps more accurately: L1 cache that can process twice the data in the same amount of time.
- deleted 4y ago[deleted]
- usrusr 4y agoThat sounds suspiciously as if an implementation tailored to that cache line size might see a considerable part of the speedup even running on non-SIMD operations? (or on less wide SIMD)
- lallysingh 4y agoAlmost any array-math implementation that's aware of cache sizes is going to outperform the ones that don't. By a heavy margin.
- eklitzke 4y agoPeople already do optimizations like this all the time, when they're working on low-level code that can benefit from it. Sorting is actually a good example, all of the major sort implementations typically use quicksort when the array size is large enough and then at some level of the recursion the arrays get small enough that insertion sort (or even sorting network) is faster. So sorting a large array will use at least two different sorting methods depending on what level of recursion is happening. You can get information about the cache line sizes and cache hierarchy at runtime from sysfs/sysconf, but I don't think many people actually do this. Instead they just size things so that on the common architectures they expect to run on things will be sized appropriately, since these cache sizes don't change frequently. If you really want to optimize things, when you compile with -march=native (or some specific target architecture) GCC/Clang will implicitly add a bunch of command line flags to the compiler invocation that set up different preprocessor defines that expose information about the cache sizes/hierarchy for the target architecture.
- doctor_eval 4y agoI read that as 10^17 times faster sorts and I thought to myself, now that’s news!
- maxioatic 4y ago"Intel has decided that CPUs no longer should sort, and instead will return original arrays in constant time. This has shown to have a 10^17 performance increase in some benchmarks."
- sylware 4y agoThis is probably the vectorized quicksort. I remember the paper detailing the algorithm here on HN. Since then, I know that if I really need to sort numbers very fast one day, I would have to learn the vectorized way to quicksort. I would probably write it directly in assembly though, with a C API (coze tinycc, cproc, scc...)
- sagarm 4y agoOn an Ice Lake GCE instance, Highway's vqsort was 40% faster when sorting uint64s. vqsort also doesn't require avx512, and supports a wider array of types (including 128-bit integers and 64-bit k/v pairs), so it's more useful IMO. It's a much heavier weight dependency though. Code / scripts here: https://github.com/funrollloops/parallel-sort-bench https://github.com/funrollloops/parallel-sort-bench I had to use a cloud instance for testing since I don't have an avx512-capable personal machine.
- janwas 4y agoThanks for sharing the benchmark :D Is there anything we could do to make Highway/vqsort (feel like) a lighter dependency?
- sagarm 4y agoI made that comment because the Intel library is header only. While header only libraries can be convenient, for non-trivial projects I prefer a well engineered CMake-based build for better compile times.
- janwas 4y agoGot it. Highway is mostly header-only and we can move towards fully if anyone is interested. We also have a CMake build, not sure about well-engineered but patches welcome from anyone with more CMake expertise :)
- fwsgonzo 4y agoI think as long as FetchContent works it's super easy to try out your library and see if its something that should be pulled in as a real dependency. I have heard that FetchContent can make something unreliable, as in dependent on having a connection, but I think it opens up the door for a lot of people to be willing to try it :) (That, and you can turn off mandatory updates, making it work offline too). I think the basic rule for making FetchContent work is to just put the CMakeLists.txt in the root directory and then make sure that you can use the project as a CMake sub-project.
- mekpro 4y agoThe ironic part is the latest Intel CPU no longer support AVX-512 and AMD now provide better AVX-512 CPU implementation in Zen 4. https://www.anandtech.com/show/17047/the-intel-12th-gen-core-i912900k-review-hybrid-performance-brings-hybrid-complexity/2 https://www.anandtech.com/show/17047/the-intel-12th-gen-core... https://www.phoronix.com/review/amd-epyc-9004-genoa https://www.phoronix.com/review/amd-epyc-9004-genoa
- ivegotnoaccount 4y agoIsn't it on their consumer lines only that Intel removed AVX-512? Saphire Rapids is indicated as having support for it. I know that even though you pointed to an EPYC CPU, all Zen4 support it, but Intel probably released it more for the professional users than their non-pro ones.
- WJW 4y agoYes it's only the Alder Lake (ie cheaper, consumer oriented CPUs) in which it has been removed. Server chips still have it AFAIK. Even on Alder Lake, the official explanation is that it has both P(erformance) and E(fficiency) cores, with the E cores being significantly more power efficient and the P cores being significantly faster. The P cores have AVX512, the E cores don't. Since most kernels have no idea that this is a thing and treat all CPUs in a system as equal, they will happily schedule code with AVX512 instructions on an E core. This obviously crashes, since the CPU doesn't know how to handle those instructions. Some motherboard manufacturers allowed you to work around this by simply turning off all the E-cores, so only the P-cores (with AVX512 support) remained. Intel was not a fan of this and eventually disabled AVX512 in hardware. As ivegotnoaccount mentioned, the Sapphire Rapids range of CPUs will have AVX512. Those are not intended for the typical consumer or mobile platform though, but for servers and big workstations where power consumption is much less of a concern. You would probably not want such a chip in your laptop or phone.
- pantalaimon 4y agoIt would have been possible to devise a system call to 'unlock' AVX512 for an application that wants to use it, which would pin it to only be scheduled on P cores.
- ww520 4y agoWhat is the speedup compared against? Is it compared against non-avx code? Or is it compared against avx2 (256-bit)? From my experience, vectorizing with avx2 can speed up 3x-10x against non-avx operations depending on the data. The operations involved are things like finding common prefix or searching in string.
- kristianp 4y agoI expect this is only for data that fits in L1 cache. Sorts are memory-constrained once you exceed cache size.
- janwas 4y agoBenchmark results using vqsort's bench_sort on Skylake workstation (patch: https://github.com/google/highway/pull/1140 https://github.com/google/highway/pull/1140) vqsort is about 1.9x and 1.8x as fast on 1M keys and 100M uniform random keys, respectively. Note that this code did not pass the benchmark's verification. AVX3: vq: i32: uniform32: 1.00E+06 1051 MB/s ( 1 threads) AVX3: intel: i32: uniform32: 1.00E+06 539 MB/s ( 1 threads) AVX3: vq: i64: uniform32: 1.00E+06 1000 MB/s ( 1 threads) AVX3: intel: i64: uniform32: 1.00E+06 500 MB/s ( 1 threads) AVX3: vq: i32: uniform32: 1.00E+08 614 MB/s ( 1 threads) AVX3: intel: i32: uniform32: 1.00E+08 345 MB/s ( 1 threads) AVX3: vq: i64: uniform32: 1.00E+08 584 MB/s ( 1 threads) AVX3: intel: i64: uniform32: 1.00E+08 314 MB/s ( 1 threads)