# Variable integer encoding

There is a varint encoding, which I call LEP64 (Little Endian Prefix Max 64-bit).

Basically, the first byte of the encoded value tells us, how many bytes follow (needed bytes encoded in unary coding, then the value encoded simply in binary):

First Byte   following   can encode values
bytes        between
xxxxxxx1       -       [ 0; 2^ 7-1 ]  // xxxx contains low bits of value
xxxxxx10   [1  byte]   [ 0; 2^14-1 ]
xxxxx100   [2 bytes]   [ 0; 2^21-1 ]
.
.
x1000000   [6 bytes]   [ 0; 2^49-1 ]
10000000   [7 bytes]   [ 0; 2^56-1 ]
00000000   [8 bytes]   [ 0; 2^64-1 ]


There is a need for a function, which can write a LEP64 into a buffer. Here's my current version (for gcc, can be ported to any current compiler easily):

int enc(unsigned char *result, unsigned long long int value) {
int nUsedBits = 64 - __builtin_clzll(value|1);
int nBytesNeeded = (nUsedBits+6)/7;
if (nBytesNeeded<9) {
value = ((value<<1)|1)<<(nBytesNeeded-1);
} else {
*result++ = 0;
nBytesNeeded = 9;
}
__builtin_memcpy(result, &value, 8);
return nBytesNeeded;
}


The question is, is it possible to improve on this function? Algorithm-wise (I don't really like the division by 7, even though it is optimized to a mul), or implementation-wise? Some clever tricks to speed up this routine? Or maybe shorten its asm code, while retaining its speed?

Note: I interested only in x86_64 platform, and it's fine that this routine always writes at least 8 bytes.

Note2: The distribution of values -- as almost always -- skewed towards small numbers (small numbers are more probable than 8-byte numbers)

• I'm not confident enough yet about this to put it in an answer, but I suspect that since this will most likely be invoked with an arbitrarily aligned result, that memcpy(,8), might end up being mighty slow most of the time even if it compiles down to a single instruction. Have you benchmarked this against copying the right amount of bytes in various destination alignment scenarios? – Frank Nov 25 '17 at 8:06
• @Frank: on average, unaligned access on x86_64 is almost as fast as aligned access. The alternative solution (write the value as independent bytes) is certainly slower. – geza Nov 25 '17 at 10:20

## 2 Answers

I actually take issue with functions written like this in general. It screams "I am smarter than a compiler", and flies in the face of most of what C++ is about at a philosophical level.

It's not portable, it's not future-proof, it's severely hamstringing the compiler, so optimizations implemented in future versions of the compiler will likely not be able to be applied.

All this to say: for me, there needs to be a crazy strong rationale to motivate the existence of something written like this in a non-toy codebase.

The biggest culprit of this in your code is the "writing more data than the size returned" part of it. The chances of this eventually stomping out-of-bounds memory is simply not worth the marginal performance difference. Considering the places in code where such encodings tend to be used, I find it highly unlikely that it has any measurable performance impact in anything that benchmarks this in context with some other code around it.

So, now that that's out of the way, here's my feedback of the function as written:

## Don't use builtins where you don't have to.

I get using __builtin_clzll, but there is no valid reason to use __builtin_memcpy over std::memcpy.

## Don't use magic values where unnecessary

That 64 coould easily be 8 * sizeof(value). Same goes for the 9, it could be sizeof(value) + 1.

I know you only care about X86_64, and unsigned long long int is always 8 bytes on that platform, but if being safe does not cost you anything (which is the case here), then there is no excuse not to be.

Alternatively, if you really want 64 bits exactly, just use std::uint64_t instead.

## Separation of concerns

The main issue I see with your function is that it conflates the encoding and the storage. You would be better off separating them, and letting the compiler reconciliate.

In the following, encode_and_store() compiles to effectively the same thing as your enc(). On top of that, since enc() is now a pure function, and does not involve any side effect anymore, the compiler is a lot more free to mix and merge it with the calling context, so odds are it'll end up being faster in actual use.

std::tuple<unsigned long long int, int> enc(unsigned long long int value) {
int nUsedBits = 64 - __builtin_clzll(value|1);
int nBytesNeeded = (nUsedBits+6)/7;

if (nBytesNeeded<9) {
value = ((value<<1)|1)<<(nBytesNeeded-1);
}
return std::make_tuple(value, nBytesNeeded);
}

int enc_and_store(unsigned char *result, unsigned long long int value) {
auto [data, bytes] = enc(value);
if(bytes >= 9) {
*result++ = 0;
}

__builtin_memcpy(result, &data, 8);
return bytes;
}

• Thanks for the answer! While I agree on most of your comments, these weren't my concerns. My main concern is the performance of the code, or decreasing code size, while retaining performance. 2 comments: 1) this is not true: "The chances of this eventually stomping out-of-bounds memory is simply not worth the marginal performance difference." There is a huge difference between this version and a "write byte-by-byte" version. 2) this is not a toy code. It is actually future proof, and portable among all little endian machines. Of course, there is a separate code for big endian machines. – geza Nov 29 '17 at 0:10
• @geza I never sugegsted you write byte by byte, I implied you use memcpy with a dynamic argument size. Declare your intent and let your compiler do its job. In any case, that point becomes moot if you apply the real main suggestion: separating the encoding from the storage. About the performance, I was refering to the performance of a fuil project making use of this code. If a program spends 0.01% of its time in there, making it 10 times faster is pointless. – Frank Nov 29 '17 at 1:21
• memcpy will do something like that. It is much slower, than a simple mov instruction. So no, I don't let the compiler do its job, because it will generate much slower code. And there's no point separating the encoding from the storage, because I need both. My program takes considerably more time than 0.01% in this routine at a specific part of the program, that's why I want to optimize it. – geza Nov 29 '17 at 1:25
• @Frank Code is about solving problems. There's no point having pretty code if the code does a worse job. That your answer doesn't understand this (and your strange comment in the last paragraph about compilers and side effects) makes me very tempted to downvote, but you have some good advice mixed in with the bad, so I won't. – Veedrac Dec 2 '17 at 12:09

Right off the bat, I see you're using arbitrary-width types to represent fixed-width values; though this isn't wrong per-se, it is certainly needlessly confusing.

If you use something like __builtin_memcpy, comment it with why you did so. As far as I can tell from looking at the assembly, this never produces different output than a straightforward, standard memcpy, so I'm strongly tempted to use the later.

Being performance conscious doesn't even mean you get to drop operator spacing, so do more of that!

We see that your if is late; doing an early test as

if (value >= (UINT64_C(1) << 56)) {
*result++ = 0;
memcpy(result, &value, 8);
return 9;
}


produces the same number of instructions total, but early-outs (*) faster for the exceptional case. Unfortunately the normal case (†) gets an extra movabs rax, 72057594037927935, though that can in theory be done in parallel to the main operations by the CPU.

    ---  before  ---                          ---  after  ---
† *     mov     rax, rsi                  † *     movabs  rax, 72057594037927935
† *     mov     ecx, 70                   † *     cmp     rsi, rax
† *     mov     edx, 613566757            † *     ja      .L5
† *     or      rax, 1                    †       mov     rax, rsi
† *     lzcnt   rax, rax                  †       mov     ecx, 70
† *     sub     ecx, eax                  †       mov     edx, 613566757
† *     mov     eax, ecx                  †       or      rax, 1
† *     mul     edx                       †       lea     rsi, [rsi+1+rsi]
† *     sub     ecx, edx                  †       lzcnt   rax, rax
† *     mov     eax, ecx                  †       sub     ecx, eax
† *     shr     eax                       †       mov     eax, ecx
† *     add     eax, edx                  †       mul     edx
† *     shr     eax, 2                    †       sub     ecx, edx
† *     cmp     eax, 8                    †       mov     eax, ecx
† *     jg      .L2                       †       shr     eax
†       lea     edx, [rax-1]              †       add     eax, edx
†       lea     rsi, [rsi+1+rsi]          †       shr     eax, 2
†       shlx    rsi, rsi, rdx             †       lea     edx, [rax-1]
†       mov     QWORD PTR [rdi], rsi      †       shlx    rsi, rsi, rdx
†       ret                               †       mov     QWORD PTR [rdi], rsi
.L2:                                  †       ret
*     mov     BYTE PTR [rdi], 0             .L5:
*     add     rdi, 1                      *     mov     BYTE PTR [rdi], 0
*     mov     eax, 9                      *     mov     QWORD PTR [rdi+1], rsi
*     mov     QWORD PTR [rdi], rsi        *     mov     eax, 9
*     ret                                 *     ret


You can take a milder approach and just move the original compare earlier.

#include <cstdint>
#include <cstring>

int32_t enc(unsigned char *result, uint64_t value) {
int32_t clz = __builtin_clzll(value | 1);
if (clz < 8) {
*result++ = 0;
memcpy(result, &value, 8);
return 9;
}

int32_t nBytesNeeded = ((64 - clz) + 6) / 7;
value = ((value << 1) | 1) << (nBytesNeeded - 1);
__builtin_memcpy(result, &value, 8);
return nBytesNeeded;
}


This actually removes an instruction from the total, but it seems to be pretty much random that before the compiler was going add rdi, 1 mov QWORD PTR [rdi], rsi and now it does mov QWORD PTR [rdi+1], rsi. Nonetheless, the faster early-out is a good thing, and you should see a small win proportional to the frequency of large integers in the program.

The rest of the logic is a little unfortunate, and as you said it's not easy to simplify. However, you can always use a lookup table!

#include <cstdint>
#include <cstring>

constexpr int8_t gap_sizes[] = {
0, 0, 0, 0, 0, 0, 0,
7, 7, 7, 7, 7, 7, 7,
6, 6, 6, 6, 6, 6, 6,
5, 5, 5, 5, 5, 5, 5,
4, 4, 4, 4, 4, 4, 4,
3, 3, 3, 3, 3, 3, 3,
2, 2, 2, 2, 2, 2, 2,
1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0,
0,
};

int32_t enc(unsigned char *result, uint64_t value) {
int8_t clz = __builtin_clzll(value);
if (clz < 8) {
*result++ = 0;
memcpy(result, &value, 8);
return 9;
}

int8_t gap = gap_sizes[clz];
value = ((value << 1) | 1) << gap;
memcpy(result, &value, 8);
return gap + 1;
}


This is only a good idea if you expect this code to be hot, but it sounds like you do. The 65 byte table is pretty small as things go, especially given you dropped a multiplication in the process.

    xor     eax, eax
lzcnt   rax, rsi
cmp     eax, 7
jle     .L6
movsx   eax, BYTE PTR gap_sizes[rax]
lea     rsi, [rsi+1+rsi]
shlx    rsi, rsi, rax
add     eax, 1
mov     QWORD PTR [rdi], rsi
ret
.L6:
mov     BYTE PTR [rdi], 0
mov     eax, 9
mov     QWORD PTR [rdi+1], rsi
ret


Our latency chain is basically

    lzcnt   rax, rsi
movsx   eax, BYTE PTR gap_sizes[rax]
shlx    rsi, rsi, rax
mov     QWORD PTR [rdi], rsi


which is about 6 cycles, half of which is lzcnt. This isn't all that long. Given the main assembly body is 11 instructions, and you'd expect an IPC approaching 4 when running a chain of these, you should expect to spend about 3 cycles per enc.

That bounds how much better you can do than that: it's going to be tough given lzcnt has a latency of 3 and throughput of 1 per cycle. The only ways I can see that seem feasible involve operating on multiple of these at once, but given these are 64 bit inputs there isn't much SIMD-style parallelism that can happen.

So that's all I've got. Predictable code might win on latency by replacing the lzcnt and lookup with inline branches, utilizing processor IPC to make branch evaluation fast, but even if it does win it's unlikely to do so outside of controlled environments and is less likely to pipeline well.

• Thanks for the answer, the table idea is quite useful! I'll benchmark it, it could be faster than my version indeed. What do you mean by this? "you're using arbitrary-width types to represent fixed-width values" – geza Dec 2 '17 at 12:19
• @geza Eg. unsigned long long int, which varies in size by platform and compiler. – Veedrac Dec 2 '17 at 12:33
• @geza Note that my code is untested, so make sure to check things. – Veedrac Dec 2 '17 at 12:34