Top all-time · #9457
Trent Nelson
Personal blog · trent.me · on HN as trentnelsonprogrammingsystems
Trent Nelson's personal blog at trent.me covers programming and systems. Since 2018, 8 different Hacker News readers have linked it 17 times, most often “Is Prefix of String in Table? a Journey into SIMD String Processing”. It is still writing: the last post was on 2025-02-13, and you can follow it by feed.
Most-linked posts?
- Is Prefix of String in Table? a Journey into SIMD String Processing5 people · 6 mentions · first linked 2018-05-04
- PyTorch and Python Free-Threading2 people · 2 mentions · first linked 2025-04-02
- Is prefix of string in table? A journey into SIMD string processing2 people · 2 mentions · first linked 2023-06-30
What Hacker News says?
Well... I mean the first version (IsPrefixOfStringInTable_1) uses the lengths from the string array to improve performance versus the baseline: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri... The super-simple baseline referred to in the intro was whipped up as a trivial example of the simplest approach you could take for the problem. Trie was never in contention as I didn't want to rely on any algori…
Comment linking /is-prefix-of-string-in-table/
on “Is Prefix of String in Table? a Journey into SIMD String Processing”Submitted Is Prefix of String in Table? a Journey into SIMD String Processing as a story · 181 points
HN discussionPatches welcome :-) But seriously though, I played around with compression a bit initially: https://github.com/tpn/tracer/blob/master/StringTable/String... . Referenced Hacker's Delight when I was working on it. Granted, this was just for compressing the USHORT lengths into BYTE-sized lengths. Are you sure your compression suggestion would work for prefix matches? If you can get lower latency than the fastest assemb…
Comment linking /is-prefix-of-string-in-table/
on “Is Prefix of String in Table? a Journey into SIMD String Processing”Submitted PyTorch and Python Free-Threading as a story · 10 points
HN discussionI love tries for larger data sets, and have used them many times for longest prefix matching problems. However, they inevitably involve pointer chasing, are quite branchy, and not really amenable to SIMD optimizations. They also do not have any means in place for doing a fast-path negative match, which was important for me. I think you'd really struggle to get anything based on pointer chasing and binary search to c…
Comment linking /is-prefix-of-string-in-table/
on “Is Prefix of String in Table? a Journey into SIMD String Processing”Submitted Is Prefix of String in Table? A Journey into SIMD String Processing as a story · 9 points
HN discussionSorting the strings by length, or lexicographical? Length sort wouldn't work for the prefix-oriented nature of the comparisons. Lexicographical sorting and a binary search involves pointer chasing, and doesn't provide any way to fast-path the negative match lookup. If I'm getting called a trillion times on a hot-path, but only a million of those times I'm receiving a module name (search string) I'm interested in, th…
Comment linking /is-prefix-of-string-in-table/
on “Is Prefix of String in Table? a Journey into SIMD String Processing”Submitted Is Prefix of String in Table? a Journey into SIMD String Processing as a story · 5 points
HN discussionThe article is much longer than I originally anticipated. If you're looking for some good bits, you could probably jump straight to here: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri... That discusses the last C implementation before I took a stab at the assembly versions. The final assembly section was pretty juicy as well: http://trent.me/is-prefix-of-string-in-table/#IsPrefixOfStri... . I was inve…
Comment linking /is-prefix-of-string-in-table/
on “Is Prefix of String in Table? a Journey into SIMD String Processing”Submitted Is Prefix of String in Table? A Journey into SIMD String Processing as a story · 3 points
HN discussionYou might enjoy https://trent.me/is-prefix-of-string-in-table/
Comment linking /is-prefix-of-string-in-table/
on “Dynamic bit shuffle using AVX-512”Submitted Is Prefix of String in Table? as a story · 3 points
HN discussionSubmitted PyTorch and Python Free-Threading: Unlocking multi-threaded parallel inference as a story · 2 points
HN discussionSubmitted Is Prefix of String in Table as a story · 2 points
HN discussionSubmitted Is prefix of string in table? as a story · 2 points
HN discussionSubmitted Is prefix of string in table? A journey into SIMD string processing as a story · 1 points
HN discussion