5
\$\begingroup\$

The asm function strlen receives the link to a string as a char - Array. To do so, the function may use SWAR on general purpose register, but without using xmm registers or SSE instructions.

The function checks with the bit manipulation: (v - 0x01010101) & ~(v & 0x80808080)in 8 byte steps, whether the quadword contains a zero byte, which would mark the end of the string. If a zero is found, it iterates byte per byte up to the zero to avoid a page fault.

The alignment works like in this GNU Libc implementation:

for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr){
    if (*char_ptr == '\0'){
        return char_ptr - str;
    }
}

Is there any way to make it faster?

; rdi <- const *char
; rax <- counter + return value
; r10 <- current array for computation
; rcx,r8 <- Bitmask
; rsi <- Arr for calculation 
            
strlen:
    PUSH rbp
    SUB rsp,8
 
    XOR rax,rax    
    MOV r8,31
alignment:
    CMP byte [rdi+rax],0
    JE end
    
    MOV rsi,rdi
    ADD rsi,rax
    AND rsi,r8
    CMP rsi,0
    JE while_parallel
    INC rax
    JMP alignment       
          
while_parallel:  
    MOV rcx,0x01010101
    MOV r8,0x80808080
while_parallel_loop:  
    MOV r10,[rdi+rax]
    MOV rsi,r10
    
    NOT r10
    AND r10,r8
    SUB rsi,rcx
    AND rsi,r10
    
    CMP rsi,0
    JGE while_single
    ADD rax,8
    JMP while_parallel_loop
    
while_single:
    CMP byte [rdi+rax],0
    JE  end
    INC rax
    JMP while_single    
end:
    ADD rsp,8
    POP rbp
    RET

Note that I do not intend to use any SSE instructions nor xmm registers.

\$\endgroup\$
6
  • \$\begingroup\$ Did you have any unit tests? \$\endgroup\$
    – harold
    Jun 4, 2023 at 18:03
  • \$\begingroup\$ no, I do not have any tests \$\endgroup\$ Jun 4, 2023 at 18:08
  • 3
    \$\begingroup\$ "it iterates byte per byte up to the zero to avoid a page fault." The byte per byte is not going to avoid a page fault, because directly before it, the whole 8 bytes already have been read. So if a page fault could happen, it would happen while reading the quadword. \$\endgroup\$
    – Sep Roland
    Jun 4, 2023 at 20:07
  • 1
    \$\begingroup\$ @SepRoland the way OP described it was wrong, but page fault are avoided through another technique: by aligning the address first \$\endgroup\$
    – harold
    Jun 4, 2023 at 20:38
  • 2
    \$\begingroup\$ This was cross-posted from Stack Overflow, where njuffa posted a full working version with some optimization improvements, including using bsf on the bithack result. Speed up strlen using SWAR in x86-64 assembly . (ping @harold). I commented there with the suggestion of checking (p & 4095) <= (4096-8) to allow an unaligned 8-byte load to start, instead of a byte-at-a-time loop until an alignment boundary, but haven't written an answer yet. Handling the page-cross case with a load from p & -4096 and a shift should also be possible. \$\endgroup\$ Jun 5, 2023 at 7:00

1 Answer 1

7
\$\begingroup\$

A bug

Your constants are for the 32-bit version of the SWAR "has zero byte" trick, but you are processing 8 bytes at once. So the constants must be the 64-bit versions, which are the same pattern but twice as long:

MOV rcx, 0x0101010101010101
MOV r8, 0x8080808080808080

Small missed opportunities

ALU operations in general set the flags according to their result, not just cmp. You don't always need cmp. For example after AND rsi,r10 when we want to know whether rsi is zero or not, that information is already available in the zero flag, there's no need for cmp rsi, 0. Since the result of the and is no longer needed, it can be turned into a test (though that doesn't make it any faster)

Similarly, the check for alignment does not need a cmp. You can change the and rsi, r8 to a test rsi, 31 (but you should probably change the 31 as well, see below) and drop the cmp.

Zeroing a 64-bit register, such as XOR rax, rax, can be done by zeroing the corresponding 32-bit register, xor eax, eax. That often saves a byte, and on some (low power) processors it is strictly better. It's never worse, so you may as well.

A non-destructive addition, such as MOV rsi,rdi \ ADD rsi,rax, can usually be implemented with lea: lea rsi, [rdi + rax]. The advantage is small (thanks to move-elimination) and on many Intel processors this restricts the execution ports which the operation can be executed by, but on modern processors (Ice Lake and newer, Zen 3/4) lea (especially with only 2 parts in the address, and not rip-relative) is quite good.

If modern instructions are allowed, not and and can be merged into andn, which is non-destructive so you can also replace a mov with it:

MOV r10, [rdi+rax]
ANDN rsi, r10, r8
SUB r10, rcx
TEST rsi, r10
JNZ while_single

Excessive alignment

The initial loop ensures that the address is aligned to a multiple of 32. That works, but you only need an alignment of 8 to make reading qwords from the string safe (in the sense of not triggering a page fault when the string ends nears a page boundary and the next page is not accessible). Over-aligning the address means that the slower byte-by-byte loops makes on average more iterations than it needs to.

Loop pattern

Loops like this:

while_parallel_loop:
    ...
    Jcc while_single
    ADD rax,8
    JMP while_parallel_loop
while_single:

Can be rewritten into this form:

    JMP loop_entry     ; could use "sub rax, 8" in this case
while_parallel_loop:
    ADD rax, 8
loop_entry:
    ...
    Jcc while_parallel_loop    ; opposite condition
while_single:

The while_single loop

The loop at the end, checking which of the 8 bytes within a qword (that is already known to contain a zero byte in it somewhere) is zero, can be replaced with a couple of instructions (without a loop) that find the index of the lowest set bit within the mask that was computed by the bithack, and then convert that bit-index into a byte-index, as shown in the answer on Stack Overflow.

\$\endgroup\$
4
  • \$\begingroup\$ > "could use "sub rax, 8" in this case" What do you mean by this? \$\endgroup\$ Jun 4, 2023 at 19:53
  • 1
    \$\begingroup\$ @HeapUnderStop the JMP skips the ADD in this case. In general there might be something there that cannot be "cancelled out", but an addition can be cancelled out with a subtraction. \$\endgroup\$
    – harold
    Jun 4, 2023 at 19:58
  • \$\begingroup\$ The advantage is small (thanks to move-elimination) - unless your code is bottlenecked on front-end throughput, then saving a uop for the front-end is exactly as good as you'd hope. Also, Ice Lake disabled mov-elim for integer registers in a microcode update to work around an erratum, so once again, a significant fraction of CPUs don't have it, forcing tune=generic to make tradeoffs. /sigh. At least it was only Ice Lake, not Skylake. (SKL has other performance potholes from errata, though, some arguably worse like the JCC erratum, and a disabled LSD loop buffer being the other major one.) \$\endgroup\$ Jun 5, 2023 at 7:21
  • \$\begingroup\$ lea is also good for flags elim; which probably isn't a problem in this code. \$\endgroup\$
    – Joshua
    Jun 5, 2023 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.