Live data from Hacker News

Wc in D: 712 Characters Without a Single Branch

dlang.org

21–30 of 89 posts

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

#21

I'm wavering between D and Rust for which one could be used as a better alternative to C++. (Though I don't see C++ getting replaced anytime soon.) Even if Rust is getting most of the attention, D also seems to be a strong candidate.

I've been using Rust for a year or so and while it's very nice once you get used to it I recently started working in D since I feel _so_ much more productive in it thanks to the GC while it still feels powerful and is fast where it matters (you can avoid the GC at performance critical places). The lack of libraries is a little annoying at times but thanks to dstep it's somewhat easy to use C stuff.

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

#22
post #19

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.

CMOV aside, I remember it was proved MOV itself is turing-complete.

slightly related, does embedding arithmetic in mov instructions go faster than explicit ALU operations ?

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

#23
Gave myself a quick D lesson just to understand the approach to flags here (Yes.keepTerminator rather than just a meaningless bool). Turns out D lets you define a template with any args you like, in this case taking a string for a name of a Flag type, which in turn contains an enum with 'yes' and 'no' boolean values. This means that you can only use the right type of Flag, with a matching name, and its yes/no value. But the syntax is a bit icky (Flag!"keepTerminator) and so _another_ nice feature of D appears to be that you can intercept field dispatch in a struct. And so the 'Yes' struct does this, captures the 'keepTerminator' as a string, and creates the correct type of flag.

For whatever reason I found all this rather cute (and apologies to any actual D programmers if I've misread this whole situation).

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

#24
post #6

Earlier quoted context omitted.

My only issue is that it's far more complicated than Java and for a language that fills that same niche it's hard for me to justify putting my resources into learning it even though I do like a lot of the features.

In what way is more complicated than Java?

Java is actually a simple language.

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

#25
post #17

I find D easier to grok coming from a Java/Python background.

I've only toyed with D a bit. IMHO, if you come from a typical OO programming language background (which to me includes C++, Java, Python...), the majority of D will immediately feel familiar, and to a great extent, obvious. 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…

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

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

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

#26
post #5
post #4

There's also a wc in rust (of course) with more code (120 lines) but quite more efficient: https://medium.com/@martinmroz/beating-c-with-120-lines-of-r...

In the blog post you linked, a library for parallelism is used.

It's an additional two lines of code when they add it (and probably one more to pull it in above), and only happens at the end of the actual work, after they've matched C's performance and beat C's memory footprint. Using the parallelism library at the very end hardly invalidates the rest of the exercise.

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

#27
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…

You are pretty much right. It isn't IO bound.

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.

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

#28
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…

You are pretty much right. It isn't IO bound. 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. Usual…

Thanks for the thorough response. This aligns with what I had in my head, but it's nice to see a clearer explication and also confirmation that I'm not way out in left field with how I understand things.

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

#29
post #19

Earlier quoted context omitted.

CMOV aside, I remember it was proved MOV itself is turing-complete.

slightly related, does embedding arithmetic in mov instructions go faster than explicit ALU operations ?

Depending on the arithmetic, it seems that yes it can! I've noticed gcc using LEA instructions for arithmetic of the form (x * a + b), where 'a' and 'b' fit with the instruction.

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

#30
post #23

Gave myself a quick D lesson just to understand the approach to flags here (Yes.keepTerminator rather than just a meaningless bool). Turns out D lets you define a template with any args you like, in this case taking a string for a name of a Flag type, which in turn contains an enum with 'yes' and 'no' boolean values. This means that you can only use the right type of Flag, with a matching name, and its yes/no value.…

Spot on! :) With the help of opDispatch (the catch-all member function temlate), it's possible to drop the string from the use site. (I don't know a way of dropping it from the type name.)

  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));
  }
Post reply on HN