# Remove leading zeroes from the beginning of a string

I want to remove leading zeroes (for a big integer library I'm currently making) in numbers represented as char arrays.

I chose assembly for speed, but in order to simplify making the algorithm and all, I decided to write it in C first. Here's the algorithm, written in C.

void remove_leading_zeroes(char *number) {
char *answer = (char *)malloc(strlen(number) + 1);
bool encounteredNonZero = false;
size_t ptr = 0;
for (size_t i = 0; i < strlen(number); i++) {
if (number[i] != '0')
encounteredNonZero = true;
if (encounteredNonZero) {
ptr++;
}
}
if (!encounteredNonZero) {
ptr++;
}
}


Also, just before translating to assembly, I like to rename variables with their register equivalents in assembly. This makes it easier for me to translate. Here's the code for that (again C).

void remove_leading_zeroes(char *rdi) {
char *rsp = (char *)malloc(strlen(rdi) + 1);
bool cl = false;
size_t r8 = 0;
size_t r9 = 0;
do {
if (rdi[r9] != '0')
cl = true;
if (cl) {
rsp[r8] = rdi[r9];
r8++;
}
r9++;
} while (r9 < strlen(rdi));
if (!cl) {
rsp[r8] = '0';
r8++;
}
rsp[r8] = 0;
r9 = 0;
do {
rdi[r9] = rsp[r9];
r9++;
} while (r9 < r8);
rdi[r9] = 0;
free(rsp);
}


And finally, the assembly code I wrote. I'm an amateur, so any suggestions on how to make this faster, or any good practice I missed would be awesome.

extern strlen

section .text
; Input:
;   - char *number -> rdi. The result will be stored in the same string.

; Registers used:
;   - rax
;   - rcx
;   - rdx
;   - r8
;   - r9

push   rbp
mov    rbp, rsp
call   strlen
inc    rax
sub    rsp, rax
dec    rax
xor    cl, cl
xor    r8, r8
xor    r9, r9
cmp    byte [rdi + r9], 48
mov    cl, 1
test   cl, cl
mov    dl, byte [rdi + r9]
mov    byte [rsp + r8], dl
inc    r8
inc    r9
cmp    r9, rax
test   cl, cl
mov    byte [rsp + r8], 48
inc    r8
mov    byte [rsp + r8], 0
xor    r9, r9
mov    dl, byte [rsp + r9]
mov    byte [rdi + r9], dl
inc    r9
cmp    r9, r8
mov    byte [rdi + r9], 0
leave
ret


(I use my own strlen function which only modifies rcx)

• Do you really think an amateur is smarter than a compiler on which thousands of experimented people worked on for thousands of hours ? For fast code, write clever speed oriented C code, trying to outsmart the compiler would help only in very specific cases.
– Puck
Commented Sep 12, 2022 at 4:58
• In C, there;s no need to cast the value from malloc() - it's a void*, which converts implicitly to any pointer type. Commented Sep 12, 2022 at 7:50
• @Puck: On the other hand, one may argue that this is a fairly specific case... Commented Sep 12, 2022 at 12:02
• What problem-size are you optimizing for? Is the typical number of leading zeros like 10 or more, or hundreds? Or is it usually only a couple? And what's a common size of later data to optimize for, like ~4K, or are short strings like under 8 bytes common? Can you make any assumptions about a 16-byte load (like movdqu xmm0, [rdi]) not crossing into the next page, especially an unmapped page? Commented Sep 12, 2022 at 23:09
• Does this even work? It appears to rely on strlen not modifying RDI, but that register is call-clobbered. (What registers are preserved through a linux x86-64 function call). On Linux/glibc, RDI is probably left pointing to the last aligned cache-line of the string, or something like that. Also, you have a leading _ in the function name, but this is supposed to be for Linux. Commented Sep 13, 2022 at 0:06

For style and formatting, your asm is pretty good except for label names. Correctly indented, and some intro comments about register usage. But missing comments about even the major steps of the algorithm on any of the instructions or labels.

It would also help to leave a blank line after the end of a loop, so it's easier to see that later code isn't going to jump back into it. It's a good place to put a comment about what invariants are now true, or what the next code does.

As other answers point out, your algorithm is doing way too much work, using malloc/free (and in asm, effectively alloca) and copying your data twice, instead of just figuring out how far to memmove it.

Beyond that, you have multiple other major and minor implementation details that could be more efficient.

(Important background reading: https://agner.org/optimize/ has lots of important micro-optimization stuff, some of which I'm going to point out specifically. If you don't know what micro-uops (uops) are, go read Agner's asm optimization guide and micro-architecture guide. Also this SO Q&A and/or some of the links from my answer. Also a good idea to use compiler-generated asm as a starting-point for your hand-written asm, because compilers generally get the small details right, and might lay out the branching nicely. (If not you can try [[likely]] somewhere and try again).)

Also, not using SIMD means you can at best check 1 byte at a time, not 16 or 32. SSE2 is baseline for x86-64, so any string processing like this should be using SIMD unless you expect strings to be tiny, like less than 8 bytes or so. (Or as a baby-steps learning exercise just to write correct scalar code, not useful for performance.) With some loop unrolling, scalar could possibly check 2 bytes per clock cycle, but branching on a SIMD compare takes more work. Still a big speedup available.

You might hope that a good C compiler could optimize simple loops to use SIMD, but unfortunately existing compilers like GCC and clang can only auto-vectorize loops where the trip-count can be computed before the first iteration. i.e. not search loops with a data-dependent exit condition. (ICC can sometimes vectorize search loops, and sometimes even do a decent job at it IIRC.) So this is actually a problem where it does make sense to get your hands dirty and use SIMD intrinsics. There's little need to hand-write anything in assembly, though, especially for x86 where compilers do a good job with intrinsics.

You might also hope that repe scasb would be efficient, but it's not, unfortunately.
Only the unconditional rep movs and rep stos instructions have Fast Strings microcode. (See Why is this code using strlen heavily 6.5x slower with GCC optimizations enabled? for how GCC used to inline an inefficient strlen at -O1 or -O2 in some cases, vs. my simple example of a 16-byte-at-a-time SSE2 implementation that assumes an aligned buffer.)

### Use more concise label names, prefer NASM local labels like .else:

Asm label names are private to the current file, like static function names or goto labels within a function in C. You don't need to make them globally unique since you're not using global foo to export them.

It took me half a minute or so to figure out the naming pattern with labels like _after_remove_leading_zeroes_if_1 vs. _remove_leading_zeroes_loop_2. The "if" vs. "loop" part is a very small part of the label. It seems obvious in hindsight once you know where to look, but on reading the code for the first time, my reaction was "what is this mess of mostly-redundant long label names? Hard to see what jumps where". Then wondering why are there two different _2 labels, then finally seeing the if vs. while naming (which also apparently go with _after_remove... vs. _remove... for no apparent reason since the last label in the function isn't named "after".

Meaningful label names are tricky, so yeah you might sometimes just give up and number them from a common base.

In NASM, .bar: following a non-dot label like foo: is the same as foo.bar:, so it lets you use short label names but still avoid name conflicts with the rest of your file.

So you could have asm like

remove_leading_zeroes:      ; in Linux ELF, C names don't get leading underscores
...
je   .no_lz
; else fall through

.find_nonzero:
...
jne  .find_nonzero

.strmove:             ; in-place strcpy to fill the gap
...
jne  .strmove

.no_lz:  ; return without copying anything
ret


## Make two loops instead of branching inside loops

  do {
if (rdi[r9] != '0')
cl = true;
if (cl) {
rsp[r8] = rdi[r9];
r8++;
}
r9++;
} while (r9 < strlen(rdi));


This is searching for the first non-'0' byte in the input string, and then copying the rest of the string to another buffer. There's no reason to put those two things into one loop, and force yourself to write asm that branches inside each iteration to figure out what to do that iteration.

It wastes at least one uop every iteration, and one side of the if is going to have an extra taken branch every iteration for that phase. (Taken branches are more expensive for the front-end, since code-fetch isn't contiguous and branch prediction has to provide a correct prediction of the new place to fetch from early enough to avoid a bubble. Also, on Haswell and later, predicted-taken jump uops can only execute on port 6; the other ALU port that can check branch predictions can only handle predicted-not-taken branches.)

There's no upside; it would be more efficient to make a simple search loop, and then strcpy (manually implemented or not). If you need some extra logic to detect the case of an all-zero string, that logic can be outside any loops. Small static code-size is nice, but fewer instructions inside loops is usually more important.

I think the simplest way to handle the possibility of an input like "0000" or the empty string is to copy the first byte unconditionally, before doing anything else. That also lets the CPU get started on getting write access to the output buffer, in case it was cold in cache or TLB, letting out-of-order exec hide latency. Normally not a factor for stack space, it's usually hot in cache. (If you can't allocate the output buffer until after reading all of the input to calculate the size, that's unfortunate. Depending on your allocator, over-allocating and then using realloc to give back a chunk at the end might be ok.)

Of course this problem goes away when you're doing it in-place, not copying to a separate buffer. Once you make that other algorithmic change, you can't use ISO C strcpy since it has undefined behaviour if the src and dst overlap. So you would need to hand-roll your copy loop for that in asm, or in C use strlen and memmove, or intrinsics like _mm_cmpeq_epi8. Pure ISO C doesn't give you the building blocks you need to make an efficient version of this function, given limitations of current compilers, so the best you can portably do in C is glue together hand-written asm building blocks like strlen and memmove, even though that makes two passes over the data.

(Perhaps cache-block it in 16KiB chunks with memchr instead of strlen, so you stop after 16K and can memmove while that part of the data is still hot in L1d cache.)

In asm you can potentially do as well as the hand-written libc code, most simply by using a copy of it. https://codebrowser.dev/glibc/glibc/sysdeps/x86_64/multiarch/strlen-avx2.S.html shows a version of glibc's strlen; with minor changes you could adapt it or memchr to look for a non-match of '0'. (That would cover finding the terminating 0 byte). Or pick any other asm strlen or memchr you want. Most should be safe for the case where dst is at a lower address than src: reads will happen before writes so it should be reading pristine data.

Depending on the input buffer, you might also have to worry about alignment, e.g. a 2 byte string in the last 2 bytes of a page, followed by an unmapped page. A 16-byte load would segfault. (Or if the next page is mapped, still be expensive, worst case even paging it in from disk if it didn't otherwise need to be touched.) See Is it safe to read past the end of a buffer within the same page on x86 and x64? - an aligned 16 or 32-byte load can never be split across a wider alignment boundary like 4k. So if your input buffer is always aligned, or always at least 32 bytes allocated, this is trivial: do the first 16-byte vector unaligned, then do (p + 32) & -32 and stay aligned from there.

# Micro-optimizations

Some of these instructions are ones you won't need after algorithmic changes, but in other functions you might still want to do something similar. Some of them will still be needed in different forms.

### Prefer pointer-increments over indexed addressing modes

cmp byte [rdi + r9], 48 / jz will decode to 3 uops for the front-end on Intel Skylake CPUs. Micro-fusion is defeated by the indexed addressing mode (2 registers), and macro-fusion of the cmp/jnz doesn't happen with cmp mem,imm (See What is instruction fusion in contemporary x86 processors?).

This also saves registers; you just need an input and an output pointer. (And an end-pointer or a down-counter).

The loop structure should be something like for(char *p = start, *endp = start+len ; p<endp ; p++) { stuff with *p; }. But of course in a do{}while() style like you're doing, with the conditional branch at the bottom. That's a very Good Thing. Generating endp = start+len just takes an LEA, and then the bottom of the loop is still a cmp/jne or jb. Otherwise you might use dec ecx/jnz or whatever for a loop like do{ p++ }while(--len);. Intel CPUs can macro-fuse dec/jnz, but AMD CPUs can only macro-fuse CMP or TEST. So it can save a uop inside the loop to do a pointer compare, at the cost of needing an LEA at the start.

Of course this only applies to counted loops in the first place, and after the algorithmic changes you wouldn't have those, just search loops. But you'd still have pointers that you increment, first read-only for the first non-'0', then from there and from the start to copy, checking for a terminating 0.

In a loop where you're going to want that byte in a register later (to store), you should just load it into a register now and test it there.

  movzx  eax, byte [rdi]    ; 1 uop, no false dependency on the old RAX
cmp    al, '0'            ;   macro-fused with jnz
jnz                       ; 1 uop
; 2 total uops for the front-end, 2 for the back-end.


(Write ASCII characters as character literals like '0', not 48)

Also, use jb or ja for comparing pointers, or jl/jg for comparing signed integers. You did

 cmp    r9, r8
js   ...


This is different from jl if the subtraction has signed overflow. That's normally not going to be a problem with 64-bit integers that work as offsets to an address, because the middle of the address space (around the signed-overflow wrapping point) is non-canonical. See Should pointer comparisons be signed or unsigned in 64-bit x86?

For performance, js won't macro-fuse with cmp on Intel CPUs, but jl and jb will.

Also, for human readers, jumping on less-than has the right semantic meaning of do{}while(r9<r8) like you wrote in your C source. Jumping if the subtraction result is negative (after wrapping) does not.

### Use movzx for byte loads, especially in loops

movzx avoids false dependencies on CPUs more recent than Nehalem and first-generation Sandybridge. See Why doesn't GCC use partial registers?.

Similarly, mov ecx, 1 or xor ecx,ecx for a boolean. Don't write partial registers if you don't need to.

In fact, always xor-zero with 32-bit operand-size, even for registers that need a REX prefix to access, because early Silvermont CPUs only recognize xor r8d,r8d as a zeroing idiom, not xor r8,r8. See details in What is the best way to set a register to zero in x86 assembly: xor, mov or and?

  inc    rax
sub    rsp, rax
dec    rax


Normally you'd want to keep the stack aligned by 16, and there's no need to change RAX when you want that value later; you could add into a different register.

  lea  rcx, [rax+1 + 15]    ; rax+1  for the extra byte, and +15 as part of (x+15)&-16 to round up to the next multiple of 16
and  rcx, -16
sub  rsp, rcx             ; alignas(16) char buf[rax+1]


To save code-size, if your string will always be less than 4GiB you can use ecx for LEA and AND (32-bit operand-size is the default in x86-64 machine code with no prefixes). On a CPU without partial-register stalls, and cl, -16 would also work efficiently, since the only bits you're clearing are in the low byte so it works to leave the rest unmodified. Same as and rcx, -16 but without needing a REX prefix.

  push   rbp
mov    rbp, rsp
...
leave


That is useful if you variably modify RSP. Otherwise don't do it. Once you fix the algorithm, there's no need to touch stack space.

• (This answer is a bit disorganized because there's so many different things to point out here, and some of the micro-architecture reasons behind them are subtle. I've written about them on Stack Overflow so I linked a bunch of those Q&As to explain why something is better.) Commented Sep 14, 2022 at 7:48
• Thank you! Finally, an answer which actually reviews the assembly code. I just put the C code there so it was easier to understand. Commented Sep 15, 2022 at 9:12

### C doesn't match assembly

  for (size_t i = 0; i < strlen(number); i++) {


You don't seem to actually be doing this. Your actual assembly is more like

  for (size_t i = 0, n = strlen(number); i < n; i++) {


Which is good, as there is no reason to call strlen on each iteration.

### Could be simpler

This seems more complicated than it needs to be. Consider

    char *answer = number;
}

return;
}



At the end of this, we know the location of the first non-zero or the null. If we never incremented answer, we know that there were no leading zeroes. Therefore, we don't have to malloc or copy. No malloc means no need to free. We can also do without encounteredNonZero and ptr.

We also don't need to check if we are at the null byte. The null byte is not '0', so we can check only for '0'. The null byte and non-zero digits get caught by the same check.

We only need to check if we incremented. If we did, we found at least one leading zero and need to move the string. If we didn't, we're done. We don't need to do anything. The original string was already correct.

The memmove does not require an intermediate variable. We can call it directly and let it worry about the overlap.

It's not clear to me if converting this version to assembly is necessary. It may be that the assembly the compiler produces is already optimized as much as it can be. In particular, I would expect memmove to be more optimized than its manual replacement on most architectures. If you want, you could change the memmove to

    while (*answer) {
++number;
}
*number = 0;


Then see if you can optimize that in assembly. But as I said, I suspect that the compiler on most architectures will already do this for you. Or do something better.

There are some assumptions that this makes that the compiler might not. For example, this assumes that answer > number. This makes sense in this code, as we only increment answer, it starts as number, and we explicitly checked if they were equal. A compiler might start its memmove by checking if answer and number are equal, less than, or greater than. Because the logic is different for those three cases.

### Consider alternatives

For example:

char *remove_leading_zeroes(char *number) {
while ('0' == *number) {
++number;
}

return number;
}


This has a different signature, returning a string rather than modifying the input string. You would use this differently. You wouldn't be able to free what this returns. You'd have to keep the original separate so you could free that.

The advantage of this form is that it doesn't move/copy the string. The disadvantage is that you have to track two variables: one to free and one to use. Yes, sometimes they are the same, but you can't rely on that. Sometimes they are different.

If you hold on to the original function signature, then obviously this won't work. This is meant to be used in a different fashion. It is less generally applicable. But without any memory allocations or copies, it should be very fast. If you find speed important enough that you are optimizing into assembly, then rewriting your calling code to work with this would likely be easier. And faster, even without converting into assembly.

• Writing in assembly lets you make maximum use of SIMD, like pcmpeqb / pmovmskb / not / tzcnt to find the position of the first non-'0' byte, i.e. the special case of strspn with a 1-byte "accept" string. If you're not going to do that, then yes it's probably best to just look at compiler-generate asm. Of course, you can manually vectorize with intrinsics in C, and let the compiler take care of things like xor ecx,ecx as being more efficient than xor cl,cl (false dependency on the full RCX). Commented Sep 12, 2022 at 6:05
• (Of course you have to beware of Is it safe to read past the end of a buffer within the same page on x86 and x64? depending on how you allocated the buffer you pass to this function. Hand-writing asm has the minor advantage of completely hiding undefined behaviour from a C compiler; reading outside the bounds of an array (even if you don't cross into another page) is still technically UB.) Commented Sep 12, 2022 at 6:11
• And BTW, no, neither GCC nor clang will optimize a C version well. You might well get something better than the hand-written asm because it's full of partial-register false dependencies and stuff, but only ICC knows how to auto-vectorize a loop with a data-dependent exit condition. (Like a search loop). So pure C isn't going to get you optimal code which handles 16 or 32 bytes at a time. Or 8 bytes at a time if the leading-zero range is often short, like a qword load + xor with '00000000', then tzcnt. Commented Sep 12, 2022 at 6:14
• But anyway, +1 for good points about the C version being way over-complicated. Yeah, just in-place memmove is the obvious thing, or (if C compilers could optimize decently), a manual loop that copies until seeing a 0 byte so you don't need a strlen to start with. Or if strcpy was safe to use on overlapping input/output... Commented Sep 12, 2022 at 6:19

Choosing assembly for speed is likely an error. You will have to spend a lot of time optimising for your hardware to beat a well-tuned compiler¹. And you'll need to repeat that every time you target a new processor.

I'm disappointed to see no unit tests for the function. Never write assembly code without tests!

We are missing the necessary check whether malloc() returned null or a valid pointer. Luckily, allocation is not required, as mdfst13's answer shows.

If we write in C, we can benefit from compiler optimisations, including function inlining. We can give our compiler an opportunity to improve the memmove() by providing an assert() so that it can be sure we're moving from higher to lower addresses.

#include <assert.h>
#include <string.h>

{
}

return;
}

/* include the terminating NUL character */
}


We might find our requirements change. Perhaps users expect an input that's all zeros to result in a single zero (usually, we denote 0 thus, not as empty string). That's easy to arrange in the C code:

#include <assert.h>
#include <string.h>

{
}

/* all zeros; retain the last one */
}

/* no zeros to remove */
return;
}

/* include the terminating NUL character */

¹ Unfortunately, which I tried gcc -O3 -march=native -mtune=native, it didn't inline or optimise the library functions here. Perhaps you should consider that a cue to direct your skills to improving their code generation for all programs, rather than resorting to manual assembly code to bypass the issue.
• Also, 2 passes over the string (strlen + memmove) sucks vs. an in-place strcpy which you can write by hand in asm, using an implementation like glibc's. Of course you have to be using at least SSE2 instructions, preferably AVX2, not just scalar to get big speedups. ISO C doesn't give you efficient building blocks for this. Although in many cases you could redesign the API to take a pointer+length so there's no need to search for a terminating 0 byte, and that would also remove a tricky problem to handle from the initial memchr in terms of reading past the end of a possibly-small array Commented Sep 12, 2022 at 21:52
• See also Why is this code using strlen heavily 6.5x slower with GCC optimizations enabled? - GCC used to inline strlen inefficiently, even worse than a simple SSE2 version, especially at -O1. It's a tough tradeoff esp. w/out -march=native, since a simple inline version could be faster for small strings, but fall behind over larger strings like a few KiB, especially if they're hot in L1d cache. (A good strlen can almost keep up with L2 bandwidth but maybe only with some unrolling, and certainly L3 bandwidth for a simple version without AVX2). Commented Sep 12, 2022 at 21:57
• All good points @PeterCordes (and a worthwhile hint to OP to use compiler for a good starting point for optimising the assembly - perhaps even write partly in C and partly in compiler intrinsics or inline assembly). I see there's a chicken-and-egg problem with strlen() and strcpy() - we don't know which implementation is best until we know the length of the string! Unless we have good a priori knowledge of the likely inputs, we might need to learn from usage (a bit like like branch prediction in CPUs), but it's likely that the overhead of measurement would outweigh the benefit. Commented Sep 13, 2022 at 6:43
• In the all-zero case, why not just number[1] = '\0'; return;? Commented Sep 13, 2022 at 10:36
• Good suggestion @Roger! We still need the test that excludes "" input, so we know number[1] is valid at that point. Commented Sep 13, 2022 at 10:41