[HN Gopher] Trimming spaces from strings faster with SVE on an A...
___________________________________________________________________
Trimming spaces from strings faster with SVE on an Amazon Graviton
3 processor
Author : ingve
Score : 78 points
Date : 2023-03-11 09:04 UTC (2 days ago)
(HTM) web link (lemire.me)
(TXT) w3m dump (lemire.me)
| carterschonwald wrote:
| I'm just excited that sve hardware is starting to be available
| recursive wrote:
| 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.
| rkunde wrote:
| I was confused too but the author uses "trim" to mean "remove
| anywhere in the string", rather than just from the beginning
| and end.
| layer8 wrote:
| What are the use cases for that, though?
| xxpor wrote:
| 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.
| layer8 wrote:
| 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?
| xxpor wrote:
| 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.
| eklitzke wrote:
| 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
| pkaye wrote:
| Maybe for processing the code for an obfuscated C contest?
| avian wrote:
| > 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;
| duped wrote:
| That's been around since C++11 although it's kind of weird to
| see it used for a char*
| owl57 wrote:
| 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).
| [deleted]
| devnullbrain wrote:
| I use it for everything, even loop variables.
| unwind wrote:
| 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...
| abbeyj wrote:
| Yes, it is called "Uniform Initialization".
| https://isocpp.org/wiki/faq/cpp11-language#uniform-init
| chrisgd wrote:
| 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?
| qbasic_forever wrote:
| 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.
| rektide wrote:
| 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.
| Palomides wrote:
| at my school (ordinary well-known state university), barely any
| CS students would graduate knowing how to approach this
| tveita wrote:
| 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.
| Symmetry wrote:
| 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...
| saagarjha wrote:
| 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.
| mydriasis wrote:
| You should work through Nand2Tetris :) it will give you an
| understanding of how computers work at a very, very low level.
| billythemaniam wrote:
| 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.
| sebazzz wrote:
| It is C, but it is assembly. That much is clear.
| secondcoming wrote:
| 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
| ape4 wrote:
| The complexity almost looks like an April Fools joke.
| Cthulhu_ wrote:
| 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.
| oceanplexian wrote:
| 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.
| jrockway wrote:
| 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!
| evancox100 wrote:
| What was the rule of thumb?
| jrockway wrote:
| 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.
| adgjlsfhk1 wrote:
| Not really. If you're 4x faster than IO, the CPU can do
| something else while waiting for IO (e.g. run another
| thread).
| dr_zoidberg wrote:
| It's also 3.6 times faster, in a world where hardware updates
| get you 20-ish % improvements per generation.
| aseipp wrote:
| 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.
| 2OEH8eoCRo0 wrote:
| No matter how advanced we think we are we are still worrying
| about minutiae like trimming spaces from strings.
| fs111 wrote:
| humans putting text into form fields will never go away
| probably, so you will always have to do this at some point.
| 2OEH8eoCRo0 wrote:
| I'm aware. It's still interesting, especially since it all
| still boils down to machine instructions.
| tyingq wrote:
| This doesn't appear to implement trimming the front and
| back, just the entire string.
| ape4 wrote:
| Yes, a much rarer thing.
| synergy20 wrote:
| 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.
| evancox100 wrote:
| 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!
| synergy20 wrote:
| yes,SVE is vector which is scalable and AVX is SIMD which has
| a few fixed width.
| renox wrote:
| 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!
| mort96 wrote:
| 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.
| Thev00d00 wrote:
| Those those unaware this by Daniel Lemire of SimdJson fame.
|
| 0. https://github.com/simdjson/simdjson
___________________________________________________________________
(page generated 2023-03-13 23:02 UTC)