5 ms·
Just curious can we try a C version?
by markus_zhang 6y ago
Just curious can we try a C version?
- zabzonk 6y agoYou can try, but it would likely be at least 10x the length of the C++ (or rust) program.
- saagarjha 6y agoMaybe 5x, with most of that increase being a handrolled associative array.
- zabzonk 6y agoYou 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.
- tptacek 6y agoWhy do you need a dynamic string of any sort for this problem? (I think you estimated badly, for what it's worth.)
- saagarjha 6y agoYou'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.)
- tptacek 6y agoYeah, I just used strdup and strsep, like a C programmer. You don't need a dynamic string to count words. :P
- saagarjha 6y agoSo it turns out that factor is just over 2.5x: https://gist.github.com/saagarjha/00faa1963023206a8ccd9877983b4546 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.
- mjbrusso 6y agoC doesn't even have a standard filesystem library!
- tptacek 6y agoEvery 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.
- GuB-42 6y agoC 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.
- markus_zhang 6y agoThanks. How about PERL? Hear it's good at string manipulation but never used it.
- tptacek 6y agoFirst, 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
- steveklabnik 6y agoIt 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.
- pornel 6y agoI 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).
- tptacek 6y agoSure. https://gist.github.com/tqbf/4de61a3e34d2e4664044666c107abe77 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.
- cb321 6y agoYou have/had a bug in your code. The realloc() needs to multiply its second argument csz by sizeof *counts or sizeof(struct wordcount).
- tptacek 6y agoOf 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
- cb321 6y agoJust 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.
- 6y ago
- saagarjha 6y agoPulling this up out of a subthread, if you happen to have some sort of notification set up for these: https://gist.github.com/saagarjha/00faa1963023206a8ccd9877983b4546 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".
- tptacek 6y agoTIL <ftw.h>! You can golf out about 10 lines of this by getting rid of the table free. :)
- saagarjha 6y agoYes, 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…