19 ms·
55 GiB/s FizzBuzz
- EastToWest 5y agoMy naive implementation (as shown in the linked question) in Rust was mind boggling slow. C could do around 150MiB/s, while Rust could only do 10MiB/s. A simple `objdump -d` shows Rust is generating a lot more code. I'm not sure how much of that is relevant though. At that point my coffee time ran out. I wish I had more time to figure out why. :-(
- steveklabnik 5y agoIt is very common for folks to forget to pass --release, were you doing that?
- HALtheWise 5y agoNow I'm kinda curious to see how much faster you could go on an M1 Max with the GPU generating the data. Once his solution gets to the point of being a bytecode interpreter, it's trivially paralellizable and the M1 has _fantastic_ memory bandwidth. Does anyone know if the implementation of pv or /dev/null actually requires loading the data into CPU cache?
- jason0597 5y agoCouldn't we load it onto an NVIDIA RTX A6000? It is much much faster than the M1 Max. It has a much greater memory bandwith too
- _2d30 5y agoWouldn’t benefit from UMA
- pcwalton 5y agoPCIe 5 speed is 64 GB/s, so theoretically if you perfectly pipelined the result you could achieve the same performance on a next-generation discrete GPU.
- HALtheWise 5y agoUnfortunately, the memory bandwidth that matters here is not bandwidth to GPU memory, but bandwidth to main system memory (unless anyone knows how to splice a pointer to GPU memory onto a unix pipe). That's specifically why the M1 came to mind, as a powerful UMA machine that can run Linux. Perhaps a modern gaming console could hit the same performance, but I don't know if they can run Linux.
- gpderetta 5y agoPv never touches the data. It splices the input into the output, /dev/null in this case, so once written, a page is never touched again. Splice is linux specific though, so you would need to run it on M1.
- HALtheWise 5y agoIf that is the case, does it actually matter what CPU core pv runs on? I feel like _something_ must ultimately zero the page out before it can get re-mapped to the process, but I'm not sure which core that happens on, or whether there's some other hardware mechanism that allows the OS to zero a page without actually utilizing memory bandwidth.
- londons_explore 5y agoThe page is reused by the generator process without being zeroed.
- _fjb4 5y agoAs an aside, it would be fun to see a programming challenge website focused on performance and optimizations, rather than code golf (shortest program) or edge case correctness (interview type sites). I took a course like this in uni where we learned low-level optimization and got to compete with other classmates to see who had the fastest program - a fun experience that I don't really see much of online.
- mhh__ 5y agoBenchmarking reliably and fairly for minimal cost is really hard in a cloud environment.
- _fjb4 5y agoThe course had a machine solely for benchmarking. It would only compile and benchmark one program at a time and the students had to queue up. It worked well for the course and the results were very consistent between runs, but that kind of setup doesn't scale well. There may be a (slow) option though, and that would be benchmarking the code using an simulated processor. The runtime would be measured relative to the simulated processor as opposed to the computer hosting the simulator.
- mhh__ 5y agoTrue, but consider that compiling hello world takes me about 5 minutes in gem5 when using a semi-realistic model of the computer.
- rustybolt 5y agoI’ve printed his entry and there are some neat tricks I learned, but ‘stage 3’, where, according to his comments, a bytecode interpreter is used, is still beyond my understanding. Also not sure why this helps, a bytecode interpreter sounds like a lot of overhead to me…
- saagarjha 5y agoThe bytecode is specifically designed so that it maps directly to the output. // The third phase operates primarily using a bytecode interpreter; it // generates a program in "FizzBuzz bytecode", for which each byte of // bytecode generates one byte of output. The bytecode language is // designed so that it can be interpreted using SIMD instructions; 32 // bytes of bytecode can be loaded from memory, interpreted, and have // its output stored back into memory using just four machine // instructions. // The bytecode format is very simple (in order to allow it to be // interpreted in just a couple of machine instructions): // - A negative byte represents a literal character (e.g. to produce // a literal 'F', you use the bytecode -'F', i.e. -70 = 0xba) // - A byte 0..7 represents the hundreds..billions digit of the line // number respectively, and asserts that the hundreds digit of the // line number is even // - A byte 8..15 represents the hundreds..billions digit of the line // number respectively, and asserts that the hundreds digit of the // line number is odd // %ymm2 holds the bytecode for outputting the hundreds and more // significant digits of a line number. The most significant digits of // this can be obtained by converting LINENO_TOP from high-decimal to // the corresponding bytecode, which is accomplished by subtracting // from 198 (i.e. 256 - 10 - '0'). The constant parts of LINENO_TOP // are 198 minus the bytecode for outputting the hundreds to billions // digit of a number; this makes it possible for a single endian // shuffle to deal with all 16 of the mid and high digits at once.
- jart 5y agoWhat's cool here is if you can make FizzBuzz go 55GB/s then you have the skill needed to make a whole bunch of other stuff go that speed too. My personal favorites are that Intel architecture lets us do population count, polynomial division, and eight tap filters at that speed too, which is wonderful.
- jtchang 5y agoThe amount of low level CPU architecture knowledge to write such a program is mind boggling. Just goes to show how much room for improvement a lot of programs have.
- SavantIdiot 5y agoAt some point I believe we will start to bump up against the limits we saw in the first three computer revolutions (tubes, transistors, integrated circuits). This will cause the pendulum to swing from commodification to optimization. What I mean is, you won't be able to snap your fingers and scale up or out, thus optimization will begin again in earnest. Clearly this isn't always the case: GPU shaders, crypto ASICs, video processing... there are plenty of places where optimization is crucial for high performance loop tuning. But optimization hasn't been required across the board like there was just before the three big innovations I described hit.
- c9fc42ad 5y agoThis tends to happen at a smaller scale with gaming consoles. Towards the end of a generation, the games coming out usually perform/look a lot better than the ones at the beginning of the generation. I'm assuming due to a lot more careful optimizations due to not being able to change the hardware. I've always been curious about how far we could really push modern computers if somebody wanted to spend the time going to the lengths in the original post when creating practical software. Of course it's usually not worth the tradeoff, but it's interesting to think about.
- hackbinary 5y agoProtip: while you made a great comment, ND people like me, and even most NT people have diffivulty ingesting walls of text like what you just wrote. Please, therefore, breakup your text into paragraphs every 3 sentences. It does wonders for readability for just about everyone. :)
- saagarjha 5y ago…it’s literally four sentences.
- Scaevolus 5y agoThis is the heart of this program. It aims to be able to produce a sustained output rate of 64 bytes of FizzBuzz per four clock cycles in its main loop (with frequent breaks to do I/O, and rare breaks to do more expensive calculations). The third phase operates primarily using a bytecode interpreter; it generates a program in "FizzBuzz bytecode", for which each byte of bytecode generates one byte of output. The bytecode language is designed so that it can be interpreted using SIMD instructions; 32 bytes of bytecode can be loaded from memory, interpreted, and have its output stored back into memory using just four machine instructions. This makes it possible to speed up the FizzBuzz calculations by hardcoding some of the calculations into the bytecode (this is similar to how JIT compilers can create a version of the program with some variables hardcoded, and throw it away on the rare occasions that those variables' values change). The bytecode format is very simple (in order to allow it to be interpreted in just a couple of machine instructions): - A negative byte represents a literal character (e.g. to produce a literal 'F', you use the bytecode -'F', i.e. -70 = 0xba) - A byte 0..7 represents the hundreds..billions digit of the line number respectively, and asserts that the hundreds digit of the line number is even - A byte 8..15 represents the hundreds..billions digit of the line number respectively, and asserts that the hundreds digit of the line number is odd In other words, the bytecode program only ever needs to read from LINENO_MID; the information stored in LINENO_LOW and LINENO_TOP therefore has to be hardcoded into it. The program therefore needs to be able to generate 600 lines of output (as the smallest number that's divisible by 100 to be able to hardcode the two low digits, 200 to be able to get the assertions about the hundreds digits correct, and 3 and 5 to get the Fizzes and Buzzes in the right place). The bytecode interpreter consists of four instructions: 1. Load the bytecode from memory into %ymm2; 2. Use it as a shuffle mask to shuffle LINENO_MID_TEMP; 3. Subtract the bytecode from the shuffle result; 4. Output the result of the subtraction. #define INTERPRET_BYTECODE(bc_offset, buf_offset) \ vmovdqu %ymm2, [%rdx + bc_offset]; \ vpshufb %ymm0, LINENO_MID_TEMP, %ymm2; \ vpsubb %ymm0, %ymm0, %ymm2; \ vmovdqa [OUTPUT_PTR + buf_offset], %ymm0
- no_time 5y agonext up: custom FizzBuzz ASIC with 128 fizz and 128 buzz cores for maximum throughput.
- function_seven 5y agoSubstandard design. You should have a suitable ratio of cores to keep them load balanced. I suggest 160 fizz cores and 96 buzz cores. EDIT: And a fizzbuzz co-processor, obviously.
- gumby 5y ago> fizzbuzz co-processor, obviously One of the functional modules on the M1 Pro Max chip, but only the Max one, unfortunately. Take that, Intel!
- mordechai9000 5y agoI think optimizing binary tree inversion is a higher priority, right now.
- WJW 5y agoNot for fizzbuzz optimisation it isn't! Get your priorities straight mate! Who is trying to get hired when we could be outputting more fizzes and/or buzzes! :)
- randy408 5y agoFizzBuzzCoin?
- deleted 5y ago[deleted]
- wtallis 5y agoOr if your ASIC generalizes the problem in a slightly different direction, you end up reinventing TWINKLE and TWIRL: https://en.wikipedia.org/wiki/TWINKLE https://en.wikipedia.org/wiki/TWINKLE
- dmitrygr 5y agoThe amount of completely unnecessary effort unleashed on this problem in this post is amazing. I want to meet the author and shake his hand! It has everything from Linux kernel trivia in terms of output speed to intel AVX2 code. So unnecessary and so awesome! I've done stuff like this before, and I imagine the satisfaction of completing it! A tip of my hat to you, sir!
- monksy 5y agoI'm not sure why there is coding done here. A ticket for this work has been made at here: https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition/issues/538 https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris... I'm going to have to ask that the contributors attend the grooming sessions and talk about the business value of this performance enhancement.
- einpoklum 5y agoI like how it has a FizzBuzzOutputGenerationContextVisitorFactory.java file.
- deleted 5y ago[deleted]
- arberx 5y agoHow do people have so much time on their hands :(
- aloisdg 5y agoMaybe they lose less time writing comment on HN. Dont hit me I am guilty of this too.
- recursive 5y agoEveryone has 24 hours per day.
- eyelidlessness 5y agoNot everyone has the same ability to utilize those hours. People have children and/or pets and/or loved ones to tend, different cognitive and physical limitations, different economic challenges, different social expectations, different living conditions which may impact all of the above. Speaking for myself: between caring for a puppy, cognitive impairments from ADHD, sustained impact from burnout, and financial responsibilities for family… my ability to carve out free time for a very long list of things I’d like to do extracurricularly is limited to a few hours a week at most. Achieving a “months of work” project in my areas of interest and applicable talents is easily going to take 10x as long. And that also means being much more circumspect about where I choose to focus those interests.
- recursive 5y agoMaybe I'd feel differently if the comment ended with :) instead of :(. But I mean, obviously, yes. Different people can do different things for a zillion different reason. I'm reacting negatively because it sounds like a criticism against the author just for spending a lot of time working on a hobby project just for the sake of it. See also: "why are you having fun when cancer still isn't cured yet?"
- eyelidlessness 5y ago
- m0ck 5y agoThanks for my daily dose of software engineer imposter syndrome.
- xyst 5y agojust keep in mind, this person claims to have taken a few months to write this. I wouldn't worry about it. It's interesting never the less. The last time I have seen this low level of code was in a college level course about assembly language.
- DC-3 5y agoAs a comment on the linked post notes, this is impressive enough that it could probably be the basis of a degree thesis. An astonishing exhibit of technical skill, very much a masterpiece in the original sense of the term.
- shp0ngle 5y agoIf you want to get better at this specific thing, work or study in this field. Person who wrote this probably won't know much about, say, compatibilities of latest version of WebPack and VueX; or about cryptographic protocols. You cannot know everything.
- btheshoe 5y agoIt never goes away, does it
- emrah 5y ago
- fnord77 5y ago> // Most FizzBuzz routines produce output with `write` or a similar > // system call, but these have the disadvantage that they need to copy > // the data being output from userspace into kernelspace. It turns out > // that when running full speed (as seen in the third phase), FizzBuzz > // actually runs faster than `memcpy` does, so `write` and friends are > // unusable when aiming for performance - this program runs five times > // faster than an equivalent that uses `write`-like system calls. Why can't `write` use a reference like vmsplice?
- tehjoker 5y agoI'm not an assembly programmer, but my intuition is that this is safer. You can only rely on "zero-copy" behavior when you have total control of the program and know that that memory region is going to stay put and remain uncorrupted. Therefore, most external code will make a copy because they can't insist on this (and because for most people, making a copy is pretty fast).
- gpderetta 5y agoI think that some of unix derivatives do or have done in the past. If the argument to write is page aligned and a multiple of a page size they play VM tricks to implement zero copy writes. The issue is that the caller to write is allowed to do anything it wants with the buffer after write returns, so the write implementation need to unmap the stolen pages and perform copy on write if the caller ever touches them again, so in practice the optimization is very fragile. For this reason Linus as always refused to implement this optimization. Splicevm gets away with it because it is part of the caller contract that it can't ever touch the pages until the kernel is done with them. Unfortunately there is no general way to know when it is safe to reuse them and it is very application specific (for example there might be an explicit ack from the consumer that it has received the data)
- nobrains 5y agoDid anyone else get recommended and see the FizzBuzz video on YouTube ( https://youtu.be/QPZ0pIK_wsc https://youtu.be/QPZ0pIK_wsc ) just before this article or did I just witness an incredible coincidence?
- jerf 5y ago"The Grid. A digital frontier. I tried to picture clusters of information as they moved through the computer. What did they look like? Ships, motorcycles? Were the circuits like freeways? I kept dreaming of a world I thought I'd never see. And then, one day I got in... It turns out The Grid is just a guy sitting in a chair, shouting about "Fizz!" and "Buzz!" as fast as he can. It wasn't really what I had in mind. (The image of this poor program, stuck shouting "fizz!" and "buzz!" for subjectively centuries at a time struck me...)
- jedberg 5y agoI kinda hope as a joke in Tron 3 they have a guy muttering in the corner "1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz" as someone walks by.
- tigershark 5y agoStill better than throwing away a significant percentage of the world total power output just to compute some useless hashes if you ask me..
- jedberg 5y agoI wonder if it slows down with really big numbers.
- kruxigt 5y agoHow common is optimization this skilled in parts of what we run everyday? Is it somewhere in some inner loop of the browser, some parts of the OS? Graphics drivers? BLAS and similar? The demo scene?
- savant_penguin 5y ago"future-proofed where possible to be able to run faster if the relevant processor bottleneck – L2 cache write speed – is ever removed)." Being able to write a function limited mostly by the l2 cache size and able to realize that is rad And btw this is an interesting example of how hand optimized assembly can be much much faster than any other solution. Can you get as fast as this solution with mostly C/C++? It uses interesting tricks to avoid memcopy (calling it slow rofl)
- BeeOnRope 5y agoYou could probably to very close to this solution with C or C++, plus AVX intrinsics. Some might consider that "cheating" since intrinsics occupy kind of a grey area between a higher level language and asm.
- bigiain 5y agoI suspect by the time you’ve disabled all the compiler “optimisations” that would lie knock a few orders of magnitude of performance off the directly translated algorithm, you may as well have written the assembler to start with… And you probably can’t fine tune your C/C++ to get this performance without knowing exactly what processor instructions you are trying to trick the compiler into generating anyway.
- kccqzy 5y ago> without knowing exactly what processor instructions you are trying to trick the compiler into generating In fact, in this case you know exactly what processor instructions the compiler is going to generate. You are using AVX intrinsics after all. And no, compiler optimizations work well with these intrinsics.
- akie 5y agoI mean, did you see the very complicated extremely optimized C and C++ code lower on the page? Despite that, they "only" got to 10% of the performance of the ASM code.
- kens 5y agoYou could probably get some blazing performance out of an FPGA. I made an FPGA version of FizzBuzz a few years ago, but it was optimized for pointless VGA animation rather than performance. https://www.righto.com/2018/04/fizzbuzz-hard-way-generating-vga-video.html https://www.righto.com/2018/04/fizzbuzz-hard-way-generating-...
- cochne 5y agoI would be doubtful since most FPGAs have a much lower clock speed than CPUs. Maybe unless you take advantage of parallelism.
- NextHendrix 5y agoWhen I saw this I did wonder how much faster I could do it in hardware, but similarly I expect the bottleneck would be outputting it in a fashion that would be considered fair to be compared to software implementations (eg outputting readable text on a screen). Regardless, I very much enjoyed your DVD screensaver-esque output.
- killingtime74 5y agoAt that point we are writing firmware for the display
- irjustin 5y agoWould you be willing to back and try to optimize this for pure output speed? I thought the exact same question, but wondered if FPGA's gate connections are too distant for FizzBuzz to beat 55 GiB/s.
- londons_explore 5y agoWith an FPGA, the speed limit will 100% be how you want to output the data. If you require it to come out of IO pins, then the limit will be the total output bandwidth of all the serdes units on the IO pins. Typically that's much more than 55GiB/s.
- ot 5y agoTo me it's almost as impressive that pv does not become the bottleneck.
- gpderetta 5y agoI was wondering the same thing! pv probably never touches its input and might itself be using splice to never read the bytes in users pace and just accumulate the byte counts. Edit: yes it has a --no-splice parameter.
- jiggawatts 5y ago“ This is faster than a number of standard functions. In particular, it's faster than memcpy, which presents interesting challenges when it comes to I/O” Wow.
- kvathupo 5y ago> 64 bytes of FizzBuzz per 4 clock cycles That's borderline incredulous, given a single AVX2 instruction can last multiple clock-cycles. The reciprocal throughput also doesn't go below ~0.3 to my, admittedly shallow, knowledge. A remarkable piece of engineering!
- gpderetta 5y agoThat's 16 bytes per clock cycle, i.e. one avx register per clock cycle. As most intel CPUs can only do one store per clock cycle, that's also the theoretical limit with avx. I wonder if using non temporal stores would help make the code be cache size agnostic. Note that the instruction latency is not important as long as you can pipeline the computation fully (which appear to be the case here!). Edit: to go faster you would need to be able to use the bandwidth of more than one cpu. I wonder if you could precompute were the output will cross a page to be able to have distinct cores work on distinct pages... Hum I need a notepad. Edit2: it is much simpler than that, you do not need to fill a page to vmsplice it. So in principle the code should parallelize quite trivially. Have each tread grab, say 1M numbers at a time, for example by atomically incrementing counter, serialize them to a bunch of pages, then grab the next batch. A simple queue will hold the ready batches that can be spliced as needed either by a service thread or opportunistically by the thread that has just finished the batch next in sequence.
- gpderetta 5y agoNote: of course SSE is 16 bytes, AVX is 32 bytes! So there is still some margin to be exploited here.
- londons_explore 5y agoExcept the program counting the data generation rate is running on only a single CPU...
- gpderetta 5y agoThat shouldn't be a problem, pv is basically only counting the number of pages being written. As long as the page size is much larger than the number of threads it should keep up just fine.
- robertwt7 5y agoI feel stupid after reading this, is this normal?
- lightbendover 5y agoIt would naturally be foreign to most, but the neat part is that it's also pretty accessible. Look up vectorization techniques and L2 cache optimization and you're most of the way to understanding. Most people who grok something like this after their first glance are specialized in the same or similar domain and probably wouldn't have an expert understanding of some things you take for granted.
- konfusinomicon 5y agoright there with you. there is a lot to learn
- booleandilemma 5y agoWow. There is programming and then there is programming. Whenever I see something like this I feel like what I do for a living is duplo blocks in comparison.
- dgunay 5y agoI am thankful every day for the work of those who came before me. Their long hours toiling over hardware, assembly, compilers, protocol stacks, libraries, frameworks, etc let us focus on the bigger picture, how to write same-y CRUD apps for businesses :)
- xtracto 5y agoIve had the opportunity to tinker with ASM, z80 architecture, low level programming and other similar stuff (I'm less than 1/1000th able as the referenced author). I find this programming it very beautiful and rewarding in that you really know that you are programming the hardware. Unfortunately it's not an easy path to get a good paying job (unless you are exceptional like the gentleman). So I ended up building fintech web apps.
- saagarjha 5y agoYou can get a well paying job off of these skills, but the job title will read something like "performance engineer" or "security researcher" rather than "assembly programmer".
- brokenmachine 5y agoI love it that humans are so diverse - there's always someone prepared to dedicate their life to the most obscure things. It's so impressive and hilarious to me that he actually spent months on this. Well done!!
- mastax 5y agoOnly getting 7GiB/s on a Ryzen 7 1800X w/DDR4 3000. Zen 1 executes AVX2 instructions at half speed, but that doesn't account for all of the difference. I guess I need a new computer. To run FizzBuzz.
- stefanos82 5y agoI personally need some assembly renaissance, around books and new content that is. This is mind blowing to say the least!
- wly_cdgr 5y agoLiteral 10x programmer moment
- ehsankia 5y agoYeah, the fact that it's a whole order of magnitude faster than all the other, even assembly based solutions, is insane.
- wellthisisgreat 5y agoSorry for the super layman question, but can someone explain why is this so amazing?
- BenjiWiebe 5y agoBecause it's super CRAZY fast.
- jodrellblank 5y agoA typical desktp computer processor runs at 3Ghz, or 3 billion cycles per second. It has 64-bit registers, which is 8x8 bytes. If it moves one register of results per clock cycle that's up to 24 billion bytes per second, 24GB/s if it does nothing else and never stalls or trips up[1]. Less than half the speed this answer is moving data. In a typical desktop computer from a few years back the connection between CPU and main memory tops out at 25GB/sec throughput[2], often less. There's delay when a user program requests that the Linux kernel does things such as allocate memory or open input/output. Printing text to a console is really quite slow. That means lots of stalls and trips waiting for IO related things and context switching as the same processor runs both the FizzBuzz printer and the PV counter and the Linux kernel and pipes connecting them together and has to keep task-switching between them. From the opening question on that page "A naive implementation written in C gets you about 170MiB/s on an average machine" and that C code is typical, there's nothing drastically bad about it. C already has a reputation as a fast, low level language. This answer is running over 320x faster than the straightforward C answer on the same hardware. If you asked people "how much faster can it possibly get without moving to specialist hardware", I doubt they'd guess that high. It's difficult to get higher speed by using more CPU cores because calculating FizzBuzz is much faster than printing it so they'd just fill up a queue and then stall waiting. To get faster, people are leaning on what exactly is happening internally, adjusting buffer sizes and how to generate the text "FizzBuzz" and get it into the right place to be printed at the right time, and which system calls can be done with less overhead, and lining up more work which can happen during the pauses, and unrolling loops to give the CPU a pattern of instructions it can execute quicker, this is getting answers into the GB/sec ranges. This answer is like the Bugatti Veyron of answers; so finely tuned it's surely getting close to the limits of what the hardware can do. Making use of AVX2 registers which can hold 32 bytes instead of 8, and can be vectorised so one instruction processes many pieces of data, which means less overhead of instructions for the CPU to decode and process per piece of data, and deeper magic, a lot of skill and knowledge required to put all of it together. And of course, someone spending months trying to send "Fizz" and "Buzz" into a counter at tens of billions of bytes per second for no good reason, is amazing in a different way. [1] A nonsense back of an envelope estimate, but good enough for context. [2] https://www.softwareok.com/?seite=faq-Beginners&faq=25 https://www.softwareok.com/?seite=faq-Beginners&faq=25
- Ericson2314 5y agoNow we just need someone to write a machine proof of correctness.
- brundolf 5y ago> Save it as fizzbuzz.S (that's a capital S as the extension) What's this about?
- Snelius 5y agoGood work!
- optymizer 5y agoHow does one debug the L2 cache? i.e. how does one inspect the data in the L2 cache and verify that loading some data from RAM actually cached X number of bytes, and the correct data has been loaded in the cache lanes, and the next instruction will use the data from there?
- uyt 5y agocallgrind/kcachegrind i think?
- nickitolas 5y agoMy naive guess would be using hardware perf counters and checking cache misses
- ummonk 5y agoI guess is faster than memcpy because both are memory bound but this only has to write to memory whereas memcpy has to both read from and write to memory? Edit: actually it sounds like it’s more cache efficient because it can always use the same block of cache memory?
- saagarjha 5y agoI believe so. A memcpy needs to touch large blocks of memory, far more than would fit in a cache, so most memcpy implementation use non-temporal stores to indicate that the memory is not going to be used again. They write directly to main memory, avoiding using up valuable cache space with a cache line that is written to once and never used again. However, this program can operate entirely within L2, so it can go faster.
- wanderingmind 5y agoprevious submission: https://news.ycombinator.com/item?id=28998588 https://news.ycombinator.com/item?id=28998588
- srcreigh 5y ago///// Third phase of output // // This is the heart of this program. It aims to be able to produce a // sustained output rate of 64 bytes of FizzBuzz per four clock cycles // in its main loop (with frequent breaks to do I/O, and rare breaks // to do more expensive calculations). // // The third phase operates primarily using a bytecode interpreter; it // generates a program in "FizzBuzz bytecode", for which each byte of // bytecode generates one byte of output. The bytecode language is // designed so that it can be interpreted using SIMD instructions; 32 // bytes of bytecode can be loaded from memory, interpreted, and have // its output stored back into memory using just four machine // instructions.
- _pastel 5y ago// [The eighth byte of LINENO_MID] changes in meaning over the course of // the program. It does indeed represent the billions digit most of // the time; but when the line number is getting close to a multiple // of 10 billion, the billions and hundred-millions digits will always // be the same as each other (either both 9s or both 0s). When this // happens, the format changes: the hundred-millions digit of // LINENO_MID represents *both* the hundred-millions and billions // digits of the line number, and the top byte then represents the // ten-billions digit. Because incrementing a number causes a row of // consecutive 9s to either stay untouched, or all roll over to 0s at // once, this effectively lets us do maths on more than 8 digits, // meaning that the normal arithmetic code within the main loop can // handle the ten-billions digit in addition to the digits below.
- DeathArrow 5y agoIt would be nice to compare its performance with a safe variant written in Rust, with a variant written in Java and one in Python to see what % of the performance we lose for high abstractions, convenience and safety.
- exikyut 5y agoIt would only be fair to write the Java version in JVM bytecode, in this style: https://news.ycombinator.com/item?id=29036245 https://news.ycombinator.com/item?id=29036245
- dijit 5y agoOnly fair then if we track the time it took to write all variants.
- DeathArrow 5y agoWhy not? That will be interesting too. For sure nothing is free and it's good to know all trade offs.
- DeathArrow 5y agoI'm imagining the author of this being called in an interview and writing this on the whiteboard. Followed by the CTO offering his job to him.
- 1vuio0pswjnm7 5y agoInteresting how he uses the C preprocessor as an Assembly preprocessor; cpp as a general purpose macro processor. Maybe this is more portable than using assembler built-in macro features that vary from assembler to assembler
- Denvercoder9 5y ago> Interesting how he uses the C preprocessor as an Assembly preprocessor It's actually a fairly common pattern, both ffmpeg and the Linux kernel do this for example.
- saagarjha 5y ago#include <sys/syscall.h> is generally the easiest way to make a syscall without hardcoding numbers into your assembly program.
- lvncelot 5y agoSomehow this reminds me of Aphyr's Technical Interview series[1], and the thought of some assembler dark wizard actually coding this in an interview is highly amusing. [1] https://aphyr.com/posts/340-reversing-the-technical-interview https://aphyr.com/posts/340-reversing-the-technical-intervie...
- dw-im-here 5y agoWow the competition for a slot in the corporation sure is fierce these days
- sireat 5y agoThe amount of optimizations remind me of story of Mel: http://www.catb.org/jargon/html/story-of-mel.html http://www.catb.org/jargon/html/story-of-mel.html
- e12e 5y agoBut does it support arbitrarily large integers? ;) Ed: no, but does pretty well: > The program outputs a quintillion lines of FizzBuzz and then exits (going further runs into problems related to the sizes of registers). This would take tens of years to accomplish, so hopefully counts as "a very high astronomical number" (although it astonishes me that it's a small enough timespan that it might be theoretically possible to reach a number as large as a quintillion without the computer breaking).
- miguelmurca 5y agoFrom the comments: "@chx: I already have a master's thesis. This was harder."
- DeathArrow 5y agoThe next level would be designing an ASIC to do FizzBuzz. :)