worth mentioning that "NP" is not "non-polynomial" but "non-deterministic polynomial (time)". If NP was non-polynomial time then NP != P would be trivial (and in fact, P != EXP is known by the time hierarchy theorem).
Non-deterministic can be explained in several ways. One is in terms of a hypothetical "nondeterministic Turing machine" with certain non-physically realizable properties. The easier way is that a NP problem gets as input not only the problem instance x, but a "witness" w, that may depend on the problem instance. This witness generally makes the problem of deciding the problem instance straightforward (e.g. for SAT, x is the SAT instance, and w is a description of how to set the variables so that it is true).
To be fair - there are statements in math that are independent of the axioms. For those statements, the universe you find yourself in can pick either version (true OR false) and still be consistent.
See also: noneuclidian geometry and axiom of choice.
Being able to solve NP hard optimization problems would enable progress in many areas of science and technology. For example it would allow us to find poly-sized Lean proofs for theorems efficiently, since proof verification can be done in polynomial time.
It would also be amusing to annihilate nearly six decades of proofs that assume P!=NP.
Leans proof checker is not polynomial time, unfortunately. It is super exponential. Basically, because it can verify the result of any function it can prove to be total.
to depress you even more, it is consistent with everything that we know that P != NP and that cryptography does not exist. So there is a worst of both worlds, and we cannot rule it out.
Of course, if we get ridiculous polynomials it doesn't mean much in practice. People who hope for P=NP generally hope for nice polynomials O(n^3) or something like that at worst.
Even worse, in a brownfield codebase that was once fairly light with comments, that's now being subject to these modifications, the insane amounts of commentary around the parts newly touched by AI lead to an excessive emphasis on those parts, for both human and AI readers (who think, well if this one part is commented so thoroughly, it must be unusually subtle)
You can do even a bit better if you're willing to use intrinsics. In particular this kind of operation is well-suited for compress-type operations, available as a first-class operation in at least AVX512, SVE and RVV; you can also emulate them reasonably quickly on NEON and AVX2.
Here's an example, building on the OP's work:
pub fn filter_compress(input: &[f64], threshold: f64) -> Vec<f64> {
use std::arch::x86_64::*;
let mut out = vec![0.0; input.len()];
let mut n = 0usize;
let (head, tail) = input.as_chunks::<8>();
for chunk in head {
unsafe {
let p = _mm512_loadu_pd(chunk.as_ptr());
let m = _mm512_cmpnle_pd_mask(p, _mm512_set1_pd(threshold));
let compress = _mm512_maskz_compress_pd(m, p);
_mm512_storeu_pd(out.as_mut_ptr().wrapping_add(n), compress);
n += m.count_ones() as usize;
}
}
for &x in tail {
out[n] = x;
n += (x > threshold) as usize;
}
out.truncate(n);
out
}
For me it's about 25% less time than the branchless version with 1,000,000 elements, and 60% less with 10,000 elements where memory bandwidth effects are less relevant.
Nice! I saw the code and thought, I bet there’s a way to do some SIMD here… never touched intrinsics in Rust before so I really appreciate you writing it up!
Memory access patterns are usually the main reason for low performance and should be optimized first because it's a great low hanging fruit (and usually the bigger problem is latency, not bandwidth).
And don't think of waiting for memory as making CPU optimizations irrelevant, but instead as an oppurtinity to hide more CPU operations in the remaining 'memory access gaps' (e.g. the CPU won't simply stop working when waiting for data to be loaded from memory, it can continue with other things that don't depend on that data).
Good question. I personally doubt that the compress instruction is easy to coax compilers into generating, as there are many edge cases to consider.
For example, you'll notice here that we perform a full vector store of 8 elements unconditionally, even if only a few of the elements are active. This is safe, though, because the output buffer is as large as the input buffer, and we're chunking by 8, so we'll never trash memory past the end; but this is a tricky analysis. Performance-wise, we rely on the CPU's store buffer to make these overlapping stores cheap.
Instead, you might think that you could just store the elements which are actually active, using a masked store. In fact there is also an intrinsic for this purpose (_mm512_mask_compressstoreu_pd), but it is extremely slow on some CPUs, namely Zen 4, so it's dangerous to use unless you know exactly what CPU you're using. (In my testing, there also seems to be some weird hazard on Zen 5 where multiple memory-destination compress instructions to nearby, even non-overlapping, addresses are serialized. But I haven't looked closer at this.)
I think WUFFS "iterate loops" might help. WUFFS requires that processing a chunk of N items has code to process one at a time, which means it'll work for any N. However you can optionally provide specialisations for doing K at a time and the compiler is responsible for carving the input up as appropriate so e.g. N = K + K + 1 + 1 + 1 your K-at-a-time code runs twice, the extras are handled 1-at-a-time.
So this divides up the problem, the compiler can vectorize your 8-at-a-time code without needing to handle edge cases where N isn't a multiple of 8, and if a later pass notices we actually never end up using those edge cases they're dead code, if it doesn't they're just a rarely-taken branch once.
I believe the bounds check, in particular, is devastating for autovectorization. There are ways around it, but it requires additional code in safe rust.
Edit: actually looks like autovectorization is in play here [1]. Doesn't look like the bounds check gets in the way at all.
Compress patterns aren't recognized by any open-source compiler autovectorizer as far as I'm aware of. (I think intel's proprietary C/C++ compiler can?)
Once you have a mask of the positions you want to compress, you can generate a shuffle index vector from that mask to place the desired elements in the low part of the vector. You can expand the mask into nibble-sized indices using pext/pdep and some magic constants, then expand those nibble-sized indices into a vector of indices to use as the shuffle indices.
Yes, that's one approach. Another reasonable approach is to get out a mask from the comparison using `vmovmskpd` and use that to look up a shuffle constant, since there are only 16 possibilities. This also works well on NEON, although I wonder there whether it'd make more sense to find the shuffle dynamically rather than loading it.
- https://github.com/andy-k/wolges - an implementation of a Scrabble AI from scratch in Rust. Andy is very smart and came up with his own algorithm and data structure that we now use throughout our projects
- https://github.com/jvc56/MAGPIE - a friend started this as a rewrite of Macondo, but in C. A lot of new development has gone into this and I've contributed a bit as well. Also no official GUI, but it is _absurdly_ fast, so fast that we can do nested Monte Carlo simulations. Some algorithms have been backported to Macondo with the help of AI.
These are the main 3, but there are people contributing in other ways, someone else has made a CNN and it has good results (I built a CNN as well in the Macondo source, and it has decent results). We're slowly going to continue to improve this until we can use it in real-time for Monte Carlo evaluations, maybe by translating it into a NNUE architecture.
Currently on Macondo I've been working on AI explainability (it's quite good already) and Bayesian inference with a stats PhD candidate. We are likely going to publish a paper on the latter. It's very mathy but it ends up beating the best bot we have so far around 52% of the time (that's actually a pretty significant edge).
You can read about some algorithms on my blog here: https://cesardelsolar.com (very in-depth discussions on inference, CNN, and my exhaustive endgame/pre-endgame algorithm)
> Some times that's appropriate, like if there's a competition for hand-made or human-written something.
Indeed, and this is the problem: unlike woodworking, where my power-assisted creation is independent of, or complements, your handcraft, this engine is directly competing with other engines. Twiss is being disingenuous when he says he has no interest in submitting it to competitions; it plays on a rated account on Lichess, for example.
Now that we can mass produce tables and chairs I would imagine there are far fewer people whose career is hand crafting tables and chairs. So machines literally did out compete them.
In fact handicraft people were out competed so hard many people forget that used to be a respectable career.
Because what they're asking for is that another person shutter their personal hobby, but what they actually want is for that person's hobby to not affect them by showing up on ranking sites.
You'll notice I didn't mention copyright, and that's because I don't think it's relevant. I think your analysis is correct. Keep in mind too that Stockfish – the engine I work on, although I wasn't at the time – was the subject of a high-profile defense of the GPL in Germany: https://stockfishchess.org/blog/2021/our-lawsuit-against-che.... That case was different as it involved wholesale copying of the source code, rather than porting ideas. Ideas shouldn't be copyrightable.
But copyright and plagiarism are orthogonal, and questions of morality are much more tied to the latter. It would be illegal (in the United States) for me to publish a copy of Nineteen Eighty-Four, but not immoral. It was not immoral, in my view, for Aaron Swartz to try to liberate JSTor articles.
That doesn't make plagiarism acceptable, either. And therefore, I'm willing to call it out when I see it.
Anyway, I don't see how this relates to the original discussion. Nor do I think the irony is particularly deep: As far as I'm aware, Deep Blue didn't plagiarize Kasparov, and indeed alpha-beta search is quite different than how humans calculate. But yes, I'd have been very demoralized if I were Kasparov, although he seems to be doing well now.
Edit: Regarding being mean-spirited, sorry to say, but I don't particularly care for the feelings of someone who has been repeatedly dishonest and used LLMs to respond to people engaging in good faith. That latter path has been exhausted now.
To co-opt your conflation of legality and morality: free speech, mf!
reply