14 ms·

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

by cb321 6y ago

tptacek 6y ago
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
- cb321 6y ago
  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.
  - tptacek 6y ago
    Oh, no, you don't sound critical at all. I'm making fun of myself. Thank you for actually reading it!
    - cb321 6y ago
      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. ;-)
      - tptacek 6y ago
        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.
        cb321 6y ago
        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.
    - cb321 6y ago
      (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.)

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

by cb321 6y ago

You 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 ago

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

cb321 6y ago
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.
- tptacek 6y ago
  Oh, no, you don't sound critical at all. I'm making fun of myself. Thank you for actually reading it!
  - cb321 6y ago
    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. ;-)
    - tptacek 6y ago
      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.
      - cb321 6y ago
        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.
  - cb321 6y ago
    (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.)