Title: The Expressive C++ Coding Challenge in D

Author: Bob Schmidt

Date: 06 March 2018 16:22:44 +00:00 or Tue, 06 March 2018 16:22:44 +00:00

Summary: Sebastian Wilzbach presents a D language solution to a C++ problem.

Body:

You might have seen that I have been coding a lot in D lately and as a few weeks ago there was the â€˜Expressive C++17 Coding Challengeâ€™ [1] with its solution in C++ [2] and Rust [3] now being public, I thought this is an excellent opportunity to show why I like D so much.

The requirements

Let me first recap the requirements of this challenge:

This command line tool should accept the following arguments:

the filename of a CSV file,
the name of the column to overwrite in that file,
the string that will be used as a replacement for that column,
the filename where the output will be written.

./program <input.csv> <colum-name> <replacement-
string> <output.csv>

Example input

Given this simple CSV as input

  name,surname,city,country
  Adam,Jones,Manchester,UK
  Joe,Doe,Cracow,Poland
  Michael,Smith,Paris,France
  Alex,McNeil,Gdynia,Poland

the program called with:

  ./program input.csv city London output.csv

should write:

  name,surname,city,country
  Adam,Jones,London,UK
  Joe,Doe,London,Poland
  Michael,Smith,London,France
  Alex,McNeil,London,Poland

Sounds fairly trivial, right?

Please have a short look first at the â€˜bestâ€™ C++ [4] and Rust [3] solutions before you look at the D solution.

The solution

Okay, so Listing 1 is one way to solve this in D.

#!/usr/bin/env rdmd
import std.algorithm, std.exception, std.format, std.range, std.stdio;
void main(string[] args) {
  enforce(args.length == 5, "Invalid args\n" ~
  "./tool <input.csv> <colum-name>
    <replacement-string> <output.csv>");
  auto inFile = args[1], columName = args[2],
    replacement = args[3], outFile = args[4];
  auto lines = File(inFile).byLine.map!(a
    => a.splitter(","));
  auto colIndex = lines.front.countUntil(
    columName);
  enforce(colIndex >= 0,
    "Invalid column. Valid columns: %(%s,
    %)".format(lines.front));
  auto os = File(outFile, "w");
  os.writefln("%(%s, %)", lines.front);
  foreach (line; lines.dropOne) {
    auto r = line
      .enumerate // iterate with an (index,
                 // value) tuple
      .map!(a => a.index == colIndex
         ? replacement : a.value)
      .joiner(",");
    os.writeln(r);
  }
}

Listing 1

If you are scared at the moment â€“ donâ€™t worry. I will explain it line by line below.

So how does this compare to C++17 and Rust?

Language	LoC	Time
C++	125	15s
Rust	83	6s
D	19	12s
D (slightly tweaked)	25	6s

Later in the article I will present a solution which only uses 12 lines, but it also uses the built-in std.csv module and I think D doesnâ€™t need to cheat.

I used the following D script to generate a simple CSV file with 10 fields and 10 million lines:

  rdmd --eval='10.iota.map!(
    a=> "field".text(a)).join(",")
  .repeat(10_000_000).joiner("\n").writeln'
    > input_big.csv

The resulting input_big.csv has a size of 668M.

Arenâ€™t you concerned that Rust is faster in this benchmark?

Not at all. The challenge was to write expressive code.

When performance really matters, D provides the same tools as C or C++ and D even supports native interoperability with C and most of C++.

In this example, however, I/O is the bottleneck and D provides a few convenience features like using locked file handles, s.t. accessing files is thread-safe by default, or supporting unicode input.

However, itâ€™s easy to opt out of such productivity features and use other tricks like memory mapped files [5]. For interested readers, I have included a slightly optimized version at the end (Listing 6).

In addition, if you are interested in performance, Jon Degenhardt (member of eBayâ€™s data science team), has made an excellent performance benchmark [6] between eBayâ€™s tsv-utils and existing CSV/TSV processing tools written in C, Go, and Rust.

1) What is #!/usr/bin/env rdmd?

One of my favorite parts of D is that it has a blazingly fast compiler. Period. I can compile the entire D front-end of the compiler (~200 kLoC) in less than two seconds or the entire standard library with lots and lots of compile-time function evaluation and templates and > 300 kLoC in 5 seconds from scratch without any cache or incremental compilation.

This means that the compiler is almost as fast as an interpreter and the rdmd tool allows you to use D as â€˜pseudo-interpretedâ€™ language. You can invoke rdmd with any file and it will automatically figure out all required files based on your dependencies and pass them to the compiler.

Itâ€™s very popular in the D community because for small scripts one doesnâ€™t even notice that the program is compiled to real machine code under the hood. Also if the shebang header is added and the file is executable, D scripts can be used as if they were script files:

  ./main.d input.csv city London output.csv

2) So you import a bunch of libraries. What do they do?

  import std.algorithm, std.exception, std.format,
  std.range, std.stdio;

In short std.stdio is for input and output, std.range is about Dâ€™s magic streams called â€˜rangesâ€™ and std.algorithm abstracts on top of them and provides generic interfaces for a lot of sophisticated algorithms.

Moreover, std.exception offers methods for working with exceptions like enforce and finally std.format bundles methods for string formatting.

Donâ€™t worry â€“ the functionality imported from these modules will be explained soon.

3) Your program has a main function. Whatâ€™s so special about it compared to C or C++?

  void main(string[] args) {
    â€¦

For starters, arrays in D have a length. Try:

  args[5].writeln;

Compared to C/C++ null-terminated strings and arrays, it wonâ€™t segfault. It would just throw a nice Error (see Figure 1).

core.exception.RangeError@./main.d(10): Range violation
----------------
??:? _d_arrayboundsp [0x43b622]
prog.d:9 void main.foo(immutable(char)[][]) [0x43ac93]
prog.d:4 _Dmain [0x43ac67]

Figure 1

Oh so D performs automatic bounds-checking before accessing the memory. Isnâ€™t that expensive?

Itâ€™s almost negligible compared to the safety it buys, but D is a language for everyone, so the people who want to squeeze out the last cycles of their processor can do so by simply compiling with -boundscheck=off (for obvious reasons this isnâ€™t recommended).

In D, strings are arrays too and thereâ€™s another nice property about Dâ€™s arrays. They are only a view on the actual memory and you donâ€™t copy the array, but just the view of the memory (in D itâ€™s called a slice).

Consider this example:

  int[] arr = [1, 2, 3];
  auto bArr = arr[1 .. $];
  bArr[] += 2; // this is a vectorized operation

  arr.writeln; // [1, 4, 5]

There many other things D has learned from C and C++.

Walter has recently written a great article [7] on how D helps to vanquish forever these bugs that blasted your kingdom, which I highly recommend if you have a C/C++ background.

4) Whatâ€™s up with this â€˜enforceâ€™?

  enforce(args.length == 5, "Invalid args.\n" ~
  "./tool <input.csv> <colum-name> <replacement-
    string> <output.csv>");

I have never seen the ~ operator before!

Itâ€™s the string concatenation (or more general array concatenation) operator. How often how you encountered code like a + b and needed to know the types of a and b to know whether itâ€™s a addition or concatenation?

Why donâ€™t you use an if statement and terminate the program explicitly?

  if (args.length < 5) {
    writeln("Invalid args.");
    writeln("./tool <input.csv> <colum-name>
      <replacement-string> <output.csv>");
    return 1;
  }

Thatâ€™s valid D too. D allows a lot of different programming styles, but this article is intended to highlight a few specific D styles like enforce.

enforce [8] is a function defined in std.exception and throws an exception if its first argument has a falsy value.

Hmm, I looked at the documentation [8] and saw this monster. I thought it simply throws an exception?

  auto enforce(E : Throwable = Exception, T)
    (T value, lazy string msg = null, string file =
    __FILE__, size_t line = __LINE__)

I donâ€™t have the time to fully dive into Dâ€™s syntax, but auto instructs the compiler to infer the return type for you. This leads to the interesting Voldemort return types [9] as they canâ€™t be named by the user, but thatâ€™s a good topic for another article.

The next part looks a bit complicated (E : Throwable = Exception, T), but donâ€™t worry yet. It means that E is a template parameter which needs to inherit from Throwable (the root of all exceptions), and is by default Exception. T is the template type of value.

Wait. I just instantiated a template without specifying its template parameters?

Yes, the D compiler does all the hard work for you.

The technical term is Implicit Function-Template Instantiation [10] (IFTI). Of course, we could have instructed enforce to throw a custom exception, but more on template instantiation later.

Alright. So this function takes a generic value and a msg, but a lazy string msg?

lazy is a special keyword in D and tells the compiler to defer the evaluation of an argument expression until is actually needed.

I donâ€™t understand. msg seems to be a string concatenation of two strings. Isnâ€™t this done before the enforce is called?

  "Invalid args.\n" ~ "./tool <input.csv>
    <colum-name> <replacement-string> <output.csv>"

No, lazy is lazy and the string concatenation doesnâ€™t happen at the caller site, but can be requested explicitly by the callee.

It gets a bit clearer if we look at the second enforce:

  enforce(colIndex < 0, "Invalid column name. Valid
    are: %(%s, %)".format(lines.front));

format and all the expensive work of formatting the error message is never done on the default path, but only if an exception actually gets thrown. Ignore the %(%s, %) formatting string for a bit, it will be explained soon.

Ok, but how does that work?

In short: the compiler performs some smart formatting for you and creates an anonymous lambda. For more details, see this advanced article about Dâ€™s lazy [10].

But thereâ€™s more magic here. Whatâ€™s __FILE__ and __LINE__?

  string file = __FILE__, size_t line = __LINE__

Remember that D is a compiled language and accessing the stack isnâ€™t as easy as asking the interpreter nicely. These two default arguments are automatically set by the compiler with the file and line number of the caller. This is important for logging or throwing exceptions like we have done here.

So an API author can simply say â€œHey, I would like to know the line number of my caller.â€ and doesnâ€™t depend on the user hacking the replacements as youâ€™d have to do in C/C++ with the preprocessor macros:

  #ifdef SPDLOG_DEBUG_ON
  #define SPDLOG_DEBUG(logger, ...) logger-> \
    debug(__VA_ARGS__)  << " (" << __FILE__  \
    << " #" << __LINE__ <<")";
  #else
  #define SPDLOG_DEBUG(logger, ...)
  #endif

In fact, D doesnâ€™t even have a preprocessor.

5) auto and a statically typed language

  auto inFile = args[1], columName = args[2],
    replacement = args[3], outFile = args[4];

Hmm, but whatâ€™s auto? I thought D was a statically typed system?

Yes D is statically typed, but the compiler is pretty smart, so we can let it do all the hard for us. auto is a filler word for the compiler that means â€˜whatever the type of the assignment, use this as type of this variableâ€™.

6) What the hell is UFCS?

  auto lines = File(inFile).byLine.map!(a =>
    a.splitter(","));

One of the major features of D is the Unified Function Call Syntax (UFCS) [11]. In short, the compiler will look up a function in the current namespace if itâ€™s not found as a member function of a type, but letâ€™s go through this step by step.

I looked at the documentation of File [12] and it has a method byLine [13]. So whereâ€™s the magic?

Have another look at map [14], itâ€™s located in std.algorithm.

Okay, wait. How does this work?

The compiler internally rewrites the expression File.byLine.map to the following:

  map(File.byLine());

Missing parenthesis are allowed too â€“ after all, the compiler knows that the symbol is a function.

Okay, but whatâ€™s up with this !(a => a.splitter(",")))?

! is similar to C++/Javaâ€™s <> and declares a template. In this case itâ€™s a lambda function of a => a.splitter(","). Notice that for splitter [15], UFCS is used again and your brain might be more used to reading splitter(a, ",") for now.

7) Ranges

Okay to recap, we have taken the input of a file, and split lines using commas ,.

Wouldnâ€™t this result in a lot of unnecessary allocation?

The short answer is: D uses â€˜iterators on steroidsâ€™ which are lazy and work is only done when explicitly requested. Usually range algorithms donâ€™t even require any heap allocation as everything is done on the stack.

For example, in the next line .front returns the first line through which countUntil explicitly iterates:

  auto colIndex =
    lines.front.countUntil(columnName);

So lines.front looks something like:

  ["name", "surname", "city", "country"]

countUntil will return the line of the first match or -1 otherwise. Itâ€™s a bit similar to an indexOf function familiar from, for example, JavaScript, but it accepts a template. So we could have supplied a custom predicate function:

  lines.front.countUntil!(a => a.endsWith("ty"));

8) std.format: and compile-time checking of parameters

The next lines are:

  enforce(colIndex >= 0, "Invalid column name.
    Valid are: %(%s, %)".format(lines.front));
  auto os = File(outFile, "w");
  os.writefln("%(s, %)", lines.front);

I have never seen writefln("%(s, %)") before. What happens here?

writefln [16] is just a handy wrapper around Dâ€™s format [17] function.

format itself provides a lot of options for serialization, but itâ€™s very similar to printf, although it does provide a few goodies like the special syntax for arrays %(s, %).

This syntax opens an array formatting â€˜scopeâ€™ delimited by %( and closes it with %). Within this array â€˜scopeâ€™ the elements should be formatted with s (their string serialization) and use ,, a delimiter between the element.

Itâ€™s a shorthand syntax that often comes in handy, but if you donâ€™t like it there are many other ways to achieve the same result. For example, joiner:

  lines.front.joiner(",").writeln;

What would such an error message look like?

It would look like Figure 2.

  object.Exception@./main.d(9): Invalid column name. Valid are: "name", "surname", "city", "country"
----------------
??:? pure @safe void std.exception.bailOut!(Exception).bailOut(immutable(char)[], ulong, const(char[])) [0x7a34b57e]
??:? pure @safe bool std.exception.enforce!(Exception, bool).enforce(bool, lazy const(char)[], immutable(char)[], ulong) [0x7a34b4f8]
??:? _Dmain [0x7a34b17f]

Figure 2

Okay, but isnâ€™t printf bad and unsafe? I heard that languages like Python are moving away from C-like formatting.

A Python library can only realize that arguments and formatted string donâ€™t fit when itâ€™s called. In D the compiler knows the types of the arguments and if you pass the format string at compile-time, guess what, the format can be checked compile-time. Try to compile a format string that tries to format strings as numbers:

  writefln!"%d"("foo");

The compiler will complain:

  /dlang/dmd/linux/bin64/../../src/phobos/std/
  stdio.d(3876): Error: static assert  "Incorrect
  format specifier for range: %d"
  onlineapp.d(4):        instantiated from here:
  writefln!("%d", string)

Wow, thatâ€™s really cool. How does this work?

D has another unique feature: compile-time function evaluation (CTFE) that allows to execute almost any function at compile-time. All that happens is that writefln is instantiated at compile-time with the string as template argument and then it calls the same format function that would normally be called at run-time with the known string. The coolest part about this is that thereâ€™s no special casing in the compiler and everything is just a few lines of library code.

9) Letâ€™s parse the file

Now that we have found the index of the replacement column, have opened the output csv file and have already written the header to it, all thatâ€™s left is to go over the input CSV file line by line and replace the specific CSV column with the replacement (Listing 2).

foreach (line; lines.dropOne)
  // remove the header
{
  auto r = line
    .enumerate // iterate with an (index, value)
             // tuple and lazily map a different
             // value for the specific CSV column
    .map!(a => a.index == colIndex ? replacement
      : a.value),
    .joiner(","); // join the lines back to a CSV
                  // format
    os.writeln(r);
}

Listing 2

One of the cool parts of D ranges is that they are so flexible. You want to do everything in a functional way? D has you covered (Listing 3).

alias csvPipe = pipe!(enumerate,
  map!(a => a.index == colIndex ? replacement
    : a.value), partial!(reverseArgs!joiner,
    "_"),);
lines.dropOne.map!csvPipe.each!(
  a => os.writeln(a));

Listing 3

Thereâ€™s another cool thing about D â€“ std.parallelism. Have you ever been annoyed that a loop takes too long, but didnâ€™t know a quick way to parallelize your code? Again, D has you covered with .parallel [18]:

  foreach (line; lines.parallel)
    // expensive operation in parallel

No way. I donâ€™t believe this can be so simple.

Just try it yourself [19].

The Garbage Collector (GC)

On the internet and especially on reddit and HackerNews thereâ€™s a huge criticism of Dâ€™s decision to do use a GC. Go, Java, Ruby, JavaScript, etc. all use a GC, but I canâ€™t better phrase it than Adam D. Ruppe:

D is a pragmatic language aimed toward writing fast code, fast. Garbage collection has proved to be a smashing success in the industry, providing productivity and memory-safety to programmers of all skill levels. Dâ€™s GC implementation follows in the footsteps of industry giants without compromising expertâ€™s ability to tweak even further.

So ask your question:

Okay, â€œability to tweak even furtherâ€ sounds a bit vague, what does this mean? I can tweak the memory usage?

Well, of course you can do that, but thatâ€™s something most languages with a GC allow you to do. D allows you to get the benefit of both worlds: profit from the convenience of the GC and use manual allocation methods for the hot paths in your program. This is great, because you can use the same language for prototyping and shipping your application.

A short and simplified summary of allocation patterns in D:

malloc and friends are available in D (everything from C is)
RAII is supported (e.g. File you saw earlier is reference-counted and automatically deallocates its buffer and close the file once all references are dead)
thereâ€™s std.experimental.allocator for everyone with custom allocation needs
std.typecons provides a lot of library goodies like Unique, Scoped, RefCounted for @nogc allocation.

Mike Parker has recently started an extensive GC Series [20] on the DBlog which I recommend to everyone who prefers performance over convenience.

Other goodies

std.csv

Hey, I saw that thereâ€™s std.csv in D, why didnâ€™t you use it?

Simple â€“ it felt like cheating. See Listing 4.

import std.algorithm, std.csv, std.functional,
  std.file, std.range;

void main(string[] args)
{
  auto inputFile = args[1], columnName = args[2],
    replacement = args[3], outputFile = args[4];
  auto records = inputFile.readText.csvReader!(
    string[string])(null);
  outputFile.write(records.map!((r) {
    r[columnName] = replacement;
    return r;
  }).pipe!(rows => records.header.join(",") ~
    "\n" ~ rows.map!(
    r => records.header.map!(
    h => r[h]).join(",")).join("\n")
  ));
}

Listing 4

std.getopt

One of the reasons why this challenge used positional arguments and no flags is that argument parsing is pretty hard in C++. Itâ€™s not in D. std.getopt provides convenience for everything out of the box. See Listing 5.

import std.getopt;
int main(string[] args)
{
  string input, output, selectedColumn,
    fill = "FOO";
  auto opts = getopt(args,
    "i|input", &input,
    "o|output", &output,
    "s|select", "Select a column to overwrite",
      &selectedColumn,
    "f|fill", "Overwrite (default: FOO)", &fill,
  );
  if (opts.helpWanted || input.length == 0) {
    defaultGetoptPrinter("./program",
      opts.options);
    return 1;
  }
  return 0;
}

Listing 5

DMD, LDC and GDC

One of the things that newcomers are often confused by is that D has three compilers. The short summary is:

DMD (DigitalMars D compiler) â€“ latest greatest features + fast compilation (= ideal for development)
LDC (uses the LLVM backend) â€“ battle-tested LLVM backend + sophisticated optimizers + cross-compilation (=ideal for production)
GDC (uses the GCC backend) â€“ similar points as LDC

Benchmark and performance

Benchmarking a language compiler is a bit tricky as very often you end up benchmarking library functions. In general, D code can be as fast as C++ and often is even faster â€“ after all the LDC and GDC compilers have the same backend as clang++ or g++ with all its optimization logic. If you are interested to see how D programs perform against similar programs written in other languages, checkout Kostyaâ€™s benchmarks [21].

Thereâ€™s also an excellent performance benchmark [6] from Jon Degenhardt (member of eBayâ€™s data science team) on how eBayâ€™s tsv-utils [6] compare against existing CSV/TSV processing tools written in C, Go, and Rust.

@safe

Even though D is a system programming language that allows you to mess with pointers, raw memory and even inline assembly, it provides a sane way to deal with the dirty details. D has a @safe subset [22] [23] of the language in which the compiler will enforce that you donâ€™t do anything stupid thing and shoot yourself in the feet with e.g. accessing undefined memory.

Unittest

One strategic advantage of D is that unit-testing is so easy as itâ€™s built-in in the language and compiler. This is a valid D program:

  unittest {
    assert(1 == 2);
  }

And with -unittest the compiler can be instructed to emit a unittest block to the object files or binary. Here, rdmd is again a friendly tool and you can directly go ahead and test your line with you this:

  rdmd -main -unittest test.d

No advanced tooling setup required. Of course, this also means that itâ€™s particulary easy to automatically verify all examples that are listed in the documentation, because they are part of the testsuite. I even went one step further and made it possible to edit and run the examples on dlang.org [23].

Other cool D features

There are many other cool features that D offers that didnâ€™t make it into this article, but as a teaser for future articles:

Code generation within the language (cut down your boilerplate)
Strong and easy Compile-Time introspection (Meta-programming)
alias this for subtyping
-betterC (using D without a runtime)
mixin for easily generating code
A module system that doesnâ€™t suck
debug attribute to break out of pure code
Built-in documentation
Contracts and invariants
scope(exit) and scope(failure) for structuring creation with its destruction
Native interfacing with C (and most of C++)
with for loading symbols into the current name

For a full list, see the â€˜Overview of Dâ€™ [24] and donâ€™t forget that the full language specification [25] is readable in one evening.

Downsides

Okay, so you say D is so great, but why hasnâ€™t it taken off?

Thereâ€™s a lot more to a programming language than just the language and compiler. D has to fight with the problems all young languages have to deal with e.g. small ecosystem, few tutorials/sparse documentation and occasional rough edges. Languages like Kotlin, Rust or Go have it a lot easier, because they have a big corporate sponsor which gives these language a big boost.

Without such a boost, itâ€™s a chicken/egg problem: if nobody is learning D, it also means that no one can write tutorials or better documentation. Also many people have learnt a few languages and use them in production. Thereâ€™s little incentive for them to redesign their entire stack.

However, things improved greatly over the last years and nowadays even companies like Netflix, eBay, or Remedy Games use D. A few examples:

the fastest parallel file system for High Performance Computing [26] is written in D
if you drive by train in Europe, chances are good that you were guided by D (Funkwerk [27] â€“ the company that manages the transport passenger information system â€“ develops their software in D)
if you donâ€™t use an Adblocker, chances are good that algorithms written in D bid in real-time for showing you advertisement (two of the leading companies in digital advertising (Sociomantic and Adroll) use D)

The â€˜organizations using Dâ€™ page [28] lists more of these success stories.

Of course, D â€“ like every other language â€“ has its â€˜uglyâ€™ parts, but thereâ€™s always work in progress to fix these and compared to all other languages I have worked with, the ugly parts are relatively tiny.

Where to go from here?

Okay that sounds great, but how do I install D on my system?

Use the install script [29]:

  curl https://dlang.org/install.sh | bash -s

or use your package manager [30].

And start hacking!

Itâ€™s possible to do three easy tweaks to make I/O faster in D:

disabling auto-decoding with byCodeUnit
non-thread-safe I/O with lockingTextWriter
use of std.mmfile [5]

#!/usr/bin/env rdmd
import std.algorithm, std.exception, std.format,
  std.mmfile, std.range, std.stdio, std.utf;

void main(string[] args) {
  enforce(args.length == 5, "Invalid args\n" ~
  "./tool <input.csv> <colum-name>
  <replacement-string> <output.csv>");
  auto inFile = args[1], columName = args[2],
    replacement = args[3].byCodeUnit,
    outFile = args[4];
  scope mmFile = new MmFile(args[1]);
  auto lines = (
    cast(string) mmFile[0..mmFile.length])
    .splitter('\n').map!(
    a => a.byCodeUnit.splitter(","));
    auto colIndex =
      lines.front.countUntil!equal(columName);
    enforce(colIndex >= 0,
      "Invalid column. Valid columns: %(%s, %)"
      .format(lines.front));
    auto os = File(outFile, "w");
    os.writefln("%(%s, %)", lines.front);
    auto w = os.lockingTextWriter;
    foreach (line; lines.dropOne) {
      auto r = line
      .enumerate // iterate with an
                 // (index, value) tuple
     .map!(a => choose(a.index == colIndex,
       replacement, a.value))
     .joiner(",".byCodeUnit);
    w.put(r);
    w.put('\n');
  }
}

Listing 6

Acknowledgements

Thanks a lot to Timothee Cour, Juan Miguel Cejuela, Jon Degenhardt, Lio Lunesu, Mike Franklin, Simen KjÃ¦rÃ¥s, Arredondo, Martin Tschierschke, Nicholas Wilson, Arun Chandrasekaran, jmh530, Dukc, and ketmar for their helpful feedback.