zwegner

(author here.) I started the x86-sat project about a week ago, which parses Intel's pseudocode for all of the intrinsic functions and converts it into a Z3 SAT model. I got a basic prototype working in around a day, and I've done some cool things with it since.

The next logical step was obviously writing a superoptimizer. You provide it with a whitelist of intrinsics to search over, a set of inputs, a set of free variables (for things like creating constants/lookup tables), and an output, and it will recursively search over all applications of the intrinsics to find the shortest instruction sequence. This is still a toy at this point, so don't expect any miracles.

Thanks for the reply!

After playing more, and switching from a trial-and-error/backtrack approach to a more deliberate style where I try to mentally prove each extension of a line, I feel less of a need for the start-line-anywhere thing. So, it's your call on whether that's worthwhile.

It would be nice to have undo/redo--I've made a couple mistakes, and in those cases I'd like to step back and check my work move by move. That might spoil the clean design a bit though!

The tap-to-skip is a good trick, thanks--no need to make other changes there.

This is really nice! Very clean design, and a great puzzle too.

Two small interface suggestions: first, allow starting a line on any square, not just one with a number (the selection would be canceled if it doesn't connect to a square with a number). This would make selecting lines where the number is in the middle a bit less annoying, requiring only one swipe instead of two. Second, speed up the between-puzzle display a little. I'm an American with a very short attention span, I don't have all day to look at puzzle names :)

I also found a solver on GitHub using Z3 that looks pretty small and readable, if anyone is curious: https://github.com/redfast00/LinjatSolver

This is very cool! I hope this gets released--even if it's a rough prototype, I would still use it in its current state.

Like others (apparently), I started writing a system remarkably similar to this earlier this year. I just wanted to generate some simple diagrams programmatically, and went down the rabbit hole of creating a Python library to combine Z3 with SVG generation. For whatever reason, I was getting awful performance from Z3, so I started writing my own constraint solver. That ended up being a lot more of a pain than I had the patience to deal with, so I abandoned it.

That's pretty cool! It's really not too different from make.py. Using decorators and python functions is likely cleaner in a lot of cases, though I'm not sure if that would fit well with make.py's pseudo-declarative model. It probably wouldn't be too hard to add support for parallelism, either.

Ah, thanks for the references. Now that you mention them, I realize I definitely knew about tup and fabricate before (and possibly waf?), but had forgotten about them. I haven't really thought much about trace-based build systems in years, until this subthread.

And looking through that waf blog post, I realize that I meant ptrace instead of strace--I want full fine-grained syscall interception, not just a text report afterwards. That gets around a lot of the overhead/parsing problems mentioned, and is required for the "pause build command so its input file can be built" case.

> I think bazels solution here is to just always make fat binaries. Or at least that's how it works if you're using blaze.

Oh, I should've specified soft/hard filesystem links--they'd make handling a virtual filesystem rather complicated. Dynamic linking is another strange case, but it looks like dylib loading happens in userspace, through an open()/mmap() (at least in Linux), that would be caught through the normal filesystem hooks.

> Ah this helps somewhat, I think there are still potential ambiguities, one thing that bazel can do is statically determine all of the input sources without actually executing the build. You of course can't do this. This has a few nice properties: you get missing input errors before doing any actual building, you have a build graph you can statically analyze (deps queries are magic), and all the sandboxing can be done ahead of time (with symlinks to create a shadow filesystem) instead of ad-hoc, you can parallelize everything, meaning you can saturate all your machines the entire time.

OK, I started out thinking that there would be very little parallelism impact from my scheme, but I realize now the problem that dependencies for a build step are only discovered serially, as each one is built and the dependent process continues.

I could imagine you could work around this with a speculation engine that uses the dependencies from the last run (possibly cancelling the speculated commands mid-flight if the dependent process doesn't end up opening their outputs, and if the speculated commands hasn't started writing files or anything). This would generally work fine, but would waste some work whenever you remove dependencies from a build step (e.g. delete an #include). But it does start to get messy!

Another note: as far as not specifying inputs, I mean inputs beyond the command line (which obviously needs to be specified up front). So you would only need speculation like the above for things like auto-generated headers. The usual cases like "build this executable out of these objects which are each built from these source files" can be parallelized just fine with no speculation.

Static analysis-type queries could be done after a build, but not in a clean tree. Not sure how much of a setback this would be--I'm not generally working in massive projects, and haven't yet felt the need for such queries.

strace performance is a good point (I don't know what sort of overhead it has), and so is memory overhead.

> I also find it easier to reason about stuff with explicit deps, but that's just me.

I could go either way on this one--I generally prefer explicit to implicit, but I don't like repeating the explicit instructions twice (build rules and source code), with the failure mode being unreliable incremental builds. If I'm going to the trouble of explicitly listing dependencies, though, I'll probably go with the ridiculously simple make.py instead of messing with Bazel...

> My understanding is that bazel is moving away from this, so that you can define toolchains by saying "here is a binary that serves the job of linking/compiling stuff".

How do they ensure determinism in that case? Is it just an easy escape hatch so that new languages can be easily supported, with no actual guarantees of hermeticity?

> The challenge with your idea is that you're basically saying "hey, we should sandbox and introspect <any number of fairly arbitrary and complex binaries> to intercept and modify their filesystem and network (at a minimum) accesses, across any number of versions and uses".

I think my approach would certainly use a syscall whitelist. Any unsupported syscall would be a build failure, and presumably a bug report if it's a legitimate use. I suspect most build commands can get by with a pretty minimal set of syscalls (mainly basic filesystem access). At some point though, if you start supporting more and more syscalls, you start re-implementing VMs/containers, which sucks. This build system only stays simple if people don't try to do a bunch of wacky things with it :)

Network accesses would probably get whitelisted by the user on a rule-by-rule basis for cases like "download these packages", with the outputs treated as always dirty. The tool would be responsible for running efficiently even if no work actually needs to be done.

One weird/hard thing to support would be soft/hard linking. I'm not sure exactly what should be done there, but that might not be needed for early versions.

> Even just handling conditionally rewriting file writes/reads based on guessing whether something is an input or re-used output isn't that easy in general.

I'm not sure I understand this. One thing I should note is that in my scheme, you still have to specify output files for rules--you only get to skip specifying the inputs.

Wow, that's kind of incredible. That bug has been open for years, and is only starting to see some progress. Lends some credence to my unsupported claim of Bazel being overengineered...

Yeah, I know about Bazel, but only at a high level--I haven't used it.

I generally think the hermetic build concept is a very good one, but IMO Bazel goes about it the wrong way, and is overengineered. Rather than needing custom-built infrastructure for every type of language supported, I'd prefer build systems to use lower level OS facilities for discovering dependencies and controlling nondeterministic behavior. That is, build rules would use something like the rules.py files of make.py, specifying any arbitrary executables to run, but without needing to specify the input dependencies of each rule. Each command run would get instrumented with strace (or the equivalent for non-Linux OSes), and filesystem accesses detected. If a file is opened by a build step, that path would be checked for other build rules. If one exists, and it's out of date, the first build step gets paused while the input file gets built, then resumed. All of this happens recursively for the whole build graph, starting from the first requested build output. Other potentially nondeterministic system calls (timestamps, multi-threading/-processing, network access, etc) would be restricted/controlled in various ways yet to be determined.

That said, I haven't actually built anything like that (or know of anyone else that has). Maybe there's some complicated issues that this couldn't deal with but Bazel could. For example, there might be sources of nondeterminism that don't involve syscalls, like vDSO, I don't know for sure though. Portability between OSes would definitely be an issue. But overall I feel that, barring any major unforeseen issues, something like this could be built in a fairly minimalist fashion; maybe a few thousand lines of Python, possibly a small C module.

Note that the author of that paper (a friend of mine) wrote another build system, the dead-simple-but-awesome make.py. I have a mirror/fork of it[0], since it's been unmaintained for a while (but it mostly doesn't need any maintenance).

The entire build system is a single Python script that's less than 500 lines of code. Rather than trying to fit complicated rules into Make's arcane syntax, rules are specified with a Python script, a rules.py file (see [1]). But the script should be thought of more as a declarative specification: the rules.py file is executed once at startup to create the dependency graph of build outputs, and the commands to build them.

Yet, despite the small size, it's generally easier to specify the right dependencies, do code generation steps, and get full CPU utilization across many cores.

At some point I'd like to write more about make.py and try to get it used a bit more by the public...

[0]https://github.com/zwegner/make.py [1]https://github.com/zwegner/make.py/blob/master/example/rules...

Oh wow, that is most definitely a bug. Thank you very much for reporting that, before this spreads too much. How embarrassing... I was in a bit of a rush to stick this up on HN before the weekend, as otherwise I'd probably never get around to it. Evidently I got a bit sloppy making the error table.

Luckily, that's a very easy bug to fix--it was just caused by a mistake constructing the error tables. The only annoying part is having to renumber the error bits and write the tables again by hand :)

Thanks too for benchmarking! I see you tried out make.py, but it didn't work? I should probably add a Makefile for people that don't want to deal with yet another random build system...

BTW, I opened an issue to track this topic: https://github.com/zwegner/faster-utf8-validator/issues/3

In case anyone sees this: I initially agreed with you, thinking that pure UTF-8 validation is a bit more of a niche than might be expected. But if I'm not mistaken, I think at least for JSON validation, the UTF-8 validation can happen completely independently of the parsing. I don't think any control characters (braces, commas, quotes, escapes, etc) will change the validity of the UTF, or vice versa. So it might be beneficial (both for speed and security, as the sibling comment notes) to validate chunks of input as UTF-8, then pass them off to the parser, which now doesn't need to deal with validation.

Maybe this could be applied to XML, but that's quite a behemoth of a standard--I really wouldn't be surprised if there was a way to switch encodings mid-stream. I have no idea though...

Thanks for the link, that's a good post! I hadn't investigated the throttling issues much in the past, not owning an AVX-512 machine, but that's much more precise than the standard "don't use AVX-512" meme that's repeated all over the place. Bookmarked!

Definitely a good idea. I had already downloaded a Mandarin Wikipedia page to look for test sequences, but hadn't benchmarked them. Getting some more pages there is a great place to start.

Ah, thanks for the reply. I understand you better now, and for the most part I agree. Taking out the early exit for ASCII can speed up the frequently-changing case to avoid the misprediction penalty, as long as sufficiently many chunks of input need to take the long validation path.

Thinking about this more, I think there's at least one way that an adaptive approach might be beneficial without too much extra complexity: keeping two copies of the main kernel for ASCII-checking and non-ASCII checking. It should be pretty cheap to add a counter that is incremented or decremented based on the ASCII-only mask, and split the outer loop into N-byte chunks, with a branch for each chunk determining whether we should take the branchless path or not.

> Right, well the ASCII one is a big one. I haven't looked at the details of your algorithm, but could the core loop be faster if say it never saw any 4-byte sequences, or certain other uncommon things? Then an adaptive approach would use an optimized kernel for that scenario if it was encountered for a while.

I started out thinking this wouldn't really work, but I think there might be some potential here. My initial problem was that even if some work could be saved if there weren't 4 byte sequences, we still need to detect them every time. But, because my algorithm uses lookup tables for error flags which have some free bits, and because the 4 byte sequences can be detected in the same indices that are used for these lookups, we can set another error bit that means "take the 4-byte slow path". Then, when some input fails validation, we only do the work there to check whether it's really a failure. This gets complicated, though: first off, the check for the proper number of continuation bytes is before the table lookup, so we'd need to put some logic in there. Secondly, this lookup table gets validation failures one byte later in the stream than the initial byte. So in the case that the 4-byte sequence starts on the last byte of a vector, we'd need to have special handling.

It'd probably be a good idea to also have some hysteresis in this approach too... So overall, I think there might be some nice gains from adaptive behavior. There are two big concerns that make me skeptical, though: code size/I$ pressure, and code complexity. While code size wouldn't be much of an issue in microbenchmarks, in real applications it matters a lot more--I don't want the size overhead to get too big. Right now the full validation algorithm is about 600 bytes of code for AVX2, I'd rather not make that explode by a large factor by adding several specializations. And I'm already reaching the limits of what little generic programming can be done in the C preprocessor... This sort of specialization is really better done with C++ templates (or maybe Rust or something). I had wanted to keep this a pure-C library, but maybe C++ might be better.

Hope some of that makes sense... I'm mostly thinking out loud here. In any case, you've given me a lot to think about, so thanks very much!

It depends on the implementation. A good starting point would be looking at the various implementations benchmarked here: https://github.com/lemire/fastvalidate-utf-8

It looks like the main naive validator there (validate_utf8) clocks in at 1.25 cycles/byte for ASCII and 11 cycles/byte for UTF-8, which is respectively a 15.8x and 41.5x slowdown from my code.

I don't have any particular plans for that, beyond getting a bit of publicity for it here :). Or really any plans at all, besides adding AVX-512 support. It was just something I hacked together in a couple days as I began thinking about adding UTF-8 support to the text editor I've been writing.

That said, I'm happy to help anyone get it integrated into their codebase if they need it. There's generally other concerns in large projects, though, like portability, that I don't care as much about.

Well, to be fair, my claim was that it was the fastest in the world that I'm aware of, which is a much weaker statement. :)

The random UTF-8 in the benchmark was generated from the code in Daniel Lemire's fastvalidate-utf-8 repository, specifically this code: https://github.com/lemire/fastvalidate-utf-8/blob/ed53c0c64b...

Looking closer at it, I think that the distribution of random UTF-8 is not as uniform as it should be: it generates one byte first, and then generates continuation bytes depending on the value of that byte. Which means that half the code points will just be ASCII.

But I think this doesn't matter very much for benchmarking, at least for the mostly-branchless SIMD algorithms like mine. For each vector of input bytes, there's three branches that can get taken: the early exit for ASCII-only, and two branches that exit the loop due to validation failures, which don't really matter for benchmarking. Even though the distribution of code points will be roughly half ASCII, for a 32-byte AVX2 vector, the probability of a pure ASCII vector is something less than 2^-32 (since non-ASCII initial bytes translate into more than one byte of output, and the probability of 32 ASCII code points in a row is 2^-32, the probability of 32 bytes in a row is less, by an amount I'd rather not try to calculate). So for this particular benchmark, random UTF-8 should be roughly equivalent to "no ASCII". To verify, I disabled generating ASCII in the linked code, and the numbers came out pretty much identical. If anything, even more ASCII bytes would be a more interesting test, since that would make the quick-ASCII branch less predictable. If you know of any good UTF-8 corpora for common use cases, I'd be happy to benchmark them.

Given that different sets of "random UTF-8 bytes" generated with this method will virtually always follow the same path, the exact distribution doesn't really matter when measuring cycles/byte. Input that is purely 2-byte code points will be faster in terms of cycles/code point than purely 4-byte input, but that's mostly a property of UTF-8 being variable length.

I doubt there's much speed to be gained by adding any sort of adaptive behavior beyond the ASCII check. Generally these days you want as few branches as you can manage, and this algorithm has only one that matters.

At least my compiler (LLVM 10) is smart enough to know that "data" isn't modified, and thus fold the addresses of the two vector loads inside the main loop into single instructions:

    1a0: c5 fe 6f 6c 31 ff     vmovdqu ymm5,YMMWORD PTR [rcx+rsi*1-0x1]
    1a6: c5 fe 6f 24 31        vmovdqu ymm4,YMMWORD PTR [rcx+rsi*1]

I'd expect most modern compilers to get this right with optimizations on, but if somebody finds one that doesn't, I'd like to know. In general, I read through the disassembly a decent amount when developing this. That's how I noticed the "req += (vmask2_t)set << n;" (instead of |=) trick, which gets compiled to one lea instruction. The disassembly got a little bit hairy when I added the code to handle trailing bytes, though...

Thanks for the kind words, though! It warms my heart :)

Well how else are you supposed to nest your preprocessor macros? :P

Thanks though! I like taking the time to make my code as clean as I can. Glad others appreciate it!

Oh interesting, I hadn't seen that. It looks like it uses the same idea of shuffle-lookups on the first three nibbles. That's a fairly large patch though, I don't think I've fully grokked it. At the very least, my code differs from that in that mine does less byte stream shifting, instead doing shifts in the scalar domain. Their code also needs to deal with quotes, escaping, etc. due to being part of a JSON validator.

> this might save megawatts of power world wide

That'd sure be neat! I really have no idea, though.

> A small nitpick: not sure whether those macros bought anything, I guess the optimizer could inline function calls to intrinsic wrappers just fine as well?

Yeah, that's a bit weird. It's my hacky generics-in-C method, that allows both AVX2 and SSE4 implementations to be compiled in one codebase, while keeping the base algorithm clean. The idea is that you can compile both versions by including multiple times, like so:

  #define AVX2
  #include "z_validate.c"
  #undef AVX2
  #define SSE4
  #include "z_validate.c"
  #undef SSE4

...which would allow a later runtime dispatch based on CPUID, etc.

Minor correction: the graph of the PCM data is displaying the data as unsigned instead of signed, so it has lots of discontinuities between ~0 and ~64k.

Though, for the sake of showing the data as "raw", I guess it doesn't matter too much.

Again, I don't see that as cheating or violating a spec (or at least any guarantee made by Intel about x86(-64) behavior that I know of). I would assume that speculation can do just about anything (access protected memory, run illegal/protected instructions, etc), as long as any effects aren't committed to architectural state until the speculated path retires. The existence of side channels (timing information of subsequent memory accesses) for retrieving information from speculative execution paths is a different issue. Perhaps it was naive of the architects to assume this wouldn't have any consequences beyond improving performance, but I don't know what spec it is supposed to violate.

> both systems protected against Spectre, Meltdown etc. (i.e. no cheating by ignoring the ISA specifications)

Does the x86 specification say "speculation will have no observable side effects on the memory subsytem"? I wasn't aware of that. In other words, Spectre/Meltdown are bad security flaws, but I don't think they're the result of cheating.

I was recently looking into audio antialiasing/interpolation algorithms for a software synthesis project and stumbled across this. It's written by Miller Puckette, who created Max/MSP and PureData. It's one of the best resources I've seen for the theory/math and implementation of digital audio algorithms.

I'll give you the Eye of Sauron example. I admit I haven't read the books, and I've seen the films once or maybe twice.

For the other examples you mention:

As ximeng mentioned, "ocean depth" here should refer to sea level. "Sea level" would probably have been a better wording.

Christ the Redeemer is a statue in Rio de Janeiro[1]. W|A can give answers for "length of blue whale", "number of blue whales", and "height of Christ the Redeemer" (but not arm span, which Wikipedia gives as 92 ft.). It's not much of a stretch to combine those to get an estimate of the answer.

The contents of every NYT issue should be available on the internet, and some of the other figures can be found on the internet without too much trouble: the font is 8.7pt Imperial[2], and there are on average 150k words per issue[3]. Of course, these are fairly obscure pieces of data, but W|A prides itself on pulling together lots of disparate data sources. And if you don't consider having a particular obscure piece of data to be intelligence, you could easily shift the question to be, "how might an AI pull this information from the internet using natural language processing?"

For the time zone example, I took it to mean time zone changes from traveling, not just from DST (hence "per day"), and the total duration refers to the amount the watch is changed, not how long it takes to change it. Though whether the question means "sum of absolute values of differences" or just "sum of differences" is unclear.

[1] https://en.wikipedia.org/wiki/Christ_the_Redeemer_(statue) [2] https://en.wikipedia.org/wiki/The_New_York_Times#Print_newsp... [3] https://www.quora.com/How-many-words-are-in-an-average-print...

Oh, it's not my account, I'm just a fan. All I know about the account is that it's run by the Reddit user Cosmologicon: https://www.reddit.com/user/Cosmologicon