Llogiq on stuff

My first unsafe code (and more)

Following a reddit discussion about possible reduction of space consumption for Option types, I decided to implement my own library as a learning experience.

I started out with an OptionBool enum with three possible values and tried to naïvely implement all of Options functions. When it came to the iter(&self) function, I dutyfully created an IterBool to copy the contents into which later gets used for iterating.

This appeared to work well enough. I even published it on crates.io as optional (though, as the README said at that time, mainly to embarrass myself).

Now I had my own first real library (that I thought should work on stable), I wanted to have it tested on that. So with help of some rustaceans I got it working and even uploading rustdocs to the project’s github pages (I could blog about how awesome both the tools and the community are, but you already know that, so I won’t). I’ll just add a small plug for Huon Wilson’s travis-cargo as it may be useful to some of you.

Well, the docs were pretty empty at that stage, but still. ACHIEVEMENT UNLOCKED!

I also wanted to implement numeric Option-like types that just wrapped the underlying value, turning one entity of the value domain into a marker for None. For unsigned integers, I used std::u*::MAX, for signed integers std::i*::MIN and for floats std::f*::NAN.

To avoid having to implement the whole Optioned struct for each of the types, I made it generic over the type T, which I bound with a Noned trait that allows to get the None value, as well as check if a value is None (this is needed because with floats, NAN != NAN). This works beautifully, and I don’t have too much code duplication.

I could use macros to even reduce that, but I’ll spare that for a future version. Still this is the first time I wrote a type to be generic – another ACHIEVEMENT UNLOCKED!

To reduce my embarrassment somewhat, I then decided that I wanted some tests and docs. So I learned how to do it (you can see my results in lib.rs if you’re interested) and added a few tests and doctests.

Now being space-efficient is all nice and dandy, but being the performance-minded person I am I wanted to know how well my class would fare against the probably highly optimized Option-class, which is after all a staple of Rust’s standard library. So I wrote a benchmark – and promptly crashed my build, because stable did not allow the requisite test::Bencher and test::black_box items, as they are unstable.

Note to self: Put benchmarks in the benches subdirectory of your project.

Now that I had actual performance numbers I saw to my great delight that my OptionBool struct was actually faster most of the time when compared to Option<bool> – well at least after I added #[inline] just about everywhere. Specialization for the win! One thing however stood out. My iterator took about double the time as Option’s – the compiler had tossed me the gauntlet.

At that time, my iter function consisted of:

fn iter(&self) { IterBool(value: *self) }

where IterBool was just a one-element struct wrapping a copy of my OptionBool. I had thought that using a copy should be faster than creating a reference, because it’s less memory. I had made that crude calculation without thinking that the method already had the reference value on the stack, and making the copy actually required one to follow the pointer.

At that time I also noticed that I had failed to supply the as_slice method (to my defence, it is still unstable at this point). Knowing that I could have arrays of booleans as const, I just created three const [bool]s and also three const &[bool]s pointing to them. Then the as_slice simply became a match over the three possible values returning one of the three const references.

Now my iter just became self.as_slice().iter(), which was faster than Option’s. Sorry if I start to bore you, but ACHIEVEMENT UNLOCKED! :-)

For the final (and titular) achievement, I wanted to also add as_slice to my Optioned type, but as it is generic, I cannot simply match over all possible values like with OptionBool. However, it is possible to create a slice from a raw pointer and length. Since I do know both – the pointer is always referencing my Optioned and the length is either 0 or 1, depending on Noned::is_none(&self), it is actually rather easy to do.

However, this requires use of the unsafe fn std::slice::from_raw_parts(ptr, len) method. The unsafety here is obvious, as we need to both uphold Rust’s guarantee that the returned slice won’t outlive our particular Optioned and our len isn’t greater than the number of elements we actually have. The former is taken care of by the function signature, which binds the lifetime of the returned slice to the Optioned’s lifetime, while the latter is quite trivial, since our length can never be greater than 1.

Still, that unsafe block looks rather awe-inspiring. I’m not sure I still can call myself a Rust Newbie at this point.

ACHIEVEMENT UNLOCKED! Sorry, I just had to :-)

Bonus: I just added a benchmark for the (still somewhat naïve and totally safe) Optioned::iter(), Optioned::as_slice().iter() and Option<u8>::iter(). To my surprise, the naïve version is faster than Option’s one, which in turn is faster than the slice-based.

I extended the benchmarks to 16-, 32- and 64bit types. It appears there is a large amount of jitter in the 8- and 16-bit ones, that may or may not be due to false sharing. The 32- and 64-bit ones are quite sane, though, and show very favorable performance.

On /r/rust, /u/nessie09 pointed out an error in my implementation of Eq for Optioned, which I promptly fixed.

I feel so accomplished… :-)