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-მნიშვნელობიანი პერიოდი სცენის supersampling-ისთვის საკმარისია. კვადრატული ფესვისთვის Heron-ის მეთოდი გაყოფის გამო არ გამოდგა, Taylor-ის მწკრივი კი 0,305-ზე დაბლა ცუდად ჯდებოდა, ამიტომ ავტორმა სვეტად გაყოფა აირჩია.

23MB პროგრამა, წუთში ერთი პიქსელი

მზა პროგრამა 23MB-ია, ანუ უფრო დიდი, ვიდრე გამოსახულება, რომელსაც ხატავს (ის დაახლოებით 0,9MB-ია); ავტორის თქმით, ასე Brainfuck შეკუმშვის ცუდი ხერხია. სიჩქარე წუთში დაახლოებით 100 სხივის გამოთვლაა, ანუ ერთი პიქსელი წუთში, ამიტომ 400×225-იან სურათს მის ლეპტოპზე დაახლოებით 62,5 დღე სჭირდება. წერის დროს 90 000-დან 1229 პიქსელი იყო მიღებული და მათგან მხოლოდ 10 განსხვავდებოდა C-ის ეტალონისგან, უმეტესად ერთი ერთეულით.

Reddit-ის თემში კომენტარმა fork/join პრიმიტივებზე იკითხა, ავტორმა კი სამაგიეროდ JIT ინტერპრეტატორი გააუმჯობესა და მკვეთრი ზრდა მიიღო. ნამდვილი რენდერი, მისივე თქმით, Van Gogh-ის ნახატს მოგაგონებს, სავარაუდოდ სიზუსტის შეცდომების გამო.