Hacker News Reader

Comment by markus_zhang | Hacker News Reader

Just curious can we try a C version?

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.

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

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.

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

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.

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

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

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

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.

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.

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.

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.

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.

Reply on news.ycombinator.com