11 ms·
A leap year check in three instructions
- qingcharles 2y agoI love these incomprehensible magic number optimizations. Every time I see one I wonder how many optimizations like this we missed back in the old days when we were writing all our inner loops in assembly? Does anyone have a collection of these things?
- masfuerte 2y agoWe didn't miss them. In those days they weren't optimizations. Multiplications were really expensive.
- kurthr 2y agoand divides were worse. (1 cycle add, 10 cycle mult, 60 cycle div)
- genewitch 2y agoThat's fair but mod is division, or no? So realistically the new magic number version would be faster. Assuming there is 32 bit int support. Sorry, this is above my paygrade.
- bobmcnamara 2y agoMany compiles will compute div-by-a-constant using the invert, multiply, and shift off the remainder trick. Once you have that, you can do mod-by-a-constant as a derivative and usually still beat 1-bit or 2-bit division.
- qingcharles 2y agoYeah, I'm thinking more of ones that remove all the divs from some crazy math functions for graphics rendering and replace them all with bit shifts or boolean ops.
- ryao 2y agoDivision still is worse: https://github.com/ridiculousfish/libdivide https://github.com/ridiculousfish/libdivide
- godelski 2y agoRelated, Computerphile had a video a few months ago where they try to put compute time relative to human time, similar to the way one might visualize an atom by making the proton the size of a golfball. I think it can help put some costs into perspective and really show why branching maters as well as the great engineering done to hide some of the slowdowns. But definitely some things are being marked simply by the sheer speed of the clock (like how the small size of a proton hides how empty an atom is) https://youtube.com/watch?v=PpaQrzoDW2I
- deleted 2y ago[deleted]
- TacticalCoder 2y ago[dead]
- JdeBP 2y agoMultiplications of this word length, one should clarify. It's not that multiplication was an inherently more expensive or different operation back then (assuming from context here that the "old days" of coding inner loops in assembly language pre-date even the 32-bit ALU era). Binary multiplication has not changed in millennia. Ancient Egyptians were using the same binary integer multiplication logic 5 millennia ago as ALUs do today. It was that generally the fast hardware multiplication operations in ALUs didn't have very many bits in the register word length, so multiplications of wider words had to be done with library functions that did long multiplication in (say) base 256. So this code in the headlined article would not be "three instructions" but three calls to internal helper library functions used by the compiler for long-word multiplication, comparison, and bitwise AND; not markedly more optimal than three internal helper function calls for the three original modulo operations, and in fact less optimal than the bit-twiddled modulo-powers-of-2 version found halfway down the headlined article, which would only need check the least significant byte and not call library functions for two of the 32-bit modulo operations. Bonus points to anyone who remembers the helper function names in Microsoft BASIC's runtime library straight off the top of xyr head. It is probably a good thing that I finally seem to have forgotten them. (-: They all began with "B$" as I recall.
- eru 2y ago> Multiplications of this word length, one should clarify. It's not that multiplication was an inherently more expensive or different operation back then (assuming from context here that the "old days" of coding inner loops in assembly language pre-date even the 32-bit ALU era). Binary multiplication has not changed in millennia. Ancient Egyptians were using the same binary integer multiplication logic 5 millennia ago as ALUs do today. Well, we can actually multiply long binary numbers asymptotically faster than Ancient Egyptians. See eg https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
- kruador 2y agoMost 8-bit CPUs didn't even have a hardware multiply instruction. To multiply on a 6502, for example, or a Z80, you have to add repeatedly. You can multiply by a power of 2 by shifting left, so you can get a bigger result by switching between shifting and adding or subtracting. Although, again, on these earlier CPUs you can only shift by one bit at a time, rather than by a variable number of bits. There's also the difference between multiplying by a hard-coded value, which can be implemented with shifts and adds, and multiplying two variables, which has to be done with an algorithm. The 8086 did have multiply instructions, but they were implemented as a loop in the microcode, adding the multiplicand, or not, once for each bit in the multiplier. More at https://www.righto.com/2023/03/8086-multiplication-microcode.html https://www.righto.com/2023/03/8086-multiplication-microcode.... Multiplying by a fixed value using shifts and adds could be faster. The prototype ARM1 did not have a multiply instruction. The architecture does have a barrel shifter which can shift one of the operands by any number of bits. For a fixed multiplication, it's possible to compute multiplying by a power of two, by (power of two plus 1), or by (power of two minus 1) in a single instruction. The latter is why ARM has both a SUB (subtract) instruction, computing rd := rs1 - Operand2, and a RSB (Reverse SuBtract) instruction, computing rd := Operand2 - rs1. The second operand goes through the barrel shifter, allowing you to write an instruction like 'RSB R0, R1, R1, #4' meaning 'R0 := (R1 << 4) - R1', or in other words '(R1 * 16) - R1', or R1 * 15. ARMv2 added in MUL and MLA (MuLtiply and Accumulate) instructions. The hardware ARM2 implementation uses a Booth's encoder to multiply 2 bits at a time, taking up to 16 cycles for 32 bits. It can exit early if the remaining bits are all 0s. Later ARM cores implemented an optional wider multiplier (that's the 'M' in 'ARM7TDMI', for example) that could multiply more bits at a time, therefore executing in fewer cycles. I believe ARM7TDMI was 8-bit, completing in up to 4 cycles (again, offering early exit). Modern ARM cores can do 64-bit multiplies in a single cycle.
- Someone 2y agoAnd branches were cheaper without pipelining
- tylerhou 2y agoYou should look at supercompilation.
- mshockwave 2y agosometimes also known as superoptimization, which many of them also use SMT solvers like Z3 mentioned in the article
- tylerhou 2y agoYes, sorry, superoptimization is the correct term.
- owl_vision 2y agothere is "Hacker's Delight" by Henry S. Warren, Jr. https://en.wikipedia.org/wiki/Hacker's_Delight https://en.wikipedia.org/wiki/Hacker's_Delight
- qingcharles 2y agoLooks awesome, thank you :)
- ryao 2y agoHere is a short list: https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html It is not on the list, but #define CMP(X, Y) (((X) > (Y)) - ((X) < (Y))) is an efficient way to do generic comparisons for things that want UNIX-style comparators. If you compare the output against 0 to check for some form of greater than, less than or equality, the compiler should automatically simplify it. For example, CMP(X, Y) > 0 is simplified to (X > Y) by a compiler. The signum(x) function that is equivalent to CMP(X, 0) can be done in 3 or 4 instructions depending on your architecture without any comparison operations: https://www.cs.cornell.edu/courses/cs6120/2022sp/blog/superoptimizer/ https://www.cs.cornell.edu/courses/cs6120/2022sp/blog/supero... It is such a famous example, that compilers probably optimize CMP(X, 0) to that, but I have not checked. Coincidentally, the expansion of CMP(X, 0) is on the bit hacks list. There are a few more superoptimized mathematical operations listed here: https://www2.cs.arizona.edu/~collberg/Teaching/553/2011/Resources/jay-slides.pdf https://www2.cs.arizona.edu/~collberg/Teaching/553/2011/Reso... Note that the assembly code appears to be for the Motorola 68000 processor and it makes use of flags that are set in edge cases to work. Finally, there is a list of helpful macros for bit operations that originated in OpenSolaris (as far as I know) here: https://github.com/freebsd/freebsd-src/blob/master/sys/cddl/contrib/opensolaris/uts/common/sys/sysmacros.h#L236 https://github.com/freebsd/freebsd-src/blob/master/sys/cddl/... There used to be an Open Solaris blog post on them, but Oracle has taken it down. Enjoy!
- JdeBP 2y agoFor an entire book on this stuff, see Henry S. Warren Jr's Hackers Delight. The "three valued compare function" is in chapter 2, for example.
- eru 2y ago> It is not on the list, but #define CMP(X, Y) (((X) > (Y)) - ((X) < (Y))) is an efficient way to do generic comparisons for things that want UNIX-style comparators. If you compare the output against 0 to check for some form of greater than, less than or equality, the compiler should automatically simplify it. For example, CMP(X, Y) > 0 is simplified to (X > Y) by a compiler. I guess this only applies when the compiler knows what version of > you are using? Eg it might not work in C++ when < and > are overloaded for eg strings?
- captaincrunch 2y agoThis is fast, READABLE, and accurate: bool is_leap_year(uint32_t y) { // Works for Gregorian years in range [0, 65535] return ((!(y & 3)) && ((y % 25 != 0) || !(y & 15))); }
- andrepd 2y agoThis impl is mentioned in TFA.. It's much slower and includes branches.
- hoten 2y agoI'd expect even without optimizations on, there wouldn't be branches in the output for that code.
- kragen 2y agoThere are, even with optimizations on. You could have checked: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:1,endLineNumber:8,positionColumn:1,positionLineNumber:8,selectionStartColumn:1,selectionStartLineNumber:8,startColumn:1,startLineNumber:8),source:'%23include+%3Cstdbool.h%3E%0A%23include+%3Cstdint.h%3E%0A%0Abool+is_leap_year(uint32_t+y)+%7B%0A++//+Works+for+Gregorian+years+in+range+%5B0,+65535%5D%0A++return+((!!(y+%26+3))+%26%26+((y+%25+25+!!%3D+0)+%7C%7C+!!(y+%26+15)))%3B%0A%7D%0A'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:47.573691284800574,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:cg151,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'1',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'-O5',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+15.1+(Editor+%231)',t:'0')),k:34.13672688710442,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(compilerName:'x86-64+gcc+(trunk)',editorid:1,fontScale:14,fontUsePx:'0',j:1,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+gcc+15.1+(Compiler+%231)',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:52.42630871519946,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... I didn't find any way to get a compiler to generate a branchless version. I tried clang and GCC, both for amd64, with -O0, -O5, -Os, and for clang, -Oz.
- drewg123 2y agoI tend to be of the opinion that for modern general purpose CPUs in this era, such micro-optimizations are totally unnecessary because modern CPUs are so fast that instructions are almost free. But do you know what's not free? Memory accesses[1]. So when I'm optimizing things, I focus on making things more cache friendly. [1] http://gec.di.uminho.pt/discip/minf/ac0102/1000gap_proc-mem_speed.pdf http://gec.di.uminho.pt/discip/minf/ac0102/1000gap_proc-mem_...
- drewg123 2y agoTo temper this slightly, these sorts of optimizations are useful on embedded CPUs for device firmware, IOT, etc. I've worked on smart NIC CPUs where cycles were so precious we'd do all kinds of crazy unreadable things.
- sitzkrieg 2y agoon the flip side of the topic, trying to do any datetime handling on the edge of embedded compute is going to be wrong 100% of the time anyway
- RaoulP 2y agoWould you mind elaborating?
- bigiain 2y agoI suspect most IOT device manufacturers expect/design their device to be landfill before worrying about leap year math. (In my least optimistic moments, I suspect some of them may intentionally implement known broken algorithms that make their eWaste stop working correctly at some point in the near future that's statistically likely to bear beyond the warranty period.)
- crote 2y ago"Is year divisible by four" will work perfectly fine for the next 75 years. Random consumer devices are definitely not going to survive that long, so being capable of dealing with it adds exactly zero value to the product. It's hard to imagine being in a situation where the cost of the additional "year divisible by 100" check, or even the "year divisible by 400" check is too much to bear, and it's trivial enough that the developer overhead is negligible, but you never know when you need those extra handful of bytes of memory I guess...
- 22c 2y agoPart-way through the section on bit-twiddling, I thought to myself "Oh I wonder if we could use a solver here". Lo and behold, I was pleasantly surprised to see the author then take that exact approach. Love the attention to detail in this post!
- andrepd 2y agoInteresting cppcon talk related to this (author is cited in TFA): https://www.youtube.com/watch?v=0s9F4QWAl-E https://www.youtube.com/watch?v=0s9F4QWAl-E
- olq 2y agoThis is gold! HN Kino! Taking the hardest problem in the world, date checking, and casually bitflipping the hell out of it. Hats off man :D
- high_pathetic 2y agohttps://news.ycombinator.com/item?id=42915723#42924485 https://news.ycombinator.com/item?id=42915723#42924485
- dndn1 2y agoIf you need to know a leap year and it's before the year 6000, I made an interactive calculator and visualization [1]. It's >3 machine instructions (and I admire the mathematical tricks included in the post), but it does do thousands of calculations fairly quickly :) [1] https://calculang.dev/examples-viewer?id=leap-year https://calculang.dev/examples-viewer?id=leap-year
- esafak 2y agoI'd be impressed if an LLM derived this independently.
- NelsonMinar 2y agoIt's rare to read code that makes me literally laugh out loud. What a delight.
- userbinator 2y agoAt first I thought it would be using the BCD instructions in some way, as shown near the bottom of this article: https://news.ycombinator.com/item?id=8477254 https://news.ycombinator.com/item?id=8477254
- kragen 2y agoYeah, I was thinking AAM, but that wouldn't get you to 3.
- deleted 2y ago[deleted]
- crossroadsguy 2y agoThis reminds me of once when I was giving an algo/ds interview (in Java) and the interviewer started asking me questions where one of the answers usually was “to be memorised” shit like this and he started pestering me to give him those answers (even though I said I don’t know and definitely don’t recall) and that too in C. As per him “everyone who coded knew C.. at least in college” and started becoming a bit more hostile. I think it was the first interview that I had ended as an interviewee. And I call this thing “bit gymnastics”.
- abrookewood 2y agoSounds like someone desperate to prove their superiority - now imagine working with them every day.
- pastage 2y agoIt is not they way todo it agreed on that, but it can be one of the only way of getting hand wavy persons to get technical. Interviewing can be frustrating when you do not see what you expected. So no need to believe it was done toxicly.
- crossroadsguy 2y ago> getting hand wavy persons to get technical Interesting. And then I literally said “hostile” in my comment and you didn’t find it toxic? Strange but it’s okay :)
- pastage 1y agoI sympathize, your experiences are of course different from mine. Hostile is such a useless tactic at interviews that I just find it mind boggling that someone would do it on purpose.
- andrewmcwatters 2y agoGod, everyone has one of these stupid stories, don't they? For me, it was some moron at a Wordpress sweatshop who pointed out that the way to find the number of parameters of a function was through (a now deprecated and unsupported!) arity property. OK, great. 16 years into my career, and I've never needed to count the number of parameters of a JavaScript function. And if you needed to, that wasn't going to be the property you'd read anyway.
- _heimdall 2y ago> return ((y * 1073750999) & 3221352463) <= 126976; > How does this work? The answer is surprisingly complex. I don't think anyone is surprised in the complexity of any explanation for that algorithm :D
- fuzunoglu 2y agoTaking a look at numbers in binary reveals some interesting patterns. Although seems obvious, it was interesting to me when I realized that all prime numbers except 2 end with 1.
- silisili 2y agoNot trying to be a jerk, but why is that interesting? Am I missing something more than all odd numbers end in 1, and primes by their nature cannot be even(except 2, as you mentioned).
- lkirkwood 2y agoJust nitpick but all odd numbers end in an odd number, not 1, and all even numbers end in an even number i.e. a multiple of 2.
- charcircuit 2y agoThe original function is likely only going to be 3 instructions. xor, test, jne and only 1 of these is dependent on a previous instruction. In the "fast" version from the article there are 4 instructions with each depending on the previous instruction. I'm not surprised it lost in the benchmark.
- degamad 2y ago3 instructions and a branch prediction.
- Dylan16807 2y agoA branch that triggers 3/4 of the time will not perform well. Whether that matters comes down to how this function integrates into the rest of the program.
- charcircuit 2y agoI don't think the years tested will be random. I think practically it will see long strings of the same value.
- usr1106 2y agoInteresting. In one place the author argues: 0 is missing, but we already know... The is no year 0, it goes 1 BC, 1 AD. So testing whether 0 is a leap year is moot.
- skissane 2y ago> The is no year 0, it goes 1 BC, 1 AD. So testing whether 0 is a leap year is moot. Not true if you use astronomical year numbering: https://en.m.wikipedia.org/wiki/Astronomical_year_numbering https://en.m.wikipedia.org/wiki/Astronomical_year_numbering Which is arguably the right thing to do outside of specific domains (such as history) in which BCE is entrenched If your software really has to display years in BCE, I think the cleanest way is store it as astronomical year numbering internally, then convert to CE/BCE on output
- rf15 2y ago> Astronomers use the Julian calendar for years before 1582, including the year 0, and the Gregorian calendar for years after 1582 So what happens when it's 1582? (sorry, currently no time to articulate a good wiki fix)
- skissane 2y agoI think they use the original Gregorian cutover, in which 1582-10-04 is followed by 1582-10-15, and the dates 1582-10-05 through 1582-10-14 don’t exist. However, in general, I think proleptic Gregorian is simpler. But in astronomy do what the astronomers do. And in history, dates between 1582 and 1923 (inclusive), you really need to explicitly mark the date as Gregorian or Julian, or have contextual information (such as the country) to determine which one to use. 1923 because that was when Greece switched from Julian to Gregorian, the last country to officially do so. Although various other countries in the Middle East and Asia adopted the Gregorian calendar more recently than 1923 - e.g. Saudi Arabia switched from the Islamic calendar to the Gregorian for most commercial purposes in 2016, and for most government purposes in 2023 - those later adoptions aren’t relevant to Julian-Gregorian cutover since they weren’t moving from Julian to Gregorian, they were moving from something non-Western to Gregorian Large chunks of the Eastern Orthodox Church still use the Julian calendar for religious purposes; other parts theoretically use a calendar called “Revised Julian” which is identical to Gregorian until 2800 and different thereafter - although I wonder if humanity (and those churches) are still around in 2800, will they actually deviate from Gregorian at that point, or will they decide not to after all, or forget that they were officially supposed to
- JdeBP 2y agoOne of these days, someone will get creative and do this sort of thing for the leap year algorithm of the Revised Julian Calendar instead of the Gregorian one.
- divbzero 2y ago> Note that modern compilers like gcc or clang will produce something like is_leap_year2 from is_leap_year1, so there is not much point in doing this in C source, but it might be useful in other programming languages. The optimizations that compilers can achieve kind of amaze me. Indeed, the latest version of cal from util-linux keeps it simple in the C source: return ( !(year % 4) && (year % 100) ) || !(year % 400); https://github.com/util-linux/util-linux/blob/v2.41/misc-utils/cal.c#L633 https://github.com/util-linux/util-linux/blob/v2.41/misc-uti...
- sigmoid10 2y agoI like how the linux one is also easier to understand because it doesn't perform three sequential checks which actually invert the last two conditions plus a default return. That's the kind of stuff that can make you crazy if you ever have to debug it.
- darkwater 2y agoI wondered 3 minutes "this is not right" til I realized that if ((y % 25) != 0) return true; was actually checking for different from 0 (which in hindsight makes also sense because the century years by default are not leap unless they divide by 400)
- cookiengineer 2y agoBut this is wrong and can only represent dates after the specific year when they switched from the Julian to Gregorian calendar! For more on this, I recommend reading and implementing a function that calculates the day of the week [1]. Then you can join me in the special insanity hell of people that were trying to deal with human calendars. And then you should implement a test case for the dates between Thursday 4 October 1582 and Friday 15 October 1582 :) [1] https://en.m.wikipedia.org/wiki/Determination_of_the_day_of_the_week https://en.m.wikipedia.org/wiki/Determination_of_the_day_of_...
- deleted 2y ago[deleted]
- JdeBP 2y agoIf the author ever reads this: The hyperlink to Jacob Pratt's article has the hyperlink URL and text swapped.
- hairtuq 2y agoThanks, fixed.
- nullc 2y agoThere are many cute binary/logic tricks, if you like them be sure to read Hackers Delight and https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html . Once you've studied enough of them you'll find yourself easily coming up with more. Warning: This may increase or decrease your popularity with fellow programmers, depending on how lucky you are in encountering problems where they make an important performance difference rather than a readability problem for people who have not deeply internalized bit twiddling. Multiply and mask for varrious purposes is a thing I commonly use in my own code-- it's much more attractive now that it was decades ago because almost all computers we target these days have extremely fast multipliers. These full-with logic operations and multipliers give you kind of a very parallel computer packed into a single instruction. The only problem is that it's a little tricky to program. :) At least this one was easy to explain mechanically. Some bit hacks require p-adic numbers and other elements of number theory to explain.
- croisillon 2y agoThey should add that to https://github.com/alexmacarthur/current-time-api https://github.com/alexmacarthur/current-time-api
- lame-lexem 2y agotha page seems to have problems with layout overflow in equation blocks on mobile. It seems that because spans are inline elements they won't overflow. I think you can make them block elements and enable some form of overflow to solve it.
- ReptileMan 2y agoSomewhat relevant and related. >“So, it’s a bug in Lotus 123?” >“Yeah, but probably an intentional one. Lotus had to fit in 640K. That’s not a lot of memory. If you ignore 1900, you can figure out if a given year is a leap year just by looking to see if the rightmost two bits are zero. That’s really fast and easy. The Lotus guys probably figured it didn’t matter to be wrong for those two months way in the past. It looks like the Basic guys wanted to be anal about those two months, so they moved the epoch one day back.” https://www.joelonsoftware.com/2006/06/16/my-first-billg-review/ https://www.joelonsoftware.com/2006/06/16/my-first-billg-rev...
- xrisk 2y agoThat was a great read. Thanks for sharing!
- Quenby 2y agoNever thought a leap year check could be this interesting. Maybe low-level programmers had already discovered tricks like this long ago,they just never got written down? Feels like there’s still so much like this, hidden in old code, waiting to be rediscovered. If anyone has a collection of these kinds of techniques, I’d really love to dig into it.
- nickdothutton 2y agoThere are things I had to learn at home in the 80s on the z80 that I have mostly forgotten. Very occasionally I wheel something out to “show the kids” (those in their 20s) and it feels like performing a magic trick.
- arp242 2y agoLotus 1-2-3 famously considers 1900 a leap year (carried over in Excel for compatibility), presumably because it just does the "(y & 3) != 0" check (arguably a reasonable optimisation given the hardware of the time). I'd be surprised if someone found this solution before, as it seems both relatively difficult to find and a small optimisation.
- nickysielicki 2y agoKnowing how to use z3 for stuff like this is a superpower that not a lot of people have, but is definitely worth knowing if you work with code that needs to be optimized at this level. I have an mcp script that interfaces with z3, and this comment is a reminder to myself to find some time to expand it in the future for this specific flow. It’s also worth calling out angr as an interface between capstone and z3, which can take this to another level.
- npendleton 2y agoThis is so cool! Terrible nitpick, but this is actually 3 operations, not instructions. On x86 you get 4: is_leap_year_fast: imul eax, edi, 1073750999 and eax, -1073614833 cmp eax, 126977 setb al ret On ARM you get a bit more due to instruction encoding: is_leap_year_fast: ldr r1, .LCPI0_0 mul r0, r0, r1 ldr r1, .LCPI0_1 and r1, r0, r1 mov r0, #0 cmp r1, #126976 movwls r0, #1 bx lr .LCPI0_0: .long 1073750999 .LCPI0_1: .long 3221352463 Compiler explorer reference: https://godbolt.org/z/7ajYqbT9z https://godbolt.org/z/7ajYqbT9z
- gpderetta 2y agoYou could argue that the setb and ret are not part of the leap year check itself. For example if the compiled inlined the call into a caller doing: if(is_leap_year_fast()) {...} Then the ret would obviously go away and the setb wouldn't be necessary as it could generate directly a conditional jmp from the result of the cmp.
- npendleton 2y agoHah, great point!
- smeej 2y ago> whether a year 0 ≤ y ≤ 102499 or equal to 0?
- cestith 2y agoYes, on the calendar being discussed.
- dahart 2y agoLooks like gcc & clang use some of the bit-twiddling tricks when you compile the original function with -O3: https://godbolt.org/z/eshd9axod https://godbolt.org/z/eshd9axod is_leap_year(unsigned int): xor eax, eax test dil, 3 jne .L1 imul edi, edi, -1030792151 mov eax, 1 mov edx, edi ror edx, 2 cmp edx, 42949672 ja .L1 ror edi, 4 cmp edi, 10737418 setbe al .L1: ret
- ryao 2y agoThey are sometimes very good at using mathematical identities to do simplifications. The following commit was actually inspired by the output of GCC: https://github.com/openzfs/spl/commit/8fc851b7b5315c9cae92557be6c32e1ee236201f https://github.com/openzfs/spl/commit/8fc851b7b5315c9cae9255... Jason had noticed that GCC’s assembly output did not match the original macro when looking for a solution to the unsigned integer overflow warning that a PaX GCC plugin had output (erroneously in my opinion). He had conjectured we could safely adopt GCC’s version as a workaround. I gave him the proof of correctness for the commit message and it was accepted into ZFS. As you can see from the proof, deriving that from the original required 4 steps. I assume that GCC had gone through a similar process to derive its output.
- AGivant 2y agoCode is written not just for computer to execute, but for other people to read and understand. If you put such code readability will suffer tremendously. Beside that, what are you doing in your code that you need to optimize leap year check?! This clever tricks it remind me phrase that lead to many accidents- 'Hold my beer and see what I can do!'