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… :-)