C does not support strings, regex and maps natively. You have external libraries that can do it, but from my experience, they are painful to use. String manipulation in general is painful in C and probably not the best language for this demo.

However, if you really want high performance, you can go ahead and write it in C with a custom matching code and a custom data structure for keeping your word count. This will most likely result in hundreds of lines of code, and enough performance to max out a PCIe SSD. However that would be an different exercise.

First, if Rust's solution gets to pull in crates, then a C program can use regexps, with pcre or cre2.

Second, it's not clear to me at all why this problem asks for regexps. Both examples used a regexp to check a file extension, and then to find word boundaries. Both are trivial† to code directly.

Am I misunderstanding the problem here? It seems like there's hardly any string manipulation in it at all.

† admittedly, I didn't bother being careful about word boundaries

It shouldn’t require them. I thought I saw a comment by the author explaining why they chose to use them, but there’s been like six different threads on three different forums and I can’t find it right now...

I know some C++ folks were annoyed it’s using regex due to criticisms of the standard regex libraries that can’t be fixed, or something, so it’s also not like folks agree that the original solution was optimal. I don’t think it was trying to be, so seems fine, but it is what it is.

The idea here is that it is a toy problem. The author is not trying to make the best word counter, he is comparing two languages by implementing the same algorithm on both and giving us his conclusions.

Using a different technique, for example by not using regexp is a bit like cheating in that context. You are not comparing two languages, you are comparing two different solutions to the problem.

That's what I meant with my previous post. Either you do it as specified in the article, with regex and maps, which require pulling libraries and working in a way that is much less convenient than with the C++ and Rust example for no good reason. Or you reimplement it using different techniques and this is not the point of the article.

Or to put it simply, the example in the article is not good for C.

The program is going to look substantially the same if I use pcre to check for ".txt" and split up words. And, if you read the original C++ article, it is not at all about comparing regex interfaces!

So, no, I don't think you're right about this.

More to the point, though: I'm talking about regex libraries because the parent comment is. My point: the Rust example uses 3p dependencies, so what C does "out of the box" is already out the window.

I assumed the original example was a bit of an overkill/lazy coding just to demonstrate that regexes and other conveniences are readily available, so the language would work nicely not just for this trivial example, but for bigger things you may want to write too.

I'm fed up with C dependencies, which like Makefiles, always seem to be very easy in principle, and then kill by thousand cuts (like a regex library that defines a symbol that happens to conflict with a POSIX regex function, which I didn't even use, but it corrupted memory of a completely different dependency elsewhere).

You definitely can't manage a C program with dependencies the way you would a Rust program with Cargo. You'd ordinarily bring in a couple major deps --- OpenSSL, zlib, pcre, &c --- and then maybe vendor in the small stuff. Most large C projects don't dep in things like logging or error handling the way Rust programs all do.

This particular program needs no third party dependencies at all; in fact, I bet it'd get longer if I added them (like a glib hash table, or pcre).

Thanks. How about PERL? Hear it's good at string manipulation but never used it.

Sure.

https://gist.github.com/tqbf/4de61a3e34d2e4664044666c107abe7...

(I don't vouch for this code; I wrote it off the top of my head, and, in keeping with the exercise, I wrote it in pico).

It's not 10x longer. I'm honestly not sure why either Rust or C++ bothered with regexps for this problem.

Anyways, you get the gist of what this looks like in C now. Obviously, don't write things like this in C.

You have/had a bug in your code. The realloc() needs to multiply its second argument csz by sizeof *counts or sizeof(struct wordcount).

Of course I have a bug in this code. Thanks, fixed! :)

With that fixed, this dumb program does my whole (very large) homedir in about 10 seconds, for some definition of "does" that may or may not include counting every word in every txt file. For the curious:

   0. get / 566006
   1. the / 158168
   2. pkg / 119419
   3. syscall / 105828
   4. const / 98259
   5. and / 86670
   6. ideal-int / 43078
   7. that / 31609
   8. for / 31129
   9. this / 24980
   10. text / 22907

:P

Just trying to help, not criticize. As to correctness, if you change the tokenization to:

  while (fgets(buf, 1024, fp)) {
    char *c, word[1024], *w = word;
    for (c = buf; *c; c++) {
      *c = tolower(*c);
      if (*c >= 'a' && *c <= 'z')
        *w++ = *c;
      else {
        *w = '\0';
        count(word, (size_t)(w - word));
        w = word;
      }
    }
    *w = '\0';
    count(word, (size_t)(w - word));
  }

and you have that `count` function skip words with len < 2 then I can match results with the other 3 (Nim, Rust, C++) versions. Also, your C version runs in just 7 ms on Tale Of Two Cities, about half the time of the PGO optimized Nim.

Oh, no, you don't sound critical at all. I'm making fun of myself. Thank you for actually reading it!

Cool. You could probably simultaneously speed it up and simplify it by changing from linked list collision to open addressing with linear probes (but you may need a larger TSZ). Besides being more cache friendly for larger files, at the end you can then just qsort your table instead of first building a flat copy. :-) You could also use the unreduced hash value as a comparison prefix (only calling strcmp on different values). But it's not bad for potato code. ;-)

I didn't do open addressing because I didn't want to write code to resize the whole table. :)

I thought about also keeping the top 10 as I go instead of copying the whole table. But I'm guessing that virtually all the time this program spends is in I/O.

I kind of suspected that might be the reason..but you do still have a scalability problem for very large vocabularies. :-)

I just did a profile and saw about 15% in strcmp in the hot cache run, but sure if it's not in RAM then IO is likely the bottleneck.

(You could also just save the len and use that as a comparison prefix, but the hash value is less likely to yield a false positive.)

Isn't this code kind of supporting the first point in the article? I mean, the article started by pointing how rust "protected" you from a "TTCTTOU" error.

This C code is not only not protecting you against that, but also it seems to have little to none error checking. What happens if fopen fails? It just skips to the next file and happily ignores all the entries in the file. What if fget fails? Again, it stops processing the file and goes to the next.

I won't even get into what happens if calloc fails and returns null. Or if ++ wraps around and you get a negative value (let's hope we are using 64 bits)

This program will likely work, but if it doesn't you will just get an invalid number and never find out.

Don't get me wrong, I understand this is "not serious" code, written in a Sunday and for fun. And I would be ok with it if the article wasn't about language safety.

Try as hard as you like, you aren't going to find anyone to argue that C is as safe as Rust.

As for the TOCTTOU issue --- which is kind of silly, and had really nothing to do with Rust --- the diff to fix that problem is tiny:

https://gist.github.com/tqbf/4de61a3e34d2e4664044666c107abe7...

On a sane system, what's going to happen if calloc (or realloc, or strdup) returns NULL is the same as what's going to happen in the Rust program: the program will abort. Checking malloc returns is a bad idea, and causes more problems than it solves.

Similarly: this code does essentially the same thing with errors that the Rust one does: it swallows them and continues.

At any rate, while this C++ vs Rust discussion might be about language safety (I vote Rust, like any other software security person would), this subthread isn't.

So, actually, this entire arc of TOCTTOU is little bit off track or at least incomplete. If someone replaces an ordinary file with a FIFO/named pipe "foo.txt" during the traversal (or simply if your recursive file tree walk does not filter out FIFOs) then any program will block during the open(2) of the FIFO. Things will never advance to the fstat() to check its file type.

I just checked and whatever default behavior dga's Rust code uses (both for traversal and for the open call) does indeed just block forever if there is a FIFO present with a name ending in .txt.

There is a way out - by adding O_NONBLOCK to the OS flags for the open call. { You could also stat() just before open(2) instad of fstat() just after, but then you still have a race condition, just with a much smaller time window. }

I love this thread so much.

Well, then you may also appreciate changing my Nim program from the `continue` to the final output `for` to:

    let mf = mopen(path)
    if mf == nil:
      stderr.write "wc: \"",path,"\" missing/irregular\n"
    else:
      var word = ""
      for c in toOpenArray(cast[ptr UncheckedArray[char]](mf.mem), 0, mf.len-1):
        let c = c.toLowerASCII
        if c in {'a'..'z'}:
          word.add c
        else:
          count.maybeCount word
          if word.len > 0: word.setLen 0
      count.maybeCount word # file ends in a word
      mf.close

You also need to add ",cligen/mfile" to the import line and install a version control head of the cligen package.

With that the Nim time goes down to 6.1 ms (no PGO) and 5.0 ms (PGO). Just a quick after dinner fix-up.

{ There is actually a trick related to ASCII where we could add `, 'A'..'Z'` to the character set and then `or` in a bit to make the letter lowercase (because 'a' - 'A' is 32), but I just did the above to test that cligen/mfile worked with FIFOs in the mix, not to maximize performance. I suspect pre-sizing the table by adding e.g., 10_000 or 20_000 to the init would make more difference.}

Beyond the above couple ideas, the next steps to make it faster would be to get rid of almost all dynamic memory allocation by having a table of byte-offset,len,count triples (or maybe add in a hashcode for a quadruple) and rolling your own "memcasecmp" if your stdlib does not provide one. This could probably make the histograms so small that they are likely fully L2 resident..roughly (8..12) times vocabSize bytes is 192 KiB for a 16384 vocabSize. https://github.com/c-blake/adix/blob/master/tests/anaPrime.n... has an example of how to do this in Nim (for values in a table, though in our case here it would be for keys and so need `hash` and `==`).

At that point if you had a lot of data, the better way to parallelize it is also not either of the two ways DGA mentions in his original blogpost with one shared table, but rather one histogram per CPU with no locks or memory contention at all and a final merge of the CPU-private histos (after processing all files) that can probably be single-threaded, though you could also organize it as a "tree" of parallel merges (e.g. first merge every pair, then every pair of the results and so on).

Whether to parallelize over files or over big chunks of files would depend upon how big your files are. The big chunks approach leads to more regular work balance because making all subproblems the same size is easy, but does need "clean-up" for any words that span each byte boundary which is a bit annoying, but there are only as many fix-ups as you have threads which is small. It would be unsurprising to me if Tale of Two Cities could be done in like 0.1 ms with 32 cores up to 500x faster than that initial Rust version (maybe omitting thread start-up overheads).

This particular problem is actually so fast that you might need to use all of Dickens cat'd together or more to get numbers less polluted by system noise and microsecond-scale thread start-up times and small L2 histo merges or do min-of-more-than-5 runs for times, but all the principles I've mentioned apply more broadly (except maybe the ASCII case trick).

Anyway, these are all sort of obvious points on a topic that was more about prog.langs, but a good systems programming language + ecosystem ought to make it "easy-ish" to get that last factor of 10..500x that is easy enough to express in a HackerNews comment.

>you aren't going to find anyone to argue that C is as safe as Rust.

That's good, I was starting to doubt humanity :)

>As for the TOCTTOU issue --- which is kind of silly, and had really nothing to do with Rust

agree. But well, was what it was claimed in the article.

>On a sane system...

I disagree with this one, although I know I am in the minority. A malloc failure is not a unrecoverable error, and the only reason to abort on memory error is because if you allow malloc errors, then virtually every line of code can fail, because it is either allocating memory or calling some other method that allocates memory. (I imagine you've already read http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p070... section 4.3 but I mention just in case someone hasn't heard of it)

Something similar happens with integer overflow, although we've collectively decided that we prefer to have 2,147,483,647 + 1 = -2,147,483,648. (in both C++ or rust in release mode). But if we assumed that i++ can cause an error, it would mean that every line of code could possible be an error.

But well, back to memory allocation: Just a month ago I had a situation where using a language (C#) which just throws an exception in memory overflow saved my day. I left running overnight a program that builds and creates setups for the programs I make. There are about 190 different setups (win32, 64, linux, and variations), all compressed using max settings in 7zip. Those builds run in parallel in a threadpool, and each 7zip compression takes a lot of memory. So much, that during the night one thread raised an out of memory error. When I woke up next day, I had 189 setups created correctly, and one that failed. I rerun that missing setup and was ready to publish them. Had I used a "sane" language, the full app would have aborted and I would have to run the 190 setups again.

But seriously, it can happen a lot, specially in embedded. You are processing images and one image is too big. Do you abort the app, or report the error and move to the next image?

>this code does essentially the same thing with errors that the Rust one does: it swallows them and continues

Thats was my point in the answer: Rust and C++ don't shallow the error. You have the line: reader.lines().filter_map(Result::ok)

And then: if let Err(e) = scanfiles() { println!("Error: Something unexpected happened: {:#?}", e);

So, if there is an error, it will report it to you, not shallow it. And that is to me the full point: The guy who coded the Rust version would have to go out of his way to shallow the error, while in C it is the default.

The Rust program surfaces errors in globwalk, but swallows the fopen errors you were talking about (it filter_maps them away, which, to be fair, is what I'd do too).

None of the counters in that C program are going to wrap. If it makes you feel better, you can replace size_t with "unsigned long long", but that's already what it is on modern systems.

That Rust program will also abort on allocation failures, just like I'd expect my C program to, so recovering from memory exhaustion isn't really in the scope of the discussion here.

If you care about security, you abort a C program when allocation fails. If you ask programmers to check failures, you get malloc checking bugs. Especially in embedded systems, where offset-from-NULL pointers can get attackers something useful. There are exceptions to every rule (at least in C programming), but if the task is "count words in files", you're nuts if you do anything but blow up when malloc fails.

> it filter_maps them away, which, to be fair, is what I'd do too

Ok, I don't know much rust and I imagined filter_maps reported to the main app. If it is shallowing them, then to me it is a big + for C++ in that area. It seems I will have to agree to disagree here, but shallowing the error is not what I would do at all. This program has the possibility to give you a completely wrong result, and you would never know. You could use that result in other thing, say publish a study where you claim there were only 100 words in the files you processed but there were 1000 because your program crashed and didn't warn you.

> If you care about security, you abort a C program when allocation fails.

Well, that's why I personally prefer C++ and exceptions. They abort by default, let you handle if you want/can.

But I think my original point was lost. My complain was that this code wasn't checking at all for failure. Shouldn't it be something like:

if(!w->next) w->next = calloc(1, sizeof(*w));

if (!w->next) abort();

    w = w->next; 

I mean, in this particular case it will indeed blow up because when it goes back to the while(w->word) w will be null and you will reference a null pointer. But that's mostly luck, and might be not be true anymore if you make changes to the code in the future. If you care about security, you should check all allocs, and abort if null. And that's my beef with C: It shallows and continues instead of crashing or reporting when there is an error.

> but if the task is "count words in files", you're nuts if you do anything but blow up when malloc fails.

I won't disagree here, if the task is count words in files. I was just trying to explain why imo, not all "sane" programs should abort in failed malloc.

In serious C programs, you rig malloc to abort rather than return NULL. With jemalloc, for instance, you'd do it with opt.xmalloc.

> A malloc failure is not a unrecoverable error

It's not, but it's also a fairly difficult error to recover from effectively. You really need to know what you're doing to get out of this–I think someone did a study for how many STL implementations handled std::bad_alloc correctly (i.e. unwound and didn't accidentally take down the program) and I think the number was zero.

> we've collectively decided that we prefer to have 2,147,483,647 + 1 = -2,147,483,648

Not always, overflowing is often exploitable since it lets you bypass less than checks.

>although we've collectively decided that we prefer to have 2,147,483,647 + 1 = -2,147,483,648. (in both C++ or rust in release mode)

Signed integer overflow is undefined behavior in C++. Only unsigned integers are defined to wrap like that.

https://stackoverflow.com/a/16188846

Thanks I got the gist. Doesn't look too bad IMO.

You can try, but it would likely be at least 10x the length of the C++ (or rust) program.

Maybe 5x, with most of that increase being a handrolled associative array.

You also need at least dynamic string of some sort. Actually, I would estimate 20x - I was being kind with 10x. But feel free to prove me wrong.

So it turns out that factor is just over 2.5x: https://gist.github.com/saagarjha/00faa1963023206a8ccd987798.... You can split hairs about it being POSIX and inefficient or not checking all the errors, but it works and isn't really all that massive.

Why do you need a dynamic string of any sort for this problem?

(I think you estimated badly, for what it's worth.)

You'd need it to read words, unless you're using a libc function that does the allocation for you. (Not that you actually need a full string, realloc works just fine for the code I'm writing.)

Yeah, I just used strdup and strsep, like a C programmer. You don't need a dynamic string to count words.

:P

Pulling this up out of a subthread, if you happen to have some sort of notification set up for these: https://gist.github.com/saagarjha/00faa1963023206a8ccd987798.... Not intended to be robust or even correct beyond "I tried it a little and it seems to work".

TIL <ftw.h>!

You can golf out about 10 lines of this by getting rid of the table free. :)

Yes, ftw.h has a couple of nice functions–it's an apt name in this case ;)

I could have done a number of things to keep the line count down–in the spirit of the challenge I tried to keep it clean, pedantic, idiomatic POSIX C because if I didn't I'm sure someone would have jumped on it for it not being that :P So it's written in nano in the style of how I might write a homework assignment rather than something I specifically golfed. In retrospect the fixed-depth buckets probably added more complexity than they saved, and using a linked list or open addressing would have probably been much easier since it'd clean up some of the resizing and traversal code. Plus, the load factor was in general fairly poor, the final table (when I ran it on my Downlods folder) had just over 8 million buckets of depth 5 allocated and only about 600k got used at all, and of that 570k were filled just once.

Oh, and here's the results on my Downloads folder:

  514464 Developer
  425236 Xcode
  386616 saagarjha
  386075 Users
  361324 Library
  337374 build
  333056 Wno
  306758 WebKit
  302892 DerivedData
  296179 eugbibmfmfphgbhczsxiimkhynol

I have a couple WebKit build logs that dominated the results…

C doesn't even have a standard filesystem library!

Every modern OS filesystem interface was designed in C. The places filesystems are hard in C, they're hard in Rust too. In practice: no, fileystems are easy in C.