7 ms·
Escaping strings faster with AVX-512
- hkgjjgjfjfjfjf 4y ago
- ArrayBoundCheck 4y agoThe internet is so bad that when I see titles like these I know the article will not be true at all. The great thing is I can see lemire next to the title and I absolutely know not only did he walk the walk but he can write about it in an understandable way. I upvoted before reading and I haven't yet been disappointed. -Edit- Done, it's nice and short and I want to reread the code example. I'm not familiar enough with avx512
- hresvelgr 4y agoThat's a weird way of saying you appreciate Daniel's writing and rigor in programming.
- ArrayBoundCheck 4y agoYeah I know, I'm saying only Daniel (and Carmack) can pull of titles like that without people thinking they're not telling the whole truth. I still remember john's tweet "I can send an IP packet to Europe faster than I can send a pixel to the screen. How f’d up is that?". A nerd said "Either he's crazy or this is an unusual situation" it was neither Carmack followed it up with https://superuser.com/a/419167 https://superuser.com/a/419167
- dwrodri 4y agoIt is really unfortunate that AVX-512 has been such a mess when it came to support from Intel on their newer hardware platforms. I think Dr. Lemire has gone quite a ways in demonstrating that there's a lot of potential for software to see performance gains with this type of platform, but I think we'll need further improvements in developer experience before it's more commonplace. The other way to look at it is that quite frankly most business services just don't hit a performance barrier where you're sitting and waiting on a string operation. You're usually waiting on some sort of I/O.
- ArrayBoundCheck 4y agoParsing JSON takes more time than IO
- wahern 4y agoAll the object allocation, pointer chasing, and general indirection is what makes JSON parsing slow, particularly building up tree structures. Bump allocators and the like don't help much, at least for the parsing--most malloc implementations already do fast, O(1) allocation for small objects, and have for decades. (Arenas are useful for making deallocation O(1), though.) If you care about raw JSON throughput, use Ragel or something similar to build a state machine that directly parses JSON into a flat, native data structure. Now you have zero allocations without even needing to shim malloc/free. AVX-512 would still be at least as useful, but it's a much more difficult problem to leverage SIMD in a parser generator than in a simple string escape routine or behind a more abstract interface like a regex library. Quite a few language environments these days provide in-language JSON deserializers, but they're still significantly slower than they could be even when they deserialize to flat data structures. The macro languages and internal compiler intrinsics used to accomplish this are the worst possible environments for development. Lisp-like languages aren't really an exception as they tend to trade easier in-language transforms for a steeper climb when it comes to generating optimized native code for the transform.
- ArrayBoundCheck 4y agoI didn't care about speed. I was merely saying the waiting on I/O is false and didn't want to go as far as saying it hasn't been true for 15+ years
- nerdponx 4y agoIs there any serialization format that is more "friendly" to memory allocators while still being human-readable and -writable?
- deleted 4y ago[deleted]
- ItsRainingBits 4y agoThere's a copy of the loop used on the escape function inside the avx512_escape function [0]. Is it needed or just a copy and paste mistake? (I know nothing about vector instructions) 0: https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2022/09/14/escape.cpp#L66 https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/...
- mmozeiko 4y agoIt is there to process last <32 elements. The vectorized loop processes up to 32 elements per iteration. The iteration does not happen if there are less than 32 elements left, because it wants to load 32 bytes as input. This is very typical in vectorized loops - process N elements per iteration and second loop that does tail of <N elements.
- ItsRainingBits 4y agoThank you!
- sakras 4y agoThough I am curious about why he didn’t switch to using predicated instructions for the tail loop. I’ve switched to that pattern when writing AVX512.
- moonchild 4y ago'Tail handling' in general is an annoying aspect of simd. Masks are great, but no panacea--in particular, if you unroll, then you cannot take care of the tail with a single masked instruction. There are various solutions to this. I favour overlapping accesses, where that's feasible (following a great deal of evangelism from mateusz guzik); a colleague uses a variant of duff's device; you can also just generate multiple masks. I would expect the linked code is just intended as a quick poc, so it does not bother to be optimal.
- renox 4y ago
- pabs3 4y agoIf you do this, just make sure to offer runtime fallbacks via FMV/etc for those of us with ancient hardware. https://wiki.debian.org/InstructionSelection https://wiki.debian.org/InstructionSelection
- pfoof 4y agoSo is CISC becoming great again. Should Apple feel threatened?
- kjeetgill 4y agoI'd argue the cisc vs risc dichotomy hasn't really been true in ages. Among other things, does a cisc-y frontend over risc-ier microcode count as a cisc or a risc cpu? I also don't think Apple's chips are particularly risc-y in the first place. I believe they have plenty of special purpose silicon.
- renox 4y ago> does a cisc-y frontend over risc-ier microcode count as a cisc or a risc cpu? I can't beleive that some are still asking the question, the answer is in the name: CISC=Complex Instruction Set; RISC=Reduced Instruction Set so if it has a CISC-y frontend the whole thing is a CISC CPU. > I also don't think Apple's chips are particularly risc-y in the first place. I believe they have plenty of special purpose silicon. I disagree: their CPU use the ARM-64 ISA is quite RISC, it's just that they don't provide only a CPU but a whole system on the chip.
- kjeetgill 4y agoI think you're too hung up on the name. My memory's a little fuzzy, and I'm no expert here, but in that day the question was one of CPU architecture and the path forward. Risc put forth the idea that reducing the instruction set would open up more doors in your silicon/design budget to produce faster CPUs compared to ever more elaborate instructions which hope shrink the total instruction counts. It was always about architecture not (at least mostly) about interface. I'm not sure how much this dichotomy really plays out in the present, I think the architectural lessons have been learned and applied everywhere. That's how I was taught it atleast.
- zmmmmm 4y agoi can't understand Step 4: I copy these bytes with the quotes and backslash characters. can anybody explain what this means?
- secondcoming 4y agoI'm envious of someone whose job allows them to work on micro-optimisation stuff like this. I often find myself sucked into a Compiler Explorer hole playing around with writing C++ code this way and that way to see what changes. I must have spent hours looking at various ways of lowercasing a string. But it's not really justifiable from my employer's point of view, there are more important things for me to do. Also, handcrafting SIMD code isn't really viable either since I predict there'll be a point where someone on my team wants to use a Mac, and so those routines will have to be written twice.
- anonymoushn 4y agoascii tolower is like 5 instructions I think. You're computing this expression: v + ((v >= 'A') & (v <= 'Z') & 32). Unlike many string operations, portable SIMD libraries should be able to do exactly the right thing here, and writing one routine for AVX2 and another for NEON would be pretty easy if you don't want to adopt a portable SIMD library. Edit: Oh, you can do it in 4 if you use an addition or subtraction by a constant to move the range you're testing for to the edge of the range of the type (in this case, [-128, 127] for i8 since there is no unsigned compare operator). The expression for this approach is v + ((v + 63 < -102) & 32).
- secondcoming 4y agoYes, I'm aware of the math, but there are other aspects like 'does this form of the code help auto-vectorisation?', 'does it work across both gcc and clang?', 'what about optimisation levels', 'does my hand-rolled version beat the compiler's optimisation of the naive code?'. Etc. It's a lot of fun.
- anonymoushn 4y agoOh. I'm skipping all of the fun by using SIMD intrinsics, I guess. You could go to https://highload.fun/ https://highload.fun/ to waste many evenings on this sort of thing.
- janwas 4y ago