Performance debugging with R

The Boyer-Moore string search in prelude.ml had a performance bug.

The search token preprocessing was taking quadratic time.

After fixing that, I special-cased n=1..4 with a per-char search for n=1 and PCRE for n=2..4.

Now it is nice and fast.

Programming books that I've liked

Programming languages

Programming Language Pragmatics
An extensive survey of how different programming languages work, i.e. how compilers and interpreters work, how different language features are implemented, what sorts of different programming languages are there, and so on. I read the book over a couple of months, and it was actually quite interesting.

The C Programming Language a.k.a. K&R
I read this over the weekend a couple weeks back and it was a nice read. Very practice-oriented, going through the language and standard library by building up example programs (even if some examples are a bit "Oh and by the way, you should never do this.") And at 200 pages or so (+100 pages of appendices), it's not going to take forever to read either.

Real World Haskell
Everyone's favourite lazily evaluated purely functional language and how to use it to get things done. You should also check out the online version of the book (and the paragraph comments in particular, such a nice idea.) While it does start off very, very slowly and tends to use an annoying mix of code snippets interleaved with function introductions in ghci, it's still quite readable.

Haskell 98 Language and Libraries: The Revised Report
The language lawyer book for Haskell. Very dense, very technical, very code-filled, very lovely. Starts off with a grammar specifying the lexical structure of valid Haskell programs, and contains the source code for Haskell's standard library, so it might require some fortitude. Also available online. This alone makes it worth checking out.

For OCaml, do see the OCaml manual and Developing Applications With Objective Caml. For Coq, I've been reading the tutorial and reading some sources.

Programming Ruby: The Pragmatic Programmers' Guide
The Ruby book. Has a very K&R vibe to it with focused examples and a tour of the standard library. I think this was the book that got me re-started on programming ~five years ago. Before that I was drawing for a living and programming for fun. Now I'm drawing for fun, programming for fun and starving for a living. Ha ha, fate, that fickle mistress.

Algorithms and data structures

Introduction to Algorithms
This was the book on our data structures course. We went through hash tables, binary trees, red-black trees and graph search algorithms. Borrowed the book from the library and read it for the exam. Can't remember a thing apart from "Hey, this book is pretty nice."

Purely Functional Data Structures
The Cormen book above contains imperative algorithms. Using them in a functional language is going to be painful. Hence Okasaki ventured forth and wrote his PhD about data structures that are better compatible with functional programming, and this book is the result. The language of the examples is SML with a laziness extension, and there's an appendix with Haskell versions of the sources. There's also a PDF of the thesis available online.

Graphics programming

Computer Graphics: Principles and Practice in C
While the drawing API parts of the book are aged (there's a whole chapter dedicated to PHIGS for crying out loud), it has a very useful chapter on parametric curves and goes through the basic shading equations and transformation matrices. It also has algorithms for drawing lines and circles and whatnot. Perhaps most useful as a 2D graphics book.

Real-Time Rendering
A thorough treatment of the theory behind real-time (read: game) rendering engines. I leafed this through at the university library, so my memories are vague. The website of the book has a very helpful list of recommended books.

GPU Gems 1, GPU Gems 2 and GPU Gems 3. Chock full of cool stuff from rendering to physics to GPGPU. And available online on the book websites (1, 2, 3.)

Physically Based Rendering - From Theory To Implementation
Focused on ray tracing, with chapters consisting of theory followed by C++. Should try to find this somewhere and Build My Very First Ray Tracer.

Fiction

Not really books about programming, but books with programming. I enjoyed them nevertheless.

The Wiz Biz
Wiz Zumwalt gets whisked away to a world where anyone can cast spells (though a good several years of training is recommended lest the wannabe mage fizzle themselves in the process) and where magic can be cast by written words. Small leap from there to writing a Forth running on the very fabric of reality. Also available online.

The Dance of Gods
A series of four books, wacky fantasy with a cast of trickster characters, multiple-viewpoint narrative and chain reaction plots. And it's CC licensed to boot.

And now that I've given you enough rope to hang your productivity for a week or two, I have some unit tests to write. 'til next time!

Revised quickcheck.ml syntax

Changed the quickcheck.ml syntax a bit to make it easier to pretty-print lists, arrays and tuples. Now you can use e.g. Q.int instead of Q.uig as a parameter to the list generator (though you need parens now.) Yesterday's example looks like this with the new syntax:

let reverse l = 
  let rec aux res l = match l with 
    | [] -> res
    | (h::t) -> aux (h::res) t in
  aux [] l
(**Q
  (Q.list_of_size (fun () -> Random.int 2) Q.int) (fun l -> reverse l = l)
  (Q.list Q.int) (fun l -> reverse (reverse l) = l)

  (* Thanks to notfancy on reddit for the following law. *)
  (* Demonstrating tuple generation *)
  (Q.pair (Q.list Q.int) (Q.list Q.int)) (fun (l,m) -> reverse (l @ m) = reverse m @ reverse l)
**)

Saving that to reverse.ml and running the test extractor on it prints out:

open OUnit
module Q = Quickcheck
open Reverse

let _iteri f l = ignore (List.fold_left (fun i v -> f v i; i + 1) 0 l)
let _TL = _iteri (fun (n,b) i ->
  OUnit.assert_bool ("Line " ^ string_of_int (i+1) ^ " of bool test: " ^ n) b)

let test_reverse_line_6 () = 
Quickcheck.laws_exn 
  "(Q.list_of_size (fun () -> Random.int 2) Q.int) (fun l -> reverse l = l)" 
  (Q.list_of_size (fun () -> Random.int 2) Q.int) (fun l -> reverse l = l);
      Quickcheck.laws_exn 
        "(Q.list Q.int) (fun l -> reverse (reverse l) = l)" 
        (Q.list Q.int) (fun l -> reverse (reverse l) = l);
      
      (* Thanks to notfancy on reddit for the following law. *)
      (* Demonstrating tuple generation *)
      Quickcheck.laws_exn 
        "(Q.pair (Q.list Q.int) (Q.list Q.int)) (fun (l,m) -> reverse (l @ m) = reverse m @ reverse l)" 
        (Q.pair (Q.list Q.int) (Q.list Q.int)) (fun (l,m) -> reverse (l @ m) = reverse m @ reverse l);()


let suite = "Reverse unit tests" >:::
  [
    "test_reverse_line_6" >:: test_reverse_line_6
  ]

let () = Tests.register suite

Low-boilerplate testing in OCaml

Continuing my search for a low-boilerplate way to write reliable code, I integrated quickcheck.ml (QuickCheck clone adapted from Core, which is adapted from this) to Prelude.ml's test suite extractor. The test suite extractor parses the source code for tests embedded in special comments and creates an oUnit test suite from them. This way I can have the tests near the code (where I think they should be), and only compile and run them when I want to (i.e. I do `omake -P test` and it extracts and reruns the tests whenever it detects changes in the source files.)

A further bonus of generating the tests is that I don't have to come up with names for them. The extractor automatically names the tests at extraction time (as test_filename_line_nnn.) This makes it a lot nicer to write tests, as you don't need to shift your focus from "what should the test do" to "what should the name be for what the test should do." The existence of the file name and line number in the auto-generated name also assures me that I _will_ find the failing test and _fast_.

Previously I had embedded unit test bodies (which I haven't used much) and lists of boolean tests (which most of my tests are.) Now I added embedded QuickCheck laws, and can perhaps eliminate a dozen manually written tests with a single property check.

let reverse l = 
  let rec aux res l = match l with 
    | [] -> res
    | (h::t) -> aux (h::res) t in
  aux [] l
(***
  (* embedded test body *)
  assert_equal (reverse []) [];
  assert_equal (reverse [1]) [1];
  assert_equal (reverse (1--10)) (10--1)
**)
(**T
  (* embedded boolean test list *)
  reverse [] = []
  reverse [1] = [1]
  reverse (1--10) = (10--1)
**)
(**Q
  (* embedded QuickCheck law list *)
  Q.list ~size_gen:(fun _ -> Random.int 2) Q.uig (fun l -> reverse l = l)
  Q.list Q.uig (fun l -> reverse (reverse l) = l)
  Q.list Q.uig (fun l -> reverse l = list (areverse (array l)))
  Q.list Q.cg (fun l -> reverse l = explode (sreverse (implode l)))
**)

As you may notice, the QuickCheck laws are generally longer to write than the tests themselves. But you shouldn't need as many laws as tests.

I haven't yet used the embedded QuickCheck tests for anything, so I can't give any real-world statistics. Maybe by the end of the week? Though the code that I'm currently testing is IO, and that tends to require whole embedded test bodies (as you need setup for temp file creation and deletion and state change checks.) Hm, maybe there's a nice way to abstract all that fiddling into an unfold of some kind...

Future directions

The FsCheck port of QuickCheck contains a shrinking feature for finding a reduction of the failed test input. Which would be nice.

My goal for the testing system is minimizing the amount of extraneous stuff I have to write to get the information I want from the code. To explain:

Tests give me information about the code. Specifically: does this function behave as expected when called with this argument.

I can only write a limited amount of lines of code per day (physically I can sustain ~300 loc / day, 1000 will get me RSI by the end of the day.) The more boilerplate I have to write, the less real code I can write.

A code:tests ratio of 1:4 means that I can write 60 lines of code per day. The rest of the budget is taken by the 240 lines of tests.

There are several ways to get at the testing information. Finding a way that expends less effort on my part will boost my productivity (and my hands will be thankful as well.)

Furthermore, I make mistakes when writing code. I also make mistakes when writing tests, missing tests that might discover mistakes in the code. The testing system should seek to find the coding mistakes and hence also minimize the amount of testing mistakes (QuickCheck and such automated test generators help there.)

The more tests the computer writes, the more and better quality code I can write.

QuickCheck in make_suite.rb

Adapted quickcheck.ml from Jane Street Capital's Core to use for Prelude.ml testing. Will write a longer post tomorrow (need to be wide awake in 7 hours), but now I can do this:

let shell_escape =
  let re = Pcre.regexp "(?=[^a-zA-Z0-9._+/-])" in
  Pcre.replace ~rex:re ~templ:"\\"
(**Q
  Q.uint (fun i -> shell_escape (string_of_int i) = (string_of_int i))
  Q.string (fun s -> slen (shell_escape s) = slen s)
**)

And get error messages like:

law Q.string (fun s -> slen (shell_escape s) = slen s) failed for 
             "\018\235\220\202U\222\146\200\002\249\232\170\015\238\147\238\004 
             \209\003\241\182\245\150\t\016P\190"

I also tweaked the bool test error messages, now they include the assertion body:

FAIL: Unit tests:0:Prelude unit tests:671:test_prelude_line_8631

OUnit: Line 5 of bool test: shell_escape "foo is fan/cy+some!" = "foo\\ is\\ fan/cy+some!"

Oh and hey, there's an F# port of QuickCheck too.

PreString tests done

Arrrr! Ahead of schedule!

Olliej told me that HTML5 now has text operations for the canvas, and henceforth I may go and make cake.js use the aforementioned. He also said that the WebKit nightly does a 640x480 ImageData fill and draw at 46fps. Which is very nice. Earlier this week, made cake.js skip malformed SVG paths instead of raising an error. And fixed a gradient bug just now.

PreArray testing stats

As I finished the first pass at PreArray unit tests yesterday, I thought to take a quick look at the testing statistics for the PreArray module. Before the test writing pass, PreArray contained 299 non-blank lines (of which 252 source, the rest tests and section headers.) With the tests, the line count rose to 1357 (of which 290 source), giving around 1020 new test lines, for a code:tests ratio of 1:3.7.

I quickly counted the number of bugfixes with gitk, and found 16 bugs fixed. So, one bug found (and fixed) for every 64 lines of tests. And one bug per every 18 lines of code for 55 bugs/ksloc for PreArray.

Compared to the previous numbers of bug per 50 test lines and 24 bugs/ksloc, PreArray has more tests per line of code, less bugs found per test, and a more than doubled bug rate per line of code (24 bugs/ksloc vs 55 bugs/ksloc.) What are the main differences between PreArray and the previously tested part? The main thing increasing bug rate might be that PreArray does [unsafe] indexed access to arrays, making sub/slice indexing harder than with lists, as the indexes need to be clamped to the array's dimensions.

Lists were perhaps less buggy because they have nicer provability (the x::xs -pattern matching, and a naturally recursive coding style.) Whereas arrays tend towards random access, which is harder to reason about.

And quite a few of the list functions and the preceding stuff was copied from prelude.hs, which would lower bug rate :)