Brainfuck-ով գրված ray tracer. 23MB ծրագիր, րոպեում մեկ պիքսել

epestr.com բլոգի հեղինակը CMake-ի ձեռնարկի մեկ տողը մարտահրավեր ընդունեց. ray tracer-ներ գրել են նույնիսկ CMake Language-ով, թեև դա խորհուրդ տրվող մոտեցում չէ։ Նա նախկինում ray tracer էր գրել և վերաշարադրել GPU-ի համար, ուստի ընտրեց Brainfuck-ը՝ իր իմացած ամենապարզ լեզուն, և նպատակ դրեց վերարտադրել Ray Tracing in One Weekend ձեռնարկի Metal բաժնի պատկերը։ Կոդը հրապարակվել է GitHub-ում՝ mTvare6/rayfuck անունով։

Ութ հրահանգ և մեկ ժապավեն

Brainfuck-ն ունի ութ գործողություն և մեկ տվյալների կառուցվածք՝ անվերջ ժապավեն բջիջներից, որտեղ ամեն բջիջ պահում է մեկ աննշան բայթ։ Մեկ բջիջից լայն ռեգիստր չկա, ոչ մի հրահանգ միաժամանակ երկու բջիջի չի դիպչում, իսկ գումարումն ու բազմապատկումը հրահանգներ չեն։ Այդ պատճառով իրական թվերը ձեռքով կոդավորվեցին. ամեն արժեք զբաղեցնում է չորս բջիջ նշանավոր Q16.16 ֆիքսված կետի ձևաչափով՝ 16 բիթ ամբողջ մասի և 16 բիթ կոտորակի համար, այսինքն 1/2^16 լուծաչափ և մոտավորապես [-2^15, 2^15) միջակայք։ Ավելի էժան Q8.8-ը չափազանց նեղ գտնվեց, քանի որ հողի դերում եղած ոլորտի շառավիղը պետք է 1000 լիներ, որ հարթ երևա։

Թվաբանությունը՝ զրոյից

23 մեգաբայթ Brainfuck ձեռքով չի գրվել. ծրագիրը փոխարկվում է SSA-ին նման ձևի, ապա վերլուծվում փոքր միջանկյալ DSL-ի՝ copy, mul, sqrt, if ու while գործողություններով։ Գլխավոր աշխատանքը կատարում են երկու պրիմիտիվ՝ move-ը ([->+<]), որ բջջի արժեքը տեղափոխում է հարևանին, և copy-ն ([->+>+<<])։ Բազմապատկումը չորս բջիջների վրա կրկնվող գումարում է, իսկ բաժանումը դպրոցական սյունակաձև բաժանման սկզբունքով է՝ 256 հիմքով. բաժանարարը մեկ բջջի համար հանվում է առավելագույնը 255 անգամ։

Մաթեմատիկական գրադարանը նույնպես կառուցվեց նույն բլոկներից։ Պատահական թվերը գալիս են փոքրիկ գեներատորից՝ A = (5*A + 1) % 256, որի 256 արժեքանոց ամբողջ պարբերաշրջանը բավական է տեսարանի գերնմուշառման համար։ Քառակուսի արմատի համար Հերոնի մեթոդը մերժվեց բաժանման պատճառով, իսկ Թեյլորի շարքը լավ չէր համապատասխանում 0,305-ից ցածր, ուստի օգտագործվեց երկար բաժանման վրա հիմնված արմատ։

Րոպեում մեկ պիքսել

Պատրաստ ծրագիրը 23MB է՝ ավելի մեծ, քան նրա ստեղծած պատկերը (մոտ 0,9MB), ուստի հեղինակը նշում է, որ Brainfuck-ը սեղմման վատ միջոց է։ Արագությունը րոպեում մոտ 100 ճառագայթի հաշվարկ է, այսինքն՝ մեկ պիքսել րոպեում, ուստի 400×225 պատկերը նրա դյուրակիր համակարգչում կտևեր մոտ 62,5 օր։ Գրելու պահին մոտ 90 000 պիքսելից ստացվել էր 1229-ը, և դրանցից միայն 10-ն էր տարբերվում C-ի հղումից, հիմնականում մեկ միավորով։

Reddit-ի թեմայում fork/join պրիմիտիվների մասին մեկնաբանությունից հետո հեղինակը փոխարենը բարելավեց JIT ինտերպրետատորը և հայտնեց զգալի արագացում. իրական ռենդերը, նրա խոսքով, հիմա մի քիչ նման է Վան Գոգի նկարի՝ հավանաբար ճշտության սխալների պատճառով։