Discrete Inversion (Generating Random Sequences XII)

While this sounds something like a shameful family secret, discrete inversion is only the finite-valued variation on the method of inversion for the generation of random numbers with a given distribution (as I’ve discussed quite a while ago here). The case we’ll consider here is a random variable with few possible outcomes, each with different odds

Of small copies and templates.

Sometimes, it’s the little things that make a big difference. For example, moving small, not machine-sized, pieces of data may be a problem. If it happens to be machine-sized (that is, the size of something like uint32_t), then the copy is readily done by a single (integer) copy. But what if it’s, say, 5 bytes?

The first solution that comes to mind is either a for-loop or a call to a library function like memcpy. The for-loop would give something like:

char * dest = ...
char * src = ...
for (std::size_t i=0;i<5;i++) dest[i]=src[i];

If you’re lucky, the compiler understands the small copy and optimizes. More likely, it will merely unroll the loop and generate something like:

14d4:   0f b6 07    movzx  eax,BYTE PTR [rdi]
14df:   88 04 24    mov    BYTE PTR [rsp],al
14e2:   0f b6 47 01 movzx  eax,BYTE PTR [rdi+0x1]
14e6:   88 44 24 01 mov    BYTE PTR [rsp+0x1],al
14ea:   0f b6 47 02 movzx  eax,BYTE PTR [rdi+0x2]
14ee:   88 44 24 02 mov    BYTE PTR [rsp+0x2],al
14f2:   0f b6 47 03 movzx  eax,BYTE PTR [rdi+0x3]
14f6:   88 44 24 03 mov    BYTE PTR [rsp+0x3],al
14fa:   0f b6 47 04 movzx  eax,BYTE PTR [rdi+0x4]
14fe:   88 44 24 04 mov    BYTE PTR [rsp+0x4],al

Let’s see how we can fix that!