Top all-time · #2955
Branch Free
Personal blog · branchfree.org · on HN as glangdaleprogrammingsystemshardware
Branch Free is a personal blog at branchfree.org about programming, systems and hardware. Since 2018, 26 different Hacker News readers have linked it 48 times, most often “Question: Is matching *fixed* regexes with Back-references in P?”. It is still writing: the last post was on 2024-11-25, and you can follow it by feed.
Too few sampled comments (17) to say how often HN recommends it.?
Why HN links it
HN readers link Geoff Langdale's blog for posts on SIMD, branch-avoiding algorithms and fast parsing, including fast JSON and CSV processing, AVX-512 instructions and bit manipulation.
Summarised by Claude from a sample of 17 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
... how empty is your pipeline?
Most-linked posts?
- Question: Is matching *fixed* regexes with Back-references in P?5 people · 6 mentions · first linked 2019-04-05
- A (Draft) Taxonomy of SIMD Usage5 people · 5 mentions · first linked 2024-06-09
- Show HN: Sheng, a Small but Fast Deterministic Finite Automaton4 people · 5 mentions · first linked 2018-05-26
- Why Ice Lake is Important – a bit-basher’s perspective4 people · 4 mentions · first linked 2019-05-29
- Finding quote pairs with carry-less multiply (PCLMULQDQ)4 people · 4 mentions · first linked 2019-03-06
- Paper: Parsing Gigabytes of JSON per Second3 people · 3 mentions · first linked 2019-02-25
- Bits to indexes in BMI2 and AVX-5123 people · 3 mentions · first linked 2018-05-22
- Fitting My Head Through the ARM Holes (Substitutes for SSE's Pmovmskb on Neon)2 people · 4 mentions · first linked 2019-04-01
- Some opinions about “algorithms startups”, from a sample size of approximately 12 people · 3 mentions · first linked 2018-06-16
- The Environment Will Be Saved If We Just Avoid Doing Icky Things (2024)2 people · 2 mentions · first linked 2024-11-25
What Hacker News says?
Nope. That still supports backreferences, and resolving backreferences is an NP-complete problem.[1] And I don't see anything in that paper that addresses that. Note that there may be some versions of the problem that maybe aren't NP-complete[2], but again, not addressed by that paper. Besides, that paper was published 12 years ago. Where is the productionized version of it? Or are you suggesting the the OP go spend…
Comment linking /2019/04/04/question-is-matching-fixed-regexes-with-back-references-in-p/
on “Show HN: Search code in GitHub repos using regular expressions”Submitted An Intel Programmer Jumps over Wall: First Impressions of ARM SIMD Programming as a story · 167 points
HN discussion... and done. Submitted to HN, and on my blog at https://branchfree.org/2018/06/12/some-opinions-about-algori...
Comment linking /2018/06/12/some-opinions-about-algorithms-startups-from-a-sample-size-of-approximately-1/
on “Ask HN: Are you working on interesting technical problems?”Submitted Hyperscan: A Fast Multi-Pattern Regex Matcher for Modern CPUs as a story · 148 points
HN discussionWell - thanks, guys. If you bookmark https://branchfree.org/ perhaps eventually I'll stop wibbling on about bits-to-indexes and pattern match algorithms and SIMD long enough to post some experiences and some thoughts on the modestly profitable world of the algorithmic startup, from an "expert" who is batting a massive 1 out of 1.
Comment linking /
on “Ask HN: Are you working on interesting technical problems?”Submitted Why Ice Lake is Important – a bit-basher’s perspective as a story · 112 points
HN discussionI suspect Thompson's NFA is not inherently dog slow (Glushkov can be done reasonably fast for decent-sized NFAs). The fact is that most Thompson-lineage engines opted for the 'lazy DFA' approach and optimized that (which is effective until it isn't). I imagine a more aggressive 'native' Thompson NFA is possible. A nice benefit of that is not having to write to your bytecode - there's a good deal of systems-level com…
Comment linking /2019/02/28/paper-hyperscan-a-fast-multi-pattern-regex-matcher-for-modern-cpus/
on “Why GNU grep is fast (2010)”Submitted A (Draft) Taxonomy of SIMD Usage as a story · 14 points
HN discussionThere are fully correct JSON parsers you aren't going to beat, even if you implement a subset. [1] [1]: https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of...
Comment linking /2019/02/25/paper-parsing-gigabytes-of-json-per-second/
on “Never use a dependency that you could replace with an afternoon of programming”Submitted Show HN: Sheng, a Small but Fast Deterministic Finite Automaton as a story · 5 points
HN discussionIn this case, Dr Lemire is using software he co-wrote to test the performance of the M1. It makes sense that he'd be focussing on that software (Simdjson) which wrings as mich speed out of the processor as possible by using vector instructions and avoiding branches. His coauthors blog iirc is even called https://branchfree.org , to indicate the importance of avoiding branch mispredictions to keep the cpu foing quick…
Comment linking /
on “ARM MacBook vs. Intel MacBook: A SIMD Benchmark”Submitted Some opinions about “algorithms startups”, from a sample size of approximately 1 as a story · 4 points
HN discussionFrancois is a smart guy, but there's a range of opinions on the matters he raises. We argue a good deal on Twitter ("constructive confrontation" between former Intel Principal Engineers :-) ). He put together the video pretty quickly so don't dismiss it just for lack of polish. Personally, I argue with him a lot on AVX-512. I think AVX-512 is a Good Thing (or will be shortly - the first instantiation in Skylake Serv…
Comment linking /2019/05/29/why-ice-lake-is-important-a-bit-bashers-perspective/
on “What's wrong with Intel, and how to fix it: Former principal engineer unloads”Submitted Bits to indexes in BMI2 and AVX-512 as a story · 4 points
HN discussionI'm not sure... I like the look of the bit manipulation stuff, but I'm not really a fan of the variable-length vector approach. I think these systems are built to make the world safe for matrix multiply - and simple math workloads - but the short-vector approach (e.g. the typical x86 SIMD style of doing things) is sometimes exactly what you want. I keep meaning to write more about this. I have found 3 categories of…
Comment linking /2018/05/30/smh-the-swiss-army-chainsaw-of-shuffle-based-matching-sequences/
on “An Intel Programmer Jumps over Wall: First Impressions of ARM SIMD Programming”Submitted Paper: Parsing Gigabytes of JSON per Second as a story · 3 points
HN discussionLangdale also has a state machine simd idea that can be used for the full csv transition table: https://branchfree.org/2018/05/25/say-hello-to-my-little-fri... I implemented this at some point (the "noisy" version, in Langdale's words) and got a csv tokenizer that spent about 1.5 cycles per byte.
Comment linking /2018/05/25/say-hello-to-my-little-friend-sheng-a-small-but-fast-deterministic-finite-automaton/
on “Fast CSV Processing with SIMD”Submitted The Environment Will Be Saved If We Just Avoid Doing Icky Things (2024) as a story · 2 points
HN discussionYou can probably get another "few x" faster still: https://branchfree.org/2019/03/06/code-fragment-finding-quot... Based on a cursory scan this is the same problem so Geoff's trick should be directly applicable. The ideas are quite similar: using bit manipulation to detect the in and out regions. Geoff's trick does the "smearing" of the bits in a single SIMD "carryless multiply", plus some supporting stuff. It is co…
Comment linking /2019/03/06/code-fragment-finding-quote-pairs-with-carry-less-multiply-pclmulqdq/
on “Fast CSV Processing with SIMD”Submitted The Environment Will Be Saved If We Just Avoid Doing Icky Things as a story · 2 points
HN discussionThere's more to SIMD than BLAS. https://branchfree.org/2024/06/09/a-draft-taxonomy-of-simd-u... .
Comment linking /2024/06/09/a-draft-taxonomy-of-simd-usage/
on “Fundamental flaws of SIMD ISAs (2021)”Submitted A (Draft) Taxonomy of SIMD Usage as a story · 2 points
HN discussionThis argument is less effective given that SIMD is not always a straightforward substitute for vector processing. Sometimes we want 128, 256 or 512 bits of processing as a unit and will follow it up with something different, not a repeated instance of that same process. We had numerous different examples of this in the Hyperscan project and I broke out something similar on my blog: https://branchfree.org/2018/05/30/…
Comment linking /2018/05/30/smh-the-swiss-army-chainsaw-of-shuffle-based-matching-sequences/
on “SIMD Instructions Considered Harmful (2017)”Submitted Finding quote pairs with carry-less multiply (PCLMULQDQ) as a story · 2 points
HN discussionDo you recall which machines VPCOMPRESSB works on? I think it's next generation Icelake? Or is it there already on Cannonlake? And along the same lines, is there a good general way of looking this up? Coincidentally, searching for this, I found Geoff Langdale's blog post where in addition to describing VPCOMPRESSB as 'dynamiting the trout stream', he also describes something very close to zwegner's PEXT approach: ht…
Comment linking /2018/05/22/bits-to-indexes-in-bmi2-and-avx-512/
on “AVX512 VBMI – remove spaces from text”Submitted Question: Is matching *fixed* regexes with Back-references in P? as a story · 2 points
HN discussionAh I see. Geoff Langdale (creator of Hyperscan) has a post about this. The comments seem relevant: https://branchfree.org/2019/04/04/question-is-matching-fixed...
Comment linking /2019/04/04/question-is-matching-fixed-regexes-with-back-references-in-p/
on “Regular expression matching can be simple and fast (2007)”Submitted Code Fragment: Finding quote pairs with carry-less multiply (PCLMULQDQ) as a story · 2 points
HN discussionPMOVMSKB is a great instruction, and 3c understates how cheap it is - if you have a throughput problem (rather than a latency problem) it's even more efficient relative to the ARM equivalent. I have a blog post about coping strategies for working around the absence of PMOVMSKB on NEON: https://branchfree.org/2019/04/01/fitting-my-head-through-th... We used these techniques in simdjson (which I presume still uses the…
Comment linking /2019/04/01/fitting-my-head-through-the-arm-holes-or-two-sequences-to-substitute-for-the-missing-pmovmskb-instruction-on-arm-neon/
on “How many x86 instructions are there? (2016)”Submitted Some opinions about “algorithms startups”, from a sample size of approximately 1 as a story · 2 points
HN discussion
