Gassa's blog

By Gassa, history, 9 months ago, translation, ,

Hi all!

This post is inspired by a question here which asks yosupo how using the D progamming language compares to using C++. I regularly use D where possible in contests (and problemsetting) since 2014, with some success (for example, a program in D brought me victory in AZsPCs: Alphabet City). So I'd like to share my experience. I'll try to focus on stuff which is important in competitive programming.

The general feeling is as follows. You can write in D as in plain C when you need full control. You can also write more like in Python using the powerful standard library. However, D is a compiled language, so in both cases, the performance is similar to C++. Additionally, when the program is written, it is much easier to debug than a similar program in C++.

For an example, let us look at two solutions of a recent problem. The first solution is written like plain C:

import std.stdio;
int main () {
int n, m, i;
double c = 1.0, x;
scanf ("%d%d", &n, &m);
for (i = 0; i < n * 2; i++) {
scanf ("%lf", &x);
c *= 1 - 1 / x;
}
printf ("%.10f\n", c > 0 ? m / c - m : -1);
return 0;
}


Looks familiar, eh? A very similar solution can be accepted in C if we just change the import line into the respective #include. It is on purpose: the authors tried their best so that, when a C program is compiled with D, it either throws a compile error or works the same.

So, we read 2 * n numbers, transform each x we read into 1 - 1 / x, multiply all results together, and finally, consider two cases.

But we can drop the lower-level stuff, like the for loop and the variables to read and store the intermediate results. Instead, we can write a solution which has more likeness to the text above: read two lines, split them at whitespace characters, transform each string piece into a double, then apply the formula, and after that, fold the resulting sequence by the multiply operation, transforming u, v, w, ... into u·v·w·.... Here's the code:

import std.algorithm, std.conv, std.stdio;
void main () {
int n, m;
readf !" %s %s " (n, m);
.splitter
.map !(to!double)
.map !(x => 1 - 1 / x)
.fold !"a * b";
writefln !"%.10f" (c > 0 ? m / c - m : -1);
}


A phrase like function !(args1) (args2) is analogous to function <args1> (args2) in C++: the arguments !(args1) are known at compile time, and the arguments (args2) at run time. In particular, this allows readf and writefln to check the types of the arguments at compile time. Empty parentheses can be omitted.

Here, we can also note that splitter and map are “lazy” functions, so the compiled code acts in the order similar to the former solution: first makes all transformations with the first number, then with the second one, then multiplies the first one and the second, then takes the third number, and so on.

In D, there is no single mega-idea around which the language is built. Instead, there are plenty of minor features which together mean a world of difference compared to C++ when writing programs. Let us consider a few specific points below.

• Error checking. Using D, it is much easier to defend against many stupid bugs. For example, array bounds are checked by default, and when run locally, an out-of-bounds access will terminate and tell the line number. However, when compiling with -boundscheck=off, as it is the case on Codeforces, the checks disappear and no longer consume precious time. Another example: if we get a string in the input instead of an integer, the program immediately terminates with a stack trace instead of running further with corrupted data. The convenient debug output of the form debug {writeln (a);}, for mostly any variable a, is also very helpful when debugging (this line will be compiled only with -debug which, again, is turned off on Codeforces server).

• Style choice. Be it an imperative program, a chain of transformations applied to the data, or metaprogramming, everything is in D from the start. On the contrary, in C++, due to its age and backward compatibility, the authors had to glue the new paradigms together with the ones already established, which harmed the overall usability.

• Library. The standard library of C++ has weak, cumbersome, and unwieldy parts: string processing, higher order functions, making structures on-the-fly via pair and tuple. Sure, C++ can do anything, but some things are just much more convenient in other languages, D included.

A few bonuses from the library:

• BigInt: seems like it's got its way into every language except C++.

• parallelism: remember the problems in Google Code Jam or Facebook Hacker Cup where a solution works just a few times slower than needed? We will of course have to separate input and output from the actual solution, but the rest is taken care of with just one magic call to parallel!

• FFT: not the most optimal implementation, but sometimes sufficient to solve a problem.

A few drawbacks:

Many of the weaknesses have the same nature: the language is not very widespread. It means that the resources spent on compiler, the standard library, and the supporting tools were less by orders of magnitude than for C++.

• Compiler bugs. Back in 2014, participating in a 5-hour contest, on average, meant I have to write one new bugreport. (On the positive side, imagine the feeling when you say “my program can't be wrong, it's all compiler's fault”, and happen to be right for a change!) Nowadays, there are a lot less bugs, but hitting another one is of course more probable than to find a bug in GCC.

• Standard library weaknesses. For example, the containers library is somewhat crude: there is a hash table (same as HashMap) and a red-black tree (same as TreeSet), but no convenience wrappers for HashSet and TreeMap. (As is the case with C++, D can do anything, it's just the matter of writing a few more lines and convenience.)

• Availability at competitions. On the platforms where 10-20 languages are available for solving problems, D is usually present. (By the way, as is the tradition: thanks to MikeMirzayanov! This time for adding and maintaining D on Codeforces.) When there are only few languages, they are most likely a subset of C, C++, Java, Pascal, Python, and maybe the organizers' language of choice. In big important competitions, it is like a chicken-egg problem: as long as there are just a few contestants using D, there is no compelling reason to add it, and as long as the contest does not allow D, there is no compelling reason to learn it.

If you got interested, take a look at the learning resources on D's site: the language tour and the list of books (many of these are just available online). I'd also be glad to answer specific questions in the comments.

•
• +312
•

 » 9 months ago, # |   +13 Thanks for sharing about D language but I have to say, seeing that compact solution for 1010A made me question my life decisions.
 » 9 months ago, # |   -27 Now every gray/green/cyan/blue coder in CF shall switch to D language because of this.
 » 9 months ago, # |   +3 What about IDE for this language? Do you have recommendations?
•  » » 9 months ago, # ^ |   0 I myself used Code::Blocks (wrote projects with students) and Visual Studio with Visual D plugin (just checked it works). A more complete list can be found at the language site.That said, I like minimalist IDEs, and commonly use Far Manager: a text editor suits the majority of possible languages :) .
•  » » » 9 months ago, # ^ |   0 though poseidon is also a very good choice as it's written in D itself but it's for big projects and is not exactly cross platform(windows/linux) only. i had my numerical computing course in D itself.
 » 9 months ago, # |   0 how fast is it
 » 9 months ago, # |   +5 Thank you for sharing knowledge about the D on Codeforces. I will use my knowledge and expertise of the D to attract many females and future employers.