Liebe RaumZeitSaunierende,

am 1. März 2020 wollen wir zuSamen den “Kalevalan päivä” und somit den Tag der finnischen Kultur (28. Februar) bei einem Spätstück nachfeiern. Zieht euer Eläkeläiset-Fanshirt aus dem Schrank und kommt um 11.30 Uhr auf eurem Nokia 3310 ins RZL vibriert. Lasst euch dieses finntastische Ereignis nicht entgehen! Damit wir wissen, wie viel Munavoi wir anrühren müssen, bitten wir um Anmeldung per Mail bis zum 25. Februar 2020. Wir freuen uns über einen Beitrag von 8 Euro für unser Finnkasso-Unternehmen.

Hyvää ruokahalua!
Eure Muumirattie

When spawning a child program, for example in an integration test, it is often helpful to know when the child program is ready to receive requests.

Delaying

A brittle strategy is to just add a delay (say, time.Sleep(2 * time.Second)) and hope the child program finishes initialization in that time. This is brittle because it depends on timing, so when the computer running the test is slow for whichever reason, your test starts failing. Many CI/CD systems have less capacity (and/or are more heavily utilized) than developer machines, so timeouts frequently need to be adjusted.

Also, relying on timing is a race to the bottom: your delay needs to work on the slowest machine that runs your code. Ergo, tests waste valuable developer time on your high-end workstation, just so that they pass on some under-powered machine.

Polling

A slightly better strategy is polling, i.e. repeatedly checking whether the child program is ready. As an example, in the dnsmasq_exporter test, I need to poll to find out when dnsmasq(8) is ready.

This approach is better because it automatically works well on both high-end and under-powered machines, without wasting time on either.

Finding a good frequency with which to poll is a bit of an art, though: the more often you poll, the less time you waste, but also the more resources you spend on polling instead of letting your program initialize. The overhead may be barely noticeable, but when starting lots of programs (e.g. in a microservice architecture) or when individual polls are costly, the overhead can add up.

Readiness notifications

The most elegant approach is to use readiness notifications: you don’t waste any time or resources.

It only takes a few lines of code to integrate this approach into your application. The specifics might vary depending on your environment, e.g. whether an environment variable is preferable to a command-line flag; my goal with this article is to explain the approach in general, and you can take care of the details.

The key idea is: the child program inherits a pipe file descriptor from the parent and closes it once ready. The parent program knows the child program is ready because an otherwise blocking read from the pipe returns once the pipe is closed.

This is similar to using a chan struct{} in Go and closing it. It doesn’t have to remain this simple, though: you can also send arbitrary data over the pipe, ranging from a simple string being sent in one direction and culminating in speaking a framed protocol in a client/server fashion. In Debian Code Search, I’m writing the chosen network address before closing the pipe, so that the parent program knows where to connect to.

Parent Program

So, how do we go about readiness notifications in Go? We create a new pipe and specify the write end in the ExtraFiles field of (os/exec).Cmd:

r, w, err := os.Pipe()
if err != nil {
  return err
}

child := exec.Command("child")
child.Stderr = os.Stderr
child.ExtraFiles = []*os.File{w}

It is good practice to explicitly specify the file descriptor number that we passed via some sort of signaling, so that the child program does not need to be modified when we add new file descriptors in the parent, and also because this behavior is usually opt-in.

In this case, we’ll do that via an environment variable and start the child program:

// Go dup2()’s ExtraFiles to file descriptor 3 and counting.
// File descriptors 0, 1, 2 are stdin, stdout and stderr.
child.Env = append(os.Environ(), "CHILD_READY_FD=3")

// Note child.Start(), not child.Run():
if err := child.Start(); err != nil {
  return fmt.Errorf("%v: %v", child.Args, err)
}

At this point, both the parent and the child process have a file descriptor referencing the write end of the pipe. Since the pipe will only be closed once all processes have closed the write end, we need to close the write end in the parent program:

// Close the write end of the pipe in the parent:
w.Close()

Now, we can blockingly read from the pipe, and know that once the read call returns, the child program is ready to receive requests:

// Avoid hanging forever in case the child program never becomes ready;
// this is easier to diagnose than an unspecified CI/CD test timeout.
// This timeout should be much much longer than initialization takes.
r.SetReadDeadline(time.Now().Add(1 * time.Minute))
if _, err := ioutil.ReadAll(r); err != nil {
  return fmt.Errorf("awaiting readiness: %v", err)
}

// …send requests…

// …tear down child program…

Child Program

In the child program, we need to recognize that the parent program requests a readiness notification, and ensure our signaling doesn’t leak to child programs of the child program:

var readyFile *os.File

func init() {
  if fd, err := strconv.Atoi(os.Getenv("CHILD_READY_FD")); err == nil {
    readyFile = os.NewFile(uintptr(fd), "readyfd")
    os.Unsetenv("CHILD_READY_FD")
  }
}

func main() {
  // …initialize…

  if readyFile != nil {
    readyFile.Close() // signal readiness
    readyFile = nil   // just to be prudent
  }
}

Conclusion

Depending on what you’re communicating from the child to the parent, and how your system is architected, it might be a good idea to use systemd socket activation (socket activation in Go). It works similarly in concept, but passes a listening socket and readiness is determined by the child process answering requests. We introduced this technique in the i3 testsuite and reduced the total wallclock time from >100 seconds to a mere 16 seconds back then (even faster today).

The technique described in this blog post is a bit more generic than systemd’s socket activation. In general, passing file descriptors between processes is a powerful idea. For example, in debiman, we’re passing individual pipe file descriptors to a persistent mandocd(8) process to quickly convert lots of man pages without encurring process creation overhead.

Earlier this month the first annual meeting of the French working group NBODY (GDR NBODY) took place in Lille. Since the GDR NBODY is an association of interdisciplinary scientists working on N-body problems in chemistry an physics, the about 80 participants came from a broad background ranging from quantum chemistry, materials science, mathematics or nuclear physics. The overall atmosphere of the conference was extremely relaxed, such that during the talks vivid discussions frequently arose. I particularly enjoyed the presentations about N-body effects in nuclear physics and the first-principle simulations of the structure of nuclei, since that topic was completely new to me. Fortunately there was one introductory talk for each of the four mayor topics of the working group bringing everyone up to speed in each others' subject.

As part of the program I presented about DFTK and our recent advances with the code. I first gave a brief rationalisation why we started DFTK as a new code for working on electronic-structure problems from the mathematical perspective, then I briefly presented two applications, where we hope our code could be useful towards developing new approaches for practical calculations. One is an investigation of increased precision and more generally estimates for the floating-point error in density-functional theory calculations. The other was a discussion of our ongoing work on SCF preconditioning techniques. In this I showed our first steps towards developing a mathematically justified SCF preconditioner suitable for tackling systems containing both a conducting and an insulating part. Our first results indicate that our approach could be more suitable than established methods, which usually rely on interpolating empirically between the established preconditioning strategies for metals and insulators. Our hope would be that our preconditioner could allow to apply DFTK in the context of simulating the electronic structure of catalytic metal surfaces in the future. In this application a challenge for SCF schemes is that employed catalysts are usually coated with an insulating oxide layer or are interfacing with more insulating organic compounds or air.

Link	Licence
Using the density-functional toolkit (DFTK) to investigate floating-point error and SCF convergence (Slides)

In case you are not yet familiar with why an initramfs (or initrd, or initial ramdisk) is typically used when starting Linux, let me quote the wikipedia definition:

“[…] initrd is a scheme for loading a temporary root file system into memory, which may be used as part of the Linux startup process […] to make preparations before the real root file system can be mounted.”

Many Linux distributions do not compile all file system drivers into the kernel, but instead load them on-demand from an initramfs, which saves memory.

Another common scenario, in which an initramfs is required, is full-disk encryption: the disk must be unlocked from userspace, but since userspace is encrypted, an initramfs is used.

Motivation

Thus far, building a distri disk image was quite slow:

This is on an AMD Ryzen 3900X 12-core processor (2019):

distri % time make cryptimage serial=1
80.29s user 13.56s system 186% cpu 50.419 total # 19s image, 31s initrd

Of these 50 seconds, dracut’s initramfs generation accounts for 31 seconds (62%)!

Initramfs generation time drops to 8.7 seconds once dracut no longer needs to use the single-threaded gzip(1) , but the multi-threaded replacement pigz(1) :

This brings the total time to build a distri disk image down to:

distri % time make cryptimage serial=1
76.85s user 13.23s system 327% cpu 27.509 total # 19s image, 8.7s initrd

Clearly, when you use dracut on any modern computer, you should make pigz available. dracut should fail to compile unless one explicitly opts into the known-slower gzip. For more thoughts on optional dependencies, see “Optional dependencies don’t work”.

But why does it take 8.7 seconds still? Can we go faster?

The answer is Yes! I recently built a distri-specific initramfs I’m calling minitrd. I wrote both big parts from scratch:

1. the initramfs generator program (distri initrd)
2. a custom Go userland (cmd/minitrd), running as /init in the initramfs.

minitrd generates the initramfs image in ≈400ms, bringing the total time down to:

distri % time make cryptimage serial=1
50.09s user 8.80s system 314% cpu 18.739 total # 18s image, 400ms initrd

(The remaining time is spent in preparing the file system, then installing and configuring the distri system, i.e. preparing a disk image you can run on real hardware.)

How can minitrd be 20 times faster than dracut?

dracut is mainly written in shell, with a C helper program. It drives the generation process by spawning lots of external dependencies (e.g. ldd or the dracut-install helper program). I assume that the combination of using an interpreted language (shell) that spawns lots of processes and precludes a concurrent architecture is to blame for the poor performance.

minitrd is written in Go, with speed as a goal. It leverages concurrency and uses no external dependencies; everything happens within a single process (but with enough threads to saturate modern hardware).

Measuring early boot time using qemu, I measured the dracut-generated initramfs taking 588ms to display the full disk encryption passphrase prompt, whereas minitrd took only 195ms.

The rest of this article dives deeper into how minitrd works.

What does an initramfs do?

Ultimately, the job of an initramfs is to make the root file system available and continue booting the system from there. Depending on the system setup, this involves the following 5 steps:

1. Load kernel modules to access the block devices with the root file system

Depending on the system, the block devices with the root file system might already be present when the initramfs runs, or some kernel modules might need to be loaded first. On my Dell XPS 9360 laptop, the NVMe system disk is already present when the initramfs starts, whereas in qemu, we need to load the virtio_pci module, followed by the virtio_scsi module.

How will our userland program know which kernel modules to load? Linux kernel modules declare patterns for their supported hardware as an alias, e.g.:

initrd# grep virtio_pci lib/modules/5.4.6/modules.alias
alias pci:v00001AF4d*sv*sd*bc*sc*i* virtio_pci

Devices in sysfs have a modalias file whose content can be matched against these declarations to identify the module to load:

initrd# cat /sys/devices/pci0000:00/*/modalias
pci:v00001AF4d00001005sv00001AF4sd00000004bc00scFFi00
pci:v00001AF4d00001004sv00001AF4sd00000008bc01sc00i00
[…]

Hence, for the initial round of module loading, it is sufficient to locate all modalias files within sysfs and load the responsible modules.

Loading a kernel module can result in new devices appearing. When that happens, the kernel sends a uevent, which the uevent consumer in userspace receives via a netlink socket. Typically, this consumer is udev(7) , but in our case, it’s minitrd.

For each uevent messages that comes with a MODALIAS variable, minitrd will load the relevant kernel module(s).

When loading a kernel module, its dependencies need to be loaded first. Dependency information is stored in the modules.dep file in a Makefile-like syntax:

initrd# grep virtio_pci lib/modules/5.4.6/modules.dep
kernel/drivers/virtio/virtio_pci.ko: kernel/drivers/virtio/virtio_ring.ko kernel/drivers/virtio/virtio.ko

To load a module, we can open its file and then call the Linux-specific finit_module(2) system call. Some modules are expected to return an error code, e.g. ENODEV or ENOENT when some hardware device is not actually present.

Side note: next to the textual versions, there are also binary versions of the modules.alias and modules.dep files. Presumably, those can be queried more quickly, but for simplicitly, I have not (yet?) implemented support in minitrd.

2. Console settings: font, keyboard layout

Setting a legible font is necessary for hi-dpi displays. On my Dell XPS 9360 (3200 x 1800 QHD+ display), the following works well:

initrd# setfont latarcyrheb-sun32

Setting the user’s keyboard layout is necessary for entering the LUKS full-disk encryption passphrase in their preferred keyboard layout. I use the NEO layout:

initrd# loadkeys neo

3. Block device identification

In the Linux kernel, block device enumeration order is not necessarily the same on each boot. Even if it was deterministic, device order could still be changed when users modify their computer’s device topology (e.g. connect a new disk to a formerly unused port).

Hence, it is good style to refer to disks and their partitions with stable identifiers. This also applies to boot loader configuration, and so most distributions will set a kernel parameter such as root=UUID=1fa04de7-30a9-4183-93e9-1b0061567121.

Identifying the block device or partition with the specified UUID is the initramfs’s job.

Depending on what the device contains, the UUID comes from a different place. For example, ext4 file systems have a UUID field in their file system superblock, whereas LUKS volumes have a UUID in their LUKS header.

Canonically, probing a device to extract the UUID is done by libblkid from the util-linux package, but the logic can easily be re-implemented in other languages and changes rarely. minitrd comes with its own implementation to avoid cgo or running the blkid(8) program.

4. LUKS full-disk encryption unlocking (only on encrypted systems)

Unlocking a LUKS-encrypted volume is done in userspace. The kernel handles the crypto, but reading the metadata, obtaining the passphrase (or e.g. key material from a file) and setting up the device mapper table entries are done in user space.

initrd# modprobe algif_skcipher
initrd# cryptsetup luksOpen /dev/sda4 cryptroot1

After the user entered their passphrase, the root file system can be mounted:

initrd# mount /dev/dm-0 /mnt

5. Continuing the boot process (switch_root)

Now that everything is set up, we need to pass execution to the init program on the root file system with a careful sequence of chdir(2) , mount(2) , chroot(2) , chdir(2) and execve(2) system calls that is explained in this busybox switch_root comment.

initrd# mount -t devtmpfs dev /mnt/dev
initrd# exec switch_root -c /dev/console /mnt /init

To conserve RAM, the files in the temporary file system to which the initramfs archive is extracted are typically deleted.

How is an initramfs generated?

An initramfs “image” (more accurately: archive) is a compressed cpio archive. Typically, gzip compression is used, but the kernel supports a bunch of different algorithms and distributions such as Ubuntu are switching to lz4.

Generators typically prepare a temporary directory and feed it to the cpio(1) program. In minitrd, we read the files into memory and generate the cpio archive using the go-cpio package. We use the pgzip package for parallel gzip compression.

The following files need to go into the cpio archive:

minitrd Go userland

The minitrd binary is copied into the cpio archive as /init and will be run by the kernel after extracting the archive.

Like the rest of distri, minitrd is built statically without cgo, which means it can be copied as-is into the cpio archive.

Linux kernel modules

Aside from the modules.alias and modules.dep metadata files, the kernel modules themselves reside in e.g. /lib/modules/5.4.6/kernel and need to be copied into the cpio archive.

Copying all modules results in a ≈80 MiB archive, so it is common to only copy modules that are relevant to the initramfs’s features. This reduces archive size to ≈24 MiB.

The filtering relies on hard-coded patterns and module names. For example, disk encryption related modules are all kernel modules underneath kernel/crypto, plus kernel/drivers/md/dm-crypt.ko.

When generating a host-only initramfs (works on precisely the computer that generated it), some initramfs generators look at the currently loaded modules and just copy those.

Console Fonts and Keymaps

The kbd package’s setfont(8) and loadkeys(1) programs load console fonts and keymaps from /usr/share/consolefonts and /usr/share/keymaps, respectively.

Hence, these directories need to be copied into the cpio archive. Depending on whether the initramfs should be generic (work on many computers) or host-only (works on precisely the computer/settings that generated it), the entire directories are copied, or only the required font/keymap.

cryptsetup, setfont, loadkeys

These programs are (currently) required because minitrd does not implement their functionality.

As they are dynamically linked, not only the programs themselves need to be copied, but also the ELF dynamic linking loader (path stored in the .interp ELF section) and any ELF library dependencies.

For example, cryptsetup in distri declares the ELF interpreter /ro/glibc-amd64-2.27-3/out/lib/ld-linux-x86-64.so.2 and declares dependencies on shared libraries libcryptsetup.so.12, libblkid.so.1 and others. Luckily, in distri, packages contain a lib subdirectory containing symbolic links to the resolved shared library paths (hermetic packaging), so it is sufficient to mirror the lib directory into the cpio archive, recursing into shared library dependencies of shared libraries.

cryptsetup also requires the GCC runtime library libgcc_s.so.1 to be present at runtime, and will abort with an error message about not being able to call pthread_cancel(3) if it is unavailable.

time zone data

To print log messages in the correct time zone, we copy /etc/localtime from the host into the cpio archive.

minitrd outside of distri?

I currently have no desire to make minitrd available outside of distri. While the technical challenges (such as extending the generator to not rely on distri’s hermetic packages) are surmountable, I don’t want to support people’s initramfs remotely.

Also, I think that people’s efforts should in general be spent on rallying behind dracut and making it work faster, thereby benefiting all Linux distributions that use dracut (increasingly more). With minitrd, I have demonstrated that significant speed-ups are achievable.

Conclusion

It was interesting to dive into how an initramfs really works. I had been working with the concept for many years, from small tasks such as “debug why the encrypted root file system is not unlocked” to more complicated tasks such as “set up a root file system on DRBD for a high-availability setup”. But even with that sort of experience, I didn’t know all the details, until I was forced to implement every little thing.

As I suspected going into this exercise, dracut is much slower than it needs to be. Re-implementing its generation stage in a modern language instead of shell helps a lot.

Of course, my minitrd does a bit less than dracut, but not drastically so. The overall architecture is the same.

I hope my effort helps with two things:

1. As a teaching implementation: instead of wading through the various components that make up a modern initramfs (udev, systemd, various shell scripts, …), people can learn about how an initramfs works in a single place.

2. I hope the significant time difference motivates people to improve dracut.

Appendix: qemu development environment

Before writing any Go code, I did some manual prototyping. Learning how other people prototype is often immensely useful to me, so I’m sharing my notes here.

First, I copied all kernel modules and a statically built busybox binary:

% mkdir -p lib/modules/5.4.6
% cp -Lr /ro/lib/modules/5.4.6/* lib/modules/5.4.6/
% cp ~/busybox-1.22.0-amd64/busybox sh

To generate an initramfs from the current directory, I used:

% find . | cpio -o -H newc | pigz > /tmp/initrd

In distri’s Makefile, I append these flags to the QEMU invocation:

-kernel /tmp/kernel \
-initrd /tmp/initrd \
-append "root=/dev/mapper/cryptroot1 rdinit=/sh ro console=ttyS0,115200 rd.luks=1 rd.luks.uuid=63051f8a-54b9-4996-b94f-3cf105af2900 rd.luks.name=63051f8a-54b9-4996-b94f-3cf105af2900=cryptroot1 rd.vconsole.keymap=neo rd.vconsole.font=latarcyrheb-sun32 init=/init systemd.setenv=PATH=/bin rw vga=836"

The vga= mode parameter is required for loading font latarcyrheb-sun32.

Once in the busybox shell, I manually prepared the required mount points and kernel modules:

ln -s sh mount
ln -s sh lsmod
mkdir /proc /sys /run /mnt
mount -t proc proc /proc
mount -t sysfs sys /sys
mount -t devtmpfs dev /dev
modprobe virtio_pci
modprobe virtio_scsi

As a next step, I copied cryptsetup and dependencies into the initramfs directory:

% for f in /ro/cryptsetup-amd64-2.0.4-6/lib/*; do full=$(readlink -f $f); rel=$(echo $full | sed 's,^/,,g'); mkdir -p $(dirname $rel); install $full $rel; done
% ln -s ld-2.27.so ro/glibc-amd64-2.27-3/out/lib/ld-linux-x86-64.so.2
% cp /ro/glibc-amd64-2.27-3/out/lib/ld-2.27.so ro/glibc-amd64-2.27-3/out/lib/ld-2.27.so
% cp -r /ro/cryptsetup-amd64-2.0.4-6/lib ro/cryptsetup-amd64-2.0.4-6/
% mkdir -p ro/gcc-libs-amd64-8.2.0-3/out/lib64/
% cp /ro/gcc-libs-amd64-8.2.0-3/out/lib64/libgcc_s.so.1 ro/gcc-libs-amd64-8.2.0-3/out/lib64/libgcc_s.so.1
% ln -s /ro/gcc-libs-amd64-8.2.0-3/out/lib64/libgcc_s.so.1 ro/cryptsetup-amd64-2.0.4-6/lib
% cp -r /ro/lvm2-amd64-2.03.00-6/lib ro/lvm2-amd64-2.03.00-6/

In busybox, I used the following commands to unlock the root file system:

modprobe algif_skcipher
./cryptsetup luksOpen /dev/sda4 cryptroot1
mount /dev/dm-0 /mnt

“Another One Bites the Crust” – Queen

Dear fellow RaumZeitLaboroyals!

Anlässlich des möglicherweise (oder auch doch noch nicht) bevorstehenden EU-Austritts des Vereinigten Königreichs, wollen wir uns am Freitag, den 31. Januar zum gemeinsamen BrexEat im RZL treffen.

Steckt eure schönste Tudor-Rosenkohl-Brosche ans Jäckchen und sattelt die Corgis, denn ab 18.30 Uhr stoßen wir auf das/die Wo/ahl unserer britischen Nachbarn an.

Chicken und Vegetable Tikka Masala mit Reis, sowie Indian Treacle Tart – für Veggie- und Beefeater wird es gleichermaßen Britisch-Indische Klassiker zum Dinieren geben.

Falls ihr zum Union Snack kommen wollt, meldet euch bitte bis zum 29.01. per Mail an und schreibt uns, ob ihr Fleisch esst oder nicht. Damit es auch in Zukunft noch “Keep calm and culinary on” heißt und wir weiter lustige Motto-Essfeste machen können, bitten wir um einen Unkostenbeitrag von mindestens 8 Euro pro Person.

Drool, Britannia!
Eure Chai Spice Girls

Werte Tageslichtablehnende und Stahlbetonfans,

die nächste Tour ist ein Highlight für uns Kellerkinder!

Am Samstag, den 8. Februar 2020, werden wir uns den Atomschutzbunker unter dem Stadthaus in N1 anschauen. Falls ihr etwas über die Geschichte des Tiefbunkers erfahren möchtet, oder wissen wollt, welche Auswirkungen der Kalte Krieg auf Mannheim hatte, solltet ihr diesen Ausflug in den Untergrund nicht verpassen. Für RaumZeitLaborierende sind 10 Plätze bei MannheimTours für die Führung ab 15.30 Uhr reserviert. Bitte meldet euch bis zum 1. Februar 2020 per Mail an, wenn ihr dabei sein wollt.

Let’s have a blast
Falloutrattie

Zwar liegen hier seit Monaten mehrere fertige Artikel technischer Natur auf der Platte, nur kann ich davon noch nichts veröffentlichen, daher zu Abwechslung mal etwas aus dem Unterhaltungssektor.

Vor einigen Tagen habe ich mir X4: Foundations gekauft, da der Einstieg im ersten Szenario etwas anstrengend ist stelle ich nun als Backup meiner Notizen die - subjektiv betrachtet - wichtigsten in den Blog. Wahrscheinlich ist es wie mit den Vorgängern, in ein paar Wochen ist die Luft mit einem millionenschweren Selbstläuferunternehmen raus und Ende des Jahres wird dann von Grund auf neu angefangen. Nur muss ich mit diesem Post nach der nächsten längeren Pause nicht ewig in meinen Notizbüchern/Dateien suchen.

Hinweis: Alle Informationen meinerseits beziehen sich auf Version 2.60 HOTFIX 2 (GOG) und können mit vorherigen oder folgenden Versionen völlig nutzlos sein.

• Der wichtigste Hinweis zu Beginn des Spiels: Über die Taste H erreicht man die Hilfstutorials die man zu Beginn braucht und die man auch spielen sollte. In den Patch Notes für die kommende Version 3.00 an wird an mehreren Stellen eine Verbesserung der Einführung und der Tutorials aufgeführt.
• Zu Beginn sind Missionen der Argonen wichtig um schnell ein Ansehen von 10 zu erreichen und günstiger effektive Mining Schiffe kaufen zu können.
• Einstieg ins Mining: Es lohnt sich kleine Schürfer der Klasse M zum sammeln von Methan Gas zu nutzen und diese über die Gebiete der verschiedenen großen Fraktionen zu verteilen. Dadurch steigt langsam mit jeder dieser Fraktionen das Ansehen und eine Marktsättigung tritt nicht zu schnell ein. Manche Schiffe können auch nur im selben Sektor Ressourcen abbauen und verkaufen, andere Nachbarsektoren mitversorgen und im Bestfall global operieren, wegen des ersten Falles wäre ein Schiff der Klasse L zu Beginn gefährlich, da es schnell zu einer Marktsättigung führt. Warum man mal auch zu Beginn des Spiels einen absoluten Experten, dann aber etliche Male einen Neueinsteiger bekommt scheint ein generell offenes Fragezeichen zu sein.
• Fortgeschrittenes Mining: Wenn Schiffe später in der Lage sind in multiplen Sektoren Bergbau und Handel zu betreiben lohnen sich Schiffe der Kategorie L zum sammeln von Nvidium und Silizium. Erz bringt nur wenig Gewinn, dafür ist die Menge der möglichen Abnehmer größer. Damit eine Fraktion eine stabile Flottenstärke hat kann man dies mit Erz unterstützen, ansonsten lohnt es sich nur für eigene Stationen im späteren Spiel.
• Wer zu Beginn fix ein paar Millionen möchte für den kann ich den Beitrag Die ersten Millionen empfehlen. Eine kurze Anleitung wie man im Xenon Sektor Fehlerhafte Logik VII (zu erreichen durch die Verbindung von Gesegnete Vision zu Fehlerhafte Logik I und dort einem Highway im Süden), im "westlichen" Teil, ein größeres Schlachtschiff findet und es kapert. (Achtung: Es kann auch links "außerhalb" der initialen Karte liegen). Ich rate jedoch davon ab, das Schiff umgehend zu verkaufen. Es ist besser es zur Schiffswerft in Argon Prime zu schicken, dort die Marine Einheit wieder an Bord zu nehmen und die Ausstattung(Antrieb/Software) und die Verbrauchsgüter zuerst zu verkaufen. Der Wert solcher Dinge, wurde zumindest bei mir nicht bei jedem Schiff dem Verkaufspreis angerechnet, bei diesem Schiff geht einem dann doch ein siebenstelliger Betrag durch die Finger. Damit das Schiff das Ziel erreicht am Besten speichern und nicht auf die Karte schauen, so nutzt man die Spielmechanik aus, dass unbeachtete Schiffe sich nicht "normal" Verhalten sondern ungebremst durch Sprungtore/Verbindugen rasen.

Sektoren für das Mining

• In Profitabler Handel (TEL kontrolliert) gibt es viele Xenon und Kha'ak Angriffe, allerdings hatte ich hier mit einem Mangel an Abnehmern für Methan und Silizium noch keine Probleme.
• Dreieinigkeit VII ist ein PAR kontrollierter Sektor in dem ein Klasse M Mineralienschürfer in Ruhe mit Silizium für eine Verbesserung der Beziehung zur Fraktion arbeiten kann.
• Gesegnete Vision ist ein HOP kontrollierter Sektor, welcher mit Fehlerhafte Logik verbunden und stark umkämpft ist. Hier lohnt es sich sowohl mit Mineralien als auch Methan zu arbeiten.
• Zweiter Kontakt II Unruheherd ist mit mehreren Fraktionen versorgt, ein kleiner Händler mit Energiezellen ist hier recht zu Beginn zwecks Gewinn von Ansehen praktisch.
• Ianamus Zura IV ist der Teladi Hauptsektor direkt in dem eigentlich durchgehend mit Xenon gekämpft wird. Es lohnt sich hier ein billiges Schiff in die Handelsstation zu stellen, schlicht um mit der später zur Verfügung stehenden Teleportation die Fraktionsvertretetung unkompliziert zu erreichen.

Nach den ersten zehn Millionen: Konstruktionsaufträge

Wenn man mindestens zehn Millionen Credits auf dem Konto hat kommt man mit Bauaufträgen schnell voran.

• Es lohnt sich sehr die Hauptquest mit dem freundlichen Boronen Boso Ta früh abzuschließen, die Belohnungen führen hier zu einer gewissen Kostenreduktion bzgl. Pläne für künftige Stationen und generell entspannterem Vorgehen im Spiel.
• Regelmäßig auf dem Superhighway zwei Runden drehen und jeden Auftrag annehmen auch wenn man die Teile noch nicht alle bauen kann. Anschließen nach Möglichkeit direkt die notwendigen Bauplätze in der Nähe von Toren kaufen, schlicht damit dort später nicht eine andere Station den Platz blockiert. Achtung: Man mag die Karte von oben sehen und glauben, das richtige Gebiet eingegrenzt zu haben, aber das Spiel spielt in einem dreidimensionalen Raum insofern die Y-Achse nicht vergessen und die Karte drehen.
• Bei den Ressourcen nicht sparen und das globale Limit für den Einkaufspreis bei 100% lassen und lieber 10k Credits nehr hinterlegen als vorgeschlagen wird. Bei mir sind schon mehrere Male Bauaufträge hängen geblieben weil für die letzte Energiezelle ein Credit gefehlt hat (95% Limit und passgenau Credits hinterlegt). Bemerkt man dies nicht darf man dann wieder 50k für das Mieten des Bauschiffs zahlen.
• Der Abschluss der Konstruktionen dauert natürlich seine Zeit, aber wenn man 5,5 Millionen Gewinn machen kann ohne viel aktiven Aufwand ist es eine wertvolle Angelegenheit. Die Höhe der Belohnungen nimmt auch zu, ich habe gerade mehrere Aufträge für Verteidigungsstationen, die mich je 2 Millionen Credits gekostet haben, für die ich jedoch mehr als 15 Millionen ausgezahlt bekommen werde.
• Meiner Meinung nach lohnt sich ein eigenes Konstruktionsschiff zu Beginn nicht. Verteilt man über die Sektoren hinweg an jeder kritischen speziellen Station Satelliten findet man immer eines, welches man für 50K Credits anheuern kann. Mehrere Millionen für ein eigenes auszugeben, das auch nur an einer Stelle gleichzeitig arbeiten kann ist vielleicht im späten Spiel sinnvoll, wenn regelmäßig eine Station erweitert werden muss.
• Vorsicht: Wenn die Stationen fertig sind sie Eigentum des Auftraggebers, eine Station zur Produktion von Waren muss man also nicht mit umfangreichen Verteidigungsmaßnahmen versorgen, sofern dies nicht gewünscht ist.
• Eigene Stationen: Eine kleine Werft in umkämpften Gebieten anzubieten lohnt sich, vor allem wenn man mit den sich bekämpfenden Fraktionen befreundet ist. *hüstel* Es dauert zwar eine Weile bis man die Credits wieder hat, aber solange sich mindestens zwei Streiten kommt kontinuierlich Geld, meist aber auch zusätzlich von unbeteiligten Fraktionen. Hierzu muss man neben den Blaupausen der Schiffe auch die der Ausrüstungsteile besitzen, je größer die Auswahl, desto mehr wird ausgegeben. Da die Einkäufe, Reparaturen und Bauaufträge komplett von der KI Situation abhängen lässt sich hier natürlich keine regelmäßiger Gewinn-/Umsatz berechnen.
• Bei einer Werft sollte man zur Gewinnmaximierung auch zeitnah nach und nach die Ressourcen selbst bereitstellen können und die Module an der selben Station oder in deren Nähe anbringen. Ohne diese Eigenproduktion geht doch viel Geld verloren. Man kann natürlich den Spieß auch umdrehen und mit den Modulen zur Ressourcenverarbeitung anfangen.

At this year's 36th Chaos Communication Congress in Leipzig, I signed up to give a short introductory workshop for Julia. To my surprise the room was completely packed yesterday, even though the meeting was scheduled for 11am on day 4 ... Everyone at the session was extremely engaged and packaged with plenty of supporting and challenging questions about Julia. Luckily a bunch of masters from the Julia community were in the audience to help out with providing the in-depth details where I failed (tip of the hat to Keno Fischer and Valentin Churavy). Thanks for everyone in the room! I really enjoyed my time and as usual with these things I learned a lot.

As I mentioned during the session, the Jupyter notebooks I used are all available on github. They were originally made for a one-day introductory Julia course, which I presented in Paris a few weeks ago (details here). The material, however, should be self-explanatory and accessible to people completely new to Julia, but which already have some familiarity with programming of some kind. Main point is to get an idea of what Julia is like, seed a little curiosity about the language and provide links to plenty of further info (see also these links). Feel free to spread the word about the repo if you like the material.

With that said, I am happy to receive any feedback you might have about the session, the notebooks and the other material. I plan to keep doing such courses in the future and I'm always looking for ways how to improve ;).

Link	Licence
https://github.com/mfherbst/course_julia_day

Lately I have been doing programming for embedded systems such as the esp32 and esp8266, and additionally I did a course on embedded systems for my masters degree. This introduced me to the wonderful world of programming close to the hardware level, and inspired me to write this post about hardware peripherals.

What are Hardware Peripherals?

Hardware Peripherals are specialized pieces of silicon that are built into a processor. They are used to perform a diverse set of task. This includes controlling the processors clock speed, power management and communication with other devices. They are responsible for configuring the device operation and during operation are used to perform tasks in parallel with the main cores.

So what can these peripherals do?

Anyone who has ever looked into the data sheet of a microprocessor will know that these data sheets are long. The data sheet for the ARM cortex m7 CPU for example is about 2000 pages long. Which is to say that there are a lot of peripherals that can do a variety of things, for example:

• Analog Digital Converters (ADC) used for measuring analog signals
• Direct Memory Access Controllers (DMA) used for copying data from sensor to memory or the other way
• GPIO Interfaces used for pin management
• I2C and SPI Interfaces used for communicating with sensor devices
• PMC the power management controller
• Other Memory interfaces such as PCI or EBI

Using Peripherals

In order for us to use a peripheral, we have to complete a few steps:

1. Setup peripheral mode

2. Start peripheral task

3. Wait for peripheral to finish

All of this is done via memory mapped registers, which is to say that within the memory range of the processor there are dedicated areas of memory that do not map to a memory controller like an SDRAM, but are mapped to registers belonging to the peripherals. The peripherals use these registers as configuration values that change how the peripheral is working or if it is running, and some of the registers are not meant to be written to but instead are used to communicate the status of the peripheral back to the CPU.

All of this is described in the data sheet of the processor you are using. Every peripheral has a section describing what it can do, and what parameters can be changed via the memory mapped registers, as well as how the peripheral can be started, stopped and how to know when it is finished.

Since all of this is highly dependent on the platform you are using, it is hard to give you a clear cut way to use any peripheral. You will always have to refer back to the data sheet and look how to use the peripheral for your platform. But in order for you to get an idea on how to do this, let us look at an example.

Example

Every example is specific to the specific device we are using. For these examples we are going to look at the simple case of toggling a GPIO pin. The chip we are using is an embedded cortex m7 cpu, from atmel. It belongs to the atsame70 family of cpu's. Datasheet

So all we want to do is let a led blink. To do this we will have to toggle the status of a pin, and all pins are managed by the GPIO peripheral. In the data sheet of this particular chip this peripheral is just called PIO. To be able to do this we first have to tell the PIO peripheral that it should take control of the pin and then tell it to configure the pin to be used as an output. After that we can change the pin state.

If you already looked into the data sheet you might have noticed so that there are multiple PIO peripherals and how the pins are mapped depends on the rest of the system. For the system that i am programming a led is connected to pin 19 on PIO C. So this is the pin I will be using in this example.

To achive an accurate timeout between turning the led on and off, we are going to use the real time timer peripheral on our device. It is in essence a configurable counter attached to a clock signal.

Let us do this in C

This example uses the C library provided by atmel which provides the correct memory addresses of the peripherals and exposes them to us as definitions and structures. By just using these we are automatically writing to the correct addresses.

	#include "atsame70.h" 
	
	void timeout_ms(int ms) {
		// restart timer and set prescaler to count every 32 clock cycles 
		// this corresponds to a 1ms clock cycle since the clock frequency is 32 kHz 
		RTT->RTT_MR = RTT_MR_RTPRES(0x20) | RTT_MR_RTTRST; 
		
		while ( (RTT->RTT_VR | RTT_VR_CRTV_Msk) < ms) {
			//wait for counter to have counted to desired timeout
		}
	}

	void blink_led() {
		//give control of the pin to the pio -> basically the running code
		ATSAME70_BASE_PIOC->PIO_PER = PIO_PC19; 
		ATSAME70_BASE_PIOC->PIO_OER = PIO_PC19;

		while(true) {
			//turn led on 
			ATSAME70_BASE_PIOC->PIO_SODR = PIO_PC19;
			
			timeout_ms(500); 
			
			//turn led off 
			ATSAME70_BASE_PIOC->PIO_CODR = PIO_PC19; 
			
			timeout_ms(500);
		}
}

Timeouts

Since the device can vary it's clock speed it is not desirable to implement a delay with just waiting a specified amount of clock cycles. Instead we are going to use the atsame70 Real Time Timer (RTT).

How to configure the RTT correctly can be read in the functional description in the data sheet. In short we have to configure the clock source since there are two at different speeds. Scale how many clock cycles trigger the counter and reset the peripheral for the new setting to take affect.

To do this we have to write to a memory mapped register:

In the figure we can see all the registers that are connected to the RTT. All the values we need to configure are in the RTT_MR register. It is basically just a 32 bit value. But every bit has a meaning. The first 16 bits represent the 16 bit prescaler value, and there is also a bit to enable the peripheral and one to the reset it. Selecting the clock source is also done with one bit.

So what do we need to wait for a certain amount of ms:

1. Select the 32kHz clock src by setting the RTC1HZ bit in RTT_MR to 0

2. Setting the RTPRES 16 bit value to 32 in order for the counter to increase ever 32 clock cycles which corresponds to increase the counter value evey 1ms

3. Set the RTTDIS bit to 0 to not disable the rtt

4. Trigger the RTT reset by setting RTTRST bit to 1

All of these 4 steps can be done with one write to the RTT_MR register.

Afterwards the timer is running and we can read the value in RTT_VR to see how much time has passed.

Controlling the LED

The PIO peripheral that manages the pins of the device is a lot more complex than the RTT peripheral. Which means it has many more registers. Using these we can do fancy things like giving other peripherals such as the SPI peripheral control over the pins it needs to communicate.

But we are just interested in simply controlling a pin ourselfs. For this we need 4 different registers:

1. PIO_PER peripheral enable register

2. PIO_OER peripheral output enable register

3. PIO_SODR set output data register

4. PIO_CODR clear output data register

They all have the same structure so i am just going to show you one of them:

Basically for every pin controlled by the PIO there is a bit. So one PIO gives us control over 32 pins. To control a pin we have to do the following steps:

1. set PIO_PER pin bit to 1 to enable control of the PIO over the pin

2. set PIO_OER pin bit to 1 to set the pin into output mode

Now setting the PIO_SODR pin bit to 1 to pull the pin high and setting the PIO_CODR pin bit to 1 pulls the pin low again.

How does all of this look in Rust

For rust there is no official library from atmel, but there is a project called svd2rust that allows us to auto-generate a library that we can use to address the correct peripheral registers. All we need is the svd file of the processor we are using, this is an xml file describing all the peripherals and their register values.

	use atsame70q21::{Peripherals}
	
	fn timeout_ms(peripherals : & Peripherals, u32 ms) {
		let rtt = &peripherals.RTT;
		
		// restart timer and set prescaler to count every 32 clock cycles 
		// this corresponds to a 1ms clock cycle since the clock frequency is 32 kHz 
		rtt.rtt_mr.write( |w| {
			unsafe {w.rtpres().bits(0x20);}
			w.rttdis().clearbit();
			w.rttrst().set_bit()
		});
		while rtt.rtt_vr.read().crtv().bits() < ms {
			// wait for counter to have counted to desired timeout
		}
	}

	fn blink_led() {
		let peripherals = Peripherals::take().unwrap();
		
		let pioc = &peripherals.PIOC;
		
		//give control of the pin to the pio -> basically the running code
		pioc.pio_per.write( |w| w.p19().set_bit() );
		pioc.pio_oer.write( |w| w.p19().set_bit() );
		
		loop() {
			//turn led on 
			pioc.pio_sodr.write( |w| w.p19().set_bit() );
			
			timeout_ms(&peripherals, 500); 
			
			//turn led off 
			pioc.pio_codr.write( |w| w.p19().set_bit() );
			
			timeout_ms(&peripherals, 500);
		}
	}

The logic of the rust code is exactly the same as the C example, and since all of the actual functionality we are using is provided by the hardware and not by the language specifics the code looks mostly the same.

I hope you liked this little excursion into bare metal programming, i am sure i will return with more blog post regarding similar topics while i keep experimenting more with rust on bare metal systems.

If you missed the Julia day at Jussieu in Paris last week, but still want to get to know the programming language Julia a little, have no fear: I'll be doing an introductory Julia session at the 36th Chaos Communication Congress in Leipzig this year (on day 4, 11am, so be prepared to get up early ;) ). Find all the infos here.

The plan is to do something similar to the Julia day, just a little more condensed with more focus on showing things rather than explaining things. Overall the workshop will not be so much centred on really teaching Julia, much rather to show you the potential of the language and get you all set to start exploring Julia on your own.

Update: Details here

Congress Everywhere

Auch dieses Mal laden wir alle, die nicht persönlich auf dem 36C3 sein können, wieder herzlich ein, etwas Congress-Atmosphäre bei uns im RaumZeitLabor zu geniessen.

Zusammen schauen wir uns ausgewählte Talks live auf dem Beamer an. Und Essen gibt’s auch. Aller Voraussicht nach gibt es morgens einen Frühstücks-Bausatz bestehend aus Nutella und frischem Brot, abends einen Essens-Bausatz bestehend aus Dürüm, Gemüse und Vleisch. Bembel, Bier und diverse anti-alkoholische Getränke (u.a. 3 Sorten Mate!) werden im Kühlschrank bereitgestellt.

So einfach ist es: Auf https://status.raumzeitlabor.de/ schauen ob die Ampel grün ist, ggf. 0621 76231370 anrufen um ganz sicher zu sein, und ab ins RZL!!!

This Blogpost will investigate the impact of different power management policies for SATA devices in Linux with regard to their power consumption as well as their performance impact. Because after all, everyone likes to get more battery life for free, right?

We will briefly discuss the test setup, then take a look at several measurement results for both power and performance to at the end take a look how to leverage the found results in practice.

Overall, we will find that for SSDs the power management policies for SATA devices can make a significant difference in power consumption while having a negligible impact on performance at the same time.

Background

On a modern linux machine, several modes for power management of a SATA drive are available. These are

• max_performance: A disk is typically kept awake and running to get the best performance out of it. This is most indicative when thinking about spinning disks, as a spindown leads to inevitable significant latencies for the next access of the drive
• min_power: This mode prefers power saving over maximum performance. For spinning disks this for example implies spindowns to save power
• medium_power: A compromise between the aforementioned two.
• med_power_with_dipm: This mode configures the drive like medium_power does, but with additional Device Initiated Power Management. It uses the same configuration the Intel IRST Windows driver uses to for drives.

Setup and Test Procedure

Setup

The measurement was performed on laptops and their internal SSDs. Due to availability to the author, the measurements were done with a Crucial M550 and a Crucial MX500, both 1TB in size. Measurements were taken with

• Linux 5.3
• no applications opened (except for the terminal with the benchmarking process)
• screen turned off (only really relevant for power)
• standard system daemons still running

Power consumption

The power consumption measurements were done using this code, to further reduce noise, wifi was disabled as well. After the link power management policy was set, the system was let idling for 10 minutes to reduce any influences from other policies or activities from before. Afterwards, power consumpiton was measured over 15 minutes via the /sys-API of the machine's battery controller. It was read every three seconds.

Three scenarios were tested for all available link power management policies:

• idle: no induced activity
• synchronous: activity right before reading the current power consumption
• asynchronous: activity in the middle of two power measurements

The entire procedure was repeated for all combinations of available link power management policies and scenarios (so in total 12 times).

Performance

After setting the link power management policy and let the system idle to ensure measurements would not be influenced by past activity. Idle time was chosen to be 15 minutes (slightly longer as for power, an additional precaution as the performance measurements were significantly shorter time-wise that the power measurements). Performance was then measured using fio 3.16 with this preset adapted from here using this script. As benchmarking is hard, the performance measurements are not intended to be an absolute statement of the drive's performance, but rather intended as a ballpark measurement to get a feel for the performance impact of different link power management policies.

Results

Power consumption

MX500

M550

Performance

The measurements for the MX500 were very consistent when repeatedly measured. The measurements for the M550 were a bit flakey, so the fio-measurement on the M550 was performed three times and the performance characteristics shown are the respective medians over all three measurements for both throughput and latency.

Throughput

Latency

Latency information was gathered as part of the fio-measurements for the different link power management policies. The results (specifically lat in fio's output) are denoted as average +/- standard deviation in microseconds to, again, get a ballpark estimate.

Conclusion

As the results clearly indicate, the power link management policy has a noticable impact on a computer's power consumption, up to a third of its total under light load when we exclude the screen. The newest mode med_power_with_dipm proves to be both among the lowest consuming ones for all modes for the tested SSD models and also very consistent in this, whereas other modes are either equal, systematically higher or highly dependent of the scenario at play (for example the min_power mode on the MX500).

The performance impact, both in latency and in throughput, was, however, somewhere between measurable and completely negligible, the highest impact could be seen in the throughput of the M550 where the data still implies med_power_with_dipm to be the preferred choice.

Beware that the results in this post are only applicable to SSDs. HDDs might have significantly different performance and power characteristics due to spin-down and spin-up times and other factors. Furthermore, the aforementioned results will likely apply for SSDs in general, but were obviously only tested on certain models. Different models, especially from differend vendors, could have different characteristics.

Practical usage

If you want to check which policy is in place, you can take a look at the content of the files /sys/class/scsi_host/host[0-9]/link_power_management_policy, which indicate the applied policy or simply use

cat /sys/class/scsi_host/host*/link_power_management_policy

to see the policies. After all, if you didn't configure anything, they should all be the same, so you'll see what's configured no matter which disk it is. To automatically set the desired policy, you can create a file /etc/udev/rules.d/disk-power.rules containing:

SUBSYSTEM=="scsi_host", KERNEL=="host*", ATTR{link_power_management_policy}="med_power_with_dipm"

that will set med_power_with_dipm for all SATA disks that will show up. Alternatively, if you use tlp, you don't have to do anything, because (at least in the default configuration) tlp does already take care of setting this policy, at least for the primary SATA disk.

Appendix

Liteonit LCS-256, 256GB

One additional dataset was donated from an additional SSD, specifically a Liteonit LCS-256, sized at 256GB. Below you find the power measurements for this disk, the measurement procedure is roughly equal to the one outlined for Crucial's MX500 and M550 above. We see that, while the exact numbers vary, the power profiles behave very similar, specifically to the ones of the MX500, and our conclusions apply for this disk as well.

If someone has a disk or SSD manufacturer not covered so far, feel invited to still send data to broaden the survey started here.

A few weeks ago on 21st and 22nd November of this year Pierre-Francois Loos invited me for two days to the Laboratoire de Chimie et Physique Quantiques of the Université Paul Sabatier Toulouse. On Thursday the 21st I had the chance to present our current status in DFTK and adcc at the lab's seminar. My talk ended up being an updated version of my talk at the Domcke group in Munich, which I held just in the previous month. After the talk and on Friday I had plenty of time to discuss with Titou, Anthony Scemama and Michel Caffarel about adcc, DFTK and their respective projects. The discussions were interesting from my end and ended up being a rather fruitful exchange of ideas. During the two days I certainly learned a lot.

As usual my slides and examples are attached below:

Link	Licence
Interdisciplinary software for electronic structure theory: adcc and DFTK (Slides seminar LCPQ)
DFTK and Julia examples (Tarball)
adcc examples (Notebook)

As part of my research stay at the Matherials team of ENPC Paris Tech and Inria I have been developing the density-functional toolkit, DFTK.jl, together with Antoine Levitt and Eric Cancès. Finally after about six months of joint effort on this Julia code, we just released a first preview in the form of version 0.0.1.

As I mentioned already in previous articles and talks the aim of DFTK is to bridge between mathematicians, computer scientists and materials scientists and to simplify mathematically-motivated research in this interdisciplinary subject. Currently we exclusively focus on a plane-wave discretisation of density-functional theory (PWDFT) as implemented in plenty of mature packages in the community (Abinit, Quantum Espresso, VASP, ...).

DFTK is mainly born from two realisations: Firstly, existing PWDFT progams have huge code bases, where reducing or altering the physical model to a case, which can be treated with rigorous mathematics is very challenging. As a result mathematical research is done in custom codes developed mostly for the purpose of a single project or research questions and findings hardly make it into a setting useful for practitioners. Secondly, such single-purpose custom codes are usually are not fast enough to treat the setting of real-world applications. This prevents verification of obtained results in the context actually relevant in practice. With DFTK we want to overcome this issue by allowing in one code to both implement toy problems and upscale them to the high-performance level needed in practice.

As of now, we're certainly not fully there, but given the short time, we're still proud of our feature list:

• Plane-wave basis sets
• All LDA and GGA functionals from libxc
• Modelling of Insulators and metals (Fermi-Dirac or Methfessel-Paxton smearing)
• GTH or HGH Pseudopotentials
• Exploitation of Brillouin zone symmetry for k-Point sampling
• Band structure computation
• Full access to intermediate quantities (density, Bloch wave)
• Three SCF algorithms (DIIS, NLsolve, damping)
• Close agreement with Abinit for a few thoroughly tested cases (silicon, graphite, manganese).
• Support for both single and double precision throughout the library for a small set of functionals. Support for arbitrary floating point types is on the way.

Recently we moved the code to JuliaMolSim a github organisation, where we want to collect Julia codes for performing molecular simulations in quantum chemistry and materials science. Along with this we registered the release with the MolSim Julia registry, which means that you can install DFTK by two simple steps:

1. Add the MolSim registry to your Julia installation. Type from a Julia REPL:

] registry add https://github.com/JuliaMolSim/MolSim.git

1. Install DFTK as usual, again from a REPL:

] add DFTK

For the time being, DFTK will probably stay in the pre-release stage, as we are not yet completely happy with the internal code structure and the API and we think some more restructuring should follow. Still, we consider the code now sufficiently advanced to suggest you to have a look and try it out :). With this naturally comes a small plea: If you discover something, which bothers you or something, which does not work, please open an issue on github and pose it for discussion. Also we are very happy if you want to contribute something, please just get going!

For further details and the DFTK source code, see the DFTK project page on github. Citations to the DFTK source code are possible using DOI 10.5281/zenodo.3541724.

Liebe RaumZeitLaborierende!

Bei unserem nächsten Ausflug geht die Post ab! Auch wenn der Leiter des Museums für Kommunikation in Frankfurt “Gold” mit Nachnamen heißt, dreht sich dort das meiste um die Farbe Gelb.

Am Sonntag, den 1. Dezember 2019, haben wir ab 13 Uhr die Möglichkeit durch die Dauerausstellung des ehemaligen Post-Museums geführt zu werden und zu schauen, welche Erfindungen und technischen Entwicklungen unsere heutige Kommunikation möglich machen. Falls euch interessiert, was ein Reiseruf ist, ihr alte Telefonzellen bewundern, einen Kraftpostbus und eine Briefsortieranlage von Nahem sehen wollt, dann solltet ihr bei dieser Adventstour dabei sein. Im Anschluss werden wir nach aktuellem Planungsstand auch die Funkstation auf dem Museumsdach besuchen können.

Für RaumZeitLaborierende ist diese Führung kostenlos, Nicht-Mitglieder bitten wir um 5 Euro für die RZL-Tourenkasse. Da diese Führung auf 15 Plätze beschränkt ist, bitte ich bis zum 24. November 2019 um Rückmeldung per elektronischem Briefchen.

Goldgelbe Grüße
FlederrattY

Over the part year or so a side project I have been working off and on has been the adcc code. This python module allows to perform excited states calculation for simulating molecular spectra based on algebraic-diagrammatic construction (ADC) methods. The speciality of the adcc code is that (a) multiple host programs are supported for supplying a Hartree-Fock reference, right now pyscf, Psi4, molsturm and veloxchem, and (b) that its hybrid C++/python design allows to implement a large part of the ADC procedure including iterative solver schemes in python and still achieve the speed required for larger ADC calculations. The code development has been a collaboration with multiple members from the old group of my PhD times, the Dreuw group from Heidelberg. Finally, today, we are publicly releasing the code following the submission of our paper on adcc last week (download link).

I have already talked about adcc and ADC methods before (see also my research interests), so I'll be brief with my summary about these. The ADC scheme builds upon the fact that the poles of the polarisation propagator, i.e. the two-particle Green's function, contains the physical information for describing excited electronic states and their properties. Using a Møller-Plesset partitioning of the Schrödinger Hamiltonian one may construct a perturbative expansion for said polarisation propagator. In the ADC approach this is done using a particular representation basis for the many-body states of the Schrödinger Hamiltonian, the so-called intermediate state basis. The outcome are a perturbative series of matrices, the so-called ADC matrices corresponding to the ADC(n) series of methods. The ADC matrices contain exactly the spectral information of the polarisation propagator consistent to order n of a Møller-Plesset expansion of the correlated ground state. Diagonalising this matrix, thus allows to obtain excitation energies and excited-state properties. For more details, see for example the theory section in the adcc documentation.

As we discuss in our paper, in adcc the basic procedure of building and diagonalising the ADC matrix is implemented in a hybrid C++/python code. The aim was to keep everything, including intermediate results, accessible from the python layer, while implementing the computationally intensive parts in C++. As a result, the code is comparable to C++-only implementations in speed, such that it can be used to e.g. treat biomolecular systems. The iterative diagonalisation procedure and other aspects of the numerics are implemented completely in python, facilitating experimenting on the numerical level in the future. Multiple variants of ADC are available up to and including ADC(3), i.e. a treatment of the polarisation propagator consistent to third-order. Originally adcc grew out of my desire to use another ADC code, which is developed in the Dreuw group, namely the adcman code, interactively from python. In its current state, however, adcc has well grown beyond being a plain wrapper around adcman. The internal code structure and workflows of both packages have very little in common, albeit the general methodology to solve ADC of both packages is certainly related. The design of adcc aims to simplify working with ADC methods as a developer, but also facilitating the use and extension of existing workflows by everyday users. For more details and a couple of examples, see the paper, or the Performing calculations with adcc section of the adcc documentation. Installing adcc is simple. Given that a few requirements (such as openblas on Linux) are available, it boils down to using pip:

pip install pybind11
pip install adcc

The full abstract reads

ADC-connect (adcc) is a hybrid python/C++ module for performing excited state calculations based on the algebraic-diagrammatic construction scheme for the polarisation propagator (ADC). Key design goal is to restrict adcc to this single purpose and facilitate connection to external packages, e.g., for obtaining the Hartree-Fock references, plotting spectra, or modelling solvents. Interfaces to four self-consistent field codes have already been implemented, namely pyscf, psi4, molsturm, and veloxchem. The computational workflow, including the numerical solvers, are implemented in python, whereas the working equations and other expensive expressions are done in C++. This equips adcc with adequate speed, making it a flexible toolkit for both rapid development of ADC-based computational spectroscopy methods as well as unusual computational workflows. This is demonstrated by three examples. Presently, ADC methods up to third order in perturbation theory are available in adcc, including the respective core-valence separation and spin-flip variants. Both restricted or unrestricted Hartree-Fock references can be employed.

One of my two NAS builds recently died, so I bought a new one until I find some time to debug the old one. Since a couple of people have been asking me what I would recommend nowadays based on my November 2016 article “Gigabit NAS (running CoreOS)”, I figured I would share the new hardware listing:

In November 2016 I paid only 225 CHF, i.e. 126 CHF less.

Why is this build so much more expensive? There are two major reasons:

The AM4 platform

The AM4 platform replaced the AM1 APU series as the cheapest broadly available AMD platform.

As you might have gathered from the links in the hardware listing above, I define “broadly available” as available at digitec, a large electronics shop in Zürich.

They offer same-day orders for pick-up in their Zürich location during Weekdays and on Saturdays, so it is kind of like being on a hardware support plan :-)

Unfortunately, the cheapest AM4 CPU is a lot more expensive (+ 23.31 CHF).

Also, there are (currently?) no AM4 mainboards with DC barrel power plugs, meaning more expensive ATX power supplies (+ 26.30 CHF) become necessary.

Additional components: fan and system disk

Definitely invest in the Noctua 120mm ULN (Ultra Low Noise) fan (+ 29.00 CHF). The fan that comes in the Silverstone case is pretty noisy, and that might be bothersome if you don’t have the luxury of stashing your NAS away in the basement.

In my last build, I had an SSD lying around that I used as system disk, this time I had to buy one (+ 27.50 CHF).

Note that I intentionally picked a SATA SSD over an M.2 SSD: the M.2 slot of the AB350 is on the back of the mainboard, so an M.2 SSD is harder to reach. The performance disadvantage of a SATA SSD compared to an M.2 SSD might be measurable, but irrelevant for my day-to-day usage. Quickly accessing the physical hardware is more important.

Yesterday we had the first instance of the Julia Paris Meetup. As the name suggests a couple of us Julia enthusiasts in the French capital got together for one evening of talks and chatting about everyone's favourite programming language. It was a great occasion to finally meet some people in person and gather around for some technical chit-chat till the late hours at one of the bars of the 11th arrondissement after the talks.

I myself was pretty excited about the evening and not quite sure what kind of people to expect. Unsurprisingly most people, who turned up had an academic background with focus on number crunching of some sort, mostly high-performance linear algebra or optimisation problems. To my big surprise, the number of people working in a industrial context was a lot larger than I expected, even though most did not use the language to a large extend in their everyday work. Still, after the evening I am yet again convinced that Julia is spreading beyond dusty desks in universities. Certainly, a great part in this plays the dedicated community of people, willing to invest a Sunday evening here and there to work on just the very thing required to advance the language and the Julia ecosystem step by step. Even though this has already been clear to me to some extent before Thursday, actually meeting the community and listening to stories and experiences from the Julia trenches, make the whole impression more vivid. I am already looking forward to the next meeting (details as always on https://julia-users-paris.github.io).

On that note, I was very happy, that I had the chance to play an active part in the evening by being one of the first to present some stories of my own. Naturally I talked about my endeavours with Julia while developing the DFTK code. Since I was not too sure about the audience, I tried to get across what makes Julia an ideal language for our efforts, what things we are currently working on and what will be our focus next and how we expect Julia to help. I'm not going to repeat the details about DFTK here, because these can be found in a previous article. See also the second half of this article. The slides of my talk can be downloaded here as usual:

Link	Licence
Electronic-structure simulations using Julia (Slides 1st Julia Paris Meetup)

Just sharing a quick convenience idea: merging Desktop and /tmp to use it as a quick drop directory. Sounds stupid? Bear with me.

XDG user directories

XDG user directories are a freedesktop.org de-facto standard for specifying typical directories within a user's home, such as Documents, Downloads, Pictures, Music etc.. Filemanagers typically mark these xdg-user-dirs with special folder icons, so even if you haven't explicitly bothered yet, you might have noticed.

Setting one of the XDG user directories allows your system (typically impersonated by your desktop environement) to ensure these folders are always existing, allows file managers to specifically mark them and to allow applications to save things there (for example applications can look up a user-specified download-folder to drop downloads there instead of reconfiguring each application separately). Also, many file managers and dialogs show you those XDG-user-dirs as quicklinks:

You can see that Desktop as well as the other xdg-dirs I use are accessible as quicklinks on the left.

Hijacking the desktop dir

I personally do not use files on my desktop, as I most of the time do not see my desktop anyways, therefore I have little use for the Desktop directory. However, as many file dialogs offer quicklinks to those directories, we can use the otherwise useless desktop dir for another purpose: putting a quick-drop directory there. In my case this is /tmp, for two reasons:

• easily accessible from the commandline to pull/push files from/to there, just two characters and a tab to type
• already set up as a tmpfs, so it lives in my computer's memory and will be cleared and empty again upon next reboot

By specifying /tmp as the Desktop directory we now have it accessible as a quicklink in close to every file dialog and can quickly drop things from any terminal location there and then access them with two clicks from every filesystem dialog (and the other way round).

Setting xdg-user-dirs

To do so we now need to set that directory. This is done via the file ~/.config/user-dirs.dirs, which for our purpose should contain the line:

XDG_DESKTOP_DIR="/tmp"

You can set additional directories, the scheme will be always the same, XDG_<dirname>_DIR, you can query directories from the commandline via xdg-user-dir <dirname> to use them in your own scripts. <dirname> can be almost anything (although most software out there of course doesn't consider any value for that).

drop-directory for display on your desktop

If you use a Desktop Environement that actually displays icons on your desktop, using /tmp is most likely unsatistfactory, as many applications use it for files and directories and therefore your desktop will be cluttered with those files.

Instead, we can create a directory specifically for that purpose, for example you could create a folder /drop in your filesystem root. This already retains the first property mentioned above, being accessible with few keystrokes (3 + tab: /dr<tab>, as /d<tab> collides with /dev). The second property we want is being in-memory, so we have simple regular clearance upon reboot and don't collect clutter over time. We can achieve that by placing the line

tmpfs /drop tmpfs rw,nodev,noexec,nosuid,mode=1777 0 0

in /etc/fstab. This mounts a tmpfs to /drop in read-write mode.

nodev,noexec,nosuid are optional, but tightening permissions a little more rarely hurts. mode=1777 makes the directory readwriteeverythingable for every user on the system, but sets the sticky bit, so only the user placing things can delete them. Certainly not the most locked-down mode you could set, so potentially you want to tighten the screws here a little more.

Adapt the entry in ~/.config/user-dirs.dirs accordingly and you're ready to go, now having an actual drop directory where you can simply drag and drop things onto your desktop.

Further reading

• ArchWiki on xdg-user-dirs
• /etc/fstab: common options

“I Want to Break Fast” - Queen

Dear fellow RaumZeitLaboroyals!

Anlässlich des möglicherweise (oder auch doch noch nicht) bevorstehenden EU-Austritts des Vereinigten Königreichs, wollen wir uns am Sonntag, den 27. Oktober zum gemeinsamen BrexEat im RZL treffen.

Steckt eure schönste Tudor-Rose-Spiegeleibrosche ans Jäckchen und sattelt die Corgis, denn ab 11.30 Uhr gibt es nicht nur einen Toast auf unsere britischen Nachbarn.

Würstchen, Hash Browns, Porridge, Bacon - für Veggie- und Beefeater wird es ein Full English Breakfast geben.

Falls ihr zum Union Snack kommen wollt, meldet euch bitte bis zum 23.10. per Mail an. Damit es auch in Zukunft noch “Keep calm and culinary on” heißt und wir weiter lustige Motto-Essfeste machen können, bitten wir um einen Unkostenbeitrag von mindestens 10 Euro pro Person.

God save our baked bean!
Eure Earls of Sandwich

A quick teaser for some Julia-related activities around Paris, I am involved with in the next months.

• 17 Oct 2019, 19:00, QuantStack (27 Rue du Chemin Vert 75011, Paris): The first Julia meet-up of Paris. We want to gather the people in and around Paris, who are interested in or working with Julia and stimulate exchanging experiences and ideas. I'll give a short talk about DFTK.jl and François Févotte will talk about AccurateArithmetic.jl. More details on https://julia-users-paris.github.io. Feel free to drop by if you are around!

• 13 Dec 2019, 09:00, Sorbonne Université, LJLL and LCT labs of Jussieu Campus. Julia Day (Journée Julia): I'll do an introductory session to Julia in the morning and talk a little bit about useful and helpful Julia packages (linear algebra, non-linear solvers, etc.) in the afternoon. followed by an introduction to DFTK.jl. For more details on the day see the website.

See the Conclusion for a summary if you’re impatient :-)

Motivation

Over the last few months, I have been developing a new index format for Debian Code Search. This required a lot of careful refactoring, re-implementation, debug tool creation and debugging.

Multiple factors motivated my work on a new index format:

1. The existing index format has a 2G size limit, into which we have bumped a few times, requiring manual intervention to keep the system running.

2. Debugging the existing system required creating ad-hoc debugging tools, which made debugging sessions unnecessarily lengthy and painful.

3. I wanted to check whether switching to a different integer compression format would improve performance (it does not).

4. I wanted to check whether storing positions with the posting lists would improve performance of identifier queries (= queries which are not using any regular expression features), which make up 78.2% of all Debian Code Search queries (it does).

I figured building a new index from scratch was the easiest approach, compared to refactoring the existing index to increase the size limit (point ①).

I also figured it would be a good idea to develop the debugging tool in lock step with the index format so that I can be sure the tool works and is useful (point ②).

Integer compression: TurboPFor

As a quick refresher, search engines typically store document IDs (representing source code files, in our case) in an ordered list (“posting list”). It usually makes sense to apply at least a rudimentary level of compression: our existing system used variable integer encoding.

TurboPFor, the self-proclaimed “Fastest Integer Compression” library, combines an advanced on-disk format with a carefully tuned SIMD implementation to reach better speeds (in micro benchmarks) at less disk usage than Russ Cox’s varint implementation in github.com/google/codesearch.

If you are curious about its inner workings, check out my “TurboPFor: an analysis”.

Applied on the Debian Code Search index, TurboPFor indeed compresses integers better:

Disk space

Switching to TurboPFor (via cgo) for storing and reading the index results in a slight speed-up of a dcs replay benchmark, which is more pronounced the more i/o is required.

Query speed (regexp, cold page cache)

Query speed (regexp, warm page cache)

Overall, TurboPFor is an all-around improvement in efficiency, albeit with a high cost in implementation complexity.

Positional index: trade more disk for faster queries

This section builds on the previous section: all figures come from the TurboPFor index, which can optionally support positions.

Conceptually, we’re going from:

type docid uint32
type index map[trigram][]docid

…to:

type occurrence struct {
    doc docid
    pos uint32 // byte offset in doc
}
type index map[trigram][]occurrence

The resulting index consumes more disk space, but can be queried faster:

1. We can do fewer queries: instead of reading all the posting lists for all the trigrams, we can read the posting lists for the query’s first and last trigram only.
   This is one of the tricks described in the paper “AS-Index: A Structure For String Search Using n-grams and Algebraic Signatures” (PDF), and goes a long way without incurring the complexity, computational cost and additional disk usage of calculating algebraic signatures.

2. Verifying the delta between the last and first position matches the length of the query term significantly reduces the number of files to read (lower false positive rate).

3. The matching phase is quicker: instead of locating the query term in the file, we only need to compare a few bytes at a known offset for equality.

4. More data is read sequentially (from the index), which is faster.

Disk space

A positional index consumes significantly more disk space, but not so much as to pose a challenge: a Hetzner EX61-NVME dedicated server (≈ 64 €/month) provides 1 TB worth of fast NVMe flash storage.

The idea behind the positional index (posrel) is to not store a (doc,pos) tuple on disk, but to store positions, accompanied by a stream of doc/pos relationship bits: 1 means this position belongs to the next document, 0 means this position belongs to the current document.

This is an easy way of saving some space without modifying the TurboPFor on-disk format: the posrel technique reduces the index size to about ¾.

With the increase in size, the Linux page cache hit ratio will be lower for the positional index, i.e. more data will need to be fetched from disk for querying the index.

As long as the disk can deliver data as fast as you can decompress posting lists, this only translates into one disk seek’s worth of additional latency. This is the case with modern NVMe disks that deliver thousands of MB/s, e.g. the Samsung 960 Pro (used in Hetzner’s aforementioned EX61-NVME server).

The values were measured by running dcs du -h /srv/dcs/shard*/full without and with the -pos argument.

Bytes read

A positional index requires fewer queries: reading only the first and last trigram’s posting lists and positions is sufficient to achieve a lower (!) false positive rate than evaluating all trigram’s posting lists in a non-positional index.

As a consequence, fewer files need to be read, resulting in fewer bytes required to read from disk overall.

As an additional bonus, in a positional index, more data is read sequentially (index), which is faster than random i/o, regardless of the underlying disk.

The values were measured by running iostat -d 25 just before running bench.zsh on an otherwise idle system.

Query speed

Even though the positional index is larger and requires more data to be read at query time (see above), thanks to the C TurboPFor library, the 2 queries on a positional index are roughly as fast as the n queries on a non-positional index (≈4s instead of ≈3s).

This is more than made up for by the combined i/o matching stage, which shrinks from ≈18.5s (7.1s i/o + 11.4s matching) to ≈1.3s.

Note that identifier query i/o was sped up not just by needing to read fewer bytes, but also by only having to verify bytes at a known offset instead of needing to locate the identifier within the file.

Conclusion

The new index format is overall slightly more efficient. This disk space efficiency allows us to introduce a positional index section for the first time.

Most Debian Code Search queries are positional queries (78.2%) and will be answered much quicker by leveraging the positions.

Bottomline, it is beneficial to use a positional index on disk over a non-positional index in RAM.

Last week, from Wednesday to Friday, I paid the Technical University of Munich (TUM) a short visit for two great opportunities to present my work: Once in the theoretical chemistry group of Professor Wolfgang Domcke and once at the annual meeting of the modeling, analysis and simulation of molecular systems (MoAnSi) interest group, a crowd consisting mostly of mathematicians and fellow modelling scientists.

Talk at Domcke group

The first presentation I gave last Wednesday in the Domcke group, where I talked about challenges and approaches to interdisciplinary software projects. I also presented two projects of my own, namely DFTK and adcc. About these codes I already gave a few details in previous articles and thus be rather brief with respect to details about them.

In the part of the talk on the plane-wave density-functional theory code DFTK I mainly focused on the question why we decided to use Julia as a programming language. For this I summarised Julia's capabilities and performance and gave a short teaser of Julia code in a Jupyter notebook. This notebook shows a Julia implementation of a Jacobi-Davidson iterative eigensolver and discusses concrete instantiations of the code in various situations. This includes a mixed-precision algorithm, which transfers intermediate results obtained in a lower precision (e.g. single precision) to higher (i.e. double) precision and then continues the iterations at this level. Other examples were diagonalisations using sparse matrices or GPU computations. Most notably, for all these cases the actual Jacobi-Davidson code was only written once and not explictly adapted to fit the respective datastructures or computational backends. Last, but not least the notebook teasered a small automatic differentiation example as well.

The main focus of the talk, however, was the adcc code, which implements the algebraic-diagrammatic construction scheme for the polarisation propagator (ADC) and allows to drive this computation from any SCF code using a python-based interface. In the presentation I sketch content from our upcoming software paper on adcc and present three examples for calculations, which we are able to do with only few lines of python code. This includes an analysis of the core-valence separation (CVS) error for water, a sophisticated combination of freezing extra core and valence orbitals alongside the CVS and a case of an ADC(2) modelling of nile red (426 basis functions) in an explicit solvent model (polarisable embedding). The code for the second example, namely the combination of CVS with freezing other orbitals, was also shown in an example notebook. Especially this part of the talk was well-received, providing fruit for many ADC-related and adcc-related discussions afterwards.

MoAnSi workshop

Directly after the day at the Domcke group I attended the MoAnSi meeting, which took place last Thursday and Friday, bringing together a bunch of mathematicians interested in computational methods for molecular science. Similar to other interdisciplinary meetings overlapping chemistry and maths, like the one in Oberwolfach, the atmosphere was friendly and open. Plenty of discussions were stimulating for thought about fundamental aspects of quantum chemistry, one usually does not think about as a chemist.

For this reason my second talk was tailored a bit more to the mathematician crowd, which meant that I focused more on DFTK and how it could be used in the context of mathematically-driven research of density-functional theory. Apart from the slides and the Julia examples I also presented some actual DFTK code, emphasising how Julia leads to extremely concise and readable programs. During the Q&A, I mentioned a blog article about a Julia case study using the language for a petascale computation. The respective project is the Celeste code and a summary of the hurdles and difficulties can be found in a post by Keno Fischer on the Julia Computing Blog.

Slides and notebooks for both talks are linked in the main text above or can be downloaded here:

Link	Licence
Interdisciplinary software for electronic structure theory: adcc and DFTK (Slides seminar Domcke group)
Two Julia examples (Notebook)
adcc Demo: Combining CVS and frozen orbitals (Notebook)
DFTK: The density-functional toolkit (Slides MoAnSi talk)

Over the last year or so I have worked on a research linux distribution in my spare time. It’s not a distribution for researchers (like Scientific Linux), but my personal playground project to research linux distribution development, i.e. try out fresh ideas.

This article focuses on the package format and its advantages, but there is more to distri, which I will cover in upcoming blog posts.

Motivation

I was a Debian Developer for the 7 years from 2012 to 2019, but using the distribution often left me frustrated, ultimately resulting in me winding down my Debian work.

Frequently, I was noticing a large gap between the actual speed of an operation (e.g. doing an update) and the possible speed based on back of the envelope calculations. I wrote more about this in my blog post “Package managers are slow”.

To me, this observation means that either there is potential to optimize the package manager itself (e.g. apt), or what the system does is just too complex. While I remember seeing some low-hanging fruit¹, through my work on distri, I wanted to explore whether all the complexity we currently have in Linux distributions such as Debian or Fedora is inherent to the problem space.

I have completed enough of the experiment to conclude that the complexity is not inherent: I can build a Linux distribution for general-enough purposes which is much less complex than existing ones.

① Those were low-hanging fruit from a user perspective. I’m not saying that fixing them is easy in the technical sense; I know too little about apt’s code base to make such a statement.

Key idea: packages are images, not archives

One key idea is to switch from using archives to using images for package contents. Common package managers such as dpkg(1) use tar(1) archives with various compression algorithms.

distri uses SquashFS images, a comparatively simple file system image format that I happen to be familiar with from my work on the gokrazy Raspberry Pi 3 Go platform.

This idea is not novel: AppImage and snappy also use images, but only for individual, self-contained applications. distri however uses images for distribution packages with dependencies. In particular, there is no duplication of shared libraries in distri.

A nice side effect of using read-only image files is that applications are immutable and can hence not be broken by accidental (or malicious!) modification.

Key idea: separate hierarchies

Package contents are made available under a fully-qualified path. E.g., all files provided by package zsh-amd64-5.6.2-3 are available under /ro/zsh-amd64-5.6.2-3. The mountpoint /ro stands for read-only, which is short yet descriptive.

Perhaps surprisingly, building software with custom prefix values of e.g. /ro/zsh-amd64-5.6.2-3 is widely supported, thanks to:

1. Linux distributions, which build software with prefix set to /usr, whereas FreeBSD (and the autotools default), which build with prefix set to /usr/local.

2. Enthusiast users in corporate or research environments, who install software into their home directories.

Because using a custom prefix is a common scenario, upstream awareness for prefix-correctness is generally high, and the rarely required patch will be quickly accepted.

Key idea: exchange directories

Software packages often exchange data by placing or locating files in well-known directories. Here are just a few examples:

• gcc(1) locates the libusb(3) headers via /usr/include
• man(1) locates the nginx(1) manpage via /usr/share/man.
• zsh(1) locates executable programs via PATH components such as /bin

In distri, these locations are called exchange directories and are provided via FUSE in /ro.

Exchange directories come in two different flavors:

1. global. The exchange directory, e.g. /ro/share, provides the union of the share sub directory of all packages in the package store.
   Global exchange directories are largely used for compatibility, see below.

2. per-package. Useful for tight coupling: e.g. irssi(1) does not provide any ABI guarantees, so plugins such as irssi-robustirc can declare that they want e.g. /ro/irssi-amd64-1.1.1-1/out/lib/irssi/modules to be a per-package exchange directory and contain files from their lib/irssi/modules.

Search paths sometimes need to be fixed

Programs which use exchange directories sometimes use search paths to access multiple exchange directories. In fact, the examples above were taken from gcc(1) ’s INCLUDEPATH, man(1) ’s MANPATH and zsh(1) ’s PATH. These are prominent ones, but more examples are easy to find: zsh(1) loads completion functions from its FPATH.

Some search path values are derived from --datadir=/ro/share and require no further attention, but others might derive from e.g. --prefix=/ro/zsh-amd64-5.6.2-3/out and need to be pointed to an exchange directory via a specific command line flag.

FHS compatibility

Global exchange directories are used to make distri provide enough of the Filesystem Hierarchy Standard (FHS) that third-party software largely just works. This includes a C development environment.

I successfully ran a few programs from their binary packages such as Google Chrome, Spotify, or Microsoft’s Visual Studio Code.

Fast package manager

I previously wrote about how Linux distribution package managers are too slow.

distri’s package manager is extremely fast. Its main bottleneck is typically the network link, even at high speed links (I tested with a 100 Gbps link).

Its speed comes largely from an architecture which allows the package manager to do less work. Specifically:

1. Package images can be added atomically to the package store, so we can safely skip fsync(2) . Corruption will be cleaned up automatically, and durability is not important: if an interactive installation is interrupted, the user can just repeat it, as it will be fresh on their mind.

2. Because all packages are co-installable thanks to separate hierarchies, there are no conflicts at the package store level, and no dependency resolution (an optimization problem requiring SAT solving) is required at all.
   In exchange directories, we resolve conflicts by selecting the package with the highest monotonically increasing distri revision number.

3. distri proves that we can build a useful Linux distribution entirely without hooks and triggers. Not having to serialize hook execution allows us to download packages into the package store with maximum concurrency.

4. Because we are using images instead of archives, we do not need to unpack anything. This means installing a package is really just writing its package image and metadata to the package store. Sequential writes are typically the fastest kind of storage usage pattern.

Fast installation also make other use-cases more bearable, such as creating disk images, be it for testing them in qemu(1) , booting them on real hardware from a USB drive, or for cloud providers such as Google Cloud.

Fast package builder

Contrary to how distribution package builders are usually implemented, the distri package builder does not actually install any packages into the build environment.

Instead, distri makes available a filtered view of the package store (only declared dependencies are available) at /ro in the build environment.

This means that even for large dependency trees, setting up a build environment happens in a fraction of a second! Such a low latency really makes a difference in how comfortable it is to iterate on distribution packages.

Package stores

In distri, package images are installed from a remote package store into the local system package store /roimg, which backs the /ro mount.

A package store is implemented as a directory of package images and their associated metadata files.

You can easily make available a package store by using distri export.

To provide a mirror for your local network, you can periodically distri update from the package store you want to mirror, and then distri export your local copy. Special tooling (e.g. debmirror in Debian) is not required because distri install is atomic (and update uses install).

Producing derivatives is easy: just add your own packages to a copy of the package store.

The package store is intentionally kept simple to manage and distribute. Its files could be exchanged via peer-to-peer file systems, or synchronized from an offline medium.

distri’s first release

distri works well enough to demonstrate the ideas explained above. I have branched this state into branch jackherer, distri’s first release code name. This way, I can keep experimenting in the distri repository without breaking your installation.

From the branch contents, our autobuilder creates:

1. disk images, which…

   • can be tested on real hardware
   • can be tested in qemu
   • can be tested in virtualbox
   • can be tested in docker
   • can be tested on Google Cloud

2. a package repository. Installations can pick up new packages with distri update.

3. documentation for the release.

   • Definitely check out the “Cool things to try” README section.

The project website can be found at https://distr1.org. The website is just the README for now, but we can improve that later.

The repository can be found at https://github.com/distr1/distri

Project outlook

Right now, distri is mainly a vehicle for my spare-time Linux distribution research. I don’t recommend anyone use distri for anything but research, and there are no medium-term plans of that changing. At the very least, please contact me before basing anything serious on distri so that we can talk about limitations and expectations.

I expect the distri project to live for as long as I have blog posts to publish, and we’ll see what happens afterwards. Note that this is a hobby for me: I will continue to explore, at my own pace, parts that I find interesting.

My hope is that established distributions might get a useful idea or two from distri.

There’s more to come: subscribe to the distri feed

I don’t want to make this post too long, but there is much more!

Please subscribe to the following URL in your feed reader to get all posts about distri:

https://michael.stapelberg.ch/posts/tags/distri/feed.xml

Next in my queue are articles about hermetic packages and good package maintainer experience (including declarative packaging).

Feedback or questions?

I’d love to discuss these ideas in case you’re interested!

Please send feedback to the distri mailing list so that everyone can participate!

I measured how long the most popular Linux distribution’s package manager take to install small and large packages (the ack(1p) source code search Perl script and qemu, respectively).

Where required, my measurements include metadata updates such as transferring an up-to-date package list. For me, requiring a metadata update is the more common case, particularly on live systems or within Docker containers.

All measurements were taken on an Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz running Docker 1.13.1 on Linux 4.19, backed by a Samsung 970 Pro NVMe drive boasting many hundreds of MB/s write performance.

See Appendix B for details on the measurement method and command outputs.

Measurements

Keep in mind that these are one-time measurements. They should be indicative of actual performance, but your experience may vary.

ack (small Perl program)

qemu (large C program)

The difference between the slowest and fastest package managers is 30x!

How can Alpine’s apk and Arch Linux’s pacman be an order of magnitude faster than the rest? They are doing a lot less than the others, and more efficiently, too.

Pain point: too much metadata

For example, Fedora transfers a lot more data than others because its main package list is 60 MB (compressed!) alone. Compare that with Alpine’s 734 KB APKINDEX.tar.gz.

Of course the extra metadata which Fedora provides helps some use case, otherwise they hopefully would have removed it altogether. The amount of metadata seems excessive for the use case of installing a single package, which I consider the main use-case of an interactive package manager.

I expect any modern Linux distribution to only transfer absolutely required data to complete my task.

Pain point: no concurrency

Because they need to sequence executing arbitrary package maintainer-provided code (hooks and triggers), all tested package managers need to install packages sequentially (one after the other) instead of concurrently (all at the same time).

In my blog post “Can we do without hooks and triggers?”, I outline that hooks and triggers are not strictly necessary to build a working Linux distribution.

Thought experiment: further speed-ups

Strictly speaking, the only required feature of a package manager is to make available the package contents so that the package can be used: a program can be started, a kernel module can be loaded, etc.

By only implementing what’s needed for this feature, and nothing more, a package manager could likely beat apk’s performance. It could, for example:

• skip archive extraction by mounting file system images (like AppImage or snappy)
• use compression which is light on CPU, as networks are fast (like apk)
• skip fsync when it is safe to do so, i.e.:
  • package installations don’t modify system state
  • atomic package installation (e.g. an append-only package store)
  • automatically clean up the package store after crashes

Current landscape

Here’s a table outlining how the various package managers listed on Wikipedia’s list of software package management systems fare:

Conclusion

As per the current landscape, there is no distribution-scoped package manager which uses images and leaves out hooks and triggers, not even in smaller Linux distributions.

I think that space is really interesting, as it uses a minimal design to achieve significant real-world speed-ups.

I have explored this idea in much more detail, and am happy to talk more about it in my post “Introducing the distri research linux distribution".

Appendix A: related work

There are a couple of recent developments going into the same direction:

• “Revisiting How We Put Together Linux Systems” describes mounting app bundles
• Android Q uses ext4 loopback images
• The Haiku Operating System’s package manager Haiku Depot uses images

Appendix B: measurement details

ack

You can expand each of these:

% docker run -t -i fedora /bin/bash
[root@722e6df10258 /]# time dnf install -y ack
Fedora Modular 30 - x86_64            4.4 MB/s | 2.7 MB     00:00
Fedora Modular 30 - x86_64 - Updates  3.7 MB/s | 2.4 MB     00:00
Fedora 30 - x86_64 - Updates           17 MB/s |  19 MB     00:01
Fedora 30 - x86_64                     31 MB/s |  70 MB     00:02
[…]
Install  44 Packages

Total download size: 13 M
Installed size: 42 M
[…]
real	0m29.498s
user	0m22.954s
sys	0m1.085s

% docker run -t -i nixos/nix
39e9186422ba:/# time sh -c 'nix-channel --update && nix-env -i perl5.28.2-ack-2.28'
unpacking channels...
created 2 symlinks in user environment
installing 'perl5.28.2-ack-2.28'
these paths will be fetched (14.91 MiB download, 80.83 MiB unpacked):
  /nix/store/57iv2vch31v8plcjrk97lcw1zbwb2n9r-perl-5.28.2
  /nix/store/89gi8cbp8l5sf0m8pgynp2mh1c6pk1gk-attr-2.4.48
  /nix/store/gkrpl3k6s43fkg71n0269yq3p1f0al88-perl5.28.2-ack-2.28-man
  /nix/store/iykxb0bmfjmi7s53kfg6pjbfpd8jmza6-glibc-2.27
  /nix/store/k8lhqzpaaymshchz8ky3z4653h4kln9d-coreutils-8.31
  /nix/store/svgkibi7105pm151prywndsgvmc4qvzs-acl-2.2.53
  /nix/store/x4knf14z1p0ci72gl314i7vza93iy7yc-perl5.28.2-File-Next-1.16
  /nix/store/zfj7ria2kwqzqj9dh91kj9kwsynxdfk0-perl5.28.2-ack-2.28
copying path '/nix/store/gkrpl3k6s43fkg71n0269yq3p1f0al88-perl5.28.2-ack-2.28-man' from 'https://cache.nixos.org'...
copying path '/nix/store/iykxb0bmfjmi7s53kfg6pjbfpd8jmza6-glibc-2.27' from 'https://cache.nixos.org'...
copying path '/nix/store/x4knf14z1p0ci72gl314i7vza93iy7yc-perl5.28.2-File-Next-1.16' from 'https://cache.nixos.org'...
copying path '/nix/store/89gi8cbp8l5sf0m8pgynp2mh1c6pk1gk-attr-2.4.48' from 'https://cache.nixos.org'...
copying path '/nix/store/svgkibi7105pm151prywndsgvmc4qvzs-acl-2.2.53' from 'https://cache.nixos.org'...
copying path '/nix/store/k8lhqzpaaymshchz8ky3z4653h4kln9d-coreutils-8.31' from 'https://cache.nixos.org'...
copying path '/nix/store/57iv2vch31v8plcjrk97lcw1zbwb2n9r-perl-5.28.2' from 'https://cache.nixos.org'...
copying path '/nix/store/zfj7ria2kwqzqj9dh91kj9kwsynxdfk0-perl5.28.2-ack-2.28' from 'https://cache.nixos.org'...
building '/nix/store/q3243sjg91x1m8ipl0sj5gjzpnbgxrqw-user-environment.drv'...
created 56 symlinks in user environment
real	0m 14.02s
user	0m 8.83s
sys	0m 2.69s

% docker run -t -i debian:sid
root@b7cc25a927ab:/# time (apt update && apt install -y ack-grep)
Get:1 http://cdn-fastly.deb.debian.org/debian sid InRelease [233 kB]
Get:2 http://cdn-fastly.deb.debian.org/debian sid/main amd64 Packages [8270 kB]
Fetched 8502 kB in 2s (4764 kB/s)
[…]
The following NEW packages will be installed:
  ack ack-grep libfile-next-perl libgdbm-compat4 libgdbm5 libperl5.26 netbase perl perl-modules-5.26
The following packages will be upgraded:
  perl-base
1 upgraded, 9 newly installed, 0 to remove and 60 not upgraded.
Need to get 8238 kB of archives.
After this operation, 42.3 MB of additional disk space will be used.
[…]
real	0m9.096s
user	0m2.616s
sys	0m0.441s

% docker run -t -i archlinux/base
[root@9604e4ae2367 /]# time (pacman -Sy && pacman -S --noconfirm ack)
:: Synchronizing package databases...
 core            132.2 KiB  1033K/s 00:00
 extra          1629.6 KiB  2.95M/s 00:01
 community         4.9 MiB  5.75M/s 00:01
[…]
Total Download Size:   0.07 MiB
Total Installed Size:  0.19 MiB
[…]
real	0m3.354s
user	0m0.224s
sys	0m0.049s

% docker run -t -i alpine
/ # time apk add ack
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/community/x86_64/APKINDEX.tar.gz
(1/4) Installing perl-file-next (1.16-r0)
(2/4) Installing libbz2 (1.0.6-r7)
(3/4) Installing perl (5.28.2-r1)
(4/4) Installing ack (3.0.0-r0)
Executing busybox-1.30.1-r2.trigger
OK: 44 MiB in 18 packages
real	0m 0.96s
user	0m 0.25s
sys	0m 0.07s

qemu

You can expand each of these:

% docker run -t -i fedora /bin/bash
[root@722e6df10258 /]# time dnf install -y qemu
Fedora Modular 30 - x86_64            3.1 MB/s | 2.7 MB     00:00
Fedora Modular 30 - x86_64 - Updates  2.7 MB/s | 2.4 MB     00:00
Fedora 30 - x86_64 - Updates           20 MB/s |  19 MB     00:00
Fedora 30 - x86_64                     31 MB/s |  70 MB     00:02
[…]
Install  262 Packages
Upgrade    4 Packages

Total download size: 172 M
[…]
real	1m7.877s
user	0m44.237s
sys	0m3.258s

% docker run -t -i nixos/nix
39e9186422ba:/# time sh -c 'nix-channel --update && nix-env -i qemu-4.0.0'
unpacking channels...
created 2 symlinks in user environment
installing 'qemu-4.0.0'
these paths will be fetched (262.18 MiB download, 1364.54 MiB unpacked):
[…]
real	0m 38.49s
user	0m 26.52s
sys	0m 4.43s

% docker run -t -i debian:sid
root@b7cc25a927ab:/# time (apt update && apt install -y qemu-system-x86)
Get:1 http://cdn-fastly.deb.debian.org/debian sid InRelease [149 kB]
Get:2 http://cdn-fastly.deb.debian.org/debian sid/main amd64 Packages [8426 kB]
Fetched 8574 kB in 1s (6716 kB/s)
[…]
Fetched 151 MB in 2s (64.6 MB/s)
[…]
real	0m51.583s
user	0m15.671s
sys	0m3.732s

% docker run -t -i archlinux/base
[root@9604e4ae2367 /]# time (pacman -Sy && pacman -S --noconfirm qemu)
:: Synchronizing package databases...
 core       132.2 KiB   751K/s 00:00
 extra     1629.6 KiB  3.04M/s 00:01
 community    4.9 MiB  6.16M/s 00:01
[…]
Total Download Size:   123.20 MiB
Total Installed Size:  587.84 MiB
[…]
real	1m2.475s
user	0m9.272s
sys	0m2.458s

% docker run -t -i alpine
/ # time apk add qemu-system-x86_64
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/community/x86_64/APKINDEX.tar.gz
[…]
OK: 78 MiB in 95 packages
real	0m 2.43s
user	0m 0.46s
sys	0m 0.09s

At the beginning of the month, from 30th June till 5th July, I attended the 9th Molecular Quantum Mechanics Conference in my old home Heidelberg. This occasion was a great opportunity to catch up with friends and colleges both in science and from my old circle in Heidelberg as well.

At the conference I presented a poster entitled Modern interdisciplinary software development in electronic-structure theory. which was highly related to my former talk in Lille a couple of weeks ago. In the poster I wanted to to motivate the use of modern languages and software development techniques and demonstrate its opportunities for enabling different communities (like mathematicians and chemists) to work jointly on the same codes. As examples I discuss three projects of my own.

Out of these, the molsturm code for basis-function-independent method development I have described in detail in our paper last year. Some words about our mathematically-driven approach in the development of the density-functional toolkit (DFTK) I already gave in my previous article. In this article I will thus focus on the third code presented on the poster, namely adcc, short for ADC connect.

The adcc project is a project I started a few years ago during my time at the Dreuw group in Heidelberg. I continue to work on it as a side project during my time at the CERMICS, jointly with some of my old group members. Our main aim is to provide one independent building block for excited states computations using the algebraic-diagrammatic construction (ADC). This means that adcc does not implement any self-consistent field algorithm itself, much rather it runs on top of any Hartree-Fock code. In practice as of now four SCF codes have been connected to adcc via our Python interface, including pyscf, Psi4 and molsturm. But Python is not only used as a glue language between SCF and ADC, much rather it allows to orchestrate the full computational procedure. See the attached poster or the introductory chapter of the adcc documentation for some examples.

A third aspect where Python plays a crucial role in adcc are the iterative solver algorithms. For example the Davidson procedure we use for solving the ADC equations is implemented purely in high-level Python code. This allows to rapidly investigate new numerical schemes and approaches in the context of ADC. We are, however, not loosing too much performance by this choice, because the time-consuming tensor contractions we require are still done in a C++ core library and only called from Python. Inside our core library we in turn use the libtensor code for tensor computations. Overall adcc therefore shows a comparable performance to the adcman code, a pure C++ implementation of ADC also developed in Heidelberg on top of libtensor.

Currently adcc is not yet publicly available, but we are in the stage of finalising adcc for a first public release within the Gator framework. A first standalone release of the code is planned within the upcoming months as well. The adcc documentation, however, is already available and gives an idea of adcc in practice.

As usual I attach my poster as a pdf below.

Link	Licence
Poster Modern interdisciplinary software development in electronic structure theory

Hooks are an extension feature provided by all package managers that are used in larger Linux distributions. For example, Debian uses apt, which has various maintainer scripts. Fedora uses rpm, which has scriptlets. Different package managers use different names for the concept, but all of them offer package maintainers the ability to run arbitrary code during package installation and upgrades. Example hook use cases include adding daemon user accounts to your system (e.g. postgres), or generating/updating cache files.

Triggers are a kind of hook which run when other packages are installed. For example, on Debian, the man(1) package comes with a trigger which regenerates the search database index whenever any package installs a manpage. When, for example, the nginx(8) package is installed, a trigger provided by the man(1) package runs.

Over the past few decades, Open Source software has become more and more uniform: instead of each piece of software defining its own rules, a small number of build systems are now widely adopted.

Hence, I think it makes sense to revisit whether offering extension via hooks and triggers is a net win or net loss.

Hooks preclude concurrent package installation

Package managers commonly can make very little assumptions about what hooks do, what preconditions they require, and which conflicts might be caused by running multiple package’s hooks concurrently.

Hence, package managers cannot concurrently install packages. At least the hook/trigger part of the installation needs to happen in sequence.

While it seems technically feasible to retrofit package manager hooks with concurrency primitives such as locks for mutual exclusion between different hook processes, the required overhaul of all hooks¹ seems like such a daunting task that it might be better to just get rid of the hooks instead. Only deleting code frees you from the burden of maintenance, automated testing and debugging.

① In Debian, there are 8620 non-generated maintainer scripts, as reported by find shard*/src/*/debian -regex ".*\(pre\|post\)\(inst\|rm\)$" on a Debian Code Search instance.

Triggers slow down installing/updating other packages

Personally, I never use the apropos(1) command, so I don’t appreciate the man(1) package’s trigger which updates the database used by apropos(1). The process takes a long time and, because hooks and triggers must be executed serially (see previous section), blocks my installation or update.

When I tell people this, they are often surprised to learn about the existance of the apropos(1) command. I suggest adopting an opt-in model.

Unnecessary work if programs are not used between updates

Hooks run when packages are installed. If a package’s contents are not used between two updates, running the hook in the first update could have been skipped. Running the hook lazily when the package contents are used reduces unnecessary work.

As a welcome side-effect, lazy hook evaluation automatically makes the hook work in operating system images, such as live USB thumb drives or SD card images for the Raspberry Pi. Such images must not ship the same crypto keys (e.g. OpenSSH host keys) to all machines, but instead generate a different key on each machine.

Why do users keep packages installed they don’t use? It’s extra work to remember and clean up those packages after use. Plus, users might not realize or value that having fewer packages installed has benefits such as faster updates.

I can also imagine that there are people for whom the cost of re-installing packages incentivizes them to just keep packages installed—you never know when you might need the program again…

Implemented in an interpreted language

While working on hermetic packages (more on that in another blog post), where the contained programs are started with modified environment variables (e.g. PATH) via a wrapper bash script, I noticed that the overhead of those wrapper bash scripts quickly becomes significant. For example, when using the excellent magit interface for Git in Emacs, I encountered second-long delays² when using hermetic packages compared to standard packages. Re-implementing wrappers in a compiled language provided a significant speed-up.

Similarly, getting rid of an extension point which mandates using shell scripts allows us to build an efficient and fast implementation of a predefined set of primitives, where you can reason about their effects and interactions.

② magit needs to run git a few times for displaying the full status, so small overhead quickly adds up.

Incentivizing more upstream standardization

Hooks are an escape hatch for distribution maintainers to express anything which their packaging system cannot express.

Distributions should only rely on well-established interfaces such as autoconf’s classic ./configure && make && make install (including commonly used flags) to build a distribution package. Integrating upstream software into a distribution should not require custom hooks. For example, instead of requiring a hook which updates a cache of schema files, the library used to interact with those files should transparently (re-)generate the cache or fall back to a slower code path.

Distribution maintainers are hard to come by, so we should value their time. In particular, there is a 1:n relationship of packages to distribution package maintainers (software is typically available in multiple Linux distributions), so it makes sense to spend the work in the 1 and have the n benefit.

Can we do without them?

If we want to get rid of hooks, we need another mechanism to achieve what we currently achieve with hooks.

If the hook is not specific to the package, it can be moved to the package manager. The desired system state should either be derived from the package contents (e.g. required system users can be discovered from systemd service files) or declaratively specified in the package build instructions—more on that in another blog post. This turns hooks (arbitrary code) into configuration, which allows the package manager to collapse and sequence the required state changes. E.g., when 5 packages are installed which each need a new system user, the package manager could update /etc/passwd just once.

If the hook is specific to the package, it should be moved into the package contents. This typically means moving the functionality into the program start (or the systemd service file if we are talking about a daemon). If (while?) upstream is not convinced, you can either wrap the program or patch it. Note that this case is relatively rare: I have worked with hundreds of packages and the only package-specific functionality I came across was automatically generating host keys before starting OpenSSH’s sshd(8)³.

There is one exception where moving the hook doesn’t work: packages which modify state outside of the system, such as bootloaders or kernel images.

③ Even that can be moved out of a package-specific hook, as Fedora demonstrates.

Conclusion

Global state modifications performed as part of package installation today use hooks, an overly expressive extension mechanism.

Instead, all modifications should be driven by configuration. This is feasible because there are only a few different kinds of desired state modifications. This makes it possible for package managers to optimize package installation.

Often enough shellscripts are the quickest solution to a given problem. However, writing shellscripts is just as hard as using any other programming language, as for example Valve (or rather Steam users) found out the hard way.

However, there are options you can set to make your shellscripts safer, which others have elaborated on already very nicely, therefore we will not look at it in detail here but instead recommend to take a look there. Just briefly, these options summarize to set -eEuo pipefail and make your script terminate on the first command exiting non-zero (including non-zero-exiting commands within a pipe chain) and when you try to use unset variables if set at the beginning of your shellscript. The aforementioned error in the steam-uninstall-script would have been prevented by this.

However, you will have to set these options in every single script. You could put them into your .bashrc, for example, but not all scripts out there and on your system might be written with this option set in mind. As adding these options into every single of your scripts might sound tedious, there is a better solution: writing a shell that is safe by default!

Implementing a safe bash

To do so we recognize that most scripts nowadays start with a line starting with the shebang: #!/path/to/interpreter. In the case of bash this is typically #!/bin/bash.

To be able to simply invoke a safebash instead of bash at this point, create a file /usr/local/bin/safebash containing

#!/bin/bash

# exit immediately when a command fails
set -e

# abort on attempting to use an undefined variable (hello Valve! :))
set -u

# set exitcode of a pipe chain to the exit code of the rightmost
# command not exiting with zero, if there are any
# in combination with -e this aborts on failure within a pipe chain
set -o pipefail

# make functions inherit ERR-traps, so that they fire when set -e takes effect there
set -E

# let subshells inherit these options
export SHELLOPTS

bash "$@"

and make it executable with chmod +x /usr/local/bin/safebash

You can now start your shellscript-file with #!/usr/local/bin/safebash instead of #!/bin/bash and all the aforementioned options will be active without specifying anything explicitly.

tl;dr: I provide a very high-level overview of what Go-the-language means vs. Go-the-ecosystem vs. Go-an-implementation. I also try to provide specific references to what documentation is most useful for what purpose. See the bottom-most section for that.

When we talk about "Go", depending on context, we can mean very different things. This is my attempt at providing a very high-level overview of the language and ecosystem and to link to the relevant documentation about how each part fits together (it's also a bit of a hodgepodge though, addressing individual random questions I encountered recently). So, let's dive in:

The Go programming language

The bottom turtle is Go, the programming language. It defines the format and meaning of source code and the authoritative source is the Go language specification. If something doesn't conform to the spec, it's not "Go". And conversely, if something isn't mentioned in the spec it's not part of the language. The language spec is maintained by the Go team and versioned, with a new release roughly every six months. At the time I wrote this post, the newest release was version 1.12.

The domain of the spec are

• The grammar of the language
• Types, values and their semantics
• What identifiers are predeclared and what their meaning is
• How Go programs get executed
• The special package unsafe (though not all of its semantics)

The spec alone should enable you to write a compiler for Go. And indeed, there are many different compilers.

A Go compiler and runtime

The language spec is a text document, which is not useful in and of itself. For that you need software that actually implements these semantics. This is done by a compiler (which analyzes and checks the source code and transforms it into an executable format) and a runtime (which provides the necessary environment to actually run the code). There are many such combinations and they all differ a bit more or a bit less. Examples are

• gc, a compiler and runtime written in pure Go (with some assembly) by the Go team themselves and versioned and released together with the language. Unlike other such tools, gc doesn't strictly separate the compiler, assembler and linker - they end up sharing a lot of code and some of the classical responsibilities move or are shared between them. As such, it's in general not possible to e.g. link packages compiled by different versions of gc.
• gccgo and libgo, a frontend for gcc and a runtime. It's written in C and maintained by the Go team. It lives in the gcc organization though and is released according to the gcc release schedule and thus often lags a bit behind the "latest" version of the Go spec.
• llgo, a frontend for LLVM. I don't know much else about it.
• gopherjs, compiling Go code into javascript and using a javascript VM plus some custom code as a runtime. Long-term, it'll probably be made obsolete by gc gaining native support for WebAssembly.
• tinygo, an incomplete implementation targeting small code size. Runs on either bare-metal micro-controllers or WebAssembly VMs, with a custom runtime. Due to its limitations it doesn't technically implement Go - notably, it doesn't include a garbage collector, concurrency or reflection.

There are more, but this gives you an overview over the variety of implementations. Each of these made potentially different choices for how to implement the language and have their own idiosyncrasies. Examples (some of them a bit exotic, to illustrate) where they might differ are:

• Size of int/uint - the language allows them to be either 32 or 64 bit wide.
• How fundamental functionalities of the runtime, like allocation, garbage collection or concurrency are implemented.
• The order of ranging over a map isn't defined in the language - gc famously explicitly randomizes it, gopherjs uses (last time I checked) whatever the javascript implementation you are running on uses.
• How much extra space append allocates if it needs to - not however, when it allocates extra space.
• How conversions between unsafe.Pointer and uintptr happen. gc, in particular, comes with its own set of rules regarding when these conversions are valid and when they aren't. In general, the unsafe package is virtual and implemented in the compiler.

In general, relying on details not mentioned in the spec (in particular the ones mentioned here) makes your program compile with different compilers, but not work as expected. So you should avoid it if possible.

If you install Go via a "normal" way (by downloading it from the website, or installing it via a package manager), you'll get gc and the official runtime by the Go team. And if the context doesn't imply otherwise, when we talk about how "Go does things", we usually refer to gc. It's the main implementation.

The standard library

The standard library is a set of packages that come with Go and can be relied upon to immediately build useful applications with. It too is maintained by the Go team and versioned and released together with the language and compiler. In general the standard library of one implementation will only work with the compiler it comes with. The reason is that most (but not all) of the runtime is part of the standard library (mainly in the packages runtime, reflect, syscall). As the compiler needs to generate code compatible with the used runtime, both need to come from the same version. The API of the standard library is stable and won't change in incompatible ways, so a Go program written against a given version of the standard library will continue to work as expected with future versions of the compiler.

Some implementations use their own version of some or all of the standard library - in particular, the runtime, reflect, unsafe and syscall packages are completely implementation-defined. As an example, I believe that AppEngine Standard used to re-define parts of the standard library for security and safety. In general, implementations try to make that transparent to the user.

There is also a separate set of repositories, colloquially referred to as x or "the subrepositories". They contain packages which are developed and maintained by the Go team with all the same processes, but are not on the same release schedule as the language and have less strict compatibility guarantees (and commitment to maintainership) than Go itself. The packages in there are either experimental (for potential future inclusion in the standard library), not widely useful enough to be included in the standard library or, in rare cases, a way for people on the Go team to work on code using the same review processes they are used to.

Again, when referring to "the standard library" devoid of extra context, we mean the officially maintained and distributed one, hosted on golang.org.

The build tool

To make the language user-friendly, you need a build tool. The primary role of this tool is to find the package you want to compile, find all of its dependencies, and execute the compiler and linker with the arguments necessary to build them. Go (the language) has support for packages, which combine multiple source files into one unit of compilation. And it defines how to import and use other packages. But importantly, it doesn't define how import paths map to source files or how they are laid out on disk. As such, each build tool comes with its own ideas for this. It's possible to use a generic build tool (like Make) for this purpose, but there are a bunch of Go-specific ones:

• The go tool¹ is the build tool officially maintained by the Go team. It is versioned and released with the language (and gc and the standard library). It expects a directory called GOROOT (from an environment variable, with a compiled default) to contain the compiler, the standard library and various other tools. And it expects all source code in a single directory called GOPATH (from an environment variable, defaulting to $HOME/go or equivalent). Specifically, package a/b is expected to have its source at $GOPATH/src/a/b/c.go etc. And $GOPATH/src/a/b is expected to only contain source files of one package. It also has a mechanism to download a package and its dependencies recursively from an arbitrary server, in a fully decentralized scheme, though it does not support versioning or verification of downloads. The go tool also contains extra tooling for testing Go code, reading documentation (golang.org is served by the Go tool), file bugs, run various tools…
• gopherjs comes with its own build tool, that largely mimics the Go tool.
• gomobile is a build tool specifically to build Go code for mobile operating systems.
• dep, gb, glide,… are community-developed build-tools and dependency managers, each with their own approach to file layout (some are compatible with the go tool, some aren't) and dependency declarations.
• bazel is the open source version of Google's own build system. While it's not actually Go-specific, I'm mentioning it explicitly due to common claims that idiosyncrasies of the go tool are intended to serve Google's own use cases, in conflict with the needs of the community. However, the go tool (and many public tools) can't be used at Google, because bazel uses an incompatible file layout.

The build tool is what most users directly interface with and as such, it's what largely determines aspects of the Go ecosystem and how packages can be combined and thus how different Go programmers interact. As above, the go tool is what's implicitly referred to (unless other context is specified) and thus its design decisions significantly influence public opinion about "Go". While there are alternative tools and they have wide adoption for use cases like company-internal code, the open source community in general expects code to conform to the expectations of the go tool, which (among other things) means:

• Be available as source code. The go tool has little support for binary distribution of packages, and what little it has is going to be removed soon.
• Be documented according to the godoc format.
• Have tests that can be run via go test.
• Be fully compilable by a go build (together with the next one, this is usually called being "go-gettable"). In particular, to use go generate if generating source-code or metaprogramming is required and commit the generated artifacts.
• Namespace import paths with a domain-name as the first component and have that domain-name either be a well-known code hoster or have a webserver running on it, so that go get works and can find the source code of dependencies.
• Have one package per directory and use build constraints for conditional compilation.

The documentation of the go tool is very comprehensive and probably a good starting point to learn how Go implements various ecosystem aspects.

Tools

Go's standard library includes several packages to interact with Go source code and the x/tools subrepo contains even more. As a result (and due to a strong desire to keep the canonical Go distribution lean), Go has developed a strong culture of developing third-party tools. In general, these tools need to know where to find source code, and might need access to type information. The go/build package implements the conventions used by the Go tool, and can thus also serve as documentation for parts of its build process. The downside is that tools built on top of it sometimes don't work with code relying on other build tools. That's why there is a new package in development which integrates nicely with other build tools.

By its nature the list of Go tools is long and everybody has their own preferences. But broadly, they contain:

• Tools developed by the Go team and released as part of the distribution.
• This includes tools for automatically formatting source code, coverage testing, runtime tracing and profiling, a static analyzer for common mistakes and a mostly obsolete tool to migrate code to new Go versions. These are generally accesed via go tool <cmd>.
• Tools developed by the Go team and maintained out-of-tree. This includes tools to write blog posts and presentations, easily do large refactors, automatically find and fix import paths and a language server.
• Third-party tools - too many to count. There are many lists of these; here is one.

In Summary

I wanted to end this with a short list of references for beginners who feel lost. So this is where you should go, if you:

• Want to start learning Go.
• Want to understand how a specific language construct works.
• Want to nitpick what is or is not valid Go and why.
• Want documentation about what the go tool does Also available via go help. It sometimes references other topics, that you can also see on the web, but not nicely.
• Want to write code that adheres to community standards.
• Want to test your code.
• Want to find new packages or look at documentation of public packages.

There are many more useful supplementary documents, but this should serve as a good start. Please let me know on Twitter if you are a beginner and there's an area of Go you are missing from this overview (I might follow this up with more specific topics), or a specific reference you found helpful. You can also drop me a note if you're a more experienced Gopher and think I missed something important (but keep in mind that I intentionally left out most references, so as to keep the ways forward crisp and clear :) ).

[1] Note: The Go team is currently rolling out support for modules, which is a unit of code distribution above packages, including support for versioning and more infrastructure to solve some issues with the "traditional" go tool. With that, basically everything in that paragraph becomes obsolete. However, for now the module support exists but is opt-in. And as the point of this article is to provide an overview of the separation of concerns, which doesn't actually change, I felt it was better to stay within ye olden days - for now.

A few weeks ago, on 23rd May I received an invitation to visit the Laboratoire de Physique des Lasers, Atomes et Molécules at the Université de Lille and present about my recent work. When it came to selecting a topic, me and my host, Andre Gomes, quickly agreed to focus on discussing more modern approaches to scientific software development and why these can be useful for electronic-structure codes. In retrospect I am very happy for this opportunity to summarise a few ideas and learned lessons from my previous and ongoing software projects. I also took the liberty to sketch possible challenges when it comes to future directions of scientific software from my personal point of view as well as propose some ideas how to tackle them.

From this angle I ended up introducing the talk by a review of the fundamental difficulties of electronic structure theory itself, namely the inherent complexity of the problem (large dimensionality and non-linearity of the respective partial-differential equations). Added to that in recent years the available high-performance computing (HPC) environments have become more heterogeneous and more complex as well. Mixed general-purpose GPU / CPU cluster setups are now standard and making use of both CPU and GPU for computations has become a strict requirement for applying for access to the top-ranked clusters of the world. Projecting into the future, where further "accelerators" such as field-programmable gate arrays (FPGAs), or even more long term quantum computers, might come up, this heterogeneity is only going to increase.

For quickly testing the usefulness of such technologies in the context of quantum chemistry, a key aspect is to be able to reuse the code, which already exists. This means that code needs to be sufficiently high-level in order to be able to adapt to changing hardware architectures. Let be be clear on this: I am not talking about achieving 100% peak performance on every hardware setup, much rather about having a good compromise between the required effort to get the code to work on new hardware and the achieved performance. The point is to quickly get an idea on what is theoretically possible and if further investigation even makes sense.

As I sketch in the talk, changing the hardware, does have an impact on questions such as the optimal basis function, numerical algorithm or even the best-suited physical model. In this "suitable" and "optimal" refers to a simulation procedure, which agrees with the available computational architecture and at the same time is physically meaningful. A consequence of this observation is that experimentation on all levels (basis functions, algorithms, numerics, linear algebra backend) is required, which often calls for interdisciplinary expertise. In an ideal world experts from different fields can thus work on the same code base, approaching the problem from various different angles.

Without a doubt this is a huge task and chances are, that this goal will in fact never be reached. Still I think, there are some opportunities to get a little closer than presently. For this purpose, key aspects are high-level and dynamic programming languages like Julia and python and a clear, modular code design, where individual aspects of the simulation procedure can be easily modified or swapped. Such an approach helps in practice to investigate different basis functions or swap computational backends with only negligible changes to the code base, as I discuss with reference to the molsturm and the DFTK codes (see below). The ability to approach the physical problem on a high level allows mathematicians and physicists to interact with the code abstractly, while computer scientists still have the freedom to tweak performance on a lower level.

I have already discussed the basis-function independent quantum chemistry package molsturm and related work a few times, so I'll skip that in this article. Instead I want to detail some aspects of a more recent project, DFTK.jl, the density-functional toolkit. The idea of this code is to be simple and minimalistic, using existing libraries and codes as much as possible. This makes the code a lot more accessible, which facilitates to construct reduced models, which can be treated in mathematical proof. The hope is that the lessons learned can than be scaled in the same code base to larger and more realistic problems and an HPC environment. The choice of programming language for this project is julia, since it is a high-level and dynamical, but strongly typed language with an impressive performance and out-of-the-box compatibility with existing libraries written in C++, Fortran, python or R. Using features such as multiple dispatch and JIT (just-in-time) compilation of code, Julia seems to be a big step forwards in the direction, where code is written once and then can be translated many times for specific computational backends or hardware. I already presented about Julia in a previous talk a few weeks ago.

All in all I am very thankful for Andre for giving me the opportunity to gather some thoughts about this matter and eventually present them in this talk. The audience in Lille was surprisingly open about the topic and to my big surprise many interesting discussions arose. Throughout the afternoon I spent time with PhD students and staff researchers discussing my ideas in their application context, leading to loads of interesting feedback, helpful ideas, questions and comments. The time in Lille truly flew by very quickly with may aspects still undiscussed after the day. Luckily we all agreed to stay in touch, such that the discussions will likely continue during other meetups in the future.

The slides and the Jupyter notebooks I used during the talk are attached below.

Link	Licence
Modern software-development techniques in electronic structure theory (Slides)
A 5-minute introduction to Julia (Jupyter notebook)