UTF-8 validation flag lookup algorithm

This algorithm uses 4-bit table lookups to lookup 8-bit "error flags" from each nibble, and treats them as an error if all nibbles in the sequence have the error flag. Turns out UTF-8 has 8 3-nibble sequences (byte 1 alongside the high nibble of the next 4 bytes) and 2 2-nibble error sequences (byte 1 by itself). It is also notable that, incredibly, no more than [8 distinct combinations] of the first byte and later paired bytes are required to reliably detect all errors.
It works by sequences of 4-bit table lookups, &'d together, so that the error is present only if all nibbles are part of the error value. For example, to detect this overlong encoding of "a" (0x61):

overlong encoding of a: 11000001 10010001
Lookup high nibble 1100 in this table, yielding ERROR_OVERLONG_2
Lookup low nibble 0001 in this table, yielding ERROR_OVERLONG_2
When &'d together, the bits align and we have an error! If the low nibble had been 0010, we would have detected no errors.

The algorithm is simple:

First byte errors: Check for errors that only require the first byte to detect: overlong encoding of 2 bytes (1100000_) and a subset of too-large encodings (anything >= 11110101). This is done by a pair of table lookups (high and low nibble) and a single &, Too-large encodings could be done quickly with >, but when we're figuring out both of these together, I couldn't find any way to beat 2 table lookups and an &, instruction-count-wise.
Second byte errors: Check for errors that require the first byte + another (overlong 3- and 4-byte encodings, missing/extra continuations, some of the smaller overlarge values, and surrogates). To accomplish this, we're essentially doing the same thing as step 1 (flag lookups with &) but with 3 nibbles each time.

Put together the first byte error flags once (high and low nibbles). We do 2 table lookups and an & on the leading byte, but we don't treat that as an error, yet.
& the first byte error flags with another flag lookup on the 2nd, 3rd, 4th and 5th bytes.

This made AVX around 1-1.5% faster on my machine (about the same as the range lookup algorithm), and astonishingly passed make test the first time I ran it! Submitting this is partly to see what ARM thinks of it :)
I'm curious if anyone has ideas for further improvement. It feels like overuse of the AND-flag-lookup method, but that method takes so few instructions (4-5 per pair) that it's hard to come up with non-lookup-based methods that compare. I suspect 2-byte-long error detection of overlong/surrogate/too-large bytes is about as optimal as it can get, but perhaps there are clever ways to handle missing/extra continuation detection or the 1-byte-long error detection that save us a few instructions.

Would you look at that! This patch is massively different from the range patch, and yet ARM takes the same size hit!
I'm wondering if the UTF-8 got so much quicker that it changed the profile of the stage 1 loop in seriously adverse ways.

It is on my todo to deep dive into the utf-8 stuff very soon.
How could speeding up UTF-8 make the performance overall worse?

@lemire yeah, it probably shouldn't.  Both of these algorithms do a lot more of them ...

I think nothing beats benchmarking on a real server and examining the metrics and so forth. I plan to do this soon-ish with these issues.
However,  if you want direct investigation, I can give you access, right now, to a ARM-based server from Ampere (via ssh).

@lemire that wouldn't hurt at all :) I have a Raspberry Pi now, which is evidently ARM 7, so I should be able to test the older ARM once I get that hooked up.

@jkeiser  I am not sure I have your email. Can you email me at<EMAIL_ADDRESS>

Doing a small diff, it seems this lookup algorithm is faster than the range algorithm on AVX2, and slower on SSE4.2 (but better than master in both cases):

AVX2
SSE4.2

Master
5.593578
3.030302

Range
5.720245
3.212182

Table Lookup
5.793716
3.123220

My guess on that one (solely a guess) is that we're running into xmm register pressure--my patch may require more constants. I'm going to look into rejiggering it so that the byte length checks for 3-5 bytes don't require constants (or at least use the same ones).

Ironically, the range approach was designed for better performance on ARM. :-)

OK, I improved the approach with fewer tables and rearranged it so that there are a few less instructions. Now it's way faster than either algorithm on SSE4.2. This algorithm is still faster than all other algorithms on AVX2, but the previous commit is about 0.4% faster in stage 1 (which probably translates to a 0.1-0.2% difference overall).

AVX2
SSE4.2

Master
5.593578
3.030302

Range
5.720245
3.212182

Table Lookup
5.793716
3.123220

New Table Lookup
5.772532
3.297728

Holy goodness, using saturating_sub instead of >= really makes a huge difference on AVX2! Makes SSE4.2 a little worse than before, which is a little weird, because >= is actually two instructions underneath; but it's still better than any other algorithm. I bet we'll end up with different algorithms for some bits, in the end: if saturating_sub is terrible on westmere, we may make a version of greater_equal that only promises that at least some bits will be 1, and implement it differently for each architecture.

It gets better still when you let multiple UTF-8 checks run simultaneously without a data dependency like prev_input or error (which is only possible because our only dependency is on the previous input (similar to @aqrit's suggestion).
I'm starting to think there could be real benefit to moving UTF8 out of the stage 1 loop entirely, because of register pressure: if UTF8 is the only thing running, a lot more registers can be constants!

... and HOLY SHIT that supposition turns out to be hella true. Unrolling further and then running UTF8 in its own separate loop is the single biggest improvement I have ever seen.
Table updated ...

The lesson (I think): register pressure is real, kids.
I haven't even optimized this to run on smaller sizes, I just happened to be running on the same 128 bytes as always.

@lemire this is worth looking at; please poke some holes. I didn't expect a change that simple to turbo boost performance quite so much. I do see a single test result that only fails on appveyor, but we're running utf8 tests in a lot of other places, so while I'm gonna fix it, it's not likely a blocker and it was definitely happening before the loop separation.

@lemire stand down; I think the tests were lying to me in very specific ways: it was validating utf8, but only in the first 128 bytes. It's slower when you move utf8 to another loop and actually validate :) Reverting to the actual algorithm here!

Next: shrink the loop, and run 64 bytes at a time instead of 128, and you get another 4% on Westmere. I just added the ability to run different sizes on different architectures.

64 bytes at a time is better on ARM, too.  Inching ever closer to parity, but still puzzled at the difference.

A note: one of the ci machines is faster with the current version of this patch. It's that one weirdo machine that stubbornly refuses to yield.

On my todo to sort things out. :-)
Yes, UTF-8 will be moved out of stage 1... :-)

Similar utf-8 validator [MIT licensed]
https://news.ycombinator.com/item?id=21547369
https://github.com/zwegner/faster-utf8-validator

@aqrit We definitively need to investigate this follow-up work. Thanks for pointing it out.

@andrewffff your UTF-8 validation algorithm came at an interesting time :) We've got two other candidates, one of which (this patch) uses a very similar approach to yours for the first two bytes.
I'm working on getting a version of yours into simdjson in there; but perhaps you'd be interested in comparing this algorithm and the range algorithm against yours as well :)

@lemire I have integrated @andrewffff's algorithm (with a few tweaks of my own) and it takes the cake here. The use of 64-bit masks for validating continuations beats the use of simd tables, even though the instruction count for the full-simd is lower--I am willing to bet this has to do with processor pipelines, and perhaps a little bit of .
I'll make what I hope is a final UTF-8 PR for this. I haven't checked it on ARM, but I've fixed things up so that ARM can use fastvalidate still if necessary.

I've been CC'ing the wrong person; the winning algorithm is @zwegner's :)

@zwegner there are two versions of your algorithm here: the unmodified code, and some modifications I made based on what we've learned writing simdjson: for example, storing an accumulated error value with | instead of an early return if statement, especially if the thing you're storing is a simd register, helps with performance. All of the changes are in @jkeiser NOTE comments inside utf8_zwegner_algorithm.h.

Awesome! Thanks for testing. I first had to check if you had pulled my code after the F0 80 overlong fix that I made late last night after @andrewffff pointed it out on HN, but it looks like you caught it independently. Glad others are paying attention :)
The delayed exit looks like a nice improvement (and looks to be mainly responsible for the 5.59->5.91 bump?). It does seem to slightly complicate some possible later changes to the validator I had thought of, though:

Rather than just returning valid/invalid, return a byte index of the first validation failure
Similarly, rather than just validating, modifying the invalid bytes in place by replacing them with ? or something. Although this feature would be pretty useful for my original intended use case (a text editor), there would be some additional hoops to jump through for SSE/AVX since there's not an inverse movemask instruction.
Adaptive behavior for 4-byte sequences. Since in most inputs, 4-byte code points should be pretty rare, it might be a decent speedup to have the main kernel not check 4-byte sequences, but instead set another bit in the error mask for these, and on validation failure, doing an additional check for them. Then, use a counter to switch to a slower always-check-4-byte-sequences path if enough of these branches are taken. I describe this some in this issue: https://github.com/zwegner/faster-utf8-validator/issues/3

Overall though, looks like I need to look through this project more. I was aware of it existing, but didn't think to check it out for UTF-8 validation--I just looked through the fastvalidate-utf8 repo. Kinda crazy we both came up with the vpshufb-on-three-consecutive-nibbles idea right around the same time...

@zwegner ugh, it appears I was running my code against an experimental, slower version--the actual version seems to be statistically identical to yours. I'm going to see if yours benefits at all from some of the outer optimizations I made to mine, though (like unrolling / running several of them at a time).

@zwegner I think you could still replace with ? without returning; you don't have to actually measure the bool, you just always run the replacement (since it ought to be one instruction). Having to de-movemask definitely complicates it, though :/
I've been thinking about the more-than-2-byte thing, too. I could imagine calculating all errors up to 2-byte leads, and then just dropping an if () statement checking if there were any 3-plus's (which you can do since you had to look at the 3rd byte to ensure that 2-byte character wasn't followed by a continuation). You wouldn't really even have to have a different algorithm, just do less work.

@zwegner The error-and-return is probably a major source of performance gain, but I made a number of changes in there that could have affected perf (and probably did). I didn't test incrementally after each change, as I was trying to fit it into both my mental model and the simdjson codebase :)

@zwegner it does seem like I messed something up translating your algorithm as there are a couple of failures. It's also worth noting that it does terribly on ARM, very likely due to the movemasks (which ARM doesn't have, so we have to work around with a bunch of instructions). That's a place that we could make a ton better by parallelizing the algorithm to 64 byte chunks, though: creating a 64-bit mask from multiple 16-byte Neon registers costs the same as creating 4 16-bit masks. 64 bits might also help because you could do a lot of the mask manipulations 1 time instead of 4, saving lots of instructions!

@zwegner it turns out I did mess something up, and something important was being optimized away--which has happened to me multiple times in this project. Specifically, I wasn't checking the result of cont_error (which led to the test failures), and the optimizer was not running some or all of the cont error checking code. Now when I run it, it's a little slower than this PR's simd-only algorithm on AVX2.
Numbers are updated. This PR is running a little bit ahead (on my machine, and again, within the margins of insignificance). However, there are still several modifications we can try out on your algorithm (including the 64-byte mask and some outer loop unrolling) that might give it the edge. I'm not sure mine can be optimized any more than it is.
Note: another of the perf-impacting changes I made to your code was to drop the & 0x0F's you made, since they were unnecessary (the Intel shuffle ignores the upper 4 bits).

@zwegner I think you could still replace with ? without returning; you don't have to actually measure the bool, you just always run the replacement (since it ought to be one instruction). Having to de-movemask definitely complicates it, though :/

Yeah, the ? replacement was an off-hand remark about how my algorithm's use of scalar masks makes that harder, not really related to other topics here.
I'm not too surprised about ARM being slow, I honestly know nothing about NEON.
I am curious to see disassembly of some of the various algorithmic options, to try and see why performance might be so different between your benchmarks and mine. Maybe your/@lemire's code leaves the scalar execution units less occupied, so other instructions can be interleaved, whereas with my algorithm they're serialized. simdjson is a big codebase, though, and it'd take a little while to ramp up enough to read the full disassembly of each algorithm...
As @aqrit points out, the &0x0F is required to prevent the zeroing. I had thought for a bit about whether the high-bit-zeroing might be somehow useful, but couldn't come up with anything.

Oh, and also: I read your note in the code: "this ascii fast path is different from the one in simdjson: it triggers less (after two consecutive ascii blocks)", and it sounded a bit off at first. I checked the code again and realized it was suboptimal, as we can always exit on ASCII-only blocks, last_cont being non-zero just means the input is invalid. So, thanks for that!

@zwegner as far as 0x0f, I believe you are doing the & even after >>4, where it is actually not needed. I didn't realize about the control bit, though ... the only reason I haven't fixed it yet is my tests show it treating c0 80 correctly as an error, which it shouldn't be given the high bit thing. I have some investigation to do there.
It's actually not impossible that ARM performance will recover after we widen the algorithm to use 64 bytes / a 64 bit mask. There are other techniques too though--if you do all 4 masks at once, it should have the same effect. I'll show some code when I get a chance.
I suspect your algorithm will win out once we widen the masks, though, and that has the happy circumstance that it can probably get even better by widening the masks to simd width.

I believe you are doing the & even after >>4, where it is actually not needed.

There is only a 16-bit shift with avx2/sse4.1 ... so garbage gets pulled into the high nibble of the LOBYTE. This seems to be handled/hidden in simd.h
https://github.com/lemire/simdjson/blob/2704b7339944687973ec755faf93cc6459005815/src/haswell/simd.h#L194

Yeah, what @aqrit said. Because of the 16-bit shifts, the mask is needed in all cases. There's a good chance that a modern compiler could at least coalesce the &0xFF from the above shift code with the &0x0F into just the latter, but I haven't checked.
vpermb on AVX-512-VBMI at least got rid of the high-bit behavior, so no masking would be needed there. I thought there might be a byte-level constant vector shift in AVX-512BW, but looking again, I don't see one.

and that has the happy circumstance that it can probably get even better by widening the masks to simd width.

@jkeiser what do you mean there? Do you mean processing blocks large enough that the scalar continuation masks would be moved into vectors? Or something ARM specific?

Yeah, what @aqrit said. Because of the 16-bit shifts, the mask is needed in all cases. There's a good chance that a modern compiler could at least coalesce the &0xFF from the above shift code with the &0x0F into just the latter, but I haven't checked.

Ugh, I'd forgotten about that. So my removal of 0x0F wasn't improving the original code. Thanks to you and @aqrit :) I still need to figure out why things are still working now that 0x0F is gone from the low bit lookup, though. Something weirder is going on there. Tests definitely reveal the high bit behavior.

@jkeiser what do you mean there? Do you mean processing blocks large enough that the scalar continuation masks would be moved into vectors? Or something ARM specific?

Yeah, once you start talking about dealing with larger masks, it becomes natural to ask about 128- and 256-bit masks. But I have a feeling it actually won't help with your code, because the actual processing being done with the masks is pretty small. I do suspect that widening to 64-bit will help, however, in part because it unrolls a bit of loop. I'd like to put both of these algorithms through the wringer until we figure out what combo is going to work best!
It's also become clear to me that we need more rigorous UTF-8 tests, which at the minimum test the min and max of each failure range at the beginning and end of each 64-/128-byte block, and multibyte errors that span across the 64-/128-byte boundary.

Yeah, once you start widening continuation masks to 64-bit, it becomes natural to ask about 128- and 256-bit masks. But I have a feeling it actually won't help with your code, because the actual processing being done with the masks is pretty small. I do suspect that widening to 64-bit will help, however, not only because it saves a few instructions but because it unrolls a bit of loop. I'd like to put both of these algorithms through the wringer until we figure out what combo is going to work best!

I think for my code in particular, that would be unlikely to gain anything (at least on x86)--as you say there's not much processing actually done on them, and the scalar instructions can be done more-or-less for free in parallel with other vector instructions. I'm not too sure unrolling could get much benefit either: my code has a decently big kernel (so the overhead of fetching/decoding one branch doesn't matter much) and doesn't have any cross-iteration dependencies besides last_cont (so no extra optimizations could be done from unrolling). It should be pretty much bottlenecked by the vector ALUs. You'd have to pay in increased code size and branch predictor pressure, which might not be worth it in the context of a larger code base.
What might be worthwhile is splitting the utf-8 validation and JSON parsing loops into separate, coarser grained chunks of say 1k each. You'd pay the cost of loading input from memory twice (though the second time should be in L1), but have the benefit of smaller, denser loops where more constants could potentially be kept in registers across iterations. I wouldn't know for sure though, just an idea to try.

It's also become clear to me that we need more rigorous UTF-8 tests, which at the minimum test the min and max of each failure range at the beginning and end of each 64-/128-byte block, and multibyte errors that span across the 64-/128-byte boundary.

You might want to look at the luajit test script in my repo. I only recently started using luajit, but it's been pretty fun, and has a super-easy FFI. It tests lots of permutations of input bytes at different frame shifts to catch any cross-vector errors. It'd probably be really easy to adapt to unit testing here, though you'd need to add some C wrappers for templated functions.

Tables updated with results after fixing the 0x0F bug. It looks like the SIMD-only algorithm is significantly faster on SSE (which is honestly the opposite of what I'd expect) and the mixed algorithm is slightly faster (1% on stage 1) on AVX2. For some reason, the AVX2 algorithm is completely unaffected by adding the & 0x0F in there. I'm not sure why it would be optimized away, if it is ...

@jkeiser
I'm a bit nervous about benchmarking just one file. Can you broaden slightly your benchmark? I suggest adding random.jsonand gsoc-2018.json just to make sure.

@lemire definitely necessary before we go much further. Right now I'm mainly using twitter while I look at the differences between algorithms, because it's a decent way to get a balance of UTF-8 and ASCII.

@lemire numbers for random and gsoc added. All of the algorithms are pretty similar on gsoc, which I'm going to assume is ASCII (will look later). Mine and @zwegner's algorithms are pretty clearly in the lead on AVX and SSE.
What's weird is, random.json mine is better on AVX @zwegner's is better on SSE, while on twitter.json it's the opposite (and I think the difference is real). I don't know how to interpret that. My best clue right now is that @zwegner's algorithm does UTF-8 processing a little more often if the file flips; let's see what happens when I fix that.

@lemire @zwegner all right! With the ASCII fast path change, @zwegner's algorithm is the lead on almost everything, and where it isn't it's pretty close. I'm convinced that on my machine at least, it's the one we should use.
Can y'all run it through some other machines? I'd like to get a comparison of lookup and zwegner at least. I have Kaby Lake R intel.
To run it:

AVX2: make parse && ./parse -tf jsonexamples/twitter.json 10-20 times and pick the biggest number.
SSE4: make parse && ./parse -tf jsonexamples/twitter.json 10-20 times and pick the biggest number.
Repeat the above with jsonexamples/gsoc-2018.json and jsonexamples/random.json.
Modify src/haswell/stage1_find_marks.h to #include "generic/utf8_zwegner_algorithm.h". Do the same with src/westmere/stage1_find_marks.h.
Repeat steps 1-3.

I don't understand the gsoc numbers: fastvalidate does decently better than the other algorithms on SSE, at least, but I can't understand why it would do any better given that they're using the same ASCII fast path. Code size? Registers? Measurement fluke?

All of the algorithms are pretty similar on gsoc

It is. But I suggested it on purpose. If you conclude that one is better than the others on gsoc, then you have a methodological flaw. :-)

With the ASCII fast path change, zwegner's algorithm is the lead on almost everything, and where it isn't it's pretty close. I'm convinced that on my machine at least, it's the one we should use.

Which fast path change? It looks like you haven't ported over this recent commit, which is a smallish improvement on the ASCII early exit: https://github.com/zwegner/faster-utf8-validator/commit/cf482014d07da56bb0b0bb62cbb1f4d1c9e9048f
...or is it something else you're talking about?

@zwegner sorry, I hadn't committed it yet. I also made a tweak when I realized that my implementation of shr was doing extra work. Your algorithm is far and away the fastest on almost everything now :)

It is. But I suggested it on purpose. If you conclude that one is better than the others on gsoc, then you have a methodological flaw. :-)

Well, fastvalidate is detectably faster on SSE. I have no idea why at the moment.

You know what else could be driving the performance difference, is the ASCII fast path ... Zach's if statement is already in scalar context so probably runs faster, and he does less work inside!

@jkeiser Your instructions above for sse4 are probably incorrect. You are missing a flag.

The instructions...

Modify src/haswell/stage1_find_marks.h to #include "generic/utf8_lookup_algorithm.h". Do the same with src/westmere/stage1_find_marks.h.

Are ill-defined. What exactly is the patch?

This PR is a clear gain over master on x64 processors when there is actual UTF-8 content in the file, whether we use SSE4 or AVX.
I am uneasy about hacking the code manually and hoping that the right code paths will be triggered. If we want to do deep comparisons between alternatives, we should use distinct branches... otherwise it quickly gets unmanageable.

This PR is also beneficial on ARM.
Before:
twitter.json
stage 1 instructions:    2335665 cycles:    3272240 (57.67 %) ins/cycles: 0.71 mis. branches:       3286 (cycles/mis.branch 995.62) cache accesses:     428354 (failure       9912)
 stage 1 runs at 5.18 cycles per input byte.

random.json
stage 1 instructions:    2751134 cycles:    3739586 (53.95 %) ins/cycles: 0.74 mis. branches:       3142 (cycles/mis.branch 1190.12) cache accesses:     562471 (failure       8012)
 stage 1 runs at 7.33 cycles per input byte.

After
twitter.json
stage 1 instructions:    2242372 cycles:    3166679 (56.77 %) ins/cycles: 0.71 mis. branches:       3311 (cycles/mis.branch 956.31) cache accesses:     257883 (failure       9898)
 stage 1 runs at 5.01 cycles per input byte.

random.json
stage 1 instructions:    2641937 cycles:    3646974 (53.17 %) ins/cycles: 0.72 mis. branches:       3865 (cycles/mis.branch 943.42) cache accesses:     351293 (failure       7999)
 stage 1 runs at 7.14 cycles per input byte.

BTW this is brilliant work.

Hmm I'm unclear why it helps on arm, it should still be using fastvalidate there.

As for what the patch is, I've placed four different utf8 algorithms in header files with identical interfaces, so that you can ditch storms by including the file for that algorithm. I'll make a branch though, agreed it's better if we're all guaranteed pointed at the same exact code.

Hmm I'm unclear why it helps on arm, it should still be using fastvalidate there.

Correct. Master was out of sync with the repo when I ran my tests. Sorry for the noise.

@jkeiser My manual inspection agrees with your results in the sense that for westmere, we get very slightly better results with your lookup but slightly better results on haswell for zwegner on twitter and random (where we have a fair amount of UTF-8). But the difference is not super large. Both are better than master.
On gsoc and some other pure ascii files, I am often getting better results with your approach (lookup). This has to do with the fast ASCII path. This seems to contradict your results?
The zwegner is faster in the UTF-8 intensive case despite generating more instructions: the trick is that it has a higher rate of instructions retired per second which might have to do with its use of both SIMD and general-purpose registers. We sometimes reach 3.8 instructions per cycle on skylake, which is flat out amazing!
As the current code stands, I think that either lookup or zwegner would serve us well. I would not be tempted to throw away lookup as it still has the benefit of generating fewer instructions, something that could prove to be an edge.
 I wouldn't mind independent verification on other machines. I also had it use my algorithm on ARM, so if you want to try that on some more modern machines, I'd love to hear what you see. (I'll climb on your ARM machines soon, but as you can see I've been a bit busy with other bits of this :))
So if you just check that out and run parse, you'll be able to grab numbers.
I haven't updated @zwegner's for ARM yet, because I need to implement simd8.get_bit on ARM, and it's not obvious how to do it efficiently (everything I came up with is strictly worse than to_bitmask, which is already a lot of instructions).

@jkeiser My results on ARM with your new branch (thanks for creating the branch, it is much easier than editing files back and forth, and less error prone).  I made changes this morning to get the patch into a shippable state, with the ability to swap between zwegner, lookup, range and fastvalidate at will. We just pick which algorithm we want right now on each architecture, and change it or even bifurcate architectures as we learn more.
Given your latest result, I recommend we either ship with lookup enabled everywhere, or zwegner on Intel and lookup on ARM. I haven't looked deeply at your numbers yet, but there are two things I'd look at to decide:

If the difference is really slight, I would prioritize homogeneity (same algorithm everywhere) when selecting so that improvements apply to multiple architectures. But I'd leave them both in the repository, for a few months at least while we stew and tinker.
I would prioritize ASCII gains a little bit higher than UTF-8 losses, if the tradeoff has to be made.  Depends on the ratio obviously.

My hunch (keeping in mind that while my hunches are getting better, I'm not ready to call them good yet) is that ARM, as well as CPUs with more homogenous execution cores, will do better with the lookup algorithm's lower instruction count. part of why I invested in making it easy to pick and choose different algorithms on different architectures.

I haven't updated @zwegner's for ARM yet, because I need to implement simd8.get_bit on ARM, and it's not obvious how to do it efficiently (everything I came up with is strictly worse than to_bitmask, which is already a lot of instructions).

Is the only difference between your algorithm and mine the movemask/scalar shifts? I.e. all the nibble-lookup stuff is the same?
It doesn't look like ARM has any fast way to do a movemask. But, looking at the answers here I think there might be a way to do the movemasks for all three byte lengths at once, with not much more overhead than the regular movemask emulation sequence. Let me look around at the NEON instructions and think some more...

Is the only difference between your algorithm and mine the movemask/scalar shifts? I.e. all the nibble-lookup stuff is the same?

@zwegner the nibble-lookup stuff is almost identical, but because I reuse the first high-nibble mask for both the byte 1-2 error check and the byte 3-5 error check, I needed 9 different error classes and the error byte only holds 8 :) So I also do input.saturating_sub(0b11111000-1) to check for lead bytes bigger than F8, external to the table lookups.
Another thing that's different is, because you are able to reuse last_cont as an error, your ASCII fastpath does less work (though for some reason that's not showing up in the numbers). I've been inspired by your algorithm on that path though, and I think all the other algorithms can be improved on that score :)

It doesn't look like ARM has any fast way to do a movemask. But, looking at the answers here I think there might be a way to do the movemasks for all three byte lengths at once, with not much more overhead than the regular movemask emulation sequence. Let me look around at the NEON instructions and think some more...

Yep. We do that with simd8x64<bool>, which is a mask (i.e. has all 8 bits set), here. simd8x64 is just a type with 4 16-bit NEON registers in it. Since we're not working with a mask, either you need to rotate the bits you want into the right positions somehow, or do simd8x64<bool>(bytes&0x80 > 0, bytes&0x40 > 0, bytes&0x20 > 0, bytes&0x10 > 0).to_bitmask() (which I think would work, but that's 8 instructions above and beyond the basic to_bitmask).

OK, I think I can significantly improve the continuation-required mask creation on ARM, with a couple of changes.
The first part is that the algorithm in this answer here can be used to aggregate all three continuation bit masks at once. For each of 2, 3, and 4-byte leader bytes, we put 0b0010, 0b0110, 0b1110 respectively in their vector lanes. This is the continuation mask required for each leader byte, like the result of the three req += (vmask2_t)set << n; operations in my code, but localized for each byte. Following the logic for the "proof" in my code for using += instead of |= when combining shifts to get an lea on x86, we can just keep the vsraq_n_uXX() reduction steps unchanged--that is, use "right shift and add" as one instruction, rather than a right shift followed by an OR. That means that (ignoring the initialization of high_bits in the linked algorithm, which is replaced by the mask I just described), all of the reduction steps can be used unchanged, except for changing the final vgetq_lane_u8s to vgetq_lane_u16s, since these masks can now overflow 8 bits. That should be a nice improvement in itself.
The next big change I found trying to avoid all the shifting and ANDing to create the above masks. Turns out they can be created in just a few instructions, using the vector count-leading-zeroes and vector shift operations. The sequence looks like this:
uint16x8_t inv_bytes = vmvnq_u8(input_bytes); // we actually want to count leading *ones*, so bitwise NOT
uint16x8_t counts = vclzq_u8(inv_bytes); // count leading zeroes in each inverted byte
                                         // ASCII == 0, cont. bytes == 1, 2-byte leader == 2, etc.
uint16x8_t ones = vdup_n_u8(1); // vector {1,1,1...}
uint16x8_t one_shift = vshlq_u8(ones, counts);   // vector (1 << count)
uint16x8_t mask = vsubq_u8(one_shift, one);   // vector (1 << count) - 1: mask of all bits below the shifted one
uint16x8_t req = vandq_u8(mask, vdup_n_u8(0x0E));   // mask out the low bit of each byte

If, in theory, there were 5, 6, etc. byte sequences in UTF-8, this would handle them with no extra instructions (but changing the 0x0E mask to include more bits). The vdup_n_u8()s are constant and could be hoisted out of a loop, if there are enough registers for them.
I'm not totally sure this second change will save time over the "obvious" shifts and ANDs that it otherwise would be--I don't know the latency of these instructions, or any other uarch details for the various ARM chips.
There might be a way to reduce more than one 16-byte vector at once, or combine the continuation mask generation with the required mask generation. Not sure yet though. And even with all these changes, it might not be faster than whatever the other algorithms are doing for continuations bytes...
Here's an untested sketch of the full algorithm:
uint32_t get_req_cont(uint16x8_t input_bytes) {
    const uint16x8_t ones = vdup_n_u8(1);
    const uint16x8_t valid_req = vdup_n_u8(0x0E);

    uint16x8_t inv_bytes = vmvnq_u8(input_bytes);
    uint16x8_t counts = vclzq_u8(inv_bytes);
    uint16x8_t one_shift = vshlq_u8(ones, counts);
    uint16x8_t mask = vsubq_u8(one_shift, one);
    uint16x8_t req = vandq_u8(mask, valid_req);

    // This part copy+pasted from the stack overflow answer
    uint32x4_t paired16 = vreinterpretq_u32_u16(
                              vsraq_n_u16(high_bits, high_bits, 7));
    uint64x2_t paired32 = vreinterpretq_u64_u32(
                              vsraq_n_u32(paired16, paired16, 14));
    uint8x16_t paired64 = vreinterpretq_u8_u64(
                              vsraq_n_u64(paired32, paired32, 28));
    // note _u16 and 4 here
    return vgetq_lane_u16(paired64, 0) | ((int)vgetq_lane_u16(paired64, 4) << 8);
}

@lemire @zwegner Inspired by the fact that Zach's fast path does no actual work (just an |), I modified the lookup fast path to "precalculate" the ASCII fast path error check inside of the UTF-8. This makes it so we don't have to recheck the error over and over again for multiple ASCII blocks--we just or the precalculated error in whenever we detect ASCII. The tradeoff is, if we see two UTF-8 blocks in a row, the work is wasted (literally not used). Zach's fast path is reusing data that he actually uses in the loop, so nothing is thrown away. It's a good compromise though, IMO.
Now the lookup algorithm beats fastvalidate at ASCII (gsoc-2018.json). It's a tiny bit better on twitter.json, and almost imperceptibly worse on heavy-UTF-8 random.json (0.5%).
I think fastvalidate can probably be modified to do it too, but it already stores so many overflow registers I was wary of adding another one for this.

@zwegner the nibble-lookup stuff is almost identical, but because I reuse the first high-nibble mask for both the byte 1-2 error check and the byte 3-5 error check, I needed 9 different error classes and the error byte only holds 8 :) So I also do input.saturating_sub(0b11111000-1) to check for lead bytes bigger than F8, external to the table lookups.

What 5 byte error check? UTF-8 (after ~2003 IIRC) doesn't allow 5 or 6 byte sequences--I think these were proposed but never standardized. In the latest version of the spec, the maximum UTF-8 code point is F4 8F BF BF.
But anyways, my point was that the continuation byte check and the mask lookup check are basically independent, and each algorithms' versions could be swapped out (mainly to not use the scalar continuation masks on ARM if we can't speed those up).

What 5 byte error check? UTF-8 (after ~2003 IIRC) doesn't allow 5 or 6 byte sequences--I think these were proposed but never standardized. In the latest version of the spec, the maximum UTF-8 code point is F4 8F BF BF.

Because I'm not using a continuation mask, I still have to check for stray continuations, which I define as "continuation bytes immediately following a valid n-byte character." Thus the 5th byte check detects  F4 8F 8F 8F _80_. Basically, if a continuation byte is preceded by an invalid character, that would have already been detected; so the 5th byte (or << 4) is as far as one has to check.

And I agree, we can almost 100% swap out the 3-byte bit. Both our algorithms are split into two functions.
The 2-byte lead check is slightly different in each, mainly because I'm checking 2-byte continuation errors alongside the "special case" errors, in the same table.

@lemire oh, I updated the jkeiser/utf8_shootout_lookup branch with the ASCII path speedup/tradeoff, as well as the numbers in the table up top.
I have to look over everybody's numbers, but as it stands I just can't decide what to use where. My summary thus far is:

Heavy UTF-8 workloads like random.json are crushed by @zwegner's algorithm (10% stage 1 or so, probably 2-3% overall) for heavy UTF-8 workloads like gsoc-2018.json.
Low-medium workloads like twitter.json are a bit of a wash--2% difference depending on arch, and that's unlikely to translate to a noticeable stage 1+2 difference.
ASCII like gsoc-2018.json heavily favors my algorithm by about 20% stage 1, so probably 4-6% overall.

...
Actually, I think I know why my fast path is faster--because I'm checking ASCII every 64 bytes, and @zwegner's currently checks every simd-width (so 4x as much on SSE and 2x as much on AVX). I'll see what happens if we widen that--I bet it will make up the difference! Probably not tonight :)

Hrm. When I widen the calls @zwegner's algorithm (running it more often), it appears to make a large ASCII / UTF-8 tradeoff difference:

AVX2
SSE4.2

@zwegner gsoc-2018.json 64-byte
7.965129
4.498285

@zwegner gsoc-2018.json original
7.923407
4.403640

@zwegner twitter.json 64-byte
5.863649
3.280597

@zwegner twitter.json original
5.952074
3.364491

@zwegner random.json 64-byte
4.130065
2.333071

@zwegner random.json original
4.318748
2.632677

The change is the top commit in the jkeiser/utf8_zwegner_64 branch.
In this case I don't think the minor ASCII performance gain is worth the massive hit in UTF-8 performance. It does make me wonder if we're making a similar tradeoff with our current validators' 64-byte processing ...

Yep. That was 100% the difference. If I change "lookup" to check one UTF-8, the numbers are WAY more in line with each other. The reason is obvious: we run UTF-8 validation on fewer blocks in UTF-8 files, but check ASCII more often.

AVX2 32-byte
AVX2 64-byte
SSE4.2 16-byte
SSE4.2 64-byte

@jkeiser gsoc-2018.json
7.773490
8.091007
4.429430
4.583158

@zwegner gsoc-2018.json
7.923407
7.965129
4.403640
4.498285

@jkeiser twitter.json
5.836553
5.825784
3.351990
3.400727

@zwegner twitter.json
5.952074
5.863649
3.364491
3.280597

@jkeiser random.json
4.275343
4.087078
2.582074
2.387633

@zwegner random.json
4.318748
4.130065
2.632677
2.333071

@lemire It's right on the boundary for me--heavy UTF-8 gains 5-10% with Zach's UTF-8 code, pure ASCII gains 2-4% with my lookup code. Twitter is right in the middle, and so are the numbers.
I'm inclined to go with Zach's version for Intel: the UTF-8 gains are substantial and I think the ASCII loss is small enough it'll be hard to notice in a full run.
This PR uses Zach's 16/32-bit step code for Intel, and my lookup code for ARM (which does tank perf on that one crazyass CI machine). We'll keep thinking about how to tweak them (I'm thinking through your ARM post @zwegner!), but I think we're all better off if we pick something, merge, and iterate :) (I'm not stuck on this particular arrangement, though, if you've got other opinions.)

This sounds very good.

One note to remember: the above numbers are stage 1, so 2-4% ends up being a little less than 1% of a full run, so 5-10% translates to something on the order of 2-4% overall.

Oh, another reason Zach's algorithm is probably faster: it not only uses the scalar cores, it uses lea so it also uses the exclusive address calculation ALU, likely getting those instructions for free (or nearly so).

I bet this goes a long way to explaining why it matters so much where we dumped the utf8 check: fastvalidate is almost all simd and we put it smack dab in the middle of a bunch of scalar operations.

I think it also explains why his ASCII fast path is a little bit slower! Again, smack dab in the middle of a bunch of scalar operations.

@lemire I think the pr is done, so once you feel satisfied it should be merged, let me know!

Will review soon. This is a great piece of engineering.

@zwegner
Maybe some of the bit twiddling for the "continuation mask" could be pre-calculated and stored in the lookup table for the high nibble? It looks like there are two free bits in the table, also some of the flags could serve double duty.
cont == bit_7
req_1 == bit_6
req_2 == OVERLONG_3
req_3 == OVERLONG_4

psllw/pmovmskb typically share a port, so paddb/pmovmskb might be better.
With SSE, I assume those psllw instructions would also require a movdqa.
(OTOH, I probably shouldn't post things late at night)

Maybe some of the bit twiddling for the "continuation mask" could be pre-calculated and stored in the lookup table for the high nibble? It looks like there are two free bits in the table, also some of the flags could serve double duty.

@aqrit, that's a really good idea! As it happens, I was just in the process of adding ARM support to my code, to test out the algorithm I was describing--afterwards I'll try and port it over here.
I don't know if fitting the bits into the existing tables is the right way to go, or if it's better to add another table lookup. For the case of putting them in the table, we'd want to put them in the same 0x0E positions in each byte, so we don't need extra shifting. I'm not quite sure how we could fit all the bits, though--if we're overlapping meanings of bits between the continuation mask and the error mask, how do we tell them apart? And otherwise we don't have enough bits... It's probably worth just using another table lookup (assuming these instructions aren't super expensive).
In any case, I'm sure this approach is a lot better (both in speed and clarity) than my wacky clz solution.

psllw/pmovmskb typically share a port, so paddb/pmovmskb might be better.
With SSE, I assume those psllw instructions would also require a movdqa.

Interesting, I hadn't gotten deep enough to look at port usage yet. When I was first implementing my algorithm, I had actually started out with vaddbs, and had to add some actual assembly directives, since LLVM was turning each vaddb(x,x) into a shift-left and mask (since it didn't know we only need the high bits and thus don't need masking). I imagine this was being done to break the dependency chains of the sequential adds. IIRC I think there was a tiny speedup when moving from adds to shifts, but it's worth checking again--I was making lots of quick changes then and not being too careful with measurements.

Only 1 pmovmskb can be done per cycle so sequential adds (I think) should be completely hidden.
The cont and req_1 bit would always be zero in the low nibble, so they would always be cleared.
If the the high nibble is 0xF, for example, then it always req_3, and it always needs to check for overlongs... the different meanings of a flag don't need to be disambiguated.

Only 1 pmovmskb can be done per cycle so sequential adds (I think) should be completely hidden.

Right, they should be hidden. Looks like vpmovmsk is port 0, vpsllw is port 0 on Haswell or port 0/1 on Skylake+, and vpaddb is port 1/5. So vpaddb should indeed be better, both from a code size and port usage standpoint. Depending on how much other work can be done in parallel, might be lost in the noise, but still worth doing.

The cont and req_1 bit would always be zero in the low nibble, so they would always be cleared.
If the the high nibble is 0xF, for example, then it always req_3, and it always needs to check for overlongs... the different meanings of a flag don't need to be disambiguated.

Ah, of course--I was thinking you meant to keep the continuation bits set in the second/third nibble masks, and pull them out at the end after ANDing the three error masks together. But there's no reason to do that--just mask them out from the first nibble lookup. The other slight change is that this gets the continuation masks shifted forward by one in the byte stream, but this shouldn't be a problem (just shift the bits to the right by one, to get 0b0001, 0b0011, 0b0111).

Per that, @zwegner, you should be able to copy the tables from my PR. They use identical numbers, but with constants, and I've done the | (and a lot of commenting). Just copy the 16 values from each .lookup call.

(Note: I realized I hadn't pushed the ASCII fixes for my algorithm. Done that now.

Not 100% related, but ... when people get a moment, can you do me a favor and see if you see the same thing I do? I'm seeing command #1 below about 1% faster on both SSE and AVX, on my machine.

git checkout jkeiser/mlga; make parse; ./parse -tf 10000 jsonexamples/twitter.json
git checkout jkeiser/utf8_flag_lookup; make parse; ./parse -tf 10000 jsonexamples/twitter.json

The only difference between these branches is that we're using a for loop instead of each, and I'm seeing a 1% gain. If this is the case, we have several places that need to have their loops disabled. I swear we looked at this before and found no perf degradation using each, but I'm seeing an increase across the board.
Thanks :)

@jkeiser Hyperfine may be of interest.

@jkeiser I’ll look into the perf difference you are reporting.

@lemire thanks. Perhaps unsurprisingly, I've taken this a little further and created another PR that builds on this one, and squeezes a further 2-4% blood out of the stage 1 stone. It restores @zwegner's original algorithm's method of loading the shifted bytes from memory rather than a previous input, among other things, with positive effects. I didn't push the changes here because I'd like this not to be a moving target for you.
Incidentally, I know as a researcher that you would probably prefer to be spending a greater percentage of your time on the new ideas you have, too. I really appreciate the time you spend looking at these!

@ArniDagur Hyperfine looks a benchmarker for executables / command lines, right? We're in the market for a nice standard benchmarking/stats program, but I think we need something that times functions in tighter loops--we are optimizing down to individual instructions here and even the small overhead of executable initialization would likely obscure the results.

Here are my results on AMD Rome, using GNU GCC 8.3. For each file, the first number is jkeiser's lookup branch (jkeiser/utf8_shootout_lookup), the second number is this PR, and the last number is master. The results are largely inconclusive.
jsonexamples/apache_builds.json
stage 1 instructions:     306679 cycles:      99502 (47.94 %) ins/cycles: 3.08 mis. branches:          3 (cycles/mis.branch 28941.91) cache accesses:          0 (failure          0)
 stage 1 runs at 0.78 cycles per input byte.
stage 1 instructions:     324579 cycles:     102364 (48.22 %) ins/cycles: 3.17 mis. branches:          7 (cycles/mis.branch 13751.24) cache accesses:          0 (failure          0)
 stage 1 runs at 0.80 cycles per input byte.
stage 1 instructions:     316616 cycles:      98166 (47.02 %) ins/cycles: 3.23 mis. branches:          4 (cycles/mis.branch 20228.06) cache accesses:          0 (failure          0)
 stage 1 runs at 0.77 cycles per input byte.
jsonexamples/canada.json
stage 1 instructions:    6071955 cycles:    2145689 (26.94 %) ins/cycles: 2.83 mis. branches:       5023 (cycles/mis.branch 427.10) cache accesses:          0 (failure          0)
 stage 1 runs at 0.95 cycles per input byte.
stage 1 instructions:    6388511 cycles:    2184612 (27.41 %) ins/cycles: 2.92 mis. branches:       4927 (cycles/mis.branch 443.36) cache accesses:          0 (failure          0)
 stage 1 runs at 0.97 cycles per input byte.
stage 1 instructions:    6247812 cycles:    2123871 (26.83 %) ins/cycles: 2.94 mis. branches:       5147 (cycles/mis.branch 412.62) cache accesses:          0 (failure          0)
 stage 1 runs at 0.94 cycles per input byte.
jsonexamples/citm_catalog.json
stage 1 instructions:    3934136 cycles:    1251294 (50.78 %) ins/cycles: 3.14 mis. branches:        160 (cycles/mis.branch 7786.53) cache accesses:          0 (failure          0)
 stage 1 runs at 0.72 cycles per input byte.
stage 1 instructions:    4174873 cycles:    1290502 (51.64 %) ins/cycles: 3.24 mis. branches:        171 (cycles/mis.branch 7537.98) cache accesses:          0 (failure          0)
 stage 1 runs at 0.75 cycles per input byte.
stage 1 instructions:    4070933 cycles:    1228183 (50.40 %) ins/cycles: 3.31 mis. branches:        156 (cycles/mis.branch 7842.81) cache accesses:          0 (failure          0)
 stage 1 runs at 0.71 cycles per input byte.
jsonexamples/github_events.json
stage 1 instructions:     146483 cycles:      47426 (46.19 %) ins/cycles: 3.09 mis. branches:          5 (cycles/mis.branch 9449.40) cache accesses:          0 (failure          0)
 stage 1 runs at 0.73 cycles per input byte.
stage 1 instructions:     155551 cycles:      48010 (48.12 %) ins/cycles: 3.24 mis. branches:          4 (cycles/mis.branch 11350.01) cache accesses:          0 (failure          0)
 stage 1 runs at 0.74 cycles per input byte.
stage 1 instructions:     151603 cycles:      45930 (46.63 %) ins/cycles: 3.30 mis. branches:          7 (cycles/mis.branch 6131.43) cache accesses:          0 (failure          0)
 stage 1 runs at 0.71 cycles per input byte.
jsonexamples/gsoc-2018.json
stage 1 instructions:    5963938 cycles:    1963497 (55.86 %) ins/cycles: 3.04 mis. branches:       5602 (cycles/mis.branch 350.49) cache accesses:          0 (failure          0)
 stage 1 runs at 0.59 cycles per input byte.
stage 1 instructions:    6431910 cycles:    1903237 (55.13 %) ins/cycles: 3.38 mis. branches:       5669 (cycles/mis.branch 335.68) cache accesses:          0 (failure          0)
 stage 1 runs at 0.57 cycles per input byte.
stage 1 instructions:    6223913 cycles:    1847328 (54.23 %) ins/cycles: 3.37 mis. branches:       5578 (cycles/mis.branch 331.15) cache accesses:          0 (failure          0)
 stage 1 runs at 0.56 cycles per input byte.
jsonexamples/instruments.json
stage 1 instructions:     544335 cycles:     178779 (44.26 %) ins/cycles: 3.04 mis. branches:         16 (cycles/mis.branch 10986.24) cache accesses:          0 (failure          0)
 stage 1 runs at 0.81 cycles per input byte.
stage 1 instructions:     575321 cycles:     183707 (45.50 %) ins/cycles: 3.13 mis. branches:         27 (cycles/mis.branch 6775.62) cache accesses:          0 (failure          0)
 stage 1 runs at 0.83 cycles per input byte.
stage 1 instructions:     561542 cycles:     176339 (44.19 %) ins/cycles: 3.18 mis. branches:         24 (cycles/mis.branch 7183.45) cache accesses:          0 (failure          0)
 stage 1 runs at 0.80 cycles per input byte.
jsonexamples/marine_ik.json
stage 1 instructions:    9122392 cycles:    3302258 (28.61 %) ins/cycles: 2.76 mis. branches:       7945 (cycles/mis.branch 415.63) cache accesses:          0 (failure          0)
 stage 1 runs at 1.11 cycles per input byte.
stage 1 instructions:    9573656 cycles:    3363298 (28.49 %) ins/cycles: 2.85 mis. branches:       7936 (cycles/mis.branch 423.79) cache accesses:          0 (failure          0)
 stage 1 runs at 1.13 cycles per input byte.
stage 1 instructions:    9383373 cycles:    3301979 (28.65 %) ins/cycles: 2.84 mis. branches:       8638 (cycles/mis.branch 382.22) cache accesses:          0 (failure          0)
 stage 1 runs at 1.11 cycles per input byte.
jsonexamples/mesh.json
stage 1 instructions:    2133351 cycles:     722832 (26.49 %) ins/cycles: 2.95 mis. branches:        462 (cycles/mis.branch 1562.33) cache accesses:          0 (failure          0)
 stage 1 runs at 1.00 cycles per input byte.
stage 1 instructions:    2249273 cycles:     743350 (26.30 %) ins/cycles: 3.03 mis. branches:        487 (cycles/mis.branch 1525.24) cache accesses:          0 (failure          0)
 stage 1 runs at 1.03 cycles per input byte.
stage 1 instructions:    2202271 cycles:     719637 (25.05 %) ins/cycles: 3.06 mis. branches:        487 (cycles/mis.branch 1476.89) cache accesses:          0 (failure          0)
 stage 1 runs at 0.99 cycles per input byte.
jsonexamples/mesh.pretty.json
stage 1 instructions:    3763763 cycles:    1220884 (33.21 %) ins/cycles: 3.08 mis. branches:         27 (cycles/mis.branch 44234.96) cache accesses:          0 (failure          0)
 stage 1 runs at 0.77 cycles per input byte.
stage 1 instructions:    3985585 cycles:    1253333 (33.68 %) ins/cycles: 3.18 mis. branches:         30 (cycles/mis.branch 40825.20) cache accesses:          0 (failure          0)
 stage 1 runs at 0.79 cycles per input byte.
stage 1 instructions:    3886990 cycles:    1199399 (32.71 %) ins/cycles: 3.24 mis. branches:         31 (cycles/mis.branch 38319.47) cache accesses:          0 (failure          0)
 stage 1 runs at 0.76 cycles per input byte.
jsonexamples/numbers.json
stage 1 instructions:     373437 cycles:     123339 (23.03 %) ins/cycles: 3.03 mis. branches:         30 (cycles/mis.branch 4025.30) cache accesses:          0 (failure          0)
 stage 1 runs at 0.82 cycles per input byte.
stage 1 instructions:     394542 cycles:     126474 (26.11 %) ins/cycles: 3.12 mis. branches:         34 (cycles/mis.branch 3667.62) cache accesses:          0 (failure          0)
 stage 1 runs at 0.84 cycles per input byte.
stage 1 instructions:     385155 cycles:     121644 (25.75 %) ins/cycles: 3.17 mis. branches:         45 (cycles/mis.branch 2684.96) cache accesses:          0 (failure          0)
 stage 1 runs at 0.81 cycles per input byte.
jsonexamples/random.json
stage 1 instructions:    1861215 cycles:     581716 (43.73 %) ins/cycles: 3.20 mis. branches:        577 (cycles/mis.branch 1007.21) cache accesses:          0 (failure          0)
 stage 1 runs at 1.14 cycles per input byte.
stage 1 instructions:    1803877 cycles:     568971 (43.26 %) ins/cycles: 3.17 mis. branches:       1006 (cycles/mis.branch 565.19) cache accesses:          0 (failure          0)
 stage 1 runs at 1.11 cycles per input byte.
stage 1 instructions:    2011749 cycles:     613214 (45.22 %) ins/cycles: 3.28 mis. branches:        595 (cycles/mis.branch 1029.02) cache accesses:          0 (failure          0)
 stage 1 runs at 1.20 cycles per input byte.
jsonexamples/small
jsonexamples/twitterescaped.json
stage 1 instructions:    1288771 cycles:     429563 (25.57 %) ins/cycles: 3.00 mis. branches:        392 (cycles/mis.branch 1095.32) cache accesses:          0 (failure          0)
 stage 1 runs at 0.76 cycles per input byte.
stage 1 instructions:    1370486 cycles:     434483 (25.84 %) ins/cycles: 3.15 mis. branches:        434 (cycles/mis.branch 1000.38) cache accesses:          0 (failure          0)
 stage 1 runs at 0.77 cycles per input byte.
stage 1 instructions:    1334897 cycles:     420720 (25.09 %) ins/cycles: 3.17 mis. branches:        452 (cycles/mis.branch 928.90) cache accesses:          0 (failure          0)
 stage 1 runs at 0.75 cycles per input byte.
jsonexamples/twitter.json
stage 1 instructions:    1640771 cycles:     518221 (49.50 %) ins/cycles: 3.17 mis. branches:        325 (cycles/mis.branch 1590.45) cache accesses:          0 (failure          0)
 stage 1 runs at 0.82 cycles per input byte.
stage 1 instructions:    1697314 cycles:     523036 (49.37 %) ins/cycles: 3.25 mis. branches:        429 (cycles/mis.branch 1217.10) cache accesses:          0 (failure          0)
 stage 1 runs at 0.83 cycles per input byte.
stage 1 instructions:    1739204 cycles:     530394 (50.33 %) ins/cycles: 3.28 mis. branches:        333 (cycles/mis.branch 1591.50) cache accesses:          0 (failure          0)
 stage 1 runs at 0.84 cycles per input byte.
jsonexamples/update-center.json
stage 1 instructions:    1306615 cycles:     445957 (40.32 %) ins/cycles: 2.93 mis. branches:        908 (cycles/mis.branch 491.09) cache accesses:          0 (failure          0)
 stage 1 runs at 0.84 cycles per input byte.
stage 1 instructions:    1381306 cycles:     453367 (40.70 %) ins/cycles: 3.05 mis. branches:        774 (cycles/mis.branch 585.62) cache accesses:          0 (failure          0)
 stage 1 runs at 0.85 cycles per input byte.
stage 1 instructions:    1349059 cycles:     441870 (40.11 %) ins/cycles: 3.05 mis. branches:        931 (cycles/mis.branch 474.27) cache accesses:          0 (failure          0)
 stage 1 runs at 0.83 cycles per input byte.

Same test with GNU GCC 8.1 and a skylake-x processor. Again, the first number of each file is from jkeiser/utf8_shootout_lookup, the second from this PR and the last one from master...
jsonexamples/apache_builds.json
stage 1 instructions:     306699 cycles:      80740 (44.13 %) ins/cycles: 3.80 mis. branches:          8 (cycles/mis.branch 9517.90) cache accesses:          0 (failure          0)
 stage 1 runs at 0.63 cycles per input byte.
stage 1 instructions:     324598 cycles:      82605 (44.96 %) ins/cycles: 3.93 mis. branches:          5 (cycles/mis.branch 13873.93) cache accesses:          0 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:     316645 cycles:      83125 (44.53 %) ins/cycles: 3.81 mis. branches:          7 (cycles/mis.branch 10738.29) cache accesses:          0 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
jsonexamples/canada.json
stage 1 instructions:    6071975 cycles:    1695974 (22.62 %) ins/cycles: 3.58 mis. branches:       5229 (cycles/mis.branch 324.33) cache accesses:      56367 (failure        185)
 stage 1 runs at 0.75 cycles per input byte.
stage 1 instructions:    6388530 cycles:    1727603 (22.92 %) ins/cycles: 3.70 mis. branches:       5284 (cycles/mis.branch 326.94) cache accesses:      56311 (failure        193)
 stage 1 runs at 0.77 cycles per input byte.
stage 1 instructions:    6247841 cycles:    1734871 (22.94 %) ins/cycles: 3.60 mis. branches:       5319 (cycles/mis.branch 326.12) cache accesses:      56350 (failure        288)
 stage 1 runs at 0.77 cycles per input byte.
jsonexamples/citm_catalog.json
stage 1 instructions:    3934135 cycles:    1041453 (45.93 %) ins/cycles: 3.78 mis. branches:        179 (cycles/mis.branch 5789.07) cache accesses:      35714 (failure          4)
 stage 1 runs at 0.60 cycles per input byte.
stage 1 instructions:    4174871 cycles:    1065195 (46.50 %) ins/cycles: 3.92 mis. branches:        189 (cycles/mis.branch 5618.12) cache accesses:      35678 (failure         12)
 stage 1 runs at 0.62 cycles per input byte.
stage 1 instructions:    4070941 cycles:    1072263 (46.75 %) ins/cycles: 3.80 mis. branches:        189 (cycles/mis.branch 5664.36) cache accesses:      35720 (failure          9)
 stage 1 runs at 0.62 cycles per input byte.
jsonexamples/github_events.json
stage 1 instructions:     146481 cycles:      39134 (43.20 %) ins/cycles: 3.74 mis. branches:          4 (cycles/mis.branch 9503.37) cache accesses:          0 (failure          0)
 stage 1 runs at 0.60 cycles per input byte.
stage 1 instructions:     155548 cycles:      40095 (44.19 %) ins/cycles: 3.88 mis. branches:          5 (cycles/mis.branch 7624.15) cache accesses:          0 (failure          0)
 stage 1 runs at 0.62 cycles per input byte.
stage 1 instructions:     151610 cycles:      40200 (44.20 %) ins/cycles: 3.77 mis. branches:          4 (cycles/mis.branch 8368.09) cache accesses:          0 (failure          0)
 stage 1 runs at 0.62 cycles per input byte.
jsonexamples/gsoc-2018.json
stage 1 instructions:    5963939 cycles:    1726316 (49.93 %) ins/cycles: 3.45 mis. branches:       5632 (cycles/mis.branch 306.49) cache accesses:      57034 (failure        370)
 stage 1 runs at 0.52 cycles per input byte.
stage 1 instructions:    6431910 cycles:    1788508 (50.60 %) ins/cycles: 3.60 mis. branches:       5611 (cycles/mis.branch 318.75) cache accesses:      57017 (failure        588)
 stage 1 runs at 0.54 cycles per input byte.
stage 1 instructions:    6223925 cycles:    1783585 (50.65 %) ins/cycles: 3.49 mis. branches:       5710 (cycles/mis.branch 312.36) cache accesses:      57037 (failure        365)
 stage 1 runs at 0.54 cycles per input byte.
jsonexamples/instruments.json
stage 1 instructions:     544353 cycles:     143194 (40.37 %) ins/cycles: 3.80 mis. branches:         21 (cycles/mis.branch 6522.76) cache accesses:          6 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:     575338 cycles:     146475 (40.97 %) ins/cycles: 3.93 mis. branches:         23 (cycles/mis.branch 6325.04) cache accesses:          0 (failure          0)
 stage 1 runs at 0.66 cycles per input byte.
stage 1 instructions:     561569 cycles:     147125 (40.87 %) ins/cycles: 3.82 mis. branches:         19 (cycles/mis.branch 7431.35) cache accesses:          0 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
jsonexamples/marine_ik.json
stage 1 instructions:    9122411 cycles:    2572956 (23.19 %) ins/cycles: 3.55 mis. branches:       8983 (cycles/mis.branch 286.41) cache accesses:      87251 (failure       6621)
 stage 1 runs at 0.86 cycles per input byte.
stage 1 instructions:    9573674 cycles:    2622283 (23.62 %) ins/cycles: 3.65 mis. branches:       8255 (cycles/mis.branch 317.66) cache accesses:      87224 (failure       7509)
 stage 1 runs at 0.88 cycles per input byte.
stage 1 instructions:    9407185 cycles:    2625957 (23.49 %) ins/cycles: 3.58 mis. branches:       8332 (cycles/mis.branch 315.16) cache accesses:      87254 (failure       6123)
 stage 1 runs at 0.88 cycles per input byte.
jsonexamples/mesh.json
stage 1 instructions:    2133371 cycles:     569986 (21.75 %) ins/cycles: 3.74 mis. branches:        734 (cycles/mis.branch 776.26) cache accesses:      20723 (failure          0)
 stage 1 runs at 0.79 cycles per input byte.
stage 1 instructions:    2249292 cycles:     586010 (22.17 %) ins/cycles: 3.84 mis. branches:        659 (cycles/mis.branch 888.81) cache accesses:      20134 (failure          0)
 stage 1 runs at 0.81 cycles per input byte.
stage 1 instructions:    2212920 cycles:     588602 (22.11 %) ins/cycles: 3.76 mis. branches:        681 (cycles/mis.branch 864.29) cache accesses:      20519 (failure          0)
 stage 1 runs at 0.81 cycles per input byte.
jsonexamples/mesh.pretty.json
stage 1 instructions:    3763783 cycles:     993297 (28.64 %) ins/cycles: 3.79 mis. branches:         41 (cycles/mis.branch 24109.15) cache accesses:      34432 (failure         10)
 stage 1 runs at 0.63 cycles per input byte.
stage 1 instructions:    3985604 cycles:    1015153 (29.25 %) ins/cycles: 3.93 mis. branches:         38 (cycles/mis.branch 26714.58) cache accesses:      34403 (failure          9)
 stage 1 runs at 0.64 cycles per input byte.
stage 1 instructions:    3887019 cycles:    1020319 (29.18 %) ins/cycles: 3.81 mis. branches:         42 (cycles/mis.branch 23839.24) cache accesses:      34413 (failure          8)
 stage 1 runs at 0.65 cycles per input byte.
jsonexamples/numbers.json
stage 1 instructions:     373436 cycles:      98732 (21.09 %) ins/cycles: 3.78 mis. branches:         31 (cycles/mis.branch 3121.59) cache accesses:          0 (failure          0)
 stage 1 runs at 0.66 cycles per input byte.
stage 1 instructions:     394539 cycles:     100988 (21.59 %) ins/cycles: 3.91 mis. branches:         32 (cycles/mis.branch 3090.98) cache accesses:          0 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
stage 1 instructions:     385162 cycles:     101681 (21.42 %) ins/cycles: 3.79 mis. branches:         46 (cycles/mis.branch 2164.95) cache accesses:          0 (failure          0)
 stage 1 runs at 0.68 cycles per input byte.
jsonexamples/random.json
stage 1 instructions:    1861235 cycles:     514732 (42.23 %) ins/cycles: 3.62 mis. branches:        823 (cycles/mis.branch 625.30) cache accesses:      10480 (failure          0)
 stage 1 runs at 1.01 cycles per input byte.
stage 1 instructions:    1803896 cycles:     495907 (41.21 %) ins/cycles: 3.64 mis. branches:       1509 (cycles/mis.branch 328.61) cache accesses:       9939 (failure          0)
 stage 1 runs at 0.97 cycles per input byte.
stage 1 instructions:    2011778 cycles:     554352 (44.36 %) ins/cycles: 3.63 mis. branches:        762 (cycles/mis.branch 727.40) cache accesses:       9705 (failure          2)
 stage 1 runs at 1.09 cycles per input byte.
jsonexamples/small
jsonexamples/twitterescaped.json
stage 1 instructions:    1288771 cycles:     373087 (22.48 %) ins/cycles: 3.45 mis. branches:       1562 (cycles/mis.branch 238.73) cache accesses:       6355 (failure          1)
 stage 1 runs at 0.66 cycles per input byte.
stage 1 instructions:    1370484 cycles:     381644 (22.95 %) ins/cycles: 3.59 mis. branches:       1481 (cycles/mis.branch 257.62) cache accesses:       6605 (failure          0)
 stage 1 runs at 0.68 cycles per input byte.
stage 1 instructions:    1336879 cycles:     380303 (22.84 %) ins/cycles: 3.52 mis. branches:       1391 (cycles/mis.branch 273.29) cache accesses:       7424 (failure          1)
 stage 1 runs at 0.68 cycles per input byte.
jsonexamples/twitter.json
stage 1 instructions:    1640770 cycles:     460755 (48.14 %) ins/cycles: 3.56 mis. branches:        931 (cycles/mis.branch 494.56) cache accesses:       8138 (failure          0)
 stage 1 runs at 0.73 cycles per input byte.
stage 1 instructions:    1697316 cycles:     456805 (47.99 %) ins/cycles: 3.72 mis. branches:        986 (cycles/mis.branch 463.04) cache accesses:       8368 (failure          1)
 stage 1 runs at 0.72 cycles per input byte.
stage 1 instructions:    1739216 cycles:     484627 (49.49 %) ins/cycles: 3.59 mis. branches:        879 (cycles/mis.branch 550.79) cache accesses:       8639 (failure          0)
 stage 1 runs at 0.77 cycles per input byte.
jsonexamples/update-center.json
stage 1 instructions:    1306633 cycles:     381007 (38.31 %) ins/cycles: 3.43 mis. branches:       1857 (cycles/mis.branch 205.16) cache accesses:       8074 (failure          1)
 stage 1 runs at 0.71 cycles per input byte.
stage 1 instructions:    1381323 cycles:     388366 (38.73 %) ins/cycles: 3.56 mis. branches:       1829 (cycles/mis.branch 212.24) cache accesses:       7184 (failure          0)
 stage 1 runs at 0.73 cycles per input byte.
stage 1 instructions:    1349440 cycles:     392281 (38.98 %) ins/cycles: 3.44 mis. branches:       1968 (cycles/mis.branch 199.32) cache accesses:       7607 (failure          1)
 stage 1 runs at 0.74 cycles per input byte.

I'm seeing command #1 below about 1% faster on both SSE and AVX, on my machine.

Verified. The mlga branch has fewer instructions (about 1% difference).
$ git checkout jkeiser/mlga; make parse; ./parse   jsonexamples/twitter.json
stage 1 instructions:    1676779 cycles:     465482 (46.87 %) ins/cycles: 3.60 mis. branches:       1128 (cycles/mis.branch 412.60) cache accesses:       9124 (failure          0)
 stage 1 runs at 0.74 cycles per input byte.

$ git checkout jkeiser/utf8_flag_lookup; make parse; ./parse   jsonexamples/twitter.json
stage 1 instructions:    1697316 cycles:     464992 (47.13 %) ins/cycles: 3.65 mis. branches:       1040 (cycles/mis.branch 446.76) cache accesses:       8294 (failure          0)
 stage 1 runs at 0.74 cycles per input byte.

Same output on a cannon lake processor, with GNU GCC 8.3. First number for each file is from jkeiser/utf8_shootout_lookup, second number is this PR, last number is master...
stage 1 instructions:     306673 cycles:      80858 (43.56 %) ins/cycles: 3.79 mis. branches:         13 (cycles/mis.branch 5800.48) cache accesses:       2311 (failure          0)
 stage 1 runs at 0.64 cycles per input byte.
stage 1 instructions:     324573 cycles:      82787 (44.33 %) ins/cycles: 3.92 mis. branches:          9 (cycles/mis.branch 8648.07) cache accesses:       2757 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:     316610 cycles:      83228 (44.69 %) ins/cycles: 3.80 mis. branches:         14 (cycles/mis.branch 5809.64) cache accesses:       2436 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
jsonexamples/canada.json
stage 1 instructions:    6071951 cycles:    1776412 (23.79 %) ins/cycles: 3.42 mis. branches:       5144 (cycles/mis.branch 345.28) cache accesses:      74553 (failure      23912)
 stage 1 runs at 0.79 cycles per input byte.
stage 1 instructions:    6388505 cycles:    1777172 (23.76 %) ins/cycles: 3.59 mis. branches:       5083 (cycles/mis.branch 349.62) cache accesses:      74596 (failure      21863)
 stage 1 runs at 0.79 cycles per input byte.
stage 1 instructions:    6247806 cycles:    1780522 (23.83 %) ins/cycles: 3.51 mis. branches:       5105 (cycles/mis.branch 348.74) cache accesses:      74606 (failure      22726)
 stage 1 runs at 0.79 cycles per input byte.
jsonexamples/citm_catalog.json
stage 1 instructions:    3934111 cycles:    1047203 (46.01 %) ins/cycles: 3.76 mis. branches:        203 (cycles/mis.branch 5148.50) cache accesses:      47226 (failure       2779)
 stage 1 runs at 0.61 cycles per input byte.
stage 1 instructions:    4174846 cycles:    1078563 (46.88 %) ins/cycles: 3.87 mis. branches:        201 (cycles/mis.branch 5355.33) cache accesses:      47141 (failure       2960)
 stage 1 runs at 0.62 cycles per input byte.
stage 1 instructions:    4070908 cycles:    1079057 (47.06 %) ins/cycles: 3.77 mis. branches:        188 (cycles/mis.branch 5730.52) cache accesses:      47223 (failure       2034)
 stage 1 runs at 0.62 cycles per input byte.
jsonexamples/github_events.json
stage 1 instructions:     146455 cycles:      39142 (43.23 %) ins/cycles: 3.74 mis. branches:          5 (cycles/mis.branch 7175.50) cache accesses:        357 (failure          0)
 stage 1 runs at 0.60 cycles per input byte.
stage 1 instructions:     155523 cycles:      40206 (43.99 %) ins/cycles: 3.87 mis. branches:          6 (cycles/mis.branch 6465.10) cache accesses:        520 (failure          0)
 stage 1 runs at 0.62 cycles per input byte.
stage 1 instructions:     151575 cycles:      40407 (44.59 %) ins/cycles: 3.75 mis. branches:          4 (cycles/mis.branch 9306.10) cache accesses:        635 (failure          0)
 stage 1 runs at 0.62 cycles per input byte.
jsonexamples/gsoc-2018.json
stage 1 instructions:    5963911 cycles:    1779017 (49.94 %) ins/cycles: 3.35 mis. branches:       5374 (cycles/mis.branch 330.99) cache accesses:      75301 (failure      18945)
 stage 1 runs at 0.53 cycles per input byte.
stage 1 instructions:    6431883 cycles:    1819443 (50.62 %) ins/cycles: 3.54 mis. branches:       5478 (cycles/mis.branch 332.12) cache accesses:      75322 (failure      18165)
 stage 1 runs at 0.55 cycles per input byte.
stage 1 instructions:    6223888 cycles:    1800758 (50.27 %) ins/cycles: 3.46 mis. branches:       5531 (cycles/mis.branch 325.52) cache accesses:      75362 (failure      19414)
 stage 1 runs at 0.54 cycles per input byte.
jsonexamples/instruments.json
stage 1 instructions:     544331 cycles:     143815 (40.83 %) ins/cycles: 3.78 mis. branches:         52 (cycles/mis.branch 2747.87) cache accesses:       6618 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:     575317 cycles:     146701 (41.27 %) ins/cycles: 3.92 mis. branches:         29 (cycles/mis.branch 4956.79) cache accesses:       6315 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
stage 1 instructions:     561538 cycles:     147087 (40.87 %) ins/cycles: 3.82 mis. branches:         24 (cycles/mis.branch 6022.73) cache accesses:       6474 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
jsonexamples/marine_ik.json
stage 1 instructions:    9122385 cycles:    2570060 (23.23 %) ins/cycles: 3.55 mis. branches:       8729 (cycles/mis.branch 294.42) cache accesses:     115875 (failure      55525)
 stage 1 runs at 0.86 cycles per input byte.
stage 1 instructions:    9573649 cycles:    2633422 (23.87 %) ins/cycles: 3.64 mis. branches:       8858 (cycles/mis.branch 297.27) cache accesses:     115737 (failure      55724)
 stage 1 runs at 0.88 cycles per input byte.
stage 1 instructions:    9383366 cycles:    2613843 (23.82 %) ins/cycles: 3.59 mis. branches:       8696 (cycles/mis.branch 300.55) cache accesses:     116013 (failure      56045)
 stage 1 runs at 0.88 cycles per input byte.
jsonexamples/mesh.json
stage 1 instructions:    2133351 cycles:     568111 (21.66 %) ins/cycles: 3.76 mis. branches:        884 (cycles/mis.branch 642.19) cache accesses:      27838 (failure         23)
 stage 1 runs at 0.79 cycles per input byte.
stage 1 instructions:    2249275 cycles:     586759 (22.36 %) ins/cycles: 3.83 mis. branches:        862 (cycles/mis.branch 679.93) cache accesses:      27826 (failure        164)
 stage 1 runs at 0.81 cycles per input byte.
stage 1 instructions:    2202273 cycles:     588539 (22.43 %) ins/cycles: 3.74 mis. branches:        460 (cycles/mis.branch 1278.83) cache accesses:      27861 (failure         15)
 stage 1 runs at 0.81 cycles per input byte.
jsonexamples/mesh.pretty.json
stage 1 instructions:    3763765 cycles:     997696 (28.75 %) ins/cycles: 3.77 mis. branches:         32 (cycles/mis.branch 30604.19) cache accesses:      45482 (failure       2533)
 stage 1 runs at 0.63 cycles per input byte.
stage 1 instructions:    3985587 cycles:    1017817 (29.41 %) ins/cycles: 3.92 mis. branches:         38 (cycles/mis.branch 26644.43) cache accesses:      45509 (failure       3403)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:    3886992 cycles:    1017145 (29.40 %) ins/cycles: 3.82 mis. branches:         39 (cycles/mis.branch 25556.41) cache accesses:      45470 (failure       2836)
 stage 1 runs at 0.64 cycles per input byte.
jsonexamples/numbers.json
stage 1 instructions:     373410 cycles:      98342 (21.04 %) ins/cycles: 3.80 mis. branches:         15 (cycles/mis.branch 6230.14) cache accesses:       3555 (failure          0)
 stage 1 runs at 0.66 cycles per input byte.
stage 1 instructions:     394514 cycles:     101032 (21.58 %) ins/cycles: 3.90 mis. branches:         34 (cycles/mis.branch 2962.38) cache accesses:       3950 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
stage 1 instructions:     385129 cycles:     101399 (21.62 %) ins/cycles: 3.80 mis. branches:         34 (cycles/mis.branch 2954.70) cache accesses:       3611 (failure          0)
 stage 1 runs at 0.68 cycles per input byte.
jsonexamples/random.json
stage 1 instructions:    1861217 cycles:     515543 (42.75 %) ins/cycles: 3.61 mis. branches:        984 (cycles/mis.branch 523.76) cache accesses:      18004 (failure          2)
 stage 1 runs at 1.01 cycles per input byte.
stage 1 instructions:    1803877 cycles:     487702 (41.71 %) ins/cycles: 3.70 mis. branches:       1310 (cycles/mis.branch 372.27) cache accesses:      17995 (failure          1)
 stage 1 runs at 0.96 cycles per input byte.
stage 1 instructions:    2011751 cycles:     551271 (44.92 %) ins/cycles: 3.65 mis. branches:        766 (cycles/mis.branch 719.65) cache accesses:      18021 (failure          0)
 stage 1 runs at 1.08 cycles per input byte.
jsonexamples/small
jsonexamples/twitterescaped.json
stage 1 instructions:    1288747 cycles:     355433 (21.90 %) ins/cycles: 3.63 mis. branches:        866 (cycles/mis.branch 410.28) cache accesses:      16386 (failure          1)
 stage 1 runs at 0.63 cycles per input byte.
stage 1 instructions:    1370461 cycles:     370373 (22.65 %) ins/cycles: 3.70 mis. branches:       1048 (cycles/mis.branch 353.26) cache accesses:      16340 (failure          2)
 stage 1 runs at 0.66 cycles per input byte.
stage 1 instructions:    1334872 cycles:     368018 (22.53 %) ins/cycles: 3.63 mis. branches:       1023 (cycles/mis.branch 359.40) cache accesses:      16395 (failure          2)
 stage 1 runs at 0.65 cycles per input byte.
jsonexamples/twitter.json
stage 1 instructions:    1640744 cycles:     461399 (49.39 %) ins/cycles: 3.56 mis. branches:        817 (cycles/mis.branch 564.21) cache accesses:      17834 (failure          2)
 stage 1 runs at 0.73 cycles per input byte.
stage 1 instructions:    1697291 cycles:     448148 (48.37 %) ins/cycles: 3.79 mis. branches:        777 (cycles/mis.branch 576.73) cache accesses:      17789 (failure          3)
 stage 1 runs at 0.71 cycles per input byte.
stage 1 instructions:    1739181 cycles:     478508 (50.15 %) ins/cycles: 3.63 mis. branches:        738 (cycles/mis.branch 648.07) cache accesses:      17835 (failure          3)
 stage 1 runs at 0.76 cycles per input byte.
jsonexamples/update-center.json
stage 1 instructions:    1306609 cycles:     368698 (38.25 %) ins/cycles: 3.54 mis. branches:       1370 (cycles/mis.branch 269.05) cache accesses:      16511 (failure          1)
 stage 1 runs at 0.69 cycles per input byte.
stage 1 instructions:    1381302 cycles:     378128 (38.97 %) ins/cycles: 3.65 mis. branches:       1448 (cycles/mis.branch 261.01) cache accesses:      16455 (failure          1)
 stage 1 runs at 0.71 cycles per input byte.
stage 1 instructions:    1349055 cycles:     376675 (38.93 %) ins/cycles: 3.58 mis. branches:       1383 (cycles/mis.branch 272.24) cache accesses:      16469 (failure          0)
 stage 1 runs at 0.71 cycles per input byte.

In terms of CPU cycles, this PR is worse than the another branch (jkeiser/utf8_shootout_lookup) in all cases on AMD Rome, except for one file (random). In fact, on AMD Rome, this PR is worse even than master most of the time.

Wow, that's a little crazy. I can switch it over. We can look at Zach's again in the new PR once we've finished breaking the prev_input dependency (it seems to benefit both algorithms, but slightly more Zach's). I may have a way to reduce the instruction count of this algorithm further, but I'll test it and let you know in a separate PR if so.

I would suggest merging jkeiser/mlga with this PR.

Thanks for looking, I was a little flabbergasted :)

@lemire changes pushed.

@jkeiser I recommend merging. I no longer see any significant performance regression anywhere.
At least with GNU GCC 8, on three different x64 processors, I see robust progress.
Here are my numbers with AMD Rome, for each file first line is master, second line is this PR. In all files, we see a reduction in both the number of instructions and the number of cycles... so it is solid progress...
stage 1 instructions:     316616 cycles:      98375 (47.19 %) ins/cycles: 3.22 mis. branches:         13 (cycles/mis.branch 7435.81) cache accesses:          0 (failure          0)
 stage 1 runs at 0.77 cycles per input byte.
stage 1 instructions:     306680 cycles:      97187 (47.09 %) ins/cycles: 3.16 mis. branches:          6 (cycles/mis.branch 14709.79) cache accesses:          0 (failure          0)
 stage 1 runs at 0.76 cycles per input byte.
jsonexamples/canada.json
stage 1 instructions:    6247812 cycles:    2126822 (26.91 %) ins/cycles: 2.94 mis. branches:       5162 (cycles/mis.branch 411.99) cache accesses:          0 (failure          0)
 stage 1 runs at 0.94 cycles per input byte.
stage 1 instructions:    6071956 cycles:    2103819 (26.66 %) ins/cycles: 2.89 mis. branches:       5080 (cycles/mis.branch 414.10) cache accesses:          0 (failure          0)
 stage 1 runs at 0.93 cycles per input byte.
jsonexamples/citm_catalog.json
stage 1 instructions:    4070933 cycles:    1228053 (50.30 %) ins/cycles: 3.31 mis. branches:        162 (cycles/mis.branch 7543.32) cache accesses:          0 (failure          0)
 stage 1 runs at 0.71 cycles per input byte.
stage 1 instructions:    3933745 cycles:    1217429 (50.24 %) ins/cycles: 3.23 mis. branches:        159 (cycles/mis.branch 7613.69) cache accesses:          0 (failure          0)
 stage 1 runs at 0.70 cycles per input byte.
jsonexamples/github_events.json
stage 1 instructions:     151602 cycles:      45913 (46.58 %) ins/cycles: 3.30 mis. branches:          4 (cycles/mis.branch 9527.62) cache accesses:          0 (failure          0)
 stage 1 runs at 0.70 cycles per input byte.
stage 1 instructions:     146475 cycles:      46084 (46.88 %) ins/cycles: 3.18 mis. branches:          6 (cycles/mis.branch 7386.50) cache accesses:          0 (failure          0)
 stage 1 runs at 0.71 cycles per input byte.
jsonexamples/gsoc-2018.json
stage 1 instructions:    6223915 cycles:    1851184 (54.26 %) ins/cycles: 3.36 mis. branches:       5706 (cycles/mis.branch 324.38) cache accesses:          0 (failure          0)
 stage 1 runs at 0.56 cycles per input byte.
stage 1 instructions:    5963937 cycles:    1918484 (55.36 %) ins/cycles: 3.11 mis. branches:       5647 (cycles/mis.branch 339.69) cache accesses:          0 (failure          0)
 stage 1 runs at 0.58 cycles per input byte.
jsonexamples/instruments.json
stage 1 instructions:     561542 cycles:     176426 (44.09 %) ins/cycles: 3.18 mis. branches:         32 (cycles/mis.branch 5454.52) cache accesses:          0 (failure          0)
 stage 1 runs at 0.80 cycles per input byte.
stage 1 instructions:     544336 cycles:     175948 (44.87 %) ins/cycles: 3.09 mis. branches:         23 (cycles/mis.branch 7400.56) cache accesses:          0 (failure          0)
 stage 1 runs at 0.80 cycles per input byte.
jsonexamples/marine_ik.json
stage 1 instructions:    9383373 cycles:    3294879 (28.55 %) ins/cycles: 2.85 mis. branches:       8466 (cycles/mis.branch 389.17) cache accesses:          0 (failure          0)
 stage 1 runs at 1.10 cycles per input byte.
stage 1 instructions:    9122393 cycles:    3234545 (28.12 %) ins/cycles: 2.82 mis. branches:       8051 (cycles/mis.branch 401.73) cache accesses:          0 (failure          0)
 stage 1 runs at 1.08 cycles per input byte.
jsonexamples/mesh.json
stage 1 instructions:    2202271 cycles:     720275 (25.08 %) ins/cycles: 3.06 mis. branches:        448 (cycles/mis.branch 1604.75) cache accesses:          0 (failure          0)
 stage 1 runs at 1.00 cycles per input byte.
stage 1 instructions:    2133352 cycles:     706488 (24.90 %) ins/cycles: 3.02 mis. branches:        422 (cycles/mis.branch 1672.05) cache accesses:          0 (failure          0)
 stage 1 runs at 0.98 cycles per input byte.
jsonexamples/mesh.pretty.json
stage 1 instructions:    3886990 cycles:    1200693 (32.81 %) ins/cycles: 3.24 mis. branches:         32 (cycles/mis.branch 36495.25) cache accesses:          0 (failure          0)
 stage 1 runs at 0.76 cycles per input byte.
stage 1 instructions:    3763764 cycles:    1187891 (32.04 %) ins/cycles: 3.17 mis. branches:         39 (cycles/mis.branch 30380.85) cache accesses:          0 (failure          0)
 stage 1 runs at 0.75 cycles per input byte.
jsonexamples/numbers.json
stage 1 instructions:     385155 cycles:     122336 (25.84 %) ins/cycles: 3.15 mis. branches:         32 (cycles/mis.branch 3800.44) cache accesses:          0 (failure          0)
 stage 1 runs at 0.81 cycles per input byte.
stage 1 instructions:     373438 cycles:     120364 (25.57 %) ins/cycles: 3.10 mis. branches:         26 (cycles/mis.branch 4580.59) cache accesses:          0 (failure          0)
 stage 1 runs at 0.80 cycles per input byte.
jsonexamples/random.json
stage 1 instructions:    2011749 cycles:     612876 (45.28 %) ins/cycles: 3.28 mis. branches:        580 (cycles/mis.branch 1056.09) cache accesses:          0 (failure          0)
 stage 1 runs at 1.20 cycles per input byte.
stage 1 instructions:    1838074 cycles:     568948 (43.37 %) ins/cycles: 3.23 mis. branches:        508 (cycles/mis.branch 1118.73) cache accesses:          0 (failure          0)
 stage 1 runs at 1.11 cycles per input byte.
jsonexamples/twitterescaped.json
stage 1 instructions:    1334897 cycles:     421679 (25.21 %) ins/cycles: 3.17 mis. branches:        522 (cycles/mis.branch 806.32) cache accesses:          0 (failure          0)
 stage 1 runs at 0.75 cycles per input byte.
stage 1 instructions:    1288773 cycles:     422319 (25.28 %) ins/cycles: 3.05 mis. branches:        540 (cycles/mis.branch 781.23) cache accesses:          0 (failure          0)
 stage 1 runs at 0.75 cycles per input byte.
jsonexamples/twitter.json
stage 1 instructions:    1739204 cycles:     527984 (50.18 %) ins/cycles: 3.29 mis. branches:        362 (cycles/mis.branch 1455.13) cache accesses:          0 (failure          0)
 stage 1 runs at 0.84 cycles per input byte.
stage 1 instructions:    1630498 cycles:     506433 (48.83 %) ins/cycles: 3.22 mis. branches:        363 (cycles/mis.branch 1391.50) cache accesses:          0 (failure          0)
 stage 1 runs at 0.80 cycles per input byte.
jsonexamples/update-center.json
stage 1 instructions:    1349059 cycles:     442039 (40.37 %) ins/cycles: 3.05 mis. branches:       1017 (cycles/mis.branch 434.37) cache accesses:          0 (failure          0)
 stage 1 runs at 0.83 cycles per input byte.
stage 1 instructions:    1306530 cycles:     435895 (39.80 %) ins/cycles: 3.00 mis. branches:        877 (cycles/mis.branch 496.78) cache accesses:          0 (failure          0)
 stage 1 runs at 0.82 cycles per input byte.

Same benchmark under cannon lake... we are better all over with this PR...
jsonexamples/apache_builds.json
stage 1 instructions:     316610 cycles:      83165 (45.02 %) ins/cycles: 3.81 mis. branches:          9 (cycles/mis.branch 8415.90) cache accesses:       2147 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:     306674 cycles:      81112 (44.15 %) ins/cycles: 3.78 mis. branches:          5 (cycles/mis.branch 14665.07) cache accesses:       2422 (failure          0)
 stage 1 runs at 0.64 cycles per input byte.
jsonexamples/canada.json
stage 1 instructions:    6247806 cycles:    1793658 (24.01 %) ins/cycles: 3.48 mis. branches:       5037 (cycles/mis.branch 356.03) cache accesses:      74508 (failure      19835)
 stage 1 runs at 0.80 cycles per input byte.
stage 1 instructions:    6071950 cycles:    1744194 (23.48 %) ins/cycles: 3.48 mis. branches:       5170 (cycles/mis.branch 337.33) cache accesses:      74518 (failure      20868)
 stage 1 runs at 0.77 cycles per input byte.
jsonexamples/citm_catalog.json
stage 1 instructions:    4070908 cycles:    1077699 (46.74 %) ins/cycles: 3.78 mis. branches:        188 (cycles/mis.branch 5711.18) cache accesses:      47288 (failure       3070)
 stage 1 runs at 0.62 cycles per input byte.
stage 1 instructions:    3933720 cycles:    1050098 (46.18 %) ins/cycles: 3.75 mis. branches:        222 (cycles/mis.branch 4717.42) cache accesses:      47256 (failure       2921)
 stage 1 runs at 0.61 cycles per input byte.
jsonexamples/github_events.json
stage 1 instructions:     151575 cycles:      40368 (44.70 %) ins/cycles: 3.75 mis. branches:          4 (cycles/mis.branch 8960.77) cache accesses:        668 (failure          0)
 stage 1 runs at 0.62 cycles per input byte.
stage 1 instructions:     146447 cycles:      39251 (43.96 %) ins/cycles: 3.73 mis. branches:          4 (cycles/mis.branch 9213.93) cache accesses:        349 (failure          0)
 stage 1 runs at 0.60 cycles per input byte.
jsonexamples/gsoc-2018.json
stage 1 instructions:    6223890 cycles:    1813202 (50.52 %) ins/cycles: 3.43 mis. branches:       5538 (cycles/mis.branch 327.38) cache accesses:      75297 (failure      21185)
 stage 1 runs at 0.54 cycles per input byte.
stage 1 instructions:    5963912 cycles:    1762461 (49.87 %) ins/cycles: 3.38 mis. branches:       5334 (cycles/mis.branch 330.41) cache accesses:      75291 (failure      18998)
 stage 1 runs at 0.53 cycles per input byte.
jsonexamples/instruments.json
stage 1 instructions:     561538 cycles:     147095 (41.49 %) ins/cycles: 3.82 mis. branches:         25 (cycles/mis.branch 5805.35) cache accesses:       6536 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
stage 1 instructions:     544332 cycles:     144488 (40.92 %) ins/cycles: 3.77 mis. branches:         52 (cycles/mis.branch 2746.21) cache accesses:       6250 (failure          0)
 stage 1 runs at 0.66 cycles per input byte.
jsonexamples/marine_ik.json
stage 1 instructions:    9383366 cycles:    2613568 (23.76 %) ins/cycles: 3.59 mis. branches:       8746 (cycles/mis.branch 298.81) cache accesses:     115888 (failure      57139)
 stage 1 runs at 0.88 cycles per input byte.
stage 1 instructions:    9122387 cycles:    2587847 (23.47 %) ins/cycles: 3.53 mis. branches:       9029 (cycles/mis.branch 286.61) cache accesses:     116103 (failure      65801)
 stage 1 runs at 0.87 cycles per input byte.
jsonexamples/mesh.json
stage 1 instructions:    2202273 cycles:     572813 (21.93 %) ins/cycles: 3.84 mis. branches:        467 (cycles/mis.branch 1225.79) cache accesses:      27860 (failure         25)
 stage 1 runs at 0.79 cycles per input byte.
stage 1 instructions:    2133354 cycles:     561467 (21.66 %) ins/cycles: 3.80 mis. branches:        444 (cycles/mis.branch 1263.95) cache accesses:      27847 (failure         79)
 stage 1 runs at 0.78 cycles per input byte.
jsonexamples/mesh.pretty.json
stage 1 instructions:    3886992 cycles:    1021982 (29.57 %) ins/cycles: 3.80 mis. branches:         40 (cycles/mis.branch 25048.58) cache accesses:      45526 (failure       2687)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:    3763766 cycles:    1003362 (29.13 %) ins/cycles: 3.75 mis. branches:         32 (cycles/mis.branch 31160.33) cache accesses:      45540 (failure       3106)
 stage 1 runs at 0.64 cycles per input byte.
jsonexamples/numbers.json
stage 1 instructions:     385129 cycles:     101249 (21.59 %) ins/cycles: 3.80 mis. branches:         24 (cycles/mis.branch 4164.06) cache accesses:       3767 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
stage 1 instructions:     373413 cycles:      99101 (21.20 %) ins/cycles: 3.77 mis. branches:         21 (cycles/mis.branch 4613.25) cache accesses:       3948 (failure          0)
 stage 1 runs at 0.66 cycles per input byte.
jsonexamples/random.json
stage 1 instructions:    2011749 cycles:     551060 (45.03 %) ins/cycles: 3.65 mis. branches:        750 (cycles/mis.branch 734.39) cache accesses:      18019 (failure          2)
 stage 1 runs at 1.08 cycles per input byte.
stage 1 instructions:    1838074 cycles:     508601 (43.11 %) ins/cycles: 3.61 mis. branches:       1007 (cycles/mis.branch 505.06) cache accesses:      18016 (failure          3)
 stage 1 runs at 1.00 cycles per input byte.
jsonexamples/twitterescaped.json
stage 1 instructions:    1334872 cycles:     367456 (22.52 %) ins/cycles: 3.63 mis. branches:        990 (cycles/mis.branch 370.85) cache accesses:      16391 (failure          3)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:    1288746 cycles:     357324 (22.00 %) ins/cycles: 3.61 mis. branches:        890 (cycles/mis.branch 401.44) cache accesses:      16388 (failure          2)
 stage 1 runs at 0.64 cycles per input byte.
jsonexamples/twitter.json
stage 1 instructions:    1739181 cycles:     482251 (50.27 %) ins/cycles: 3.61 mis. branches:        739 (cycles/mis.branch 652.13) cache accesses:      17834 (failure          2)
 stage 1 runs at 0.76 cycles per input byte.
stage 1 instructions:    1630471 cycles:     456655 (48.94 %) ins/cycles: 3.57 mis. branches:        956 (cycles/mis.branch 477.57) cache accesses:      17832 (failure         15)
 stage 1 runs at 0.72 cycles per input byte.
jsonexamples/update-center.json
stage 1 instructions:    1349055 cycles:     377159 (38.94 %) ins/cycles: 3.58 mis. branches:       1386 (cycles/mis.branch 272.10) cache accesses:      16467 (failure          2)
 stage 1 runs at 0.71 cycles per input byte.
stage 1 instructions:    1306526 cycles:     373290 (38.71 %) ins/cycles: 3.50 mis. branches:       1600 (cycles/mis.branch 233.30) cache accesses:      16500 (failure          4)
 stage 1 runs at 0.70 cycles per input byte.

For the older skylake processors,  the story is much the same... this PR is a win everywhere...
stage 1 instructions:     316614 cycles:      84092 (44.26 %) ins/cycles: 3.77 mis. branches:          6 (cycles/mis.branch 13345.87) cache accesses:       4239 (failure          0)
 stage 1 runs at 0.66 cycles per input byte.
stage 1 instructions:     306678 cycles:      82465 (44.06 %) ins/cycles: 3.72 mis. branches:         11 (cycles/mis.branch 7039.88) cache accesses:       4193 (failure          0)
 stage 1 runs at 0.65 cycles per input byte.
jsonexamples/canada.json
stage 1 instructions:    6247810 cycles:    1739059 (22.84 %) ins/cycles: 3.59 mis. branches:       5274 (cycles/mis.branch 329.69) cache accesses:     122825 (failure       2642)
 stage 1 runs at 0.77 cycles per input byte.
stage 1 instructions:    6071954 cycles:    1712430 (22.60 %) ins/cycles: 3.55 mis. branches:       5325 (cycles/mis.branch 321.56) cache accesses:     122863 (failure       2650)
 stage 1 runs at 0.76 cycles per input byte.
jsonexamples/citm_catalog.json
stage 1 instructions:    4070910 cycles:    1077585 (46.28 %) ins/cycles: 3.78 mis. branches:        183 (cycles/mis.branch 5859.63) cache accesses:      72119 (failure         19)
 stage 1 runs at 0.62 cycles per input byte.
stage 1 instructions:    3933722 cycles:    1050667 (45.70 %) ins/cycles: 3.74 mis. branches:        193 (cycles/mis.branch 5432.62) cache accesses:      72189 (failure         12)
 stage 1 runs at 0.61 cycles per input byte.
jsonexamples/github_events.json
stage 1 instructions:     151579 cycles:      40852 (44.17 %) ins/cycles: 3.71 mis. branches:          4 (cycles/mis.branch 8693.82) cache accesses:        346 (failure          0)
 stage 1 runs at 0.63 cycles per input byte.
stage 1 instructions:     146451 cycles:      39933 (43.99 %) ins/cycles: 3.67 mis. branches:          4 (cycles/mis.branch 8519.96) cache accesses:        801 (failure          0)
 stage 1 runs at 0.61 cycles per input byte.
jsonexamples/gsoc-2018.json
stage 1 instructions:    6223894 cycles:    1788703 (51.37 %) ins/cycles: 3.48 mis. branches:       5628 (cycles/mis.branch 317.81) cache accesses:     123261 (failure       3503)
 stage 1 runs at 0.54 cycles per input byte.
stage 1 instructions:    5963918 cycles:    1878634 (52.61 %) ins/cycles: 3.17 mis. branches:       5730 (cycles/mis.branch 327.81) cache accesses:     123291 (failure       4186)
 stage 1 runs at 0.56 cycles per input byte.
jsonexamples/instruments.json
stage 1 instructions:     561538 cycles:     148982 (40.82 %) ins/cycles: 3.77 mis. branches:         24 (cycles/mis.branch 6081.65) cache accesses:      10437 (failure          0)
 stage 1 runs at 0.68 cycles per input byte.
stage 1 instructions:     544332 cycles:     150380 (41.10 %) ins/cycles: 3.62 mis. branches:         48 (cycles/mis.branch 3127.13) cache accesses:      10285 (failure          0)
 stage 1 runs at 0.68 cycles per input byte.
jsonexamples/marine_ik.json
stage 1 instructions:    9379354 cycles:    2610053 (23.32 %) ins/cycles: 3.59 mis. branches:       8387 (cycles/mis.branch 311.19) cache accesses:     192859 (failure      36307)
 stage 1 runs at 0.87 cycles per input byte.
stage 1 instructions:    9122390 cycles:    2581112 (23.09 %) ins/cycles: 3.53 mis. branches:       8684 (cycles/mis.branch 297.21) cache accesses:     191719 (failure      29990)
 stage 1 runs at 0.87 cycles per input byte.
jsonexamples/mesh.json
stage 1 instructions:    2200498 cycles:     581631 (21.73 %) ins/cycles: 3.78 mis. branches:        628 (cycles/mis.branch 924.91) cache accesses:      43088 (failure          0)
 stage 1 runs at 0.80 cycles per input byte.
stage 1 instructions:    2133350 cycles:     574460 (21.44 %) ins/cycles: 3.71 mis. branches:        799 (cycles/mis.branch 718.71) cache accesses:      43111 (failure          0)
 stage 1 runs at 0.79 cycles per input byte.
jsonexamples/mesh.pretty.json
stage 1 instructions:    3886988 cycles:    1024687 (28.98 %) ins/cycles: 3.79 mis. branches:         39 (cycles/mis.branch 26206.84) cache accesses:      69681 (failure         37)
 stage 1 runs at 0.65 cycles per input byte.
stage 1 instructions:    3763762 cycles:    1001806 (28.44 %) ins/cycles: 3.76 mis. branches:         50 (cycles/mis.branch 19720.60) cache accesses:      74968 (failure         47)
 stage 1 runs at 0.64 cycles per input byte.
jsonexamples/numbers.json
stage 1 instructions:     385131 cycles:     102491 (21.20 %) ins/cycles: 3.76 mis. branches:         19 (cycles/mis.branch 5248.96) cache accesses:       5594 (failure          0)
 stage 1 runs at 0.68 cycles per input byte.
stage 1 instructions:     373415 cycles:     100503 (20.84 %) ins/cycles: 3.72 mis. branches:         25 (cycles/mis.branch 3957.30) cache accesses:       6350 (failure          0)
 stage 1 runs at 0.67 cycles per input byte.
jsonexamples/random.json
stage 1 instructions:    2011746 cycles:     560420 (43.47 %) ins/cycles: 3.59 mis. branches:        764 (cycles/mis.branch 732.72) cache accesses:      29795 (failure          0)
 stage 1 runs at 1.10 cycles per input byte.
stage 1 instructions:    1838072 cycles:     521865 (41.91 %) ins/cycles: 3.52 mis. branches:       1186 (cycles/mis.branch 439.92) cache accesses:      29787 (failure          0)
 stage 1 runs at 1.02 cycles per input byte.
jsonexamples/twitterescaped.json
stage 1 instructions:    1334580 cycles:     383388 (22.92 %) ins/cycles: 3.48 mis. branches:       1600 (cycles/mis.branch 239.57) cache accesses:      25056 (failure          0)
 stage 1 runs at 0.68 cycles per input byte.
stage 1 instructions:    1288750 cycles:     371475 (22.40 %) ins/cycles: 3.47 mis. branches:       1377 (cycles/mis.branch 269.72) cache accesses:      25157 (failure          0)
 stage 1 runs at 0.66 cycles per input byte.
jsonexamples/twitter.json
stage 1 instructions:    1739185 cycles:     486210 (49.26 %) ins/cycles: 3.58 mis. branches:        810 (cycles/mis.branch 599.88) cache accesses:      27266 (failure          0)
 stage 1 runs at 0.77 cycles per input byte.
stage 1 instructions:    1630475 cycles:     470493 (48.42 %) ins/cycles: 3.47 mis. branches:       1274 (cycles/mis.branch 369.14) cache accesses:      29189 (failure          0)
 stage 1 runs at 0.75 cycles per input byte.
jsonexamples/update-center.json
stage 1 instructions:    1349004 cycles:     385782 (38.45 %) ins/cycles: 3.50 mis. branches:       1643 (cycles/mis.branch 234.79) cache accesses:      27096 (failure          0)
 stage 1 runs at 0.72 cycles per input byte.
stage 1 instructions:    1306526 cycles:     382401 (38.26 %) ins/cycles: 3.42 mis. branches:       1797 (cycles/mis.branch 212.73) cache accesses:      27070 (failure          0)
 stage 1 runs at 0.72 cycles per input byte.

Oh. Will merge without my little tiny change I just made, that'll be a separate PR :)

@jkeiser belated thanks for CCing me in :) I have not had time to engage, looks like you guys arrived at a good shared solution.