https://hueffner.de/falk/blog/a-leap-year-check-in-three-instructions.html
bool is_leap_year_fast(uint32_t y) {
return ((y * 1073750999) & 3221352463) <= 126976;
}
проверка за високосна година с 3 инструкции
То там и класическия алгоритъм няма да е бърз като няма инструкции за умножение и деление/остатък.
А умножение с константа може да се напише доста ефективно с бит шифт, та без проба трудно може да се прецени колко ще е бърз този алгоритъм на 8 битов процесор. Но на 32 битов процесор с хардуерно умножение е друга бира.
А за какво ти е да знаеш високосна година на 8051 ... ?
По принцип е забавно, но е типичен пример за безмислена оптимизация. Такъв код трябва да е четим, а не бърз.
Е, то без обясненията в линка кода изглежда като магия. Пък и автора си признава, че е правил brute force за да намери подходящи константи. Нещо подобно на обратния квадрат в quake.
Малко е тъпо да мериш без да гледаш какъв асемблерски код е генериран, но много подозирам, че причината първите имплементации са толкова бавни е, че има три return-а вместо един.
Това е кода, който генерира clang O3 на Мака от функцията is_leap_year1:
mov w8, #1 ; =0x1
mov w9, #23593 ; =0x5c29
movk w9, #49807, lsl #16
mul w9, w0, w9
mov w10, #28835 ; =0x70a3
movk w10, #2621, lsl #16
tst w0, #0xc
cset w11, eq
cmp w9, w10
csel w8, w8, w11, hi
tst w0, #0x3
csel w0, wzr, w8, ne
ret
Това е is_leap_year_fast:
mov w8, #9175 ; =0x23d7
movk w8, #16384, lsl #16
mul w8, w0, w8
mov w9, #61455 ; =0xf00f
movk w9, #49153, lsl #16
and w8, w8, w9
cmp w8, #31, lsl #12 ; =126976
cset w0, ls
ret
Изглеждат много подобни. Мързи ме да меря, но се съмнявам, че първия е по-бавен от втория, като се има предвид колко независими data paths има в първия и втория случай и че процесорите изпълняват доста от инструкциите едновременно.
Не знам за Интел, вече нямам машини с x86.
Та, извода е а) учете асемблер; б) не си губи времето с глупости, освен ако не е за забавление. :)
Бях забравил, че кланг сигурно може да компилира и за x86. Blah, the x86 code is NASTY и има 2 jump-a и два ret-a.
is_leap_year1()
# %bb.0:
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
xorl %eax, %eax
testb $3, %dil
je .LBB0_1
.LBB0_3:
popq %rbp
.cfi_def_cfa %rsp, 8
retq
.LBB0_1:
.cfi_def_cfa %rbp, 16
imull $-1030792151, %edi, %ecx # imm = 0xC28F5C29
movl $1, %eax
cmpl $171798691, %ecx # imm = 0xA3D70A3
ja .LBB0_3
# %bb.2:
xorl %eax, %eax
testb $12, %dil
sete %al
popq %rbp
.cfi_def_cfa %rsp, 8
retq
is_leap_year_fast()
# %bb.0:
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset %rbp, -16
movq %rsp, %rbp
.cfi_def_cfa_register %rbp
imull $1073750999, %edi, %ecx # imm = 0x400023D7
andl $-1073614833, %ecx # imm = 0xC001F00F
xorl %eax, %eax
cmpl $126977, %ecx # imm = 0x1F001
setb %al
popq %rbp
.cfi_def_cfa %rsp, 8
retq
Фокуса ми е в красотата на неортодоксалния алгоритъм. Подхода за намирането му и т.н.
Няма смисъл да ми обясняваш, че няма смисъл да се оптимизира нещо което се ползва от дъжд на вятър.
Търсих една тема дето беше писал, че нямало вече програмистки разговори и като не я намерих отворих тази.
Ай наздраве ти! Изнамерих в хладилника една изостанала черешова бира и го пия с отвращение тоя добре ферментирал компот. 8 градуса. Би се ядвало ако не го водят бира.
Би ли пуснал в продукция код, който не разбираш, урсулопитек малоумен?
Интересно е, но най-изненадващото е, че алгоритъма очевидно не е толкова неортодоксален. Компилатора генерира много подобен код.
А което е още по-интересно е, че това явно го прави backend-a, защото IR няма никакви странни константи:
define range(i32 0, 2) i32 @is_leap_year1(i32 noundef %0) local_unnamed_addr #0 {
%2 = and i32 %0, 3
%3 = icmp eq i32 %2, 0
br i1 %3, label %4, label %11
4: ; preds = %1
%5 = urem i32 %0, 25
%6 = icmp eq i32 %5, 0
br i1 %6, label %7, label %11
7: ; preds = %4
%8 = and i32 %0, 12
%9 = icmp eq i32 %8, 0
%10 = zext i1 %9 to i32
br label %11
11: ; preds = %7, %4, %1
%12 = phi i32 [ 0, %1 ], [ 1, %4 ], [ %10, %7 ]
ret i32 %12
}
Това което ти се струва аналогично май всъщност е %25 изчислен с умножение вместо с деление. А в три операционния алгоритъм заигравката със сметките е по дълбоко. Иначе спор няма, че компилаторите захитряват все повече и повече.
СМЪРТ ЗА АМЕРИКА КУР ЗА АМЕРИКА ЧУМА ЗА АМЕРИКА АТОМ ЗА АМЕРИКА
СМЪРТ ЗА ИЗРАЕЛ КУР ЗА ИЗРАЕЛ ЧУМА ЗА ИЗРАЕЛ АТОМ ЗА ИЗРАЕЛ
СМЪРТ ЗА АНГЛИЯ КУР ЗА АНГЛИЯ ЧУМА ЗА АНГЛИЯ АТОМ ЗА АНГЛИЯ
СМЪРТ ЗA ЕВРЕОГЕЙСКИЯ СЪЮЗ КУР ЗА ЕВРЕОГЕЙСКИЯ СЪЮЗ ЧУМА ЗА ЕВРЕОГЕЙСКИЯ СЪЮЗ АТОМ ЗА ЕВРЕОГЕЙСКИЯ СЪЮЗ
СМЪРТ ЗА АМЕРИКАНСКИЯ БУМЕР КУР ЗА АМЕРИКАНСКИЯ БУМЕР ЧУМА ЗА АМЕРИКАНСКИЯ БУМЕР АТОМ ЗА АМЕРИКАНСКИЯ БУМЕР
СМЪРТ ЗА ЖИДОВЕТЕ КУР ЗА ЖИДОВЕТЕ ЧУМА ЗА ЖИДОВЕТЕ АТОМ ЗА ЖИДОВЕТЕ
СМЪРТ ЗА НАГЛО-САКСОНЦИТЕ КУР ЗА НАГЛО-САКСОНЦИТЕ ЧУМА ЗА НАГЛО-САКСОНЦИТЕ АТОМ ЗА НАГЛО-САКСОНЦИТЕ
Да не отварям нова тема:
Размисли относно паралелизиране при изчисляване на 256 битови числа на 64 битова архитектура.
в университета учихме техика за паралелен пренос, тя си се ползва в процесорите инзаче забрави за 32 битов суматор на 3 гигахерца
Интересна идея и е добро четиво за хора, на които не им е ясно как се изпълняват инструкциите в процесора.
Не знам доколко е практично в реален код обаче. Първо че увеличава броя използвани регистри, и второ предполага, че няма други аритметични операции, които да запълнят пайплаайна.
Да пусна и аз един линк…
Смятане на умножение на fp64 матрици с използване на int8 матрични операции: