Tom Ridge's blog

This is a short note to detail the issues that are raised by the filesystem operation of renaming a directory from its parent directory to some other directory. Background A filesystem typically allows a nested collection directories: the root directory contains subdirectories, which in turn contain subdirectories, and so on.  The on-disk state of the filesystem will typically lag the in-memory state. Indeed, more advanced filesystems may even permit the on-disk state to diverge from the in-memory state, so that the on-disk state may not represent any state that occurred in-memory. For example, we create a file "foo.txt" then a file "bar.txt". It is quite possible that a filesystem that then crashed might restart in a state where the file "bar.txt" exists, but "foo.txt" does not, even though this state was never seen in-memory. Implementation optimizations Implementations of filesystems would like to treat every file and every directory as indepe...

I wrote a "one file" implementation of my favourite profiling technique, "waypoints". The idea of waypoints is that you can mark points (waypoints!) in your code, and the profiling library will record, for each pair of waypoints, the count (how many times each pair of waypoints was traversed), and the total time (from which it can compute the average time). Here is some example code: Here there are 5 waypoints, w1... The instrumented code consists of a for-loop, wrapping some trivial branching code, with random sleeps at various points. By default, when the program terminates the profiling data is printed to stdout: This tells you (for example) that the w2 branch was taken 7 times, and the w3 branch was taken 3 times. The average time for the w2-w2' section was 3.7 * 10^9, compared with 117 * 10^6 for w3-w3'. Clearly it is worth trying to optimise the w2-w2' section first... The "time" here is measured using the time stamp counter , i.e., measu...

I wanted to document (part of) the model of file behaviour that I use. This model is important to understand for people writing reliable crash-safe systems. Simple scenario, no file length update We consider the case of a single file, whose existence at a given path has been made persistent (i.e., after a crash, the file will still be found at that path).  We restrict to the case where we write over existing data, without extending the file length (again, the file length is assumed to already be persistent).  The model of the file data is as follows: There is an array of bytes which represents the data which is definitely on disk. There is also a "partial" (some entries may be missing) array of bytes which have been written by the application (eg via a call to pwrite), but which have not yet made it to disk, and so are "pending". An example: the file contents are initially: abcdefghij (10 bytes), and we use pwrite to write hello (5 bytes) at offset 2. Then the pendi...

This piece of code  adds write buffering for append operations on a file, and read buffering to attempt to make repeated preads quicker. Ultimately the implementation supports (buffered) pread, pwrite and (buffered) append. I'm posting it here because I thought it nicely demonstrated separation of concerns: first we build a file which maintains its own length in memory (V2); then we add the write buffer (V3); then finally we add the read buffer (V4). Each implementation builds on the previous. But each level is reasonably self-contained and addresses the single feature at that level. Previously I tried to do this by implementing everything in a single level, but the code was considerably more complex and harder to follow. 

TL;DR: Writing documentation can be beneficial even for a lone programmer writing code that will never be read by anyone else; however, the benefits, when other programmers are involved, are cumulative and potentially huge in terms of time saved (of those programmers) when trying to grok the existing codebase.  It is well known that programmers in general hate to write documentation. There are lots of reasons for this. For example, in the heat of writing code, the programmer simply cannot envisage what it would be like for someone else to come along in a couple of years and try to understand the code from scratch... And anyway, what does the programmer owe to that future person? (The programmer will likely have moved on by that point...) etc. etc. So, poor documentation (or lack of documentation altogether) is a problem that stems from the programmer, and probably left unfixed by the managers of the programmer, right up the chain of responsibility. This post isn't an attempt to add...

[NOTE: this post was inspired by looking at the mirage/index code and trying to understand the properties that code provides in a crash scenario] In systems with reasonable claims to robustness in the event of system crash, the issue arises that we want to write to a file in an "atomic" way. Let's simplify by considering appending data to a file. Let's also assume that the filesystem performs blk-sized blk-aligned writes atomically (but multiple such writes may be reordered). Simplify further by assuming we only want to append a single block of data to a file at a position that is a multiple of the block size. What can go wrong?  The problem is that there are many moving parts, each of which can result in incorrectness. Here are some possibilities: We append a new block at the end of the file (at a position that is a multiple of the blk size). This should be atomic. Has the FS (filesystem) freelist correctly recorded that the block is now in use? Has the FS updated th...

At OCamlLabs/Tarides, I have been working on kv-hash ( https://github.com/tomjridge/kv-hash ), a replacement for irmin/index ( https://github.com/mirage/index ) The original index code implements a key-value store. New key-values are written first to a log, and then when the log is large it is merged into the main data store, and a new log is started. The performance is good initially, but deteriorates over time (essentially because the entire store needs to be written whenever the log is merged into the store).  kv-hash is an alternative, where the performance remains constant over time, and where the merge duration in particular is fast and constant. In our tests, this avoids various issues with off-the-shelf solutions such as LMDB, RocksDB, SQLite etc. LMDB is great, providing the active set of keys fits in memory; if it doesn't, the use of an mmap means that performance degrades quite significantly RocksDB has amazing write performance, but the relatively poor read performance ...

I wrote a thin wrapper round SQLite to implement a simple Key Value store interface. The github repository is  https://github.com/tomjridge/kv-lite The bindings use Lwt for concurrency.  Performance is reasonably good: a batch set of 100k operations completes in about 1.5s. This is not as quick as mini-btree, but SQLite is probably doing a bit more here, and the layers of wrapping probably add some overhead too.

The mini-btree library is here:  https://github.com/tomjridge/mini-btree Recently I made some changes. Now, mmap is used throughout, and there is no use of the Lwt monad. So, the interface is somewhat simpler, and the performance is slightly improved (although the performance was already fairly good, we can now achieve about 1M inserts per second).  This work was done while employed by OCamlLabs, so many thanks to them. This library may in the future form part of the irmin/irmin-pack/index library used by Tezos.

 In the last couple of days I wrote a minimal B-tree implementation (based on previous work, of course). The link is here:  https://github.com/tomjridge/mini-btree This B-tree is resistant to write reordering, that is, the block device can reorder writes, and crash, and the B-tree will still function correctly (although obviously some recent operations may not have flushed fully to disk unless you managed a sync before the crash).

Just a quick update to announce that from August 2021 I will take up a position as a "Principal Software Engineer" at OCamlLabs  https://ocamllabs.io/  (although I initially interviewed with the French counterpart, Tarides). I will be working, at least initially, on various libraries such as: cactus  https://github.com/mirage/cactus index  https://github.com/mirage/index irmin  https://github.com/mirage/irmin The irmin library provides a git-like database, and is used by clients such as Tezos  https://tezos.com/  for their cryptocurrency systems. I guess initially I will be trying to use my knowledge of B-trees to try to improve the performance of these libraries.  I am very much looking forward to this stage of my career, and very glad to put the mess that is the University of Leicester behind me.

Just a short note to record that there are various differences between e.g. dune install, and opam install. Indeed, with the current p0 repo, dune install seems to install the library (which can be seen by ocamlfind and dune installed-libraries commands), but not by opam (which doesn't list any p0_lib package). It is not quite clear to me what the semantics of "dune install" is, and why it differs from "opam install". I get that dune, opam and ocamlfind are all different tools, but it seems strange that "dune install" will install files into the opam switch, but won't install the actual opam package. Another one of life's mysteries I guess.

I am shortly leaving the University. As with many others, I am bound by a "gagging clause", so unable to report on what is happening here. I can, however, link to reports made by others. Recently, one of the academics in the School of Business resigned, citing a "toxic work environment". The student magazine has reported on this here:  https://leicesterstudent.com/2021/04/13/lecturer-resigns-over-toxic-work-environment-at-university-of-leicester/ Particularly telling is the University response (effectively, staff being bullied by the management are encouraged to "ring a counselling helpline"):

 I updated my minimal monadic/combinator parsing library to specialize to strings, and to remove ineffectual functors. The link is here: https://github.com/tomjridge/p0/blob/master/src/p0_2021.ml

My final teaching evaluation before leaving Leicester. The module was an introductory programming module, following  Think Like a Computer Scientist (online, free version) . The module culminated in the students implementing a simple TODO list web application. Not many students filled in the questionnaire of course. Still. Not too shabby... especially considering the module had to be delivered by a single person (me) with very little preparation, and wholly online.

 After reviewing my old code for an Earley parser, I thought I would try to write a new version following my preferences for OCaml coding in 2021. The result is here: https://github.com/tomjridge/tjr_simple_earley/blob/master/src/earley_2021q1.ml Compared to previous versions, the code is pleasingly easy to read (due to use of mutability everywhere). For example, the following are the types and implementations for sets and "map to set"s: Timings: time ./earley_main.exe earley_2021q1 :1x100 begin ------------------------------------------------- earley_2021q1; grammar=EEE; input_length=100 (bin/earley_main.ml) Tjr_simple_earley__Earley_2021q1: count is 15756 end --------------------------------------------------- real 0m0.110s user 0m0.090s sys 0m0.004s time ./earley_main.exe earley_2021q1 :1x200 begin ------------------------------------------------- earley_2021q1; grammar=EEE; input_length=200 (bin/earley_main.ml) Tjr_simple_earley__Earley_2021q1: count is 61506 end --...

 This is some test math: \( x+ y = z \). Seems to work fine.

Repository is here:  https://github.com/tomjridge/tjr_simple_earley This commentary refers to commit 0dc99ad ocamldoc is available OCaml source code in src/ Main file: tjr_simple_earley.ml  https://github.com/tomjridge/tjr_simple_earley/blob/master/src/tjr_simple_earley.ml Config and Misc are utility modules.  Earley_intf has the main interfaces. Earley_base is the first implementation. General comments about the code: In order to run fast, we want every representation (of terminal, nonterminal, symbol, list of symbols, etc) to be an integer. Thus, we try to keep everything independent of the exact representation. Unfortunately this code was written about 5 years ago and I think I could do a better job today. Earley_intf https://github.com/tomjridge/tjr_simple_earley/blob/master/src/earley_intf.ml Starts with a general input type. Introduces nonterminals nt and terminals tm (symbols). A (simple) grammar is a function from nt to a list of (a list of symbols). A variation ...