[PATCH v2] aarch64: add optimised strspn/strcspn

[Wilco Dijkstra]

Hi remph,

> Wilco: thanks for the feedback; here's an implementation with a bit array
> and 2-register TBL.  This version is much smaller, since there should be
> no need for different loops if 2-register TBL is generally fast enough,
> which means a faster init time.  Speed is comparable to the best case of
> my previous version, and there is no worst case.

The new version is seriously fast indeed! For longer strings it is now ~5x faster,
and even short strings are always faster (they were slower previously).
I have a few comments below.

Also would you mind posting a version to Arm Optimized Routines [1]?
We maintain AArch64 optimized string functions there under a permissive license
so they can be used in other projects and libraries. The assembly code is identical
apart for the license, include filename and any libc_hidden_def macros.

[1] https://github.com/ARM-software/optimized-routines

Cheers,
Wilco


+ENTRY(STRSPN)
+	ldrb	w2, [set]
+	cbz	w2, L(early)
+#ifdef USE_AS_STRCSPN
+	ldrb	w3, [set, 1]
+	cbz	w3, L(early)
+#endif
+	/* Table has ones for bytes to reject and zeros for bytes to accept */
+#ifdef USE_AS_STRCSPN
+	stp	xzr, xzr, [sp, -16]
+	stp	xzr, xzr, [sp, -32]!

Missing unwind directive (and below).

+#else
+	mvni	v0.4s, 0
+	stp	q0, q0, [sp, -32]!
+#endif
+
+	mov	one, 1

Why not move this before the stp so that you can use it in the 2nd STP and
ensure the bit for NUL char is set already? Then the defines below can be
removed and we avoid 1 iteration for USE_AS_STRCSPN.

+	.balign 32,,16
+L(fill_table):
+#ifdef USE_AS_STRCSPN
+	ldrb	w2, [set], 1
+#endif
+	lsr	byte_i, x2, 6	/* x2 / 64 */
+	lsl	bits_i, one, x2	/* x2 % 64 implicitly */
+	ldr	x5, [sp, byte_i, lsl 3]
+	SBT	x5, x5, bits_i
+	str	x5, [sp, byte_i, lsl 3]
+#ifndef USE_AS_STRCSPN
+	ldrb	w2, [set, 1]!
+#endif
+	cbnz	w2, L(fill_table)
+
+	ld1	{table}, [sp], 32

Why not use .2d for the table? That avoids the need to do extra work
for big-endian since the loop above deals with 64-bit words already.

+	ubfiz	off, og_s, 2, 4	/* Bottom 4 bits, times 4 to count nibbles */
+	and	s, og_s, -16	/* Round S down to 16-byte boundary */
+	movi	sevens, 7
+#ifdef __AARCH64EB__
+	rev64	table_a, table_a
+	rev64	table_b, table_b
+#endif
+
+	.balign 64,,16

This doesn't seem to be very effective - this loop is at a bad alignment.
We typically use .p2align 4 for performance critical loops. If you use the max
padding feature, you always need a 2nd directive for minimum alignment
(so you avoid getting no alignment at all if the padding would be too large).

+L(loop):
+	ldr	q0, [s], 16
+	mov	save_off, off	/* OFF and SYNDROME overlap */

This is highly confusing...

+	ushr	vbyte_i, v0.16b, 3
+	bic	vbits_i, sevens, v0.16b
+	tbl	v0.16b, {table}, vbyte_i
+	/* Bring the relevant bit to the MSB of each byte */
+	sshl	v0.16b, v0.16b, vbits_i
+	/* Set every bit of each byte to its MSB */
+	cmlt	v0.16b, v0.16b, 0
+	/* Bytes->nibbles */
+	shrn	v0.8b, v0.8h, 4
+	fmov	x2, d0
+	LS_FW	syndrome, x2, syndrome

And also relies on this implicitly setting save_off to zero in the next iteration...

+	cbz	syndrome, L(loop)
+
+#ifndef __AARCH64EB__
+	rbit	syndrome, syndrome
+#endif
+	sub	s, s, 16
+	sub	x0, s, og_s
+	clz	syndrome, syndrome
+	add	x0, x0, save_off, lsr 2
+	add	x0, x0, syndrome, lsr 2
+	ret

The extra save_off addition here adds another 2 cycles of latency.

I think this could be done by using a mask to clear off bits from syndrome
rather than a variable shift, and then setting the mask to zero for the next
iteration. Then you don't ever need the extra ADD at the end.

Or even better, treat the first 16 bytes specially - then the shift works fine
and you just return ctz (syndrome) >> 2. Plus it allows interleaving of the
instructions, eg. moving the ldr q0, [s] much earlier. The first 16 bytes will
be faster as you save at least 6 instructions, we remove 2 instructions from
the loop and 2 in the tail.

+L(early):
+#ifdef USE_AS_STRCSPN
+	/* strlen(set) < 2: call strchrnul(s, *set) and get its offset from S */
+	stp	fp, lr, [sp, -64]!
+	str	x19, [sp, 32]
+	mov	w1, w2
+	mov	fp, sp
+	mov	x19, x0
+	bl	strchrnul

This should be __strchrnul to avoid localplt failures in GLIBC testsuite...

+	sub	x0, x0, x19
+	ldr	x19, [sp, 32]
+	ldp	fp, lr, [sp], 64

This also needs unwind directives (easiest option is to copy them from C).