Just checking whether I understand correctly: aligned_end is not aligned, but good enough to serve as the end of the loop over aligned values. To make it really aligned we would need to do something like aligned_end = _Py_SIZE_ROUND_DOWN(_end, SIZEOF_SIZE_T)?

Yes that is the gist of it. I tried something similar to _Py_SIZE_ROUND_DOWN and got segfaults so I opted for this simpler tried and true solution. The name aligned_end is probably not the best, but I can't think of a better name now.

Should be something like

Py_ssize_t n = end - begin;
const STRINGLIB_CHAR *p = begin;
const STRINGLIB_CHAR *aligned_end = begin + _Py_SIZE_ROUND_DOWN(n, ALIGNOF_SIZE_T);

Would be interested in understanding why you got a segfault though.

This can be done in a for-loop instead.

The original code is a while loop. Any particular reason why a for loop is preferable?

I would just say "for clarity" but let's leave it like this if it was the original code (less changes in this sense).

We could combine these two loops into a single loop right? Worst case we do a single loop over 32-1=31 bytes instead of two while loops (the loop over _p (7 steps) and the loop over p (3 steps)).

The more optimal solution is to do an unaligned load of a size_t at (end - SIZEOF_SIZE_T). That would remove the entire last while loop. I do not know if all architectures support unaligned loads however. I guess some could theoretically abort?

I single loop over 31 bytes taking 31 steps is less optimal than 2 while loops taking 10 steps in total. (Or even 7 in the case of 64-bit size_t, that would be the majority of platforms).

You can use the memcpy trick to do an unaligned load, it will be optimized by any reasonable compiler, for example:

  size_t value;
  memcpy(&value, end - sizeof(value), sizeof(value));

That's a very nice suggestion! That would simplify the code a lot.

As in the other PR, maybe the 4/8 choice can be chosen at compile time depending on the architecture.

99% of production work were performance matters will be done on ARM64 (with 16-byte neon vectors) and X86-64 (with SSE2 vectors) other platforms will not be hurt by this decision. I think there is no reason to complicate the build with choices like this.

and here, you would have some #if arch == ... to choose between 4 or 8 values.

I feel that those vector load could be macros, for clarity purposes. It would then be optimized by the compiler but having them as macros might be helpful for future work.

I would to not have a macro, the code is good as it is.

@encukou Should we still use macros such as SIZEOF_SIZE_T and ALIGNOF_SIZE_T, or should we prefer sizeof and _Alignof?

IMO, we should prefer sizeof and _Alignof here.
Things are a bit different in public headers (where sizeof is OK but _Alignof isn't) or the preprocessor (in #if, neither work).

(There is no C API WG formal guideline yet; this is a personal recommendation. If anyone wants a wider discussion, do that in Discourse.)

Is CPython supported on some platform where size_t is strictly greater than void*? I know this PR doesn't touch this conditional, but I'm curious. @encukou

I'm not aware of any platform where sizeof(size_t) != sizeof(void*).

This is not really about supported platforms (i.e. where we run the tests), or currently supported platforms.
We should aim for standard C whenever it's reasonable; if a speedup needs an extra assumption it should document that with this kind of #if.

Is the restrict keyword and the assignment to value0, ..., value3 required for the compiler? If not, then this code can be written more compact.

In general I think the compiler can judge from the function that no writes happen in either __p or _q so pointer aliasing is not problematic. But I'd rather make this explicit rather than relying on the compiler to deduce this. MSVC and Clang do this scalarly despite the hint. GCC correctly vectorizes the load store and does not need the hint. I cannot judge all possible compilers out there. I think it is more likely that clang and MSVC will do the correct thing in the future with the hint than without it.

It would only save the restrict keyword as the (size_t *) cast is still needed, as that makes the rest of the code more readable. Are the 8 characters extra width that problematic?

You technically have 3 blocks of SIZEOF_SIZE_T until you reach size_t_end. In this case, I'd suggest creating a macro which is the unrolling of that (I'm not sure the compiler knows this or not, but maybe it does).

Good suggestion to check if the compiler unrolls this. After all, I removed the if statement and only check at the end.

Unfortunately this leads to very suboptimal assembly. So the extra while loop is useful here.

Again, here you have only 3 chunks so maybe check whether you can unroll the loop once again (actually, just check whether the assembly with -O2 or -O3 unrolls stuff).