OCaml Planet

October 30, 2014

Functional Jobs

Senior Software Engineer at Soda Software Labs (Full-time)

Role: Senior Software Engineer Primary Location: Manchester, UK Employee Status: Permanent (Full Time) Salary: Competitive, with share options possible

Company Overview

Soda Software Labs are searching for a world class software engineer to help with the design and development of their flagship FinTech product PROFILE. At the heart of the product is a behavioural analysis platform which mines social data and performs analysis to provide insight for a number of industry verticals. The role offers the opportunity to join a small but fast growing company, to innovate in a number of industries and to get in at the ‘ground level’ within the fascinating space of BIG and social data.

The Role

We are looking for someone who not only has a proven track record of working with complex systems, but someone who has the passion, drive and motivation to continually develop our products to the highest standard.Typical duties of the role will involve:

Investigating current applications to improve their functionality Testing the product to ensure that it operates satisfactorily Confidently training and liaising with users Producing specifications and agreeing proposals Costing new or modified systems Writing new software and operating manuals

Knowledge and Skills

We are looking for an experienced senior-level software engineer, with experience across a range of programming languages of at least 2 or 3 different paradigms i.e. Java and C#/.NET being classified as a single language on the wider spectrum (as is C++).

The candidate needs to have functional programming knowledge of one or more of the following: Lisp/Scheme Erlang ML/OCaml Haskell Scala Python Ruby

A good understanding of social platform APIs such as Twitter API, Facebook API, LinkedIn API is also essential.

Additional Experience

3-4 years’ experience as a test/ software engineer Degree educated, preferably in a relevant subject such as computer science, software engineering, physics, mathematics or electronics Excellent critical thinking and analytical skills Ability to work to another’s design Commercial awareness Good communication skills

You'll be joining a well funded FinTech start up in the centre of Manchester with a work hard (but sometimes play hard too) culture. Moreover, it's the chance to get in at ground level with a business that has an extremely strong team and huge ambition. If this sounds like your kind of place, we'd love to hear from you.

Get information on how to apply for this position.

October 30, 2014 07:35 AM

OCamlCore Forge News

Calendar v2.04

A new version of calendar, aka calendar v2.04, is available.

by Julien Signoles at October 30, 2014 07:10 AM

October 27, 2014

Thomas Leonard

Visualising an asynchronous monad

Many asynchronous programs make use of promises (also known as using light-weight threads or an asynchronous monad) to manage concurrency. I’ve been working on tools to collect trace data from such programs and visualise the results, to help with profiling and debugging.

The diagram below shows a trace from a Mirage unikernel reading data from disk in a loop. You should be able to pan around by dragging in the diagram, and zoom by using your mouse’s scroll wheel. If you’re on a mobile device then pinch-to-zoom should work if you follow the full-screen link, although it will probably be slow. If nothing else works, the ugly zoom buttons at the bottom zoom around the last point clicked.

<canvas id="canvas-intro" style="width: 100%; height: 500px">

Mirage Trace Viewer screenshot
WARNING: No HTML canvas support (this is just a static image)! Try a newer browser…

</canvas>

View full screen

The web viewer requires JavaScript and HTML canvas support. If it doesn’t work, you can also build the trace viewer as a (much faster) native GTK application.

In this post I’ll explain how to read these diagrams, and how to trace your own programs.

( this post also appeared on Hacker News and Reddit )

Table of Contents

Introduction

Many asynchronous programs make use of promises (also known as using light-weight threads or an asynchronous monad). A promise/thread is a place-holder for a value that will arrive in the future.

Here’s a really simple example (an OCaml program using Lwt). It creates a thread that resolves to unit (void) after one second:

<notextile><figure class="code">
1
2
3
4
5
6
7
8
9
open Lwt
open Lwt_unix

let example_1 () =
  sleep 1.0

let () =
  (* Run the main loop until example_1 resolves. *)
  Lwt_unix.run (example_1 ());
</figure></notextile>
<canvas id="canvas-example_1" style="width: 100%; height: 106px"></canvas>

In the diagram, time runs from left to right. Threads (promises) are shown as horizontal lines. The diagram shows:

  • Initially, only the main thread (“0”) is present.
  • The main thread then creates a new thread, labelled “sleep”.
  • The sleep thread is a “task” thread (this is just a helpful label added when the thread is created).
  • The whole process then goes to sleep for one second, which is shown by the darker background.
  • At the end of the second, the process wakes up and resolves the sleep thread to its value (unit), shown by the green arrow.
  • The main thread, which was waiting for the sleep thread, reads the value (the blue arrow) and exits the program.

If you zoom in on the arrows (go down to a grid division of about 10 microseconds), you’ll also see a white segment on the main thread, which shows when it was running (only one thread runs at a time).

Because thread 0 is actually the main event loop (rather than a Lwt thread), things are a little more complicated than normal. When the process has nothing to do, thread 0 puts the process to sleep until the next scheduled timer. When the OS wakes the process, thread 0 resumes, determines that the “sleep” thread can be resolved, and does so. This causes any callbacks registered on the sleep thread to be called, but in this case there aren’t any and control returns to thread 0. Thread 0 then checks the sleep thread (because that determines when to finish), and ends the loop because it’s resolved.

Bind

Callbacks can be attached to a promise/thread to process the value when it arrives. Attaching the callback immediately creates a new promise for the final result of the callback.

Here’s a program that sleeps twice in series. The >>= (bind) operator attaches the callback function to the first thread. I’ve made the sleeps very short so you can see the process waking up without having to zoom.

<notextile><figure class="code">
1
2
3
let example_2 () =
  sleep 0.00001 >>= fun () ->
  sleep 0.00001
</figure></notextile>
<canvas id="canvas-example_2" style="width: 100%; height: 136px"></canvas>

In this case, the main thread creates two new threads at the start: one for the result of the first sleep and a second (“bind”) for the result of running the callback on the result. It’s easier to see how the first thread is resolved here: the main thread handling the polling loop wakes up and resolves the sleep thread, which then causes the bind thread to resume.

You might wonder why the bind thread disappears when the second sleep starts. It hasn’t finished, but when the bind’s callback function returns the second sleep thread as its result, the bind thread is merged with the sleep thread. This is the asynchronous equivalent of a tail call optimisation, allowing us to create loops without needing an unbounded number of threads.

Actually, displaying binds in this way tends to clutter up the diagrams, so the viewer has a simplification rule that is enabled by default: if the first event on a bind thread is a read, the part of the bind up to that point isn’t drawn. Therefore, the default display for this program is:

<canvas id="canvas-example_2b" style="width: 100%; height: 106px"></canvas>

If you zoom in on the central green arrow, you can see the tiny remaining bind thread between the two sleeps.

Join

Lwt.join waits for a collection of threads to finish:

<notextile><figure class="code">
1
2
3
4
5
6
let example_3 () =
  join [
    sleep 0.003;
    sleep 0.001;
    sleep 0.002;
  ]
</figure></notextile>
<canvas id="canvas-example_3" style="width: 100%; height: 196px"></canvas>

In the trace, you can see the join thread being notified each time one of the threads it’s waiting for completes. When they’re all done, it resolves itself.

Choose

Lwt.choose is similar to join, but only waits until one of its threads finishes:

<notextile><figure class="code">
1
2
3
4
5
6
let example_4 () =
  choose [
    sleep 0.003;
    sleep 0.00001;
    sleep 0.002;
  ]
</figure></notextile>
<canvas id="canvas-example_4" style="width: 100%; height: 196px"></canvas>

I cheated a bit here. To avoid clutter, the viewer only draws each thread until its last recorded event (without this, threads that get garbage collected span the whole width of the trace), so I used Profile.label ~thread "(continues)" to create extra label events on the two remaining threads to make it clearer what’s happening here.

Pick

Lwt.pick is similar to choose, but additionally cancels the other threads:

<notextile><figure class="code">
1
2
3
4
5
6
let example_5 () =
  pick [
    sleep 0.003;
    sleep 0.00001;
    sleep 0.001;
  ]
</figure></notextile>
<canvas id="canvas-example_5" style="width: 100%; height: 196px"></canvas>

Exceptions

Failed threads are shown with a red bar at the end and the exception message is displayed. Also, any “reads” arrow coming from it is shown in red rather than blue. Here, the bind thread fails but the try one doesn’t because it catches the exception and returns unit.

<notextile><figure class="code">
1
2
3
4
5
6
let example_6 () =
  try_lwt
    sleep 0.0001 >>= fun () ->
    failwith "oops"
  with _ ->
    return ()
</figure></notextile>

Note: I’m using the Lwt syntax extension here for try_lwt, but you can use Lwt.try_bind if you prefer.

<canvas id="canvas-example_6" style="width: 100%; height: 106px"></canvas>

The same simplification done for “bind” threads also applies to “try” threads, so the try thread doesn’t appear at all until you zoom in on the red arrow.

Making your own traces

( If you’re not interested in making traces, skip to the examples )

To generate your own traces, start by pinning my version of Lwt, which adds tracing support:

$ opam pin add lwt https://github.com/talex5/lwt.git#tracing

Next, install the mirage-profile library, which is what records the events:

$ git clone https://github.com/talex5/mirage-profile.git
$ cd mirage-profile
$ make
$ make install

Finally, make your program depend on mirage-profile and use the library to dump out a log file at the end:

<notextile><figure class="code"><figcaption>example.ml </figcaption>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
open Lwt
open Lwt_unix

let example_1 () =
  sleep 1.0

let () =
  Profile.start ~size:10000;
  Lwt_unix.run (example_1 ());
  let events = Profile.events () in
  let ch = open_out "log.sexp" in
  events |> Array.iter (fun ev ->
    output_string ch (Profile.to_string ev ^ "\n")
  );
  close_out ch
</figure></notextile>

Events are logged to a ring buffer with size elements (so if you get more events than this, you will lose the earlier ones). Your program will then generate a log.sexp file that looks something like this:

<notextile><figure class="code"><figcaption>log.sexp </figcaption>
1
2
3
4
5
6
7
8
((time 1413802819.475449)(op(Switch 0)))
((time 1413802819.475451)(op(Creates 0 1 Task)))
((time 1413802819.475451)(op(Label 1 sleep)))
((time 1413802819.475455)(op(Switch -1)))
((time 1413802820.475969)(op(Switch 0)))
((time 1413802820.475973)(op(Resolves 0 1())))
((time 1413802820.475975)(op(Reads 0 1)))
((time 1413802820.476045)(op(Resolves 0 0())))
</figure></notextile>

Note: this format is likely to change. Using S-expressions was just an easy way to dump the data out without writing any code.

You can then view the trace using mirage-trace-viewer:

$ git clone https://github.com/talex5/mirage-trace-viewer.git
$ cd mirage-trace-viewer 
$ make
$ ./gtk_viewer.native .../log.sexp

There’s also an example of a JavaScript viewer, in the examples directory.

Instrumenting Mirage unikernels

As above, you’ll need my version of Lwt and the mirage-profile module. In addition, you’ll want modified versions of some of the Mirage libraries because they add helpful comments to the traces. In particular, the modified mirage-xen shows when the VM is sleeping, when the OCaml garbage collector is running and which threads correspond to which Xen event channels:

opam pin add mirage-xen https://github.com/talex5/mirage-platform.git#tracing
opam pin add mirage-block-xen https://github.com/talex5/mirage-block-xen.git#tracing
opam pin add tcpip https://github.com/talex5/mirage-tcpip.git#tracing
opam pin add shared-memory-ring https://github.com/talex5/shared-memory-ring#tracing
opam pin add mirage-console https://github.com/talex5/mirage-console#tracing
opam pin add cohttp https://github.com/talex5/ocaml-cohttp.git#tracing
opam pin add xen-gnt https://github.com/talex5/ocaml-gnt.git#tracing
opam pin add mirage-net-xen https://github.com/talex5/mirage-net-xen.git#tracing

My plan here is that if Lwt is compiled without tracing support then mirage-profile will just compile stubs that do nothing, and the OCaml compiler’s cross-module inlining will optimise them out. Then we can add profiling annotations to all libraries without creating performance problems when profiling isn’t used, meaning we won’t need all these pins in future.

Finally, add calls to the Profile library to start the trace and dump the results:

<notextile><figure class="code"><figcaption>unikernel.ml </figcaption>
1
2
3
4
5
6
7
8
9
10
module Main (C: V1_LWT.CONSOLE) = struct
  let () = Profile.start ~size:10000

  let start c =
    ...
    let events = Profile.events () in
    for_lwt i = 0 to Array.length events - 1 do
      C.log_s c (Profile.to_string events.(i))
    done >>= fun () ->
    OS.Time.sleep 1.0
</figure></notextile>

Here, I’m starting it from a top-level module initialiser so that it captures events that happen before start is called. This is useful if you want to include the setup tasks performed by main.ml. At the end, I’m dumping the trace to the console (which works as long as nothing else writes to the console while you’re dumping the results; watch out for the network code doing this!). The final sleep is to give the console reader enough time to read the whole trace before the VM exits.

Alternatively, if your unikernel exposes an HTTP service then you might like to provide a /trace resource that dumps out the current ring buffer (you could even return a JavaScript viewer for it).

Examples

A few months ago, I made my first unikernel - a REST service for queuing files as a Xen guest OS. Unlike a normal guest, which would include a Linux kernel, init system, libc, shell, Apache, etc, a Mirage unikernel is a single executable, and almost pure OCaml (apart from malloc, the garbage collector, etc). Unikernels can be very small and simple, and have a much smaller attack surface than traditional systems.

For my first attempt at optimising the unikernel, I used OCaml’s built-in profiling support. This recorded function calls and how much time was spent in each one. But I quickly discovered that CPU time was rarely the important factor - how the various asynchronous threads were scheduled was more important, and the tracing made it difficult to see this.

So, let’s see how the new tracing does on my previous problems…

Profiling the console

In the previous profiling post, I generated this graph using libreoffice:

As a reminder, Xen guests output to the console by writing the text to a shared memory page, increasing a counter to indicate this, and signalling dom0. The console logger in dom0 reads the data, increments another counter to confirm it got it, and signals back to the guest that that part of the buffer is free again.

To use the new tracing system, I added a Profile.note_increase "sent" len to the main loop, which increments a “sent” count on each iteration (i.e. each time we write a line to the console). The viewer adds a mark on the trace for each increment and overlays a graph (the red line) so you can see overall progress easily:

<canvas id="canvas-console" style="width: 100%; height: 300px"></canvas>

View full screen | Download console.sexp

As before, we can see that we send messages rapidly in bursts, followed by long periods without progress. Zooming in to the places where the red line is increasing, we can see the messages being written to the buffer without any delays. Looking at the edges of the sleeping regions, it’s clear that we’re simply waiting for Xen to notify us of space by signalling us on event channel 2.

Here’s the complete test code:

<notextile><figure class="code">
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
open Lwt

module Main (C: V1_LWT.CONSOLE) = struct
  let () = Profile.start ~size:10000

  let start c =
    let len = 6 in
    let msg = String.make (len - 1) 'X' in
    let iterations = 1800 in
    let bytes = len * iterations in
    let rec loop = function
      | 0 -> return ()
      | i ->
          Profile.note_increase "sent" len;
          C.log_s c msg >>= fun () -> loop (i - 1) in

    let t0 = Clock.time () in
    loop iterations >>= fun () ->
    let t1 = Clock.time () in
    let time = t1 -. t0 in
    C.log_s c (Printf.sprintf "Wrote %d bytes in %.3f seconds (%.2f KB/s)"
      bytes time
      (float_of_int bytes /. time /. 1024.)) >>= fun () ->
    let events = Profile.events () in
    for_lwt i = 0 to Array.length events - 1 do
      C.log_s c (Profile.to_string events.(i))
    done >>= fun () ->
    OS.Time.sleep 1.0
end
</figure></notextile>

UDP transmission

Last time, we saw packet transmission being interrupted by periods of sleeping, garbage collection, and some brief but mysterious pauses. I noted that the GC tended to run during Ring.ack_responses, suggesting that was getting called quite often, and with the new tracing we can see why.

This trace shows a unikernel booting (scroll left if you want to see that) and then sending 10 UDP packets. I’ve left the trace running a little longer so you can see the acks (this is very obvious when sending more than 10 packets, but I wanted to keep this trace small):

<canvas id="canvas-udp" style="width: 100%; height: 700px"></canvas>

View full screen | Download udp.sexp

Mirage creates two threads for each packet that we add to the ring buffer and they stick around until we get a notification back from dom0 that the packet has been read (actually, we create six threads for each packet, but the bind simplification hides four of them).

It looks like each packet is in two parts, as each one generates two acks, one much later than the other. I think the two parts are the UDP header and the payload, which each have their own IO page. Given the time needed to share and unshare pages, it would probably be more efficient to copy the payload into the same page as the header. Interestingly, dom0 seems to ack all the headers first, but holds on to the payload pages for longer.

With 20 threads for just ten packets, you can imagine that the trace gets rather crowded when sending thousands!

TCP transmission

As before, the TCP picture is rather complicated:

<canvas id="canvas-tcp" style="width: 100%; height: 700px"></canvas>

View full screen | Download tcp.sexp

The above shows a unikernel running on my ARM Cubietruck connecting to netcat on my laptop and sending 100 TCP packets over the stream. There are three counters here:

  • main-to-tcp (purple) is incremented by the main thread just before sending a block of data to the TCP stream (just enough to fill one TCP segment).
  • tcp-to-ip (red) shows when the TCP system sent a segment to the IP layer for transmission.
  • tcp-ackd-segs (orange) shows when the TCP system got confirmation of receipt from the remote host (note: a TCP ask is not the same as a dom0 ring ack, which just says the network driver has accepted the segment for transmission).

There is clearly scope to improve the viewer here, but a few things can be seen already. The general cycle is:

  • The unikernel is sleeping, waiting for TCP acks.
  • The remote end acks some packets (the orange line goes up).
  • The TCP layer transmits some of the buffered packets (red line goes up).
  • The TCP layer allows the main code to send more data (purple line goes up).
  • The transmitted pages are freed (the dense vertical green lines) once Xen acks them.

I did wonder whether we unshared the pages as soon as dom0 had read the segment, or only when the remote end sent the TCP ack. Having the graphs overlaid on the trace lets us answer this question - you can see that when the red line goes up (segments sent to dom0), the ring.write thread that is created then ends (and the page is unshared) in response to ring.poll ack_responses, before the TCP acks arrive.

TCP starts slowly, but as the window size gets bigger and more packets are transmitted at a time, the sleeping periods get shorter and then disappear as the process becomes CPU-bound.

There’s also a long garbage collection period near the end (shortly before we close the socket). This might be partly the fault of the tracing system, which currently allocates lots of small values, rather than writing to a preallocated buffer.

Disk access

For our final example, let’s revisit the block device profiling from last time. Back then, making a series of read requests, each for 32 pages of data, produced this chart:

With the new tracing, we can finally see what those mysterious wake-ups in the middle are:

<canvas id="canvas-disk-direct" style="width: 100%; height: 500px"></canvas>

View full screen | Download disk-direct.sexp

Each time the main test code’s read call returns, the orange trace (“read”) goes up. You can see that we make three blocking calls to dom0 for each request. I added another counter for the number of active grant refs (pages shared with dom0), shown as the red line (“gntref”). You can see that for each call we share a bunch of pages, wait, and then unshare them all again.

In each group of three, we share 11 pages for the first two requests, but only 10 for the third. This makes obvious what previously required a careful reading of the block code: requests for more than 11 pages have to be split up because that’s all you can fit in the request structure. Our request for 32 pages is split into requests for 11 + 11 + 10 pages, which are sent in series.

In fact, Xen also supports “indirect” requests, where the request structure references full pages of requests. I added support for this to mirage-block-xen, which improved the speed nicely. Here’s a trace with indirect requests enabled:

<canvas id="canvas-disk-indirect" style="width: 100%; height: 500px"></canvas>

View full screen | Download disk-indirect.sexp

If you zoom in where the red line starts to rise, you can see it has 32 steps, as we allocate all the pages in one go, followed by a final later increment for the indirect page.

Zooming out, you can see we paused for GC a little later. We got lucky here, with the GC occurring just after we sent the request and just before we started waiting for the reply, so it hardly slowed us down. If we’d been unlucky the GC might have run before we sent the request, leaving dom0 idle and wasting the time. Keeping multiple requests in flight would eliminate this risk.

Implementation notes

I originally wrote the viewer as a native GTK application in OCaml. The browser version was created by running the magical js_of_ocaml tool, which turned out to be incredibly easy. I just had to add support for the HTML canvas API alongside the code for GTK’s Cairo canvas, but they’re almost the same anyway. Now my embarrassing inability to learn JavaScript need not hold me back!

Finding a layout algorithm that produced sensible results was the hardest part. I’m quite pleased with the result. The basic algorithm is:

  • Generate an interval tree of the thread lifetimes.
  • Starting with the root thread, place each thread at the highest place on the screen where it doesn’t overlap any other threads, and no higher than its parent.
  • Visit the threads recursively, depth first, visiting the child threads created in reverse order.
  • If one thread merges with another, allow them to overlap.
  • Don’t show bind-type threads as children of their actual creator, but instead delay their start time to when they get activated and make them children of the thread that activates them, unless their parent merges with them.

For the vertical layout I originally used scrolling, but it was hard to navigate. It now transforms the vertical coordinates from the layout engine by passing them through the tanh function, allowing you to focus on a particular thread but still see all the others, just more bunched up. The main difficulty here is focusing on one of the top or bottom threads without wasting half the display area, which complicated the code a bit.

Summary

Understanding concurrent programs can be much easier with a good visualisation. By instrumenting Lwt, it was quite easy to collect useful information about what threads were doing. Libraries that use Lwt only needed to be modified in order to label the threads.

My particular interest in making these tools is to explore the behaviour of Mirage unikernels - tiny virtual machines written in OCaml that run without the overhead of traditional operating systems.

The traces produced provide much more information than the graphs I made previously. We can see now not just when the unikernel isn’t making progress, but why. We saw that the networking code spends a lot of time handling ack messages from dom0 saying that it has read the data we shared with it, and that the disk code was splitting requests into small chunks because it didn’t support indirect requests.

There is plenty of scope for improvement in the tools - some things I’d like include:

  • A way to group or hide threads if you want to focus on something else, as diagrams can become very cluttered with e.g. threads waiting for shared pages to be released.
  • The ability to stitch together traces from multiple machines so you can e.g. follow the progress of an IP packet after it leaves the VM.
  • A visual indication of when interrupts occur vs when Mirage gets around to servicing them.
  • More stats collection and reporting (e.g. average response time to handle a TCP request, etc).
  • A more compact log format and more efficient tracing.

But hopefully, these tools will already help people to learn more about how their unikernels behave. If you’re interested in tracing or unikernels, the Mirage mailing list is a good place to discuss things.

<script src="http://roscidus.com/blog/javascripts/visualising-lwt.js" type="text/javascript"></script> <script type="text/javascript"> function addSidebarToggler() { if(!$('body').hasClass('sidebar-footer')) { $('#content').append(''); $('.toggle-sidebar').bind('click', function(e) { e.preventDefault(); if ($('body').hasClass('collapse-sidebar')) { $('body').removeClass('collapse-sidebar'); } else { $('body').addClass('collapse-sidebar'); } resizeCanvasElements(); }); } } </script>

October 27, 2014 07:21 AM

October 25, 2014

Coq

Coq 8.4pl5 is out

Version 8.4pl5 of Coq fixes several bugs of version 8.4pl4 including the compatibility with OCaml 4.02. More information to be found in the CHANGES file.

by boutillier at October 25, 2014 08:08 AM

October 24, 2014

Jane Street

Interviewing At Jane Street

Welcome to our version of the seemingly obligatory post about technical interviews. This topic has been covered by a lot of people already, so I'm going to do my best to not repeat all of the copious advice already out there.

Like many companies, we are looking for extremely talented technical people, and we have a challenging interview process that we think does a good job of selecting people who will do well here.

That said, we know that we miss lots of good people too. Some of that is because of the awkwardness of the interview process itself: time is short, the questions are weirdly artificial, and, of course, people get nervous. It's made even worse by the fact that programming on a whiteboard, a web browser, or even just on a computer that isn't yours is a bit like playing classical guitar with mittens on. It can put even an accomplished person off their game.

Missing out on good people makes us sad.

That's what this post is for. We hope that by talking a bit about what we're looking for, the ways people do poorly, and how we think you might be able to prepare, that we'll reduce the mitten handicap - at least a bit.

What Are We Looking For?

From our perspective, the main thing we want to figure out when we interview someone is: are they someone we want to work with?

That seems obvious enough, but it's a point that can get lost in the puzzles and whiteboard coding of an interview. Really, we think of our interviews as little simulations of what it's like to work together with the candidate. And while at the time, it may seem to the candidate that the interview is all about solving the problem, it's really not. We're much more interested in learning about how you work than we are in whether you actually finish whatever problem we put in front of you.

It's not that technical skill is irrelevant --- far from it. But it's only part of the story. Just as important to us is whether we can have a productive and fun discussion with the candidate.

To that end, we try to avoid algorithm bingo and puzzles with clever "aha" solutions. We prefer more open-ended problems that have no single right answer, since they give us more freedom to work together, and to see how the candidates' thinking plays out.

That sounds nice enough, but it's a bit high-level and hand-wavy. So here's a more concrete list of suggestions that follow from our overall approach.

Be nice

The smartest, best person in the world won't get hired at Jane Street if they aren't courteous and pleasant to talk to most of the time. Almost nothing will end your interview faster than being rude, pushy, or obnoxious.

Remember, we are looking for someone to work with, not just someone who can win an argument.

Be clear

And by clear, we mean simple and to the point. Use words and examples that get the core idea across to the widest technical audience possible.

Avoid showy, highly technical or deeply obscure terms of art, especially if you don't fully understand them. In the best case we'll likely just ask exactly what you meant by "hylomorphism", which wastes precious time. In the worst case it will become clear that you should have said "metamorphism" instead, which is just embarrassing for everyone involved.

Know what you don't know

Naturally we like it when candidates are good at solving the problems we put in front of them. But just as important, perhaps more important, is their ability to think reasonably about their own level of understanding.

In other words, we really like people who can express appropriate levels of confidence: admitting ignorance when they're unsure, and speaking confidently when they have the basis to do so. At a basic level this means being willing to say, "I don't know" rather than guessing and hoping when we ask you about something you aren't familiar with.

Know your language

Code is a wonderful language for communicating complex ideas because it provides a clear, concise and unambiguous way of expressing them. But, like any foreign language, it takes a lot of time and practice to get really comfortable.

We need you to be comfortable with it, because we communicate ideas in code a lot.

Now, comfortable doesn't mean that you have to be the world's best coder, or that you need to have memorized your favorite algorithms book. It means that you should be able to read and write code in at least one language without constant access to reference materials for common things, such as:

  • Standard control structures (loops/if-then/etc.)
  • Function, module, class, type, etc. definitions
  • Common data types like arrays, lists, hash tables/maps/dictionaries
  • Exceptions and other error handling techniques

Also, pick coding tools you understand well. Don't pick a functional language to make us happy. We'd much prefer you use a language that you know well. Similarly, when picking which features of the language to use, pick the ones you understand best. We're not going to be impressed with your elegant use of Python decorators if you don't really understand the details of what they do.

In other words, pick a simple, clunky solution that you understand over a fancy, elegant one that you don't.

Remember CS 101

We've hired plenty of successful people who didn't have a traditional college background in CS, and we certainly don't require a masters or a PhD. That said, we need you to have a solid working knowledge of core computer science concepts, including:

  • Abstraction layers like functions, objects, and modules

  • Basic algorithms and data structures, including binary search, sorting, hashing, breadth/depth first search, hashtables, binary trees and heaps.

  • Techniques for estimating CPU and memory costs, including big-O notation.

So if you can't for the life of you recall what amortized analysis is, and you can't nimbly bang out the code for a depth-first search it's probably worth reviewing some of this material.

Think about real computers

Depending on your point of view it's either a sad or beautiful fact that the most elegant code can only run on top of the giant, complex, odd stack of parts and abstractions that is a real computer. Since we need programs to actually run, we need people who understand the inner workings of that behemoth.

Now, this doesn't mean that we quiz every candidate about deep kernel internals, or the differences between SDRAM vs SGRAM. But for some jobs in systems development we do expect a fair amount of detailed knowledge, and in general it's a big plus if in your thinking you can take into account things like cache effects, IO patterns, memory representations, and the capabilities of real CPUs.

What We Don't Look For

  • Perfection. Our questions are often designed to be open ended enough that even the best people we've seen couldn't answer them fully in the time alloted. We want to keep the conversation going to learn everything we can, and we don't expect that you'll answer everything 100% perfectly.

  • We don't ask developers mental math, or math olympiad questions despite what you might have read online. Dev interviews are about programming.

  • We don't ask developers logic puzzles about pirates, people who only tell the truth, or which door the tiger is behind. Dev interviews are about programming.

How do people do poorly?

The most common issue is, of course, that some candidates just don't have the background for the job they are applying for. The solution to that is to learn more, and practice more. But there are a few other less obvious reasons that interviews with otherwise technically good people can go awry.

They're careless

One of the most common pieces of negative feedback from our interviewers is that the candidate was careless. This usually doesn't mean that the candidate didn't make progress, or didn't have good insights. It means that the candidate didn't think carefully and systematically about how their program might go wrong.

We care that you make progress, but we are rarely concerned about finishing a problem. In fact, many of the problems are designed to go on for far longer than the average interview length. It's better to step back and check your work carefully before you claim that it is finished than to rush.

They talk more than they code

Some candidates do a good job of talking through the problem and explaining their thinking, but never quite get around to concretely answering the question. We want to hear your ideas, but we also want to see you produce concrete solutions, which almost always involves writing code. There are lots of things that we can't learn about a candidate without seeing their code and talking through the details.

Take some time at the beginning to think about the solution and to talk about your plans, but make sure you start writing code - even if it isn't the code you would write if you had more time.

They don't generalize

We try to keep our interviews interactive, and we'll often stop candidates to ask about something they have just done, or to point out something that we think might be confusing or incorrect. We understand that we've seen these problems over and over again, and that you are coming to them fresh, so you shouldn't worry just because we've found a problem with your solution.

What you should do is generalize the advice. If we point out that you missed a case, consider other cases you might have missed. If we remind you of an invariant you forgot, find a way to protect yourself from making the mistake in other places in your code.

They say one thing and do another

We love it when a plan comes together, but it's extra hard to watch when a good plan falls apart on execution. If you hear a question, and discuss a plan of attack with your interviewer, do what you claim you will do. Don't change the plan in the middle, or drop it entirely in favor of a better idea without some discussion. You have a very limited amount of time to describe your solution in code, and executing a decent plan well is better than producing a Frankenstein's monster of 3 different plans that doesn't quite come to life.

If you do get partway through and start to lose faith step back and talk about it. Explain exactly why you are concerned, and whether you think it might be fatally flawed at the core, or just not ideal. If there really is a fatal flaw and you've seen it, we'll help you get out of the jam, and we'll appreciate that you articulated it. If it's just not quite perfect we'll likely encourage you to continue.

So, what can you do to prepare?

This part is short and sweet. Build something - from scratch - in a language you like. Don't stop short. Build the whole thing.

Now, show it to the smartest people you know, get feedback, tear it down and build it again with what you've learned.

Repeat with a new problem.

We are looking for people to build real things with us, and practice really does make perfect.

by David Powers at October 24, 2014 05:54 PM

October 23, 2014

OCaml Platform

OPAM 1.2.0 Released

We are very proud to announce the availability of OPAM 1.2.0.

Upgrade from 1.1

Simply follow the usual instructions, using your preferred method (package from your distribution, binary, source, etc.) as documented on the homepage.

NOTE: There are small changes to the internal repository format (~/.opam). It will be transparently updated on first run, but in case you might want to go back and have anything precious there, you're advised to back it up.

Usability

Lot of work has been put into providing a cleaner interface, with helpful behaviour and messages in case of errors.

The documentation pages also have been largely rewritten for consistency and clarity.

New features

This is just the top of the list:

  • A extended and versatile opam pin command. See the Simplified packaging workflow
  • More expressive queries, see for example opam source
  • New metadata fields, including source repositories, bug-trackers, and finer control of package behaviour
  • An opam lint command to check the quality of packages

For more detail, see the announcement for the beta, the full changelog, and the bug-tracker.

Package format

The package format has been extended to the benefit of both packagers and users. The repository already accepts packages in the 1.2 format, and this won't affect 1.1 users as a rewrite is done on the server for compatibility with 1.1.

If you are hosting a repository, you may be interested in these administration scripts to quickly take advantage of the new features or retain compatibility.

by Louis Gesbert at October 23, 2014 12:00 AM

October 22, 2014

Sylvain Le Gall

Release of OASIS 0.4.5

On behalf of Jacques-Pascal Deplaix

I am happy to announce the release of OASIS v0.4.5.

Logo OASIS small

OASIS is a tool to help OCaml developers to integrate configure, build and install systems in their projects. It should help to create standard entry points in the source code build system, allowing external tools to analyse projects easily.

This tool is freely inspired by Cabal which is the same kind of tool for Haskell.

You can find the new release here and the changelog here. More information about OASIS in general on the OASIS website.

Here is a quick summary of the important changes:

  • Build and install annotation files.
  • Use builtin bin_annot and annot tags.
  • Tag .mly files on the same basis as .ml and .mli files (required by menhir).
  • Remove 'program' constraint from C-dependencies. Currently, when a library has C-sources and e.g. an executable depends on that library, then changing the C-sources and running '-build' does not yield a rebuild of the library. By adding these dependencies (rather removing the constraint), it seems to work fine.
  • Some bug fixes

Features:

  • no_automatic_syntax (alpha): Disable the automatic inclusion of -syntax camlp4o for packages that matches the internal heuristic (if a dependency ends with a .syntax or is a well known syntax).
  • compiled_setup_ml (alpha): Fix a bug using multiple arguments to the configure script.

This new version is a small release to catch up with all the fixes/pull requests present in the VCS that have not yet been published. This should made the life of my dear contributors easier -- thanks again for being patient.

I would like to thanks again the contributor for this release: Christopher Zimmermann, Jerome Vouillon, Tomohiro Matsuyama and Christoph Höger. Their help is greatly appreciated.

by gildor at October 22, 2014 09:42 PM