Dave's Data

 A recent blog post asked " Does C++ still deserve its bad rap ?" While that title presumes the answer (after all, a "bad rap" implies that the judgement is undeserved), I think C++'s reputation for making it very difficult to achieve security or memory safety or thread-safety remains well-deserved, even though it's gotten a lot better over the years. I mean that: The c++-17 version of that program is years better than it would have been with c++0x, and it let a careful programmer write a nice program. The post used a simple multi-file word count as an example:  Count all words in all ".txt" files in the current directory and all of its subdirectories, where words were defined as things matching the regexp  "([a-z]{2,})" in a case-insensitive manner. First, I'll walk through the example from that blog post and identify some remaining bugs.  And then we'll build up a (IMO) better version in Rust that's faster, safer, and more c...

Having ported the Pi searcher to Rust , I've started exploring fuzzing frameworks to help find bugs.  I settled on Rust's cargo-fuzz  using the libfuzzer backend, since I'm familiar with libfuzzer from using it on TensorFlow . Naturally, since the Pi Searcher had been comparatively stable for 7 years in Go, and the translation from Go to Rust was fairly straightforward... I introduced a bug that my tests didn't find, and the fuzzer found over dinner: Whoopsie.  That bug arose because of an error in handling the boundary condition of searching for just "9" using the index (which doesn't happen normally because the search function uses a simple sequential search for short strings): Here, num_digits is 200 million, but they're stored compressed, so the bug was using the size of the file (100 million bytes), which caused the binary search to return a bad range.  Fuzzing is awesome, and adapting the fuzzer to the Pi searcher was straightforward: ...

Seven years ago (almost to the date), I wrote about my experience moving the Pi Searcher from C++ to Go .  In that article, I mentioned that while the core searching code got slower, the system as a whole sped up by avoiding the per-request fork overhead of the earlier CGI-based code. This year I moved the Pi Searcher to Rust, hoping to get the best of both worlds.  The tl;dr is that it worked and gave me and end-to-end throughput increase of at least 22%.  But not entirely in the place I'd expected!  The code is basically a transliteration of the Go to Rust, except for moving from Go's internal net/http server to actix-web for Rust.  The algorithm is the same:  sequential search for short search strings, and using a suffix array for longer strings. Results Code length isn't too different.  I was a little sloppy in writing the Rust version, so I don't think a comparison is entirely fair, but they're within 50% of each other and would probably be ...

xkcd 1137 Over the past year, I've spent some time working on improving the robustness of TensorFlow.  As I mentioned earlier, one of my goals for my time at Google was to dive into industry best-practices for writing good code .  At Google, writing good code starts with careful programmers, requires good tests that get run on a fantastic internal testing infrastructure , is improved through code review , and makes use of several code quality tools and linters. One part of that testing that's been gaining more visibility recently is fuzzing - throwing random inputs at programs or libraries to try to cause them to crash.   John Regehr has been fuzzing compilers for a while now - very effectively.  (That link has a nice taxonomy of the types of fuzzers.)  Google's Project Zero has been fuzzing the FreeType library for the last 4 years , and has found a tremendous number of security vulnerabilities  in all sorts of programs.   (This isn't to s...

Daniel Lemire  and Maxime Chevalier  just had a great exchange on Twitter  about the state of compilers and being able to automatically vectorize code, such as a scalar product.  Of course, hoping the compiler can correctly vectorize your code can be a bit fragile, and as Maxime points out, writing raw intrinsics results in an unreadable pain in the editor, and a GPU-style implementation in CUDA or OpenCL might be more scalable and maintainable. A few years ago, some folks at Intel wrote a compiler called ISPC, the Intel SPMD Program Compiler .  A possibly unfairly simple way to describe ISPC is that it's OpenCL-style programming for x86 vector units.  You can write code that looks like this: export uniform float scalar_product(uniform float a[],                                     uniform float b[],                ...

In discussions on Hacker News, I repeatedly see comments about " nobody ever implements sorting algorithms " -- or, generalized, that it's a waste of time studying up on basic data structures and algorithms, because they're all already implemented. While it's rare, it's not been my experience to never re-implement the basics.  I decided to data-mine my and my research group's past and current projects to identify the number of places we've implemented elementary data structures for good reasons. Sorting In the Cuckoo Filter, we implement a custom sort  to sort the four items that can go in a bucket.  Because this is a high-performance context, and the size of the set to be sorted is fixed and small, it's much faster to do this inline.  This sort only cares about the least-significant byte of the key.     inline void SortPair(uint32_t& a, uint32_t& b) {          if ((a & 0x0f) > (b & 0x0f)) {   ...

I'm spending the year in Google's Visiting Faculty program.  I had a few goals for my experience here: From xkcd 378 Learn learn learn !  I hoped to get a different perspective from the inside of the largest collection of computing & distributed systems that the world has ever seen, and to learn enough about machine learning to think better about providing systems support for it.  I haven't been disappointed. Do some real engineering .  I spend most of my time as a faculty member teaching & mentoring my Ph.D. students in research.  I love this - it's terribly fun and working with fantastic students is an incredibly rewarding experience.  But I also get a lot of creative satisfaction from coding, and I can only carve out a bit of my faculty time to dedicate to it.  I haven't written large amounts of production code since I was 21 - and the world has changed a lot since then.   Contribute something useful to Google while I was here....