Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Wc in D: 712 Characters Without a Single Branch

dlang.org

Post reply on HN
Print view View original

51–60 of 89 posts

Re: Wc in D: 712 Characters Without a Single Branch

#51

Post by coldtea »

monadic2 wrote: post #49

This is ridiculous: of course there are branches, but you don’t explicitly write them. This is purely aesthetic. Edit: i simply wish the author illustrated why this is good or desirable—conditionals are not difficult to read.

The aesthetic aspect is insignificant, it's about the semantics -- and thus reasoning about the code and other such properties. So nothing ridiculous about it.

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".

Re: Wc in D: 712 Characters Without a Single Branch

#53

Post by unwind »

EvenThisAcronym wrote: post #46
greggyb wrote: post #14

Perhaps I'm just being pedantic or maybe I am misunderstanding. 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 mi…

> So what am I missing here? 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.

GNU coreutils' wc (which is the reference) does not seem to be using threads, no.

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;...

Re: Wc in D: 712 Characters Without a Single Branch

#54

Post by pasquinelli »

jnordwick wrote: post #12
andrepd wrote: post #7

"without a single branch" I thought it meant actually a branchless version of wc. Turns out it's just no explicit if statements.

If you were careful, it seems pretty plausible to be able to use some indexing tricks and CMOV to write a jump/branchless version of wc. You are basically counting newlines and runs of whitespace.

"Counting newlines" implies branching.

Re: Wc in D: 712 Characters Without a Single Branch

#55

Post by [deleted] »

dig1 wrote: post #47

I believe I'm missing something here or my day was too long, but in Clojure this can be squeezed in 13 lines and 435 characters keeping things fairly readable (for Clojure & Lisp developers ;)). (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"))] [(…

[deleted]

Re: Wc in D: 712 Characters Without a Single Branch

#56

Post by BeeOnRope »

jnordwick wrote: post #12
andrepd wrote: post #7

"without a single branch" I thought it meant actually a branchless version of wc. Turns out it's just no explicit if statements.

If you were careful, it seems pretty plausible to be able to use some indexing tricks and CMOV to write a jump/branchless version of wc. You are basically counting newlines and runs of whitespace.

Yeah, it's Nnt just plausible, it's fairly straightforward. Here are some untested versions that have branch-free inner loops for lines (easiest, this will probably compile branch-free even if you aren't careful), and words:

https://godbolt.org/z/JNU-_G

Re: Wc in D: 712 Characters Without a Single Branch

#57

Post by tazjin »

dig1 wrote: post #47

I believe I'm missing something here or my day was too long, but in Clojure this can be squeezed in 13 lines and 435 characters keeping things fairly readable (for Clojure & Lisp developers ;)). (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"))] [(…

Neat! I wonder if the character decoding & regex usage has noticeable performance impact. My Common Lisp version was sped up somewhat by switching from a character stream to a byte stream: https://git.tazj.in/tree/fun/wcl/wc.lisp

You can try this one via Nix with:

  nix-build -E '(import (builtins.fetchGit "https://git.tazj.in") {}).fun.wcl'

Re: Wc in D: 712 Characters Without a Single Branch

#58

Post by gpderetta »

pasquinelli wrote: post #54
jnordwick wrote: post #12

Earlier quoted context omitted.

If you were careful, it seems pretty plausible to be able to use some indexing tricks and CMOV to write a jump/branchless version of wc. You are basically counting newlines and runs of whitespace.

"Counting newlines" implies branching.

Not really:

   cnt += *ptr++ == '\n'
Should compile down to no branches (not even cmov) by summing the value of the flag register directly. Would be a it hard to stop without taking a branch though. Would you consider function pointer calls a branch? If that's too easy, what about taking a segfault?

Re: Wc in D: 712 Characters Without a Single Branch

#59

Post by rcoveson »

pasquinelli wrote: post #54
jnordwick wrote: post #12

Earlier quoted context omitted.

If you were careful, it seems pretty plausible to be able to use some indexing tricks and CMOV to write a jump/branchless version of wc. You are basically counting newlines and runs of whitespace.

"Counting newlines" implies branching.

You could subtract the value of '\n' from each byte, bitwise-or the result with its negated value, right shift the sign bit into the least significant position, and push that into an accumulator.

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

>> 31

>> 31

Re: Wc in D: 712 Characters Without a Single Branch

#60

Post by egdod »

coldtea wrote: post #51
monadic2 wrote: post #49

This is ridiculous: of course there are branches, but you don’t explicitly write them. This is purely aesthetic. Edit: i simply wish the author illustrated why this is good or desirable—conditionals are not difficult to read.

The aesthetic aspect is insignificant, it's about the semantics -- and thus reasoning about the code and other such properties. So nothing ridiculous about it. 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".

Branches aren’t hard to reason about though. The only* reason anyone cares about branches is that branch misprediction is expensive.
Post reply on HN