Wc in D: 712 Characters Without a Single Branch
dlang.org
dlang.org
The author claims to be IO bound toward the end. But they are comparing to two versions that are faster.
It is my understanding that IO-bound means that the IO subsystem is the thing which limits run time of the program. But the author clearly demonstrates that the IO subsystem of their machine is capable of supporting faster wc binaries.
So what am I missing here?
If your definition said IO must be the only thing limiting the time, then few programs would be IO bound, except trivial ones like "count arriving packets". In a packet counter, your "implementation" would not affect wall clock time at all until packets could arrive faster than 3GHz, or if you figured out a way to make `count++` run slower than packets could arrive.
Usually IO bound means 'kinda like that packet counter'. There are problems with being exactly like that packet counter (e.g. are you using the IO subsystem inefficiently, like reading one char at a time?), but it has the property that speeding up IO speeds up the program, and speeding up your code doesn't speed up the program (much, or at all).
You're right that it isn't a useful comparison between existing programs. It is useful to compare your program's CPU performance to theoretical limits on wall time. When your `wc` implementation approaches the speed of reading a file and doing nothing with it, then you can say it's IO bound. For this reason, there are very few single-file-reading programs that could be described as IO bound. It's common in networking where networks go much slower, and in filesystem traversal (e.g. ripgrep) but not for plain file reading.
Like they will talk about how their web app is IO bound because the DB query takes 1 second while their slow ruby code only takes 300ms after it gets the result from the DB back.
Well guess what, making the web app twice as fast still cuts 150ms off the response time, and it still means you can do twice as many requests on the same server.
In order to be able to say that something is “bound” by something else, you have to have some kind of concurrency going on. One task has to be doing all it’s work in the time that it’s waiting for more work to arrive from another.
The Haskell program is multi-threaded (I don't know about wc's official implementation, but I assume it is as well), while the D program is single-threaded.
At least not at all obviously. No obvious header included and no mention of threads. I only checked the code [1] very quickly, though.
[1] https://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob;...
If adding threads increases the speed, this implies that the program is both CPU-bound and that it has opportunities for parallelism.
My implementation was very close to what I calculated for my hardware's max throughput within 20x the runtime of doing a direct file copy.
For my test file I'm using a copy of the linux source tree in a singe file generated with: `(find linux/ -type f -name ".c" && find linux/ -type f -name ".h") | xargs cat > linux.txt` which is about 770MB of text.
To get an idea of the maximum possible performance I could hope to achieve:
cat linux.txt | pv > /dev/null
769MiB 0:00:00 [3.08GiB/s] [ <=>
]
First the haskell implementation that uses optics, concurrency, and other magic:
$ nproc
32
$ time ./hs-wc lazy linux.txt
24961824 77271007 807304327 linux.txt
./hs-wc lazy linux.txt 6.88s user 0.89s system 317% cpu 2.446 total
$ time ./hs-wc simple linux.txt
24961824 77270977 807299417 linux.txt
./hs-wc simple linux.txt 509.04s user 432.26s system 1850% cpu 50.867 total
$ time ./d-wc linux.txt
24961824 77270980 807299417 linux.txt
./d-wc linux.txt 22.09s user 0.14s system 99% cpu 22.238 total
$ time wc linux.txt
24961824 77270960 807304327 linux.txt
wc linux.txt 3.59s user 0.08s system 99% cpu 3.672 total
$ time ./mine-wc linux.txt
24961824 77270966 807304327 linux.txt
./mine-wc linux.txt 1.70s user 0.10s system 99% cpu 1.804 total
$ gcc -O0 wc.c
$ time ./a.out linux.txt
24961824 77270966 807304327 linux.txt
./a.out linux.txt 6.51s user 0.12s system 99% cpu 6.636 total
$ gcc -Wall -Isrc/ -pedantic-errors -Ofast -ftree-vectorize -msse -msse2 -ffast-math wc.c
$ time ./a.out linux.txt
24961824 77270966 807304327 linux.txt
./a.out linux.txt 1.37s user 0.09s system 99% cpu 1.467 total
Any reasonable wc should be fast enough for that purpose; just remember to use the '-l' switch to activate the fast path for line counting.
>Some things I noted when doing my testing is that each program counted the number of lines, characters, and words differently in this corpus.
All programs should report the same line counts (should be exactly the number of line feed characters in the input).
Other than that, it really depends on your current locale and the wc you're using (see https://github.com/expr-fi/fastlwc README for more details). Do note that this D implementation seems to implement the wc character counting behaviour you get with the '-m' switch (instead of the byte counting default).
Also worth noting that different operating systems have different locale definitions; glibc locales explicitly treat non-breaking spaces as non-whitespace characters, while for example Windows doesn't.
For whatever reason I found all this rather cute (and apologies to any actual D programmers if I've misread this whole situation).
import std.stdio;
import std.typecons;
import std.string;
// This type's opDispatch removes the need for string in the flag name.
struct FlagFromBool {
auto opDispatch(string flagName)(bool value) {
mixin (format!q{
return value ? Yes.%s : No.%s;
}(flagName, flagName));
}
}
// A convenience function to remove the need for empty struct construction parenthesis.
auto flagFromBool() {
return FlagFromBool();
}
// Unfortunately, the type name still requires string flag names:
void bar(Flag!"foo" flag) {
writeln("called with ", flag);
}
void main() {
// However, the expressions don't need a string:
bar(flagFromBool.foo(false));
bar(flagFromBool.foo(true));
}struct FlagImpl(string name) { bool value; alias value this; }
struct Flag { alias opDispatch(string name) = FlagImpl!name; }
struct Yes { static auto opDispatch(string name)() { return FlagImpl!name(true); } }
struct No { static auto opDispatch(string name)() { return FlagImpl!name(false); } }
void fun(Flag.foo a) {} // Look ma, no quotes!
unittest { fun(Yes.foo); fun(Flag.foo(true)); }
But if you use D as a BetterC compiler, then the D compiler can check the O/B rules in the code.
Functions that are O/B checked are marked with the `@live` attribute, meaning that you'll be able to incrementally use O/B in the code. This is much like how you can use the `pure` attribute to incrementally write functionally pure code.
Google took me right back to your comment.
posting for anyone wondering
Basically, it is possible to reduce a byte into a one or a zero if it does or does not match a value using only bitwise instructions. I don't know if the way I just described uses the fewest instructions, but you can definitely do it without branching.
In fact, you can do this to test any integer comparison. Start by subtracting the arguments to the comparison operator, and then use one of these "squash" functions for the comparison operator in question (assuming 32 bit signed integers are being compared):
== : ~(c | -c) >>> 31
!= : (c | -c) >>> 31
> : -c >>> 31
>= : ~c >>> 31
< : c >>> 31
<= : ~-c >>> 31
cnt += *ptr++ == '\n'
Only icc vectorizes this at -O2 (still branchless, of course), but clang and gcc vectorize it if you go to -O3.
I just want to gently push back on the notion that the source level branchy-ness is tightly tied to the generated assembly level branchiness.
Sometimes, it is - but it is a long topic to characterize when. For simple things like counters based on a condition, you'll almost always get branch-free. Same for assignment/return value based on a condition, where the possibilities don't involve lots of asymmetric work (or a asymmetric memory access).
(defn wc [^String file]
(with-open [rdr (clojure.java.io/reader file)]
(apply (partial printf "%d %d %d\n")
(reduce
(fn [[nl nw nb] ^String ln]
(let [words (count (.split ln "[ ]+"))
bytes (alength (.getBytes ln "UTF-8"))]
[(inc nl) (+ nw words) (+ nb bytes)]))
[0 0 0]
(line-seq rdr)))))
(defn -main [& args]
(wc (first args)))
You can try this one via Nix with:
nix-build -E '(import (builtins.fetchGit "https://git.tazj.in") {}).fun.wcl' wc=:[:+/[:(1:,([:#'\S+'&rxmatches),>:@#);._2 freads
* recompiling with -march=native can give significant wins over more generic binaries provided by linux distros.
* parallel processing helps with bigger files, and it's easy enough to leverage the existing wc binary to process in parallel.
Both points are discussed at: https://www.pixelbeat.org/docs/unix-parallel-tools.html
However, if the most important features of C++ is RAII, shared pointers, unique pointers, move semantics, then you'd probably enjoy Rust more, because it focuses on this kind of memory/resource management techniques.
Edit: i simply wish the author illustrated why this is good or desirable—conditionals are not difficult to read.
It's like Haskell code "of course has" anything C has, as underneath the both run assembly instructions full of gotos and state manipulation, you just "don't explicitly write it".
Meanwhile the semantics of objects, especially one named “Output”, are super obvious and easy to reason about.
Of course there is no data to back this up, but I think one of the next trends in programming beyond the adoption of functional styles, immutable data, "functional core / imperative shell" will be abstracting away from explicit conditional/branching logic in higher level code.
Obviously people can come up with pedantic/extreme cases where the abstraction does nothing to hide the complexity, or even makes things more complex but im not taking about that. I mean more simple abstractions like what was used in OP, or a filter() abstracting over a while and if combo.
I'm convinced based on personal experience that it makes for cleaner code and will become more widely adopted over the years as people explore it.
Why are immutable data structures easier to reason about? They still produce the same results.
None of the above are proven facts, but they are generally agreed upon principles that a number of people have observed. And I happen to believe them as well.
Overall my opinion of why it's easier is that like most optimizations it reduces the number of states/cases you have to think about in the "common path". With a solid abstraction you rarely need to think about the internals, with explicit code you need to check and think through all of the edge cases.
filter() (or map, or ...) is probably the best simple case I can think about. There is more room for bugs in an explicit (ex. for (int = 0; i < ...) {}) than in a filter over a collection / enumerable. When reading the code you need to think through base and termination conditions as well as confirm aggregation is happening correctly. With a filter() you don't have to do it / be explicit about it. Obviously you still need to know what filter means (which means you know it's implementation) but you don't need to focus on the details, only the filter condition: the signal amid the noise. The rest is pushed behind a solid reusable abstraction. Again thinking about it in isolation if someone just introduced the filter function to you you might look at it an say it really doesn't add much and if anything obscures my code I don't see the value. But after adopting it, and it's related family of monadic collection operations, code can now be written at a much denser, fewer off-by-one errors, higher signal to noise, level of abstraction. It's provided structure and common abstractions to unstructured iteration. To the point you begin to think in these abstractions (which I think is a benefit).
Another example are parser combinators. There is nothing that parser combinators do that can't be done by hand. But one of the primary way they simplify coding is by hiding away conditional (and looping logic). "?*.." , | and & concepts. Parser combinators also benefit in simplifying things by building an algebra for users to work in with nice closed operations. But again that only became possible by abstracting away the conditional and looping logic and making these nice simple abstractions that can be easily combined.
So my summary is, my view is that abstracting over control flow code does a lot to simplify logic. A lot of logic involving looping has already been abstracted over and included in languages and libraries (in general "functional programming" styles). Now that the low hanging fruit has been incorporated I think next will be the next layer of non-looping conditional logic.
The syntax is familiar and the ideas are familiar. You don't have to learn anything new (not immediately anyway) like you do in Rust (where you basically need to learn EVERYTHING new).
Where this idyllic scenario starts falling apart with when you start actually using it for anything half-serious. Some of the bits feel extremely unintuitive and the documentation is difficult to navigate. There are few examples and the tutorial is a bit spartan. For example, I needed a deque-like container (double-ended queue), but it took me ages to figure out that a) the language actually has one and b) how to use the bloody thing.
There is also a bit of schizophrenia going on, with the "new" ideas and the "old" ideas clashing in some places. For example, they claim that you can run D without a GC (the new), but apparently a good chunk of the stdlib requires the GC (the old), so you're stuck.
I find this all to be unfortunate because D, to me, feels like it could be a better, saner C++.
AFAIK this is somewhat intentional; they don't want to make any hard compatibility breaks, so there's a long deprecation period for any 'old' idea. There's also a lack of manpower to renovate libraries; e.g. there's no good xml library.
Regarding GC, it's IMO not a huge problem. The GC is really not a problem for most applications, and for those where it is, you can simply avoid GC allocations in inner loops (GC only runs when you allocate from it).
The intent isn't to turn off the GC completely (though GC-averse folks assume that it is). The `@nogc` function attribute is intended to be applied where you need it. Then you can guarantee that in that function's call stack, no language features that require the GC will be used.
The standard library has been retrofitted to eliminate use of the GC where it isn't needed and provide alternatives where possible (such as a function that takes a buffer as an argument alongside one that allocates). There may still be places where it can be trimmed down even more, but it will never be fully `@nogc` compatible.
D is meant to be used with the GC, but provides the means to avoid allocations, turn collections on/off (`GC.disable/enable`) and command line options for profiling GC usage and affecting its behavior. Anyone who wants to turn off the GC completely is going beyond the primary intended use case and is of course going to run into bumps with the standard library. Much of it is still usable, though.
Just as you would for C and C++.
Other languages may need libraries to be installed, but not D.