4 ms·

This 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 !

This 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 1y ago
This impl is mentioned in TFA.. It's much slower and includes branches.
- hoten 1y ago
  I'd expect even without optimizations on, there wouldn't be branches in the output for that code.
  - kragen 1y ago
    There 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.
    - mmozeiko 1y ago
      If you change logic and/or to bitwise and/or then it'll be branchless.
      - kragen 1y ago
        True: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:39,endLineNumber:6,positionColumn:39,positionLineNumber:6,selectionStartColumn:39,selectionStartLineNumber:6,startColumn:39,startLineNumber:6),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+((y+%25+25+!!%3D+0)+%7C+!!(y+%26+15)))%3B%0A%7D%0A'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:52.61910152938722,l:'4',n:'0',o:'',s:0,t:'0'),(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:47.38089847061277,l:'4',m:100,n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... but I understood hoten to be saying that compilers would generally produce that version from the short-circuiting version, and they don't.
        hoten 1y ago
        Yeah I was wrong. Do we know why the compiler doesn't do it? Surely the output is the same and avoiding branches is clearly faster. Maybe short circuiting requires such an optimization not be made?
        kragen 1y ago
        There are cases where the optimization wouldn't be safe (like i < n && a[i] != k) but this is not one of them. Maybe the compiler is just dum. Or maybe avoiding branches is not clearly faster in cases like this? Have you measured this particular case?
kragen 1y ago
You commented out your entire function body and the closing }. Also, on 32-bit platforms, it doesn't stop working at 65535.
- captaincrunch 1y ago
  just a formatting issue on my side, there were \n.
  - archargelod 1y ago
    This website eats newlines, unless you double them (one of the annoying features of markdown). You can use codeblocks by putting 4 spaces before each line: int main() { // this should be properly formatted return 0; };
  - kragen 1y ago
    If you fix it, other people can test your code without having to fix the syntax themselves first.
windward 1y ago
>READABLE Great. It will be useful for the exhaustive tests of the faster version.

This 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 1y ago

This impl is mentioned in TFA.. It's much slower and includes branches.

hoten 1y ago
I'd expect even without optimizations on, there wouldn't be branches in the output for that code.
- kragen 1y ago
  There 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.
  - mmozeiko 1y ago
    If you change logic and/or to bitwise and/or then it'll be branchless.
    - kragen 1y ago
      True: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:39,endLineNumber:6,positionColumn:39,positionLineNumber:6,selectionStartColumn:39,selectionStartLineNumber:6,startColumn:39,startLineNumber:6),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+((y+%25+25+!!%3D+0)+%7C+!!(y+%26+15)))%3B%0A%7D%0A'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:52.61910152938722,l:'4',n:'0',o:'',s:0,t:'0'),(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:47.38089847061277,l:'4',m:100,n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... but I understood hoten to be saying that compilers would generally produce that version from the short-circuiting version, and they don't.
      - hoten 1y ago
        Yeah I was wrong. Do we know why the compiler doesn't do it? Surely the output is the same and avoiding branches is clearly faster. Maybe short circuiting requires such an optimization not be made?
        kragen 1y ago
        There are cases where the optimization wouldn't be safe (like i < n && a[i] != k) but this is not one of them. Maybe the compiler is just dum. Or maybe avoiding branches is not clearly faster in cases like this? Have you measured this particular case?

kragen 1y ago

You commented out your entire function body and the closing }. Also, on 32-bit platforms, it doesn't stop working at 65535.

captaincrunch 1y ago
just a formatting issue on my side, there were \n.
- archargelod 1y ago
  This website eats newlines, unless you double them (one of the annoying features of markdown). You can use codeblocks by putting 4 spaces before each line: int main() { // this should be properly formatted return 0; };
- kragen 1y ago
  If you fix it, other people can test your code without having to fix the syntax themselves first.

windward 1y ago

>READABLE Great. It will be useful for the exhaustive tests of the faster version.