41 ms·
55 GiB/s FizzBuzz (2021)
- idlewords 3y agoThe first company to offer a native hardware implementation of FizzBuzz is going to revolutionize hiring and bring back boom times for our industry.
- duxup 3y agoAt the very least their hiring question will be relevant.
- sweetjuly 3y agoYou don't even need to spin your own silicon, just slap FizzBuzz on the $50k Xilinx XCVU13P and FizzBuzz at a whopping >500GB/s using all of its transceivers. Though, you'd probably need two of 'em (somebody has to receive all that FizzBuzz) so toss in another $50k for another, and them hmm you need some top tier signaling talent to manage all that, so probably add in $250k to get somebody to do this. A mere $350k for the FizzBuzz crown, it's a steal really.
- 15155 3y agoIf you're paying more than $300-500 for a XCVU13P, you're doing it wrong.
- Foobar8568 3y agoIs there a joke somewhere there? Because I don't see how this chip can be found at $300-500.
- zorgmonkey 3y agoHere is one on ebay for $600, realistically you'd need a nice rework station and the skills to reball it to actually use it. FPGA pricing for on places like mouser and digikey is notorious for being an outright lie, the high volume prices are way less then 50k (don't get me wrong they're still expensive chips, just less expensive than that). https://www.ebay.com/itm/364213117135?hash=item54cccb20cf:g:iIcAAOSw2ENkM7wH https://www.ebay.com/itm/364213117135?hash=item54cccb20cf:g:...
- 15155 3y agoThe China secondhand market is teeming with them.
- m3kw9 3y agoHarnessing power of the sun we can build a planet scale computer to bring fizzbuzz to 50gigaterrabits bee second
- mindcrime 3y agoAt Fogbeam Labs work has been proceeding to bring perfection to the crudely conceived idea of a FizzCabulator. This device not only supplies inverse reactive current for use in unilateral phase detractors, but is also capable of automatically synchronizing cardinal grammeters. The only new principle involved is that instead of power being generated by the relative motion of fizzes and buzzes, it is generated by the modial interaction of magneto-reluctance and capacitive duractance.
- logicallee 3y agoI love it. How about a quantum computing version? You know who wrote this: "Essentially, the Quantum FizzBuzz Decoupler is a device that bifurcates the bifizzial substrates and recoheres them into units of Buzzifactive tri-fusion. Its pivotal design focuses on the tripticate circuitry which utilizes pseudo-string theory, ensuring the cyclic decoupling of the Fizzionic and Buzzionic isotopes, thereby creating a conflux of cryptic poly-angular interdigitations. This hyper-convoluted mechanism leverages the intrinsic infra-doodlality of its multitudinous nano-digitators, producing a reiterative bi-fractal resonance with every flicker of the reciprocal quark-flux nano-helices. Interlocking harmonic modulators within the Decoupler support the synchronous crystallization of the brizzulated waveforms, thus reinforcing the transluminal juxtapositioning of multi-fuzzional intermediates. Within its dual-core, it harmonizes the phasic disentanglement of quasi-quintessential quantum flux through the divaricating spindles of the orthofizzial transinductor. Furthermore, the Decoupler incorporates an ultra-gloptic resonator to facilitate the recursive modulation of the bifizzial and tri-buzzoidal constituents, hence the stupendously high FizzBuzz output."
- nazgul17 3y ago...GPT? If so, what prompt did you use?
- hyperdimension 3y agoHe used the Retro Encabulator to generate this text. https://youtube.com/watch?v=RXJKdh1KZ0w https://youtube.com/watch?v=RXJKdh1KZ0w (my favorite version) It's an old engineering in-joke. Edit: oops, thought your comment was a reply to 'mindcrime. I'm keeping it here though for the lucky (very lucky in this case) 10,000.
- kazinator 3y agoThat's trivial; a shift register that latches the 15 initial values, and then just rotates them around, reading off the last one as the output.
- sweettea 3y agoAh, but for 8 of the values, you need to print the number, which changes each iteration.
- bjoli 3y agoThis realization almost got me suspended in a high school. Our goal was to make an extensible fizzbuzz(barbazzfrongetc)er and I got fascinated by the problem of making wheels. I wrote a program the generated circular lists in mit scheme that could be used as wheels (ie circular lists with either #f or fizz, buzz, bar, fizzbuzz etc). It was structured as a competition (fastest fizzbuzz up to int16 where the fizzes and buzzes would be given by the teacher at competition time), and the winner would get a chocolate bar or something inane. I couldn't eat it because I can't eat milk. I was the only one who spent some serious time on the task, and in the end my implementation was the fastest by several orders of magnitude, despite being the only using something else than C, C++ or java. The programming teacher refused to believe I wrote it myself, but due to a stroke of luck I have saved every revision of the code as a part of a primitive folder based SCM-scheme. I ended up getting a louse grade due to me not caring too much about school, but the teacher and I were on good terms and he became somewhat of a programming mentor to me
- Aromasin 3y agoYou'll maybe be pleased to know that I've already had this as a coding interview at a couple of high frequency trading FPGA interviews. I didn't do well at all in the first interview. Second time I got asked it I laughed, because I had spent a weekend down a rabbit hole, programming one on an old Cyclone V. Basically just a load of counters and state-machines. It's something like this: http://www.righto.com/2018/03/implementing-fizzbuzz-on-fpga.html http://www.righto.com/2018/03/implementing-fizzbuzz-on-fpga....
- MortimerDukePhD 3y agoMy all-time favorite FizzBuzz story: https://css-tricks.com/tales-of-a-non-unicorn-a-story-about-the-trouble-with-job-titles-and-descriptions/ https://css-tricks.com/tales-of-a-non-unicorn-a-story-about-...
- Noumenon72 3y agoIn this context, I was expecting another unusual/proficient implementation of FizzBuzz. I didn't enjoy this story about someone who was asked FizzBuzz in an interview and didn't think the position should require her to know that.
- firesteelrain 3y agoWell it’s a silly test. Her point is that the interview should match job description. These FAANG coding tests are stupid
- nickelpro 3y agoThe job description required Javascript familiarity, FizzBuzz is a bare minimum for familiarity It is barely in the same family tree as FAANG coding tests.
- firesteelrain 3y agoNo, you need to go back and read it again. According to her story, it said: “ HTML5, CSS3, JavaScript. I’m a master at the first two, but since there was no mention of programming stuff and the responsibilities section was so design-centric, I figured my jQuery proficiency and capacity to self-teach would suffice.” The entire job description read like a UI/UX designer with a minimal understanding of JavaScript. Her point is that if they wanted a software engineer then they should have hired one. She isn’t trying to be one.
- nickelpro 3y ago> Experienced with Object Oriented JavaScript and modern JavaScript libraries such as Ember, Backbone, or Angular. There's no version of a person who meets this requirement that cannot fizzbuzz. They put engineer in the title of the position. "UX Engineer" is a completely reasonable title for someone who uses Javascript, HTML, and CSS to build web frontends. That person is absolutely a programmer, and absolutely must be able to fizzbuzz (and much, much more).
- lxe 3y agoI keep getting failures to resize kernel buffer, no matter how or where I pipe it.
- langsoul-com 3y agoInteresting how Java is so fast. Among the fastest of c, cpp, asm, go and rust. How?
- Veliladon 3y agoBecause the JVM has had 27 years of R&D work done to it. If you have a really hot path a JIT will typically continually recompile it in the background with more and more optimization work and start putting the loop through that progressively more optimized code. When you're doing gigabytes of FizzBuzz the JIT will quickly have something pretty comparable to the best native code.
- colmmacc 3y agoIt doesn't matter for FizzBuzz, but in general JIT should really out-perform "native" statically compiled compilers on most real-world workloads. While there's a small penalty for the profiling JIT needs, there are massive gains for data and access dependent optimizations that static compilation can't achieve without explicit hints. For example, a JIT can observe the most commonly accessed data and re-order it to optimize for the pre-fetching pipeline. Or it can re-order operations to optimize for cache-line hotness.
- pkolaczk 3y ago> but in general JIT should really out-perform "native" statically compiled compilers on most real-world workloads. In theory, yes, but in practice I've never seen it happen. Best I ever saw was matching C speed at toy benchmarks. Even in this benchmark here, Java is decent, but does not beat even the naive implementations in C/Rust. Also, AOT compilers can do PGO as well, so they can use the same techniques. But they also have way more time and resources, so they can do things like whole program optimization, which is something JITs cannot do because they have much smaller computation and memory budget. It happened already many times to me that the first naive version of a C/C++/Rust program/function I wrote was already faster than a carefully tuned Java equivalent. AOT compilers for "fast languages" got really good these days. The design of language also influences how well it can be optimized by the compiler. E.g. it might look impressive JVM can devirtualize dynamic calls at runtime, but C++/Rust often don't have to do this at all as programs in those languages tend to have very few virtual calls if any at all.
- x86x87 3y agomaybe it's fast, but is it enterprise quality? https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...
- Noumenon72 3y agoBesides living up to the username of "ais523 - high effort answers", the author also does some high effort comments with someone who can't get the program to run. The resolution: > I suspect that what's happening is that the program was somehow compiled with ASLR turned on. For some reason, the dynamic linker doesn't respect the 4 MiB alignment of the BSS segment in this case, effectively ignoring my .align, and that's what's causing the bugs.
- simlevesque 3y agoI sometimes wonder if someone is running that program right now until it crashes in a couple decades.
- sschueller 3y agoFor a second I thought it said 55 GiB/s FritzBox which is a popular router in the German speaking part of Europe. My ISP also just last week tweeted a new 60 GiB/s capable OPNSense box[1] that will be available soon. [1] https://twitter.com/init7/status/1674920410889043973 https://twitter.com/init7/status/1674920410889043973
- deleted 3y ago[deleted]
- MrFoof 3y agoI’ve a DEC750 that I’ve bumped to 16GB memory. A 10GbE capable (2.3GbE Wireguard) router that’s silent and idles on par with my cable modem (8W) has been a great piece of equipment I don’t see myself replacing until 2030-2035. I even plugged in a USB WiFi adapter so if cable goes out, it fails over specific VLANs and will use my cell phone to keep core connectivity up for work, etc. They’re not cheap, but if you want some serious kit that also financially supports the OPNSense project, the Deciso appliances are tough to argue. Power efficient, durability-focused components, just work. It’s nice seeing their commercial offerings getting beefier.
- pier25 3y agoMakes you wonder... How fast would everything be if it was written in assembly. In audio dev it's very common for dsp code to be written in assembly.
- geek_at 3y agoOr if everything had been written by "ais523 - high effort answers"
- xxs 3y agoYou dont need Assembly, you need to the code not to be terrible, which is generally hard with the amount of code/developers needed.
- dumdumchan 3y agoIt wouldn't run at all since it wouldn't exist.
- nickelpro 3y agoAssembly is hardly the reason this is fast. It is necessary to this solution but by no means sufficient. Extreme algorithmic research combined with a high LOK of Linux syscalls and platform specific optimizations is what allows this to exist. To quote the author, Alex Smith, himself: > @chx: I already have a master's thesis. This was harder. This is in a different universe than what can be produced by simply "do it in assembly".
- wheelerof4te 3y ago"Extreme algorithmic research combined with a high LOK of Linux syscalls and platform specific optimizations is what allows this to exist." No, author's extreme boredom and/or free time allowed this to exist. Nothing else.
- moreati 3y agoWhat's LOK in this context? Search and Wikipedia didn't throw up anything. Thanks.
- mellosouls 3y agoPrevious: https://news.ycombinator.com/item?id=29031488 https://news.ycombinator.com/item?id=29031488 https://news.ycombinator.com/item?id=29413656 https://news.ycombinator.com/item?id=29413656
- haunter 3y ago> Save it as fizzbuzz.S (that's a capital S as the extension) What’s the significane of “.S” vs “.s”?
- easytiger 3y agoGCC et al won't overwrite a .S but if you ask it to gen ASM (e.g. gcc -S xyz.c) it will overwrite a .s
- harrisi 3y agoCapital S will run the pre processor first. Edit: From manpage: file.s Assembler code. file.S file.sx Assembler code that must be preprocessed.
- wkz 3y agoIIRC, I believe that the difference traditionally was whether to pass the input through the preprocessor (.S), or not (.s). Not sure if it makes a difference on modern toolchains.
- zen_1 3y agoThe convention I'm used to uses .S to denote hand-written assembly files (usually tracked in git) vs .s for machine generated assembly which can be overwritten as needed.
- edwintorok 3y agoThis doesn't use io_uring so it might be possible to make this go even faster these days...
- saagarjha 3y agoI would expect this to slow it down rather than make it go faster.
- rs38 3y agodo I need glasses, or not a single c#/.net implementation?
- rs38 3y agofound my glasses and there is a candidate AVX optimized to 1 GB/s
- leijurv 3y agoThis inspired me to plumb the depths of FizzBuzz, seeking further into it than anyone ever has before: the 10^10000000000th digit (it's a "1"): https://github.com/leijurv/reverse-fizzbuzz https://github.com/leijurv/reverse-fizzbuzz
- saagarjha 3y agoAh yes, the hyper log log log algorithm
- jagrsw 3y agoThis exercise appears to be somewhat flawed, even if entertaining/informative. Instead of evaluating the speed at which complex problems are resolved, it predominantly tests a peripheral issue: the efficiency of extracting memory from one process and transferring it to another. This allows for the illusion that the second process continues to write to a console/file, even though, technically, it does not - executing pv >/dev/null is essentially a no-op, as the write system call returns almost instantly. vmsplice grants access to a process' buffer/memory to another process - a shared mem equivalent. As the initial competition requirements are likely vague, I'd imagine it's unclear if this is still good wrt the rules.
- LegionMammal978 3y ago> As the initial competition requirements are likely vague, I'd imagine it's unclear if this is still good wrt the rules. You can scroll upward to the original question to see the initial requirements, and check the edit history to verify that they haven't changed since the start of the challenge: > Write your fizz buzz program. Run it. Pipe the output through <your_program> | pv > /dev/null. The higher the throughput, the better you did. > The program output must be exactly valid fizzbuzz. No playing tricks such as writing null bytes in between the valid output - null bytes that don't show up in the console but do count towards pv throughput. And vmsplice(2) indeed produces a stream of bytes in the standard output pipe that pv(1) can splice into /dev/null, or cat(1) can copy into the terminal. This submission was not the only one that uses vmsplice(2); others have found that it's far from a magic bullet. Once you pass the I/O hurdle, much work remains in generating the pages of output as quickly as possible.
- tkluck 3y agoI disagree, because one does not get to the bottleneck being _the efficiency of extracting memory from one process and transferring it to another_ without major fizzbuzz-specific optimizations first. For example, there's a clever bit representation to get base-10 carries to happen natively. The initial competition requirements are not particularly vague about this point: Measuring throughput with `<program> | pv > /dev/null` is prescribed, and it also says > Architecture specific optimizations / assembly is also allowed. This is not a real contest - I just want to see how people push fizz buzz to its limit - even if it only works in special circumstances/platforms.
- DeathArrow 3y agoMeanwhile 99% of developers claim that writing desktop apps with Electron is perfectly fine, speed of the language and runtime doesn't matter since you are going to wait for I/O anyway and waiting a few seconds after launching an app to be able to use it, is perfectly fine even on most powerful hardware. 99% of managers claim that developers cost more than hardware, so it's perfectly fine if the code is slow, they can just buy more hardware.
- sillysaurusx 3y agoThese two viewpoints aren’t mutually exclusive. If they needed to develop fizzbuzz at 55GB/s, they might conclude that electron won’t get them there.
- wsve 3y agoIs your point that we should prioritize app performance and spending more on larger teams of develops, over the ease of quickly writing apps in popular frameworks that work on any system and the web? If so, that's missing half the picture. "People don't care about performance" isn't why devs gravitate towards Electron. Devs and managers gravitate towards Electron because it means they don't have to hire extra people and do more work to get their native apps working on whatever operating systems they ship to and rewrite the whole app for the web. Yeah, it'd be nice not to have the performance penalty, but some teams have accurately calculated that the performance loss the customer realistically notices is worth the benefits of writing and maintaining the app.
- hk1337 3y agoI feel like a lot of devs take things like YAGNI and “move fast and break” things a bit too seriously and to great extreme. They’re too willing to accept an adequate solution because it “works” rather than spending just a little bit more time to find a more appropriate solution.
- sokoloff 3y agoIf it works (or even “works”) for the users and for the business, it’s probably appropriate.
- k1next 3y agoInterviewer: So let's start with a simple coding challenge, it's called FizzBuzz. Have you heard of it?
- qazpot 3y agoI wrote simple implementations (simple if/else/while and printing to stdout) with no optimizations in Rust, Python3 and C Rust -> 23.2MiB/s Python3 -> 28.6MiB/s C -> 238MiB/s Does anyone know why Rust's performance is in the same ballpark as Python3. I thought it would be more closer to C.
- shakow 3y agoCan we see your code?
- dontlaugh 3y agoAlmost certainly the limitation is due to printing, likely buffering or locking.
- ismailmaj 3y agoI wrote this a long time ago, you might find it useful. https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-concurrency https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
- qazpot 3y agoThanks for writing this, led me to a rabbit hole.
- sicariusnoctis 3y agoNeat tricks. Beyond BufWriter (which I'm already using) and multthreading, I'm guessing there's not much to be done to improve my "frece" (a simple CLI frecency-indexed database) tool's performance without making it overly complicated. https://github.com/YodaEmbedding/frece/blob/master/src/main.rs#L79-L92 https://github.com/YodaEmbedding/frece/blob/master/src/main....
- cyber_kinetist 3y agoRust’s print function locks by default (because of safety), C doesn’t. For more info see the Rust documentation: https://doc.rust-lang.org/std/macro.print.html https://doc.rust-lang.org/std/macro.print.html In order to get similar performance as C, you probably need to take care of this lock yourself: let mut lock = stdout().lock(); write!(lock, "hello world").unwrap(); (And also you need to make the buffering size for stdout match C’s.)
- londons_explore 3y agoThe most impressive thing to me is that Linux allows data piped from one program to another to stay entirely in L2 cache and not hit main memory. To me, that is amazing systems architectural design - so many different parts of a regular linux kernel all working together to let this fastpath happen. Would such a thing be possible on Mac OSX's Mach ports or Windows's Named Pipes?
- zeusk 3y agoIf a CPU's caches are physically tagged and both process's page tables share the same backing physical page then the CPU will let the cache contents be used by either process as long as the OS doesn't explicitly flush/invalidate cache on context switch.
- twoodfin 3y agoThe major cost of two processes coordinating shared data over two threads is TLB invalidation on a context switch. I assume this is what the author meant by “page table contention” as a bottleneck: Without TLB invalidation there would be no need for either process/thread to ever touch page tables in a scenario like this.
- zeusk 3y agoIt's unrelated to TLB; page table contention is related to associative caches where you can have two distinct addresses map to the same cache set and cause false cache miss or exhaust the cache set and cause repeated fill from memory. TLB has to be flushed for process context switch on x86 regardless of Windows/Linux - but modern systems typically allow it to be selectively flushed (the system can elect to not flush tlb for the shared mappings that exist in both processes). TLB miss vs Cache miss are an order of magnitude apart, and multiple orders if the corresponding pte itself is resident in dcache.
- twoodfin 3y agoTLB has to be flushed for process context switch on x86 regardless of Windows/Linux - but modern systems typically allow it to be selectively flushed (the system can elect to not flush tlb for the shared mappings that exist in both processes). What’s the mechanism for this? AFAIK one of the main motivations for the recent heated discussions on PostgreSQL adopting a threaded model would be eliminating TLB flushes in high-context-switch environments. Can Linux already preserve their (massive) shared mappings?
- miguelmurca 3y agoEvery time this is reposted I giggle at this comment: > @chx: I already have a master's thesis. This was harder. – ais523 - high effort answers Oct 29, 2021 at 1:17
- unpopularopp 3y agoI'm trying to go through this, obviously incredibly complicated, can anyone explain this comment? >LINENO_TOP doesn't need to be initialized for new widths, because an overrun by 100 lines is possible, but by 10 billion lines isn't
- londons_explore 3y ago// The main loop // The bytecode interpreter consists of four instructions: // 1. Load the bytecode from memory into %ymm2; What is the performance impact of this load? Do you get more store-to-L2 memory bandwidth if you aren't loading at the same time?
- NKosmatos 3y agoHow come no one has asked our GPT/AI/LLM “overlords” for a faster FizzBuzz implementation ;-)
- jadtz 3y agoLLM cannot produce something that doesnt exist already, it will probably spit out the same code ais523 wrote.
- dredmorbius 3y agoMore in the tradition of code golf, my reasonably-terse gawk fizzbuzz, abusing conditional expressions: #!/usr/bin/env gawk -f BEGIN { for (i=1;i<=100;i++) { printf(" %2s", i%(3*5)!=0 ? i%5!=0 ? i%3!=0 ? i : "fizz" : "buzz" : "fizzbuzz\n" ) } printf("\n") } No idea as to actual throughput though. I believe this is slower than explicit loop, if/then, or switch/case testing though (based on hazy recollections of past performance testing).
- omgmajk 3y agoI love these challenges because I always learn a ton from just reading through and (trying) to understand the answers/entries. Same as with IOCCC [1]. [1] https://www.ioccc.org/ https://www.ioccc.org/
- husamia 3y agoCould the FizzBuzz logic be computed "in-memory"?
- winrid 3y agoCool to know that I can write simple Java code and it's almost in the same order of magnitude as the insane sanic version.