5 ms·

Nice! There's a part two in which I rewrote the C. I got a 12x speedup :) https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-a

Nice! There's a part two in which I rewrote the C. I got a 12x speedup :) https://owen.cafe/posts/the-same-speed-as-c/ https://owen.cafe/posts/the-same-speed-as-c/ And as others have pointed out, you can tweak the input, then vectorize the algo, if you want to go that route. I considered this a pedagogical exercise and I sincerely hope nobody will start dropping down to assembly without a very good reason to.

rajnathani 3y ago
Great post! One thought: If the code is rewritten using bit arithmetic, then potentially the result could be even faster as there need not be a pointer look-up. A bit arithmetic solution would have a mask created for the characters ‘p’ and ‘s’, and then the result could be AND-ed, and then with more bit arithmetic this all 1s value can be translated to a 1 if and only if all the bits are 1. Following which, there would be a no conditional check and simply be both an add and a subtract operation but where the value to be added will only be 1 if the mask for ‘p’ matches and 1 to be subtracted if the mask for ‘s’ matches respectively. I’m not fully sure if this would necessarily be faster than the pointer look-up solution, but it would be interested to try this version of the code and see how fast it performs. Update: The bit arithmetic could also be done with an XOR on the mask, and following which the ‘popcnt’ x86 instruction could be used to figure out if all are 0 bits.
JohnMakin 3y ago
Thank you for your post and reply but I fear with a post + title like this you may just be chumming the waters.
- jdsalaro 3y ago
  What do you mean by "chumming the waters" in this context?
  - mayli 3y ago
    "Clickbait"
  - bombcar 3y ago
    People who just skim the headline and article will come away convinced that dropping to assembly is the “way to go fast” even if they never actually do it.
    - sh34r 3y ago
      Anyone with a passing understanding of Assembly or compilers would find that idea laughable. As for the others, it turns out not knowing what you don’t know can be very expensive.
sriku 3y ago
Wondering how res += (c=='s')-(c=='p') might do. I sure there is some C undefined behaviour relevant there. Curious but too lazy to check it myself!
- Tempest1981 3y ago
  While `false` evaluates to 0, not sure `true` always evaluate to 1 in C... maybe compiler dependent. Maybe add `? 1 : 0`
  - ladberg 3y ago
    C doesn't even originally have true/false, I think you may be conflating the two concepts that "any nonzero int is truthy" and "boolean expressions evaluate to ints". The standard mandates that boolean expressions like equality always evaluate to 0/1.
  - loeg 3y ago
    The `true` constant is always 1. C11 §7.18 (3): > true which expands to the integer constant 1, And equality yields a 1 or 0. C11 §6.5.9 (3): > The == (equal to) and != (not equal to) operators are analogous to the relational operators except for their lower precedence. Each of the operators yields 1 if the specified relation is true and 0 if it is false.
- romnon 3y ago
  ive seen people doing += !!(c=='s')-!!(c=='p') for that
  - simonkagedal 3y ago
    That is entirely unneccessary. An == expression will always evaluate to 1 or 0. The !!x trick can be useful in some other situations, though. Here’s a thing you could do (but I don’t know why): += !(c-’s’) - !(c-’p’)
  - sweetjuly 3y ago
    I'm sure people do that (even though it's not necessary per some year C standard) but generally the pattern is actually for converting things which are not already 0 or 1 into 0 or 1. For example, you might want to use it here: int num_empty_strings = !!(strlen(s1)) + !!(strlen(s2)) + !!(strlen(s3)) which is equivalent to: int num_empty_strings = (strlen(s1) != 0) + (strlen(s2) != 0) + (strlen(s3) != 0) Which you use is really a matter of coding style.

rajnathani 3y ago

Great post! One thought: If the code is rewritten using bit arithmetic, then potentially the result could be even faster as there need not be a pointer look-up. A bit arithmetic solution would have a mask created for the characters ‘p’ and ‘s’, and then the result could be AND-ed, and then with more bit arithmetic this all 1s value can be translated to a 1 if and only if all the bits are 1. Following which, there would be a no conditional check and simply be both an add and a subtract operation but where the value to be added will only be 1 if the mask for ‘p’ matches and 1 to be subtracted if the mask for ‘s’ matches respectively. I’m not fully sure if this would necessarily be faster than the pointer look-up solution, but it would be interested to try this version of the code and see how fast it performs. Update: The bit arithmetic could also be done with an XOR on the mask, and following which the ‘popcnt’ x86 instruction could be used to figure out if all are 0 bits.

JohnMakin 3y ago

Thank you for your post and reply but I fear with a post + title like this you may just be chumming the waters.

jdsalaro 3y ago
What do you mean by "chumming the waters" in this context?
- mayli 3y ago
  "Clickbait"
- bombcar 3y ago
  People who just skim the headline and article will come away convinced that dropping to assembly is the “way to go fast” even if they never actually do it.
  - sh34r 3y ago
    Anyone with a passing understanding of Assembly or compilers would find that idea laughable. As for the others, it turns out not knowing what you don’t know can be very expensive.

sriku 3y ago

Wondering how res += (c=='s')-(c=='p') might do. I sure there is some C undefined behaviour relevant there. Curious but too lazy to check it myself!

Tempest1981 3y ago
While `false` evaluates to 0, not sure `true` always evaluate to 1 in C... maybe compiler dependent. Maybe add `? 1 : 0`
- ladberg 3y ago
  C doesn't even originally have true/false, I think you may be conflating the two concepts that "any nonzero int is truthy" and "boolean expressions evaluate to ints". The standard mandates that boolean expressions like equality always evaluate to 0/1.
- loeg 3y ago
  The `true` constant is always 1. C11 §7.18 (3): > true which expands to the integer constant 1, And equality yields a 1 or 0. C11 §6.5.9 (3): > The == (equal to) and != (not equal to) operators are analogous to the relational operators except for their lower precedence. Each of the operators yields 1 if the specified relation is true and 0 if it is false.
romnon 3y ago
ive seen people doing += !!(c=='s')-!!(c=='p') for that
- simonkagedal 3y ago
  That is entirely unneccessary. An == expression will always evaluate to 1 or 0. The !!x trick can be useful in some other situations, though. Here’s a thing you could do (but I don’t know why): += !(c-’s’) - !(c-’p’)
- sweetjuly 3y ago
  I'm sure people do that (even though it's not necessary per some year C standard) but generally the pattern is actually for converting things which are not already 0 or 1 into 0 or 1. For example, you might want to use it here: int num_empty_strings = !!(strlen(s1)) + !!(strlen(s2)) + !!(strlen(s3)) which is equivalent to: int num_empty_strings = (strlen(s1) != 0) + (strlen(s2) != 0) + (strlen(s3) != 0) Which you use is really a matter of coding style.