Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor | Hacker News Reader

Trimming spaces from strings faster with SVE on an Amazon Graviton 3 processor

lemire.me

82 pointsingve49 comments

Is all this worth it when you may have only a few chars of whitespace at most?

When I was looking at something related to this recently I noticed gcc doing a pretty cool optimisation [0], where it converted the whitespace chars into a bitfield and leveraged the `bt` instruction. It seems quite sensitive to the char string though and falls back to worse code easily (e.g add "\f\v" to the string) but it's easy to manually write the code so that gcc always generates the same.

https://godbolt.org/z/Tzr8e7x6q

SVE and SVE2 are similar to Intel's AVX512-etc for vector, I would use intrinsics instead of hand crafting ASM code, unless it's a performance bottleneck.

And yes if you want to play with SVE, Amazon's own ARM chip is the best one available now, maybe the only one in fact, for the general public.

Just to be clear, SVE is similar to AVX512 but the “Scalable” part is that the length is not hard-coded to any set number of bits or elements. It is more like the vector computers of old, such as the Cray-1.

This means there is no need for continually updating the instruction set with longer and longer versions of the same instructions. Hopefully this leads to a more stable base and wider adoption, we’ll see how that works in practice though!

I'm not really convinced we need to continually update the instruction set with non-scalable vector instructions either tbh, it seems like we've stalled on 256 bit wide instructions to the point where AMD is emulating 512 bit instructions using 256 bit wide execution units and the performance benefits of 512 bit wide instructions even on Intel is marginal at best.

That's not to say scalable instructions are a bad idea. It certainly makes it easier to make small CPUs which support all the software written for vector instructions without having to emulate 256 or 512 bit wide execution units.

I seem to remember reading that the 'scalable' part of SVM was lost as soon as you did loop unrolling.. I hope I'm wrong though!

yes,SVE is vector which is scalable and AVX is SIMD which has a few fixed width.

I don't think scalable vectors is particularly useful feature, especially compared to what compilers have to go though to support it. It's much more useful to be able to do "more powerful" things with existing vector widths at hardware speeds (or perhaps just make the existing stuff faster than it is) than to be able to go wider. Scalable vectors also doesn't solve the ISA problem: don't break existing processors.

Of course they are free to add new "more powerful" instructions to SVE at any time, just like Intel could for AVX, etc.

Also, I think it is supposed to be easier for compilers to autovectorize SVE than, say, neon. Whether that's the case in practice I don't know. Is there something specific you see that makes it more difficult than with SIMD-style, fixed operation width instructions? Or you are referring to something else with "compiler support"?

In order for this to matter, you'd need to expect the possibility of strings with huge numbers of leading spaces. Why then would you use this naive algorithm for comparison? An obvious and more straight forward improvement would be to compare 4 bytes at a time with 0x20202020. (or maybe 8) There would be a maximum of 3 spaces to identify individually.

I was confused too but the author uses “trim” to mean “remove anywhere in the string”, rather than just from the beginning and end.

What are the use cases for that, though?

Maybe for processing the code for an obfuscated C contest?

There's a ton if you think of it as a byte array, rather than just a string. For example, network proxies that may remove various protocol TLV options from a packet.

Is that an example of “remove all occurrences of a specific byte value from an array”? Wouldn’t packet processing require some sort of structural parsing?

Packets are usually parsed by casting a uint8_t * to a struct. Frequently, the part that needs to be removed is always at the same offset in the non-error case.

This particular routine doesn't seem that useful, but sometimes these weird vector algorithms that don't seem useful on their own are composed together in interesting ways to solve a larger, more interesting problem. For example, there was a cppcon talk a few years ago where the presenter came up with a novel way of using AVX instructions to efficiently find the median of seven (yes, exactly seven) integers, by coming up with a novel representation of the problem that AVX instructions were well-suited for.^[1]

That said, I don't know if this particular routine is something the author came up with while working on some other problem, or if it's just a neat idea that he came up with and wrote a short blog post about.

[1] https://www.youtube.com/watch?v=qejTqnxQRcw

better word is compact?

Those those unaware this by Daniel Lemire of SimdJson fame.

0. https://github.com/simdjson/simdjson

> char * init_out{out};

Are the curly braces in the initialization some new C++ syntax? I haven't been keeping up with C++ developments in the last decade or so.

Based on the code that follows I would expect

    char* init_out = out;

Yes, I was going to comment on that both code samples are C++, even though they are not clearly labelled as such. List initialization seems to be the recommended syntax to use nowadays in C++ [1].

I'm a fan of the type of optimization and exploration that Lemire often publishes, it's really cool and impressive. I just have a pet peeve about people lumping together C and C++ as if they're interchangable when they are (more clearly than ever, and growing further apart) not.

[1]: https://en.cppreference.com/w/cpp/language/list_initializati...

Yes, it is called "Uniform Initialization". https://isocpp.org/wiki/faq/cpp11-language#uniform-init

That's been around since C++11 although it's kind of weird to see it used for a char*

A bit weird, but I would support a local style guide that limits initialization style choices to parens for calling non-initializer-list constructors and braces for everything else — for simplicity, consistency, less confusion with assignment, and that odd case where it would actually catch an error (unindended narrowing conversion).

I use it for everything, even loop variables.

I’m just excited that sve hardware is starting to be available

Thanks for sharing. Is understanding how best to utilize computer hardware part of a classic CS program or is most learned on the job?

I studied Econ in college and been a python guy for last 8 years but have no knowledge of how the machine actually interacts with my code. Is there a formal name for understanding that?

CS program, but depends on the classes you take. For me, the main class was called "computer architecture". Classes about compilers, databases, servers, embedded programming, server clustering can all help to understand the machine.

Of course, it can be learned on your own too. But generally this path is harder because it's hard to know what to study. The CS program will expose you to breadth of concepts.

You should work through Nand2Tetris :) it will give you an understanding of how computers work at a very, very low level.

It'd be fun to ask Daniel Lemire's undergrads if they learned about vector/simd instructions.

It's hard for me to answer, because I was learning everything I could on the internet before undergrad, following each tiny micro-architectural tweak in minute detail. It makes it hard to remember what things college really provided & what was self-taught.

at my school (ordinary well-known state university), barely any CS students would graduate knowing how to approach this

Yes, a BS in computer engineering is typically what you want for a 50/50 mix of software and hardware. Basically if you get that degree you understand and can build a machine from digital logic/basic circuits all the way up to it boots to an operating system (that you wrote) and its login prompt. It's a deep dive into machine architecture and system programming. An electrical engineering degree doesn't focus as much on the software side, and a regular CS degree doesn't focus as much on the hardware--computer engineering is in the middle.

At MIT, at least, everybody in EECS (all one department) has to take 6.004 where you build a simple computer from the transistors up which at least gives you a framework for thinking about this stuff. The simple processor doesn't have caches, of course, so that's a big whole in terms of things you have to understand for optimization, but it's the basics at least.

EDIT: Link to course in OpenCourseware if you want to virtually take it: https://ocw.mit.edu/courses/6-004-computation-structures-spr...

I don’t really know of many computer science programs that focus on this kind of thing. The other comments talk about little hobby computers, which is not a bad thing to learn about, but trying to apply principles from an 8-bit toy computer to a modern superscalar, pipelined, and heavily OoO machine is like comparing a toy rocket to the Space Shuttle.

If you’re interested in learning more about microarchitectural optimization I find that getting a basic understanding of how a modern processor has evolved and then reading posts like these (looking things up when necessary) can get you mostly up to speed with the area. Most people don’t use these details in their everyday code so if you’re just looking to make your code fast learning how to measure algorithmic complexity and use a profiler is likely to be much more valuable.

A course in high performance computing should include some material on computer architecture and SIMD, though the focus is more on parallel programming and GPU.

To get into the right mindset for SIMD optimization, play Zachtronic games. You have a big pile of odd-shaped tools that take some input and output a result a few cycles later, you have limits on how many instructions can run at once, but maybe you can do something like a load each cycle for free. Run your benchmark, count the cycles, make a small tweak and test again.

It is C, but it is assembly. That much is clear.

The complexity almost looks like an April Fools joke.

But if it's hidden behind a standard library's 'trim' functions it's all fine to me; I don't need to know how it works under the hood, but want to rely on the maintainer's knowledge that their implementation is as fast and efficient as possible on whichever architecture.

Low level string operations happen so often under the hood in any application that 10x more code and complexity in an implementation is worth it if it increases efficiency.

It's also 3.6 times faster, in a world where hardware updates get you 20-ish % improvements per generation.

It doesn’t need to be “As fast as possible” it just needs to be faster than the I/O. For sure, congrats that it is X times faster but the writer doesn’t really describe performance in terms of real world constraints.

I/O is fast, and efficiency matters for every workload. The sooner your CPU is done running code, the sooner it can go into an energy saving state. Energy saving means a longer battery life on portable computers, and less cost in the server case. Remember that people are running algorithms like this "in the cloud" against millions of concurrent requests. The 40Gbps network card can keep the CPU busy, and users are waiting for you to be done. Writing efficient code to make 1 computer do the work of 2 is just operational cost savings 101.

When I was at Google there was a "rules of thumb" page that described how much of your time X performance was worth. I always looked at that before micro-optimizing, but also always came out ahead. I remember a coworker and I redesigning one of our subsystems late on some Friday evening; the rules of thumb said that the performance improvement we predicted, at our scale, was worth a month of SWE time. We did it in 2 hours. So we came out ahead, and our system worked better. (I joked that my colleague and I would be taking 2 extra weeks of vacation.)

TL;DR performance matters everywhere. The one user using an interactive tool on their workstation will appreciate their day not being wasted by random pauses. The person out and about on their phone will appreciate the additional battery life. And your company's bean counters will be quite happy to hear that your cloud bill or data center expense forecast for next year is down. Finally, it's fun! Truly a win/win. Make it fast!

What was the rule of thumb?

This was based on yearly RAM cost. I worked on a log analysis system. In the beginning, it ran on one computer. That one program would read logs, generate fleet-wide analytics, and serve those out of RAM. Eventually we wanted to run on more than one computer, for both scaling and reliability reasons. The design of the system allowed us to basically do the same serving with many replicas, so for a long time we just ran a fleet of replicas that still had all the capabilities of the monolith. The change we made was to move the aggregation stage to a new dedicated program, that we only ran 3 copies of worldwide. (A man with 2 replicas never knows which one is broken, they say.) This meant that the mappers became significantly lighter RAM-wise, they just existed to use as much CPU time as they could, and then we had 3 beefy reducer replicas to aggregate and serve data.

This was a very easy change; we just made a new main.go and an RPC to send the data to aggregate. The system was designed internally to be logically isolated across that boundary, so we just stuck in the RPC and then the other side of the boundary could be another data center.

In the end, I think we saved a few terabytes of RAM-years. Not a big deal, but it was something.

Not really. If you're 4x faster than IO, the CPU can do something else while waiting for IO (e.g. run another thread).

No matter how advanced we think we are we are still worrying about minutiae like trimming spaces from strings.

humans putting text into form fields will never go away probably, so you will always have to do this at some point.

I'm aware. It's still interesting, especially since it all still boils down to machine instructions.

This doesn't appear to implement trimming the front and back, just the entire string.

Yes, a much rarer thing.

Not really IMO. Seems pretty by the books SIMD optimization at the high level (main body vs manually peeled iteration for the tail), just using a nice instruction set. Straightforward vectorization of the original code. I suspect modern AVX is probably not much worse.

You're more-or-less programming in assembly here using these intrinsics, using C for goodies like for loops, and at the moment that's about as good as you can do while scalable autovectorization is still WIP/NIH in most compilers, so it's not really surprising or noteworthy. For experienced SIMD programmers, this is the standard approach to getting data parallelism out of many "boring" algorithms.

Reply on news.ycombinator.com