{"id":2303,"date":"2020-01-28T13:54:16","date_gmt":"2020-01-28T13:54:16","guid":{"rendered":"http:\/\/dlang.org\/blog\/?p=2303"},"modified":"2021-09-30T13:37:19","modified_gmt":"2021-09-30T13:37:19","slug":"wc-in-d-712-characters-without-a-single-branch","status":"publish","type":"post","link":"https:\/\/dlang.org\/blog\/2020\/01\/28\/wc-in-d-712-characters-without-a-single-branch\/","title":{"rendered":"wc in D: 712 Characters Without a Single Branch"},"content":{"rendered":"

After reading \u201cBeating C With 80 Lines Of Haskell: Wc\u201d<\/a>, which I found on Hacker News<\/a>, I thought D could do better. So I wrote a wc<\/code> in D.<\/p>\n

The Program<\/h2>\n

It consists of one file and has 34 lines and 712 characters.<\/p>\n

import std.stdio : writefln, File;\r\nimport std.algorithm : map, fold, splitter;\r\nimport std.range : walkLength;\r\nimport std.typecons : Yes;\r\nimport std.uni : byCodePoint;\r\n\r\nstruct Line {\r\n\tsize_t chars;\r\n\tsize_t words;\r\n}\r\n\r\nstruct Output {\r\n\tsize_t lines;\r\n\tsize_t words;\r\n\tsize_t chars;\r\n}\r\n\r\nOutput combine(Output a, Line b) pure nothrow {\r\n\treturn Output(a.lines + 1, a.words + b.words, a.chars + b.chars);\r\n}\r\n\r\nLine toLine(char[] l) pure {\r\n\treturn Line(l.byCodePoint.walkLength, l.splitter.walkLength);\r\n}\r\n\r\nvoid main(string[] args) {\r\n\tauto f = File(args[1]);\r\n\tOutput o = f\r\n\t\t.byLine(Yes.keepTerminator)\r\n\t\t.map!(l => toLine(l))\r\n\t\t.fold!(combine)(Output(0, 0, 0));\r\n\r\n\twritefln!\"%u %u %u %s\"(o.lines, o.words, o.chars, args[1]);\r\n}<\/pre>\n
Sure, it is using Phobos, D\u2019s standard library<\/a>, but then why wouldn\u2019t it? Phobos is awesome and ships with every D compiler. The program itself does not contain a single if<\/code> statement. The Haskell wc<\/code> implementation has several if<\/code> statements. The D program, apart from the main<\/code> function, contains three tiny functions. I could have easily put all the functionally in one range chain, but then it probably would have exceeded 80 characters per line. That\u2019s a major code-smell.<\/p>\n
The Performance<\/h2>\n
Is the D wc<\/code> faster than the coreutils wc<\/code>? No, but it took me 15 minutes to write mine (I had to search for walkLength<\/code><\/a>, because I forgot its name).<\/p>\n\n\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n\n
 
file<\/th>\nlines<\/th>\nbytes<\/th>\ncoreutils<\/th>\nhaskell<\/th>\nD<\/th>\n<\/tr>\n<\/thead>\n
app.d<\/td>\n46<\/td>\n906<\/td>\n3.5 ms +- 1.9 ms<\/td>\n39.6 ms +- 7.8 ms<\/td>\n8.9 ms +- 2.1 ms<\/td>\n<\/tr>\n
big.txt<\/td>\n862<\/td>\n64k<\/td>\n4.7 ms +- 2.0 ms<\/td>\n39.6 ms +- 7.8 ms<\/td>\n9.8 ms +- 2.1 ms<\/td>\n<\/tr>\n
vbig.txt<\/td>\n1.7M<\/td>\n96M<\/td>\n658.6ms +- 24.5ms<\/td>\n226.4 ms +- 29.5 ms<\/td>\n1.102 s +- 0.022 s<\/td>\n<\/tr>\n
vbig2.txt<\/td>\n12.1M<\/td>\n671M<\/td>\n4.4 s +- 0.058 s<\/td>\n1.1 s +- 0.039 s<\/td>\n7.4 s +- 0.085 s<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Memory:<\/p>\n\n\n\n\n\n<\/colgroup>\n\n\n\n\n\n\n\n
 
file<\/th>\ncoreutils<\/th>\nhaskell<\/th>\nD<\/th>\n<\/tr>\n<\/thead>\n
app.d<\/td>\n2052K<\/td>\n7228K<\/td>\n7708K<\/td>\n<\/tr>\n
big.txt<\/td>\n2112K<\/td>\n7512K<\/td>\n7616K<\/td>\n<\/tr>\n
vbig.txt<\/td>\n2288K<\/td>\n42620K<\/td>\n7712K<\/td>\n<\/tr>\n
vbig2.txt<\/td>\n2360K<\/td>\n50860K<\/td>\n7736K<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Is the Haskell wc<\/code> faster? For big files, absolutely, but then it is using threads. For small files, GNU’s coreutils still beats the competition. At this stage my version is very likely IO bound, and it\u2019s fast enough anyway.<\/p>\n
I\u2019ll not claim that one language is faster than another. If you spend a chunk of time on optimizing a micro-benchmark, you are likely going to beat the competition. That\u2019s not real life. But I will claim that functional programming in D gives functional programming in Haskell a run for its money.<\/strong><\/p>\n
A Bit About Ranges<\/h2>\n
\"DigitalA range is an abstraction that you can consume through iteration without consuming the underlying collection (if there is one). Technically, a range can be a struct or a class that adheres to one of a handful of Range<\/code> interfaces. The most basic form, the InputRange<\/code><\/a>, requires the function<\/p>\n
void popFront();<\/pre>\n
and two members or properties:<\/p>\n
T front;\r\nbool empty;<\/pre>\n
T<\/code> is the generic type of the elements the range iterates.<\/p>\n
In D, ranges are special in a way that other objects are not. When a range is given to a foreach<\/code> statement, the compiler does a little rewrite.<\/p>\n
foreach (e; range) { ... }<\/pre>\n
is rewritten to<\/p>\n
for (auto __r = range; !__r.empty; __r.popFront()) {\r\n    auto e = __r.front;\r\n    ...\r\n}<\/pre>\n
auto e =<\/code> infers the type and is equivalent to T e =<\/code>.<\/p>\n
Given this knowledge, building a range that can be used by foreach<\/code> is easy.<\/p>\n
struct Iota {\r\n\tint front;\r\n\tint end;\r\n\r\n\t@property bool empty() const {\r\n\t\treturn this.front == this.end;\r\n\t}\r\n\r\n\tvoid popFront() {\r\n\t\t++this.front;\r\n\t}\r\n}\r\n\r\nunittest {\r\n\timport std.stdio;\r\n\tforeach(it; Iota(0, 10)) {\r\n\t\twriteln(it);\r\n\t}\r\n}<\/pre>\n
Iota<\/code> is a very simple range. It functions as a generator, having no underlying collection. It iterates integers from front to end in steps of one. This snippet introduces a little bit of D syntax.<\/p>\n
@property bool empty() const {<\/pre>\n
The @property<\/code> attribute allows us to use the function empty<\/code> the same way as a member variable (calling the function without the parenthesis). The trailing const<\/code> means that we don\u2019t modify any data of the instance we call empty<\/code> on. The built-in unit test prints the numbers 0<\/code> to 10<\/code>.<\/p>\n
Another small feature is the lack of an explicit constructor. The struct Iota<\/code> has two member variables of type int<\/code>. In the foreach<\/code> statement in the test, we create an Iota<\/code> instance as if it had a constructor that takes two int<\/code>s. This is a struct literal<\/a>. When the D compiler sees this, and the struct has no matching constructor, the int<\/code>s will be assigned to the struct\u2019s member variables from top to bottom in the order of declaration.<\/p>\n
The relation between the three members is really simple. If empty<\/code> is false<\/code>, front<\/code> is guaranteed to return a different element, the next one in the iteration, after a call to popFront<\/code>. After calling popFront<\/code> the value of empty<\/code> might have changed. If it is true<\/code>, this means there are no more elements to iterate and any further calls to front<\/code> are not valid. According to the InputRange<\/code> documentation<\/a>:<\/p>\n