WHO'S AWESOME

We often face such a scenario in writing code:

our_loop:
    // some code before
    if (flag):
       do_something()
    else:
       do_something_else()
    // some code after

The flag is usually a constant, for example, an argument (e.g. true/false; 0/1) we passed to this function at runtime. The functions do_something() and do_something_else() may also be some code blocks and they’re almost identical. Well, if we know the flag will definitely not change within the loop we can move the conditional statement out of the loop so that the flag will only be tested once.

if (flag):
    our_loop:
        // some code before
        do_something()
        // some code after
else:
    our_loop:
        // some code before
        do_something_else()
        // some code after

This is great, except, …, well, it really looks ugly and we’re repeating ourselves. If the code within the loop is large, it makes our binary executable a bit larger (.text section).

To be concrete, let’s consider the following C++ code that computes the rank of the current value in arr[beg, end):

int get_rank(int arr[], int beg, int end, int cur, bool desc)
{
    int rank = 1;
    for (int i = beg; i < end; ++i) {
        if (i == cur)
            continue;
        if (!desc) {
            if (arr[i] < arr[cur])
                rank++;
        }
        else {
            if (arr[i] > arr[cur])
                rank++;
        }
    }
    return rank;
}

One may want to compute the ascending rank or the descending rank of a value in an array/range. Here the order (asc/desc) is a runtime constant. However, if it’s a compile-time constant one can avoid repeating themselves by using C++17’s if constexpr:

template<bool desc>
int get_rank(int arr[], int beg, int end, int cur)
{
    int rank = 1;
    for (int i = beg; i < end; ++i) {
        if (i == cur)
            continue;
        if constexpr(!desc) {  // requires C++17 or later
            if (arr[i] < arr[cur])
                rank++;
        }
        else {
            if (arr[i] > arr[cur])
                rank++;
        }
    }
    return rank;
}

// usage:
// int rank = get_rank<false>(arr, beg, end, cur);
// or
// constexpr bool desc = false; // or some compile-time constant
// int rank = get_rank<desc>(arr, beg, end, cur);

This solution combines both efficiency and elegance (thanks to the compiler). But how about the efficiency of the non-templated function (the one with an additional parameter desc)? I wasn’t sure if the compiler would do any sort of optimization. But I do know that modern computer architectures are designed to do a great job in branch prediction. The compiler may also aid in generating branch-friendly (or even branchless) code. So, if the prediction was correct, the fitched instructions for this branch will be kept hot (remaining in the cache and busy running in the CPU pipeline). Otherwise, the fitched instructions by the wrong prediction may be discarded (evicted from the cache) and instructions for the other branch will be fetched. Also, the CPU stalls caused by the pipeline invalidation will make it worse. Luckily, here in this case, the branch condition is constant and therefore the CPU is on our side.

Next, let’s see what the compile can do for us. Compiling this function in godbolt using gcc 12.2 with -O3 flag yields the following assembly code:

get_rank(int*, int, int, int, bool):
        movq    %rdi, %r9
        movl    %edx, %edi
        cmpl    %edx, %esi
        jge     .L9
        movslq  %ecx, %rax
        movl    $1, %edx
        leaq    (%r9,%rax,4), %r10
        movslq  %esi, %rax
        testb   %r8b, %r8b
        jne     .L8
.L5:
        cmpl    %eax, %ecx
        je      .L4
        movl    (%r10), %esi
        cmpl    %esi, (%r9,%rax,4)
        setl    %sil
        movzbl  %sil, %esi
        addl    %esi, %edx
.L4:
        addq    $1, %rax
        cmpl    %eax, %edi
        jg      .L5
        movl    %edx, %eax
        ret
.L8:
        cmpl    %eax, %ecx  ; if (i == cur)
        je      .L7
        movl    (%r10), %esi
        cmpl    %esi, (%r9,%rax,4)
        setg    %sil
        movzbl  %sil, %esi
        addl    %esi, %edx
.L7: ; for (int i = beg; i < end; ++i)
        addq    $1, %rax
        cmpl    %eax, %edi
        jg      .L8
        movl    %edx, %eax
        ret
.L9:
        movl    $1, %edx
        movl    %edx, %eax
        ret

We can see that desc is only tested once. Cheers! With -O0 flag it gives

get_rank(int*, int, int, int, bool):
        pushq   %rbp
        movq    %rsp, %rbp
        movq    %rdi, -24(%rbp)
        movl    %esi, -28(%rbp)
        movl    %edx, -32(%rbp)
        movl    %ecx, -36(%rbp)
        movl    %r8d, %eax
        movb    %al, -40(%rbp)
        movl    $1, -4(%rbp)
        movl    -28(%rbp), %eax
        movl    %eax, -8(%rbp)
        jmp     .L2
.L6:
        movl    -8(%rbp), %eax
        cmpl    -36(%rbp), %eax
        je      .L8
        movzbl  -40(%rbp), %eax
        xorl    $1, %eax
        testb   %al, %al
        je      .L5
        movl    -8(%rbp), %eax
        cltq
        leaq    0(,%rax,4), %rdx
        movq    -24(%rbp), %rax
        addq    %rdx, %rax
        movl    (%rax), %edx
        movl    -36(%rbp), %eax
        cltq
        leaq    0(,%rax,4), %rcx
        movq    -24(%rbp), %rax
        addq    %rcx, %rax
        movl    (%rax), %eax
        cmpl    %eax, %edx
        jge     .L4
        addl    $1, -4(%rbp)
        jmp     .L4
.L5:
        movl    -8(%rbp), %eax
        cltq
        leaq    0(,%rax,4), %rdx
        movq    -24(%rbp), %rax
        addq    %rdx, %rax
        movl    (%rax), %edx
        movl    -36(%rbp), %eax
        cltq
        leaq    0(,%rax,4), %rcx
        movq    -24(%rbp), %rax
        addq    %rcx, %rax
        movl    (%rax), %eax
        cmpl    %eax, %edx
        jle     .L4
        addl    $1, -4(%rbp)
        jmp     .L4
.L8:
        nop
.L4:
        addl    $1, -8(%rbp)
.L2: ; for (int i = beg; i < end; ++i)
        movl    -8(%rbp), %eax
        cmpl    -32(%rbp), %eax
        jl      .L6
        movl    -4(%rbp), %eax
        popq    %rbp
        ret

which suggests desc is tested within each loop.

Now we know that compilers can actually perform this optimization (although it’s not enabled by default), we should be relaxed and fearless to choose our seemingly inefficient but shorter & sweeter code. Cheers again ;)

See also https://en.wikipedia.org/wiki/Loop-invariant_code_motion, https://en.wikipedia.org/wiki/Loop_unswitching, http://www.cs.cmu.edu/afs/cs/academic/class/15745-s06/web/handouts/06.pdf.

We can turn any process into a server in an incredibly simple manner using the powerful networking utility netcat. For example, we can make a shell a server:

(a computer with ip address 192.168.1.2)
$ mkfifo fifo  # create a named pipe
$ cat fifo | sh -i 2>&1 | nc -l 1234 > fifo  # server

(on another window)
$ nc localhost 1234  # client

(or if you're on the same netwok from another computer)
$ nc 192.168.1.2 1234  # client

Now let’s try to understand the above-highlighted line. Noting that a pipeline runs in parallel, cat fifo therefore outputs the content of fifo only when nc -l 1234 writes its output to the pipe fifo.

We know that when the client connects to the server via netcat, if the client types in anything, it will be output to the server; and vice versa. Hence, nc localhost 1234‘s input becomes nc -l 1234‘s output, and nc -l 1234‘s input becomes nc localhost 1234‘s output.

When the client types in something, say, the command ls, it also appears in the output of the server, which then is redirected to the pipe fifo, which in turn goes to cat fifo (read end comes the data). Then the output of cat fifo (“ls”) is redirected to as the input of sh -i 2>&1, which executes the command ls and sends the results to the server nc -l 1234 as its input, which finally as output appears in the client nc localhost 1234.

Isn’t it beautiful? Just setting a few pipes and redirections we can turn a process into a server. Pipes are really one of the greatest UNIX inventions. They make many incredible things possible.

See also using netcat as a proxy.

Consider the following code:

int main()
{
    struct s {
        int m0;
        int m1;
        int m2;
    };

    struct s *p = NULL;
    int a = (int) &((struct s *)p)->m2;  // crash ??
    int b = (int) &((struct s *)0)->m2;  // crash ??
    int c = (int) p->m2;  // definitely dead

    return 0;
}

So, do you think the above two highlighted lines will crash the program? Well, at least to me, it will, since they’re dereferencing null pointers. Take, int b = (int) &((struct s *)0)->m2;, for example, we first dereference the zero pointer to get the member m2, and then obtain its address. Right? This is how we literally read &p_struct->member.

However, this is not how the compiler interprets it. The compiler is a very cool and knowledgeable guy who is assumed to know everything. So the compiler knows the offset of each member in a structure, and he says, “Well, why do I even care for the values of those members (dereferencing)? To obtain the address of a member in a structure, I just need to add the offset of the member to the address of the structure: &p_struct->member := p_struct + offset(member).”

With such ability, the compiler now can generate assembly code

6       {
   0x0000000000001129 <+0>:     endbr64
   0x000000000000112d <+4>:     push   %rbp
   0x000000000000112e <+5>:     mov    %rsp,%rbp

7           struct s {
8               int m0;
9               int m1;
10              int m2;
11          };
12
13          struct s *p = NULL;
   0x0000000000001131 <+8>:     movq   $0x0,-0x8(%rbp)

14          int a = (int) &((struct s *)p)->m2;  // okay
   0x0000000000001139 <+16>:    mov    -0x8(%rbp),%rax
   0x000000000000113d <+20>:    add    $0x8,%rax
   0x0000000000001141 <+24>:    mov    %eax,-0x14(%rbp)

15          int b = (int) &((struct s *)0)->m2;  // okay
   0x0000000000001144 <+27>:    movl   $0x8,-0x10(%rbp)

16          int c = (int) p->m2;  // dead
   0x000000000000114b <+34>:    mov    -0x8(%rbp),%rax
   0x000000000000114f <+38>:    mov    0x8(%rax),%eax # segfault, since it tries to access invalid memory address 0x8 (page 0)
   0x0000000000001152 <+41>:    mov    %eax,-0xc(%rbp)

17
18          return 0;
   0x0000000000001155 <+44>:    mov    $0x0,%eax

19      }
   0x000000000000115a <+49>:    pop    %rbp
   0x000000000000115b <+50>:    ret

We can see that there are no dereferences whatsoever when we try to get the address of a member in a structure, just the addition of the member offset to the address of the structure.

Therefore, as a special case with the structure address being zero, &((TYPE *)0)->MEMBER yields the exact offset of the member in a structure, which accounts for why the macro

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

works in the Linux kernel.

The basic idea is open addressing, but without any redirections (thus making Swiss tables very memory efficient). Also, Swiss tables store a densely packed array of metadata with each entry consisting of 1 byte (which makes the metadata table easier to fit into CPU cache, as opposed to, say, a metadata of pointers of 8 bytes), sort of like UNIX file system inodes and bit maps (see OSTEP: Chapter 40 File System Implementation). Thus, we can use the metadata to tell if an entry in the table is present or not (by using the single control bit and the 7-bit H2 hash, see the details at https://abseil.io/about/design/swisstables).

And there’s an excellent video about it on youtube.

Finally, let’s see the performance differences on the counting words benchmark.

see the details at https://stackoverflow.com/questions/6972635/efficient-string-sorting-algorithm/71349193#71349193