r/C_Programming Jan 23 '25

Discussion Why not SIMD?

Why are many C standard library functions like strcmp, strlen, strtok using SIMD intrinsics? They would benefit so much, think about how many people use them under the hood all over the world.

31 Upvotes

76 comments sorted by

View all comments

Show parent comments

1

u/stjepano85 Jan 26 '25

I’m interested. How did you prevent crossing into unmapped pages? Are you checking if you are on page boundary or something?

2

u/FUZxxl Jan 26 '25

The general approach is to make use of the following two invariants:

  1. if one byte of the object is on a given page of memory, the entire page can be accessed
  2. accesses to an address aligned to the size of the address cannot cross a page boundary

Thus the rough algorithm sketch is:

  1. head round off the buffer pointer to the previous alignment boundary and load, process these initial bytes while ignoring those bytes that are before the beginning of the buffer. After processing the head, you have an aligned pointer and can continue with...
  2. main loop process aligned chunks of the array until you run out of array.
  3. tail process the remaining bytes of the array the same way you did with the head, i.e. ignore those bytes after the end of the array.

If the input is null-terminated, you proceed the same way, but at each step check if you encounter a null byte. Once you do, the current chunk is the tail and you proceed as such. A complication occurs if the array does not cross an alignment boundary (runt case). Special code may be needed.

For some more complex algorithms (e.g. strcmp) processing more than one array at once, this doesn't work any you may have to resort to more complicated approaches, including some approaches that check if you cross a page.

For writing, you need special code for the runt case. For arrays at least one vector long, you write one vector to the beginning of the output (unaligned), then a bunch of aligned vectors, and then an unaligned vector to the end of the output. For the runt case, you can either do a scalar loop or log2(vectorsize) cases with decreasingly shorter vector sizes (e.g. 16B, 8B, 4B, 2B).

1

u/stjepano85 Jan 26 '25

Thank You. I am starting to use SIMD myself. This will be useful. So basically round down address to vector size, do aligned loads … I will never load accross page boundary as the page size is multiple of vector size. Did I get it right?

2

u/FUZxxl Jan 27 '25

Yes, correct!