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

Using the most unhinged AVX-512 instruction to make fastest phrase search algo

gab-menezes.github.io

Post reply on HN
Print view View original

51–60 of 62 posts

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#51

Post by cesarb »

p_l wrote: post #27
adrian_b wrote: post #26

Earlier quoted context omitted.

They had to disable AVX-512 only because Microsoft was too lazy to rewrite their thread scheduler to handle heterogeneous CPU cores. The Intel-AMD x86-64 architecture is full of horrible things, starting with the System Management Mode added in 1990, which have been added by Intel only because every time Microsoft has refused to update Windows, expecting that the hardware vendors must do the work instead of Microsoft…

Windows can work without SMM, especially NT - the problem is that SMM was created for a world where majority used DOS and the idea of using OS services instead of every possibly quirk of IBM PC was anathema to developers. Thus, SMM, because there was no other way to hook power management on a 386 laptop running " normal" DOS

> Thus, SMM, because there was no other way to hook power management on a 386 laptop running " normal" DOS

In theory, there was: you could have a separate microcontroller, accessed through some of the I/O ports, doing the power management; it's mostly how it's done nowadays, with the EC (Embedded Controller) on laptops (and nowadays there's also the PSP or ME, which is a separate processor core doing startup and power management for the main CPU cores). But back then, it would also be more expensive (a whole other chip) than simply adding an extra mode to the single CPU core (multiple cores back then usually required multiple CPU chips).

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#52

Post by slashdev »

nemoniac wrote: post #44

Fascinating blog post. Having said that, it may seem like nitpicking but I have to take issue with the point about recursion, which is often far too easily blamed for inefficiency. The blog post mentions it as one of the reasons for the inefficiency of the conventional algorithm. A glance at the algorithm shows that the recursion in question is a tail call. This means that any overhead can be readily eliminated using…

A lot of modern programming languages do not do tail call optimization, often citing keeping accurate stack history for debugging as an excuse.

Regardless of how valid the excuse is, for such an obvious and old optimization, it’s very poorly supported.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#53

Post by cesarb »

slashdev wrote: post #52
nemoniac wrote: post #44

Fascinating blog post. Having said that, it may seem like nitpicking but I have to take issue with the point about recursion, which is often far too easily blamed for inefficiency. The blog post mentions it as one of the reasons for the inefficiency of the conventional algorithm. A glance at the algorithm shows that the recursion in question is a tail call. This means that any overhead can be readily eliminated using…

A lot of modern programming languages do not do tail call optimization, often citing keeping accurate stack history for debugging as an excuse. Regardless of how valid the excuse is, for such an obvious and old optimization, it’s very poorly supported.

The main problem with tail call optimization is that it's unreliable; small apparently unrelated changes elsewhere in the function, a difference in the compiler command line flags, or a different compiler version, could all make a tail call become a non-tail call. Some languages have proposed explicit markers to force a call to be a tail call (and generate a compilation error if it can't), but I don't think these proposals have been adopted yet.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#54

Post by irthomasthomas »

iamnotagenius wrote: post #3

Imo the most "unhinged" cpus for AVX-512 are early batches of Alder Lakes which is the only cpu family that has nearly full coverage of all existing avx-512 subsets.

I think I have two of these sitting in a box, one prototype with avx512 and one retail without. Is it worth me breaking these out for ML experiments and such?

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#55

Post by bri3d »

queuebert wrote: post #47
nemoniac wrote: post #44

Fascinating blog post. Having said that, it may seem like nitpicking but I have to take issue with the point about recursion, which is often far too easily blamed for inefficiency. The blog post mentions it as one of the reasons for the inefficiency of the conventional algorithm. A glance at the algorithm shows that the recursion in question is a tail call. This means that any overhead can be readily eliminated using…

Dumb question: does modern stack layout randomization affect the efficiency of recursion? On first glance I would be worried about cache misses.

Not specifically address space layout randomization in the way it's usually implemented; ASLR as applied in most modern production OSes randomizes each stack's base address, but each stack is still laid out and used in a normal way. There are some research projects towards actual stack layout randomization (involving stack rearrangement via static analysis, randomly sized stack padding frames, and other techniques) which would also definitely blow up cache, but none that are mainstream in a production system as far as I know.

However, for the naive case where the recursion is a full-blown function call, without some kind of optimization, other security mitigations than ASLR will significantly affect the efficiency of recursion by adding function call overhead (and possible cache side effects) - for example, the stack cookie will still be verified and control-flow guard checks and the shadow/return stack will still be in play, if present.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#56

Post by yorwba »

> Why are you merging up to one rare token at the beginning or at the end? Let’s consider that someone searched for C_0 R_1 C_2 C_3. If we don’t do this merge, we would end up searching for C_0, R_1, C_2 C_3, and this is bad. As established, intersecting common tokens is a problem, so it’s way better to search C_0 R_1, C_2 C_3. I learned this the hard way…

But since R_1 C_2 C_3 is in the index as well, instead of searching for C_0 R_1, C_2 C_3 with a distance of 2, you can instead search for C_0 R_1, R_1 C_2 C_3 with a distance of 1 (overlapping), which hopefully means that the lists to intersect are smaller.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#57

Post by iamnotagenius »

Aurornis wrote: post #16
Namidairo wrote: post #14

Earlier quoted context omitted.

It's a shame that Intel seemed to really not want people to use it, given they started disabling the ability to use it in future microcode, and fused it off in later parts.

> It's a shame that Intel seemed to really not want people to use it AVX-512 was never part of the specification for those CPUs. It was never advertised as a feature or selling point. You had to disable the E cores to enable AVX-512, assuming your motherboard even supported it. Alder Lake AVX-512 has reached mythical status, but I think the number of people angry about it is far higher than the number of people who e…

I use AVX-512 on Alder and it does not increase the voltage above AVX-2 voltages, and even then power dissipation is considerably lower than AVX-2.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#58

Post by theandrewbailey »

adgjlsfhk1 wrote: post #17
iamnotagenius wrote: post #3

Imo the most "unhinged" cpus for AVX-512 are early batches of Alder Lakes which is the only cpu family that has nearly full coverage of all existing avx-512 subsets.

What about Zen5?

AMD advertised and enabled AVX-512 on all Zen 5 CPUs. You have to resort to workarounds to get AVX-512 working on Alder Lake.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#59

Post by p_l »

cesarb wrote: post #51
p_l wrote: post #27

Earlier quoted context omitted.

Windows can work without SMM, especially NT - the problem is that SMM was created for a world where majority used DOS and the idea of using OS services instead of every possibly quirk of IBM PC was anathema to developers. Thus, SMM, because there was no other way to hook power management on a 386 laptop running " normal" DOS

> Thus, SMM, because there was no other way to hook power management on a 386 laptop running " normal" DOS In theory, there was: you could have a separate microcontroller, accessed through some of the I/O ports, doing the power management; it's mostly how it's done nowadays, with the EC (Embedded Controller) on laptops (and nowadays there's also the PSP or ME, which is a separate processor core doing startup and powe…

The problem is reliably interrupting the CPU in a way that didn't require extra OS support. SMM provided such trigger, and in fact is generally used as part of the scheme with EC cooperating.

Re: Using the most unhinged AVX-512 instruction to make fastest phrase search algo

#60

Post by p_l »

kccqzy wrote: post #48
p_l wrote: post #27

Earlier quoted context omitted.

Windows can work without SMM, especially NT - the problem is that SMM was created for a world where majority used DOS and the idea of using OS services instead of every possibly quirk of IBM PC was anathema to developers. Thus, SMM, because there was no other way to hook power management on a 386 laptop running " normal" DOS

If Windows could work without SMM, is there a historical reason why SMM mode didn't just die and become disused after Windows becomes popular and nobody uses DOS any more? There are plenty of features in x86 that are disused.

The feature turned out too useful for all sorts of things, including dealing with the fact that before NT loaded itself you still had to emulate being an IBM PC including the fiction of booting from cassette tape or jumping to ROM BASIC.

Also, it's been cheaper to implement various features through small piece of code instead of adding a separate MCU to handle them, including prosaic things like handling NVRAM storage for variables (instead of interacting with external MCU or having separate NVRAM, you end up with SMM code being "trusted" to update the homogenous flash chip that contains both NVRAM and boot code)

Post reply on HN