06Sep

Studying this week: A Faster Buddhabrot, and a little Scheme…

Posted by Elf Sternberg as Uncategorized

This week, I finished off the basic Programming Rust exercises by extending the Mandelbrot example in the book to produce Buddhabrots instead. In my last post, I mentioned that I’d gotten the Buddhabrot working, but only in a very basic way. I was unhappy with the result; my point-to-pixel mapper was giving me weirdly squashed results, and what I was producing didn’t look like many of the examples found in the wild. The O’Reilly Mandelbrot exercise extended the code to work on multi-core machines, so I tried to do that with the Buddhabrot.

The Mandelbrot set divides the complex plane into two sets: for a given complex point c and a zero-zero complex point z, those points in which the equation z = 

z * z + c iterated infinitely goes to infinity, and those for which z remains within a bounded region, usually the circle starting at the origin with a radius of 2+2ᵢ. For those starting points that go to infinity, the velocity at which it goes gives a grayscale number, from which we generate the mandelbrot set.

The Buddhabrot says, “Wait a minute, for all those points that don’t go to infinity, what if we colored those instead?” For those, for each iteration, we track the points it makes within the black center of the Mandelbrot set, and the number of times a point corresponds to a pixel gives us a number we can then render as a greyscale.

So: the problem here is easy. For Mandelbrot set, each point is not dependent on any other points on the screen. For the Buddhabrot, this isn’t true: most points are dependent upon the behavior of some previous point. The Mandelbrot set could be divided up into different regions and each region handed to a different core. For the Buddhabrot, we have to build up each map in total.

Even on my monitor, which is 3840×2160, using 16-bit greyscale and 8 threads, that was still under a gigabyte of memory. Yay for modern computers!


One of the biggest problems I had learning this was the notation for Rust mutation. And this is before we get to things like reference counters, boxes, and reference cells!

Here’s what I need to remember:

let x = 5; // defines a location, 'x', and puts 5 into it.
// x = 6; // illegal: x isn't mutable.

let mut x = 5; // legal: This shadows the value above.
x = 6; // redefines 'x' to be 6, which is legal because x is now
       // mutable.  The types must match!
{
    let y = &mut x; // 'y' is a mutable reference to 'x'. 'y' cannot be
                    // reassigned, but what it points to can be mutated:
    *y += 1;
}

That covers the basics, and helps a lot. The other thing is that the &mut syntax inside function signatures has a subtle meaning: that the function only takes mutabl

e references, and there can only be one of those at a time.


The rules about mutability in Rust just killed me. I wanted to run my Buddhabrot generator the way I would expect in any other object-oriented language: multiple planes on which to operate, each one running independently. I couldn’t get it to work with a vec of Plane objects, because Rust really didn’t want to move those massive planes around.

The only way to get it to work was to generate one gigantic vec, then use Vec::chunks_mut to break it up into subplanes, one for each thread, and hand them over to an immutable processor that did all the work of calculating the Buddhabrot for that plane. It worked, but what a pain in the neck.


The other thing I did this week was rip through the first 100 pages or so of The Little Schemer, a classic book teaching you how to use Scheme. I went through it using Racket, which was lovely, and taught me a lot about how Scheme works inside. I have two thoughts as I return to the Scheme land after wandering around in Rust: I really, really want better guarantees in my language that I won’t be passing around non-containers to functions that expect containers, and I really want better guarantees that the types I pass to functions are understood by those functions ahead of time.

Maybe I want Haskell. Or some kind of typed scheme. Or something. But this exercise was just… weird.

2 Responses to Studying this week: A Faster Buddhabrot, and a little Scheme…

Buddha Buck

September 6th, 2018 at 2:01 pm

I have the Little Schemer, as well as its sequel the Seasoned Schemer. The authors also have similar style books on Java (A Little Java, A Few Patterns) and ML (The Little MLer). I’d love to read their “The Little Haskeller”, but it doesn’t exist.

You might want to try ML. It is functional, like Scheme, but strongly typed (using Hindley Milner type inference), and thus provides better guarantees in the language that you won’t be passing around non-containers to functions that expect containers, and better guarantees that the types passed to functions are understood by those functions ahead of time.

Mark Jason Dominus has a talk where he demonstrates the ability of ML to catch a semantic error at compile time because the ML compiler was unable to reconcile the types asked of it.

I don’t know if ML would make the Buddhabrot (which puts in mind a German sausage made of…me. Ulp!) problem easier. But it might resolve the typing issues with Scheme.

Elf Sternberg

September 13th, 2018 at 11:37 am

Oh, I’ve read Dominus’s talk before! I remember reading it a long time ago. Yeah, it inspired me to take up a lot of things. Sadly, I haven’t been able to use that knowledge for a long time due to professional pressures.

Comment Form

Subscribe to Feed

Categories

Calendar

September 2018
M T W T F S S
« Aug   Oct »
 12
3456789
10111213141516
17181920212223
24252627282930