C++ still isn't cutting it

Re:C++ still isn't cutting it by cb321 on Sunday October 18, 2020 @04:41PM (#24820964)

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.

[ Parent | on HN ]

Re:C++ still isn't cutting it by tptacek on Sunday October 18, 2020 @04:45PM (#24820998)

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

[ Parent | on HN ]

Re:C++ still isn't cutting it by cb321 on Sunday October 18, 2020 @04:51PM (#24821045)

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

[ Parent | on HN ]

Re:C++ still isn't cutting it by tptacek on Sunday October 18, 2020 @04:59PM (#24821095)

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.

[ Parent | on HN ]

Re:C++ still isn't cutting it by cb321 on Sunday October 18, 2020 @05:15PM (#24821188)

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.

[ Parent | on HN ]

Re:C++ still isn't cutting it by cb321 on Sunday October 18, 2020 @04:54PM (#24821060)

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

[ Parent | on HN ]