BB y
AA x
AA xx
AA x
BB x

AA
        x
        x
        xx
BB
        x
        y

$ gcc -O2 -fno-omit-frame-pointer -fno-inline -g \
      textprocessor1.c -o textprocessor1

$ python gen_test_data.py > input.txt

$ sudo perf stat \
      ./textprocessor1 input.txt /dev/null

# started on Sun Oct  6 21:40:42 2019
Performance counter stats for './textprocessor1 input.txt /dev/null':

      1,676.09 msec task-clock       #    1.000 CPUs utilized
             4      context-switches #    0.002 K/sec
             0      cpu-migrations   #    0.000 K/sec
       106,012      page-faults      #    0.063 M/sec
 5,016,328,300      cycles           #    2.993 GHz
10,217,335,197      instructions     #    2.04  insn per cycle
 2,253,680,016      branches         # 1344.605 M/sec
    15,744,959      branch-misses    #    0.70% of all branches

   1.676458791 seconds time elapsed

   1.420940000 seconds user
   0.255449000 seconds sys

$ sudo perf record -g --call-graph fp \
      -o textprocessor1.fp.perf.data \
      ./textprocessor1 input.txt /dev/null

$ sudo perf report --stdio --children \
      -i textprocessor1.fp.perf.data

47.91%     0.00%  textprocessor1  [unknown] [.] 0x08ce258d4c544155
    |
    ---0x8ce258d4c544155
        __libc_start_main
        |
        --47.67%--main
                    |
                    |--29.52%--__strcmp_sse2_unaligned
                    |
                    |--14.55%--string_map_add
                    |
                    |--1.59%--string_map_delete
                    |          |
                    |           --1.53%--cfree@GLIBC_2.2.5
                    |
                    --1.01%--string_list_append

39.01%    34.26%  textprocessor1  libc-2.27.so [.] __strcmp_sse2_unaligned
        |
        |--29.57%--0x8ce258d4c544155
        |          __libc_start_main
        |          main
        |          |
        |          |--24.95%--__strcmp_sse2_unaligned
        |          |
        |           --4.62%--string_map_add
        |
         --9.41%--__strcmp_sse2_unaligned

$ sudo perf record -g --call-graph lbr \
      -o textprocessor1.lbr.perf.data \
      ./textprocessor1 input.txt /dev/null

$ sudo perf report --stdio --children \
      -i textprocessor1.lbr.perf.data

99.36%     0.00%  textprocessor1  textprocessor1     [.] _start
        |
        ---_start
           __libc_start_main
           main
           |
           |--45.63%--string_map_add
           |          |
           |           --28.90%--strcmp@plt
           |
           |--13.05%--string_list_append
           |          |
           |          |--11.81%--__strdup
           |          |          |
           |          |          |--9.97%--malloc
           |          |          |          _int_malloc
           |          |          |          |
           |          |          |          |--3.87%--0xffffffff8c2010ee

$ sudo perf report --stdio --no-children \
      -i textprocessor1.lbr.perf.data

33.44%  textprocessor1  libc-2.27.so [.] __strcmp_sse2_unaligned
        |
        |--23.73%--strcmp@plt
        |          string_map_add
        |          main
        |          __libc_start_main
        |          _start
        |
        |--4.95%--string_map_add
        |          main
        |          __libc_start_main
        |          _start
        |
         --4.68%--str_ptr_compare
                   msort_with_tmp.part.0
                   |
                   |--4.13%--msort_with_tmp.part.0

int string_map_add(string_map *self, const char *key,
                   const char *value) {
  assert(self != NULL);
  assert(key != NULL);
  assert(value != NULL);

  // Find the matching key and add the value to the list.
  size_t i;
  for (i = 0; i < self->num_elements; ++i) {
    if (strcmp(key, self->elements[i].key) == 0) {
      return string_list_append(self->elements[i].value, value);
    }
  }

  // ... skipped ...

  string_map_entry *ent = &self->elements[self->num_elements];
  ent->key = new_key;
  ent->value = new_list;
  self->num_elements++;
  return 1;
}

int string_map_add(string_map *self, const char *key,
                   const char *value) {
  assert(self != NULL);
  assert(key != NULL);
  assert(value != NULL);

  // Find the matching key and add the value to the list.
  size_t start = 0;
  size_t end = self->num_elements;
  while (start < end) {
    size_t mid = start + (end - start) / 2;
    int cmp = strcmp(self->elements[mid].key, key);
    if (cmp == 0) {
      return string_list_append(self->elements[mid].value, value);
    } else if (cmp < 0) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }

  // ... skipped ...

  memmove(self->elements + start + 1, self->elements + start,
          sizeof(string_map_entry) * (self->num_elements - start));
  string_map_entry *ent = &self->elements[start];
  ent->key = new_key;
  ent->value = new_list;
  self->num_elements++;
  return 1;
}

$ gcc -O2 -fno-omit-frame-pointer -fno-inline -g \
      textprocessor2.c -o textprocessor2

$ sudo perf stat \
      ./textprocessor2 input.txt /dev/null

# started on Sun Oct  6 21:40:44 2019
Performance counter stats for './textprocessor2 input.txt /dev/null':

      1,090.55 msec task-clock       #    1.000 CPUs utilized
             5      context-switches #    0.005 K/sec
             0      cpu-migrations   #    0.000 K/sec
       106,011      page-faults      #    0.097 M/sec
 2,973,836,135      cycles           #    2.727 GHz
 2,754,413,677      instructions     #    0.93  insn per cycle
   555,628,887      branches         #  509.493 M/sec
    13,331,051      branch-misses    #    2.40% of all branches

   1.090851312 seconds time elapsed

   0.910295000 seconds user
   0.180455000 seconds sys

$ sudo perf record -g --call-graph lbr \
      -o textprocessor2.lbr.perf.data \
      ./textprocessor2 input.txt /dev/null

$ sudo perf report --stdio --no-children \
      -i textprocessor2.lbr.perf.data

14.35%  textprocessor2  libc-2.27.so       [.] cfree@GLIBC_2.2.5
    |
     --14.31%--free@plt
               string_list_delete
               string_map_delete
               main
               __libc_start_main
               _start

struct arena_allocator {
  char *buf_head;
  size_t begin;
};

arena_allocator *arena_new() {
  arena_allocator *self =
      (arena_allocator *)malloc(sizeof(arena_allocator));
  if (!self) {
    return NULL;
  }
  self->buf_head = NULL;
  self->begin = 0;
  return self;
}

void arena_delete(arena_allocator *self) {
  if (self) {
    void *cur = self->buf_head;
    while (cur != NULL) {
      void *next = *(void **)cur;
      free(cur);
      cur = next;
    }
    free(self);
  }
}

void *arena_alloc(arena_allocator *self, size_t size) {
  assert(self != NULL);

  size_t aligned_begin = ARENA_ALLOC_ALIGN(self->begin);
  size_t aligned_end = aligned_begin + size;

  if (self->buf_head && aligned_end <= ARENA_ALLOC_BUF_SIZE) {
    void *p = self->buf_head + aligned_begin;
    self->begin = aligned_end;
    return p;
  }

  size_t alloc_size = MAX(sizeof(void *) + size, ARENA_ALLOC_BUF_SIZE);
  char *buf = (char *)malloc(alloc_size);
  if (!buf) {
    return NULL;
  }

  *(void **)buf = self->buf_head;
  self->buf_head = buf;
  self->begin = sizeof(void *) + size;
  return buf + sizeof(void *);
}

$ gcc -O2 -fno-omit-frame-pointer -fno-inline -g \
      textprocessor3.c -o textprocessor3

$ sudo perf stat \
      ./textprocessor3 input.txt /dev/null

# started on Sun Oct  6 21:40:45 2019
Performance counter stats for './textprocessor3 input.txt /dev/null':

            841.33 msec task-clock       #    1.000 CPUs utilized
                 8      context-switches #    0.010 K/sec
                 0      cpu-migrations   #    0.000 K/sec
           105,264      page-faults      #    0.125 M/sec
     2,595,040,498      cycles           #    3.084 GHz
     2,600,730,011      instructions     #    1.00  insn per cycle
       545,582,983      branches         #  648.473 M/sec
        13,110,046      branch-misses    #    2.40% of all branches

       0.841712243 seconds time elapsed

       0.641217000 seconds user
       0.200380000 seconds sys

$ sudo perf record -g --call-graph lbr \
      -o textprocessor3.lbr.perf.data \
      ./textprocessor3 input.txt /dev/null

$ sudo perf report --stdio --no-children \
      -i textprocessor3.lbr.perf.data

16.11%  textprocessor3  libc-2.27.so       [.] __strcmp_sse2_unaligned
        |
        |--10.41%--str_ptr_compare
        |          msort_with_tmp.part.0
        |          |
... skipped ...
        |          |
        |           --1.13%--__GI___qsort_r
        |                     string_map_sort
        |                     main
        |                     __libc_start_main
        |                     _start
        |
         --5.49%--strcmp@plt
                   string_map_add
                   main
                   __libc_start_main
                   _start

12.77%  textprocessor3  libc-2.27.so       [.] __strlen_avx2
        |
        |--11.93%--@plt
        |          _IO_fputs
        |          string_map_dump
        |          main
        |          __libc_start_main
        |          _start
        |
         --0.82%--strlen@plt
                   string_list_append
                   main
                   __libc_start_main
                   _start

struct string {
  size_t len;
  char str[];
};

int string_list_append(string_list *self, const char *str,
                       arena_allocator *allocator) {
  size_t len = strlen(str);
  string *new_str = (string *)arena_alloc(
      allocator, sizeof(string) + len + 1);
  if (!new_str) {
    return 0;
  }
  new_str->len = len;
  memcpy(new_str->str, str, len + 1);

  // ... skipped ...
}

void string_map_dump(string_map *self, FILE *fp) {
  size_t i, j;
  for (i = 0; i < self->num_elements; ++i) {
    // ... skipped ...
    for (j = 0; j < list->num_elements; ++j) {
      fputc('\t', fp);
      fwrite(list->elements[j]->str, list->elements[i]->len, 1, fp);
      fputc('\n', fp);
    }
  }
}

$ gcc -O2 -fno-omit-frame-pointer -fno-inline -g \
      textprocessor4.c -o textprocessor4

$ sudo perf stat \
      ./textprocessor4 input.txt /dev/null

# started on Sun Oct  6 21:40:46 2019
 Performance counter stats for './textprocessor4 input.txt /dev/null':

            824.87 msec task-clock       #    1.000 CPUs utilized
                 3      context-switches #    0.004 K/sec
                 0      cpu-migrations   #    0.000 K/sec
           106,827      page-faults      #    0.130 M/sec
     2,546,158,876      cycles           #    3.087 GHz
     2,529,577,956      instructions     #    0.99  insn per cycle
       520,276,190      branches         #  630.740 M/sec
        12,139,306      branch-misses    #    2.33% of all branches

       0.825163632 seconds time elapsed

       0.601894000 seconds user
       0.223219000 seconds sys

$ sudo perf record -g --call-graph lbr \
      -o textprocessor4.lbr.perf.data \
      ./textprocessor4 input.txt /dev/null

$ sudo perf report --stdio --no-children \
      -i textprocessor4.lbr.perf.data

19.11%  textprocessor4  libc-2.27.so [.] __memmove_avx_unaligned_erms
        |
        |--12.86%--@plt
        |          |
        |          |--11.31%--_IO_file_xsputn@@GLIBC_2.2.5
        |          |          _IO_fwrite
        |          |          string_map_dump
        |          |          main
        |          |          __libc_start_main
        |          |          _start
... skipped ...

$ sudo perf report --stdio --no-children \
      -i textprocessor3.lbr.perf.data

12.77%  textprocessor3  libc-2.27.so [.] __strlen_avx2
        |
        |--11.93%--@plt
        |          _IO_fputs
        |          string_map_dump
        |          main
        |          __libc_start_main
        |          _start
... skipped ...

 8.31%  textprocessor3  libc-2.27.so [.] __memmove_avx_unaligned_erms
... skipped ...
        |
        |--1.86%--@plt
        |          |
... skipped ...
        |          |
        |           --0.72%--_IO_file_xsputn@@GLIBC_2.2.5
        |                     _IO_fputs
        |                     string_map_dump
        |                     main
        |                     __libc_start_main
        |                     _start