3 ms·

I'd expect even without optimizations on, there wouldn't be branches in the output for that code.

by hoten 1y ago

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?

I'd expect even without optimizations on, there wouldn't be branches in the output for that code.

by hoten 1y ago

I'd expect even without optimizations on, there wouldn't be branches in the output for that code.

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?