This is probably the most useless optimization I've ever made. I can imagine this solution could be used as part of a more complex search algorithm or, in rare cases, to search for a combination in a short string. Anyway, have fun reading this. Full source code can be found here: https://github.com/Lezh1k/Codewars_c/blob/master/src/trench_assault.c Problem In short, there are two groups of letters. Each letter has a 'weight.' Full problem statement here. The left side letters and their power: w - 4 p - 3 b - 2 s - 1 The right side letters and their power: m - 4 q - 3 d - 2 z - 1 So, we need a function to acquire each symbol's weight and "side" in the input string. The side can be defined as a sign of the weight (negative - left side, positive - right side). Solution Let's define the letters and sides: static const char left_side_letters[] = {'s', 'b', 'p', 'w', 0};
static const char right_side_letters[] = {'z', 'd', 'q', 'm', 0};
static const char relief_letters[] = {' ', '-', '|', 0}; These arrays will be cast to uint32. Do not do it on prod. Use union instead. Something like this: typedef union short_str {
  uint32_t val;
  char arr[4];
} short_str_t; The most obvious way is to use a simple switch, but it’s easy to lose something there. So, here is the initial simplest implementation of the 'weight' function: int weight_slow(char s) {
  for (const char *pl = relief_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return 0;
  }

  for (const char *pl = left_side_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return -((int)(pl - left_side_letters) + 1);
  }

  for (const char *pl = right_side_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return (int)(pl - right_side_letters) + 1;
  }
  // invalid input, raise error
  exit(1);
} But I didn't feel like this was the fastest way to find a character in a short string. These 4 bytes fit one 32-bit integer. Therefore, we can combine making a mask from the searched byte and XORing it with one of the letter sets. Optimizations The main idea is pretty simple. For example, left-side letters can be expressed as 0x73627077. If we are looking for symbol 'p' (0x70), we can xor each byte with 0x70, and only the match will give zero as the XOR result. In our case, the result is 0x03120007. The only thing left is to find the index of the 0x00 byte in an integer. This is possible. See the weight function below. MMX Optimization The first attempt included an MMX because there are special CPU instructions on comparing bytes and getting the mask. .intel_syntax noprefix
.text
.global barr8_char_idx

# Function prototype:
# int barr8_char_idx(const char* array, char input_char);

barr8_char_idx:
    # array (address of 8-byte array) -> rdi
    # input_char -> esi 
    movdqu    xmm0, [rdi]
    # Broadcast the input_char across an SSE register
    movd    xmm1, esi
    pshufd  xmm1, xmm1, 0
    # Compare each byte of xmm0 with xmm1
    pcmpeqb xmm0, xmm1
    # Extract the result into a mask
    pmovmskb eax, xmm0
    # Check if the mask is non-zero
    test    eax, eax 
    jz not_found
    bsf eax, eax
    ret    
  not_found:
    mov eax, -1
    ret This one works slowly (even slower than the first solution). Data is not aligned + using MMX is too much for such a small issue. But MMX has ready functions to compare registers and convert results into a bitmask. This was just the proof of concept. Math + bit twiddling hack optimization So the main challenge is to find the 0x00 byte in uint32. This is possible, and we can convert all the non-zero bytes in uint32 to 0xff and all the zero bytes into 0x7f. Inverting the result gives all zeros except in the position of the 0x00 byte. After transforming and inverting, it equals 0x80. Then, the only thing left is to count trailing zero bits and divide the result by 8 to get the byte index. There are several ways to count trailing zero bits (Please see https://graphics.stanford.edu/\~seander/bithacks.html#ZerosOnRightLinear). Sometimes, it's possible to find the necessary function among the compiler’s built-in functions or in the CPU instructions set (BSF for x86_64). The second attempt is the fastest implementation at this time: int zbyte_32(uint32_t x) {
  // for 0 byte set 0x7f, for other bytes - 0xff
  uint32_t y = (x & 0x7f7f7f7f) + 0x7f7f7f7f;
  // inverting gives 0x80 where 0 byte was and 0 for other bytes
  y = ~(y | x | 0x7f7f7f7f);
  
  //This check is necessary because 0 as an argument of __builtin_ctz is undefined behavior
  // without this check gcc/clang compilers change the weight function just to return 0;     
  // statement.
  if (y == 0) {
    return -1;
  }
  // find index of first non zero bit in int32_t
  int n = __builtin_ctz(y);
  // divide this index by 8 to get byte index (instead of bit index)
  return n >> 3;
}

int weight(char s) {
  uint32_t s_msk = (uint32_t)s * 0x01010101;
  uint32_t relief_val = *(const uint32_t *)relief_letters;
  uint32_t left_side_val = *(const uint32_t *)left_side_letters;
  uint32_t right_side_val = *(const uint32_t *)right_side_letters;  
  int w = zbyte_32(relief_val ^ s_msk);
  if (w != -1) 
    return 0;
  w = zbyte_32(right_side_val ^ s_msk);
  if (w != -1)
    return w + 1;
  w = zbyte_32(left_side_val ^ s_msk);
  if (w != -1)
    return -w - 1;
  __builtin_unreachable();
} I also tried to optimize the zbyte_32 function. if (y == 0) return -1; - this check seemed excessive. The BFS function scans the source operand for the first bit set. Sets ZF if a bit is found set and loads the destination with an index to the first set bit. Clears ZF if no bits are found set. So why should I check Y before calling this function? I can use BSF and then check the ZF flag and return -1 if it is set. So I tried this implementation: .intel_syntax noprefix
.text
.global zbyte_32_asm

# Function prototype:
# extern int zbyte_32_asm(uint32_t x);

zbyte_32_asm:
  # Input: rdi -> input uint32_t
  mov eax, edi
  and eax, 0x7f7f7f7f
  add eax, 0x7f7f7f7f

  or eax, edi
  or eax, 0x7f7f7f7f
  not eax

  bsf eax, eax
  jz not_found
  shr eax, 3
  ret

not_found:
  mov eax, -1
  ret It works 10 times slower than what compilers generate. See the profiling results. Profiling results To profile the function, I tried to get the weight of each symbol of the test string sbpwzdqm -|sbpwzdqm -|sbpwzdqm -|sbpwzdqm -| 10,000,000 times. Here are the results: slow() took 1.2938900000 seconds to execute
fast()  took 0.1967720000 seconds to execute
asm()   took 1.6532540000 seconds to execute In most cases, micro-optimizations are a waste of time, as it's much more useful (and sometimes easier) to reduce complexity, add a cache, change a memory allocator etc. However, in rare cases, micro-optimizations are the only means of achieving the necessary service performance. This is probably the most useless optimization I've ever made. I can imagine this solution could be used as part of a more complex search algorithm or, in rare cases, to search for a combination in a short string. Anyway, have fun reading this. Full source code can be found here: https://github.com/Lezh1k/Codewars_c/blob/master/src/trench_assault.c Full source code can be found here: https://github.com/Lezh1k/Codewars_c/blob/master/src/trench_assault.c https://github.com/Lezh1k/Codewars_c/blob/master/src/trench_assault.c Problem Problem In short, there are two groups of letters. Each letter has a 'weight.' Full problem statement here. Full problem statement here . here here The left side letters and their power: The left side letters and their power: w - 4 w - 4 p - 3 p - 3 b - 2 b - 2 s - 1 s - 1 The right side letters and their power: The right side letters and their power: m - 4 m - 4 q - 3 q - 3 d - 2 d - 2 z - 1 z - 1 So, we need a function to acquire each symbol's weight and "side" in the input string. The side can be defined as a sign of the weight (negative - left side, positive - right side). Solution Let's define the letters and sides: Let's define the letters and sides: static const char left_side_letters[] = {'s', 'b', 'p', 'w', 0};
static const char right_side_letters[] = {'z', 'd', 'q', 'm', 0};
static const char relief_letters[] = {' ', '-', '|', 0}; static const char left_side_letters[] = {'s', 'b', 'p', 'w', 0};
static const char right_side_letters[] = {'z', 'd', 'q', 'm', 0};
static const char relief_letters[] = {' ', '-', '|', 0}; These arrays will be cast to uint32. Do not do it on prod. Use union instead. These arrays will be cast to uint32. Do not do it on prod. Use union instead. Something like this: Something like this: typedef union short_str {
  uint32_t val;
  char arr[4];
} short_str_t; typedef union short_str {
  uint32_t val;
  char arr[4];
} short_str_t; The most obvious way is to use a simple switch, but it’s easy to lose something there. So, here is the initial simplest implementation of the 'weight' function: int weight_slow(char s) {
  for (const char *pl = relief_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return 0;
  }

  for (const char *pl = left_side_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return -((int)(pl - left_side_letters) + 1);
  }

  for (const char *pl = right_side_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return (int)(pl - right_side_letters) + 1;
  }
  // invalid input, raise error
  exit(1);
} int weight_slow(char s) {
  for (const char *pl = relief_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return 0;
  }

  for (const char *pl = left_side_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return -((int)(pl - left_side_letters) + 1);
  }

  for (const char *pl = right_side_letters; *pl; ++pl) {
    if (*pl != s)
      continue;
    return (int)(pl - right_side_letters) + 1;
  }
  // invalid input, raise error
  exit(1);
} But I didn't feel like this was the fastest way to find a character in a short string. These 4 bytes fit one 32-bit integer. Therefore, we can combine making a mask from the searched byte and XORing it with one of the letter sets. Optimizations The main idea is pretty simple. For example, left-side letters can be expressed as 0x7362 70 77. If we are looking for symbol 'p' (0x70), we can xor each byte with 0x70, and only the match will give zero as the XOR result. In our case, the result is 0x0312 00 07. The only thing left is to find the index of the 0x00 byte in an integer. This is possible. See the weight function below. 70 00 weight MMX Optimization The first attempt included an MMX because there are special CPU instructions on comparing bytes and getting the mask. .intel_syntax noprefix
.text
.global barr8_char_idx

# Function prototype:
# int barr8_char_idx(const char* array, char input_char);

barr8_char_idx:
    # array (address of 8-byte array) -> rdi
    # input_char -> esi 
    movdqu    xmm0, [rdi]
    # Broadcast the input_char across an SSE register
    movd    xmm1, esi
    pshufd  xmm1, xmm1, 0
    # Compare each byte of xmm0 with xmm1
    pcmpeqb xmm0, xmm1
    # Extract the result into a mask
    pmovmskb eax, xmm0
    # Check if the mask is non-zero
    test    eax, eax 
    jz not_found
    bsf eax, eax
    ret    
  not_found:
    mov eax, -1
    ret .intel_syntax noprefix
.text
.global barr8_char_idx

# Function prototype:
# int barr8_char_idx(const char* array, char input_char);

barr8_char_idx:
    # array (address of 8-byte array) -> rdi
    # input_char -> esi 
    movdqu    xmm0, [rdi]
    # Broadcast the input_char across an SSE register
    movd    xmm1, esi
    pshufd  xmm1, xmm1, 0
    # Compare each byte of xmm0 with xmm1
    pcmpeqb xmm0, xmm1
    # Extract the result into a mask
    pmovmskb eax, xmm0
    # Check if the mask is non-zero
    test    eax, eax 
    jz not_found
    bsf eax, eax
    ret    
  not_found:
    mov eax, -1
    ret This one works slowly (even slower than the first solution). Data is not aligned + using MMX is too much for such a small issue. But MMX has ready functions to compare registers and convert results into a bitmask. This was just the proof of concept. Math + bit twiddling hack optimization So the main challenge is to find the 0x00 byte in uint32. This is possible, and we can convert all the non-zero bytes in uint32 to 0xff and all the zero bytes into 0x7f. Inverting the result gives all zeros except in the position of the 0x00 byte. After transforming and inverting, it equals 0x80. Then, the only thing left is to count trailing zero bits and divide the result by 8 to get the byte index. There are several ways to count trailing zero bits (Please see https://graphics.stanford.edu/\~seander/bithacks.html#ZerosOnRightLinear ). Sometimes, it's possible to find the necessary function among the compiler’s built-in functions or in the CPU instructions set ( BSF for x86_64). https://graphics.stanford.edu/\~seander/bithacks.html#ZerosOnRightLinear https://graphics.stanford.edu/\~seander/bithacks.html#ZerosOnRightLinear BSF BSF The second attempt is the fastest implementation at this time: int zbyte_32(uint32_t x) {
  // for 0 byte set 0x7f, for other bytes - 0xff
  uint32_t y = (x & 0x7f7f7f7f) + 0x7f7f7f7f;
  // inverting gives 0x80 where 0 byte was and 0 for other bytes
  y = ~(y | x | 0x7f7f7f7f);
  
  //This check is necessary because 0 as an argument of __builtin_ctz is undefined behavior
  // without this check gcc/clang compilers change the weight function just to return 0;     
  // statement.
  if (y == 0) {
    return -1;
  }
  // find index of first non zero bit in int32_t
  int n = __builtin_ctz(y);
  // divide this index by 8 to get byte index (instead of bit index)
  return n >> 3;
}

int weight(char s) {
  uint32_t s_msk = (uint32_t)s * 0x01010101;
  uint32_t relief_val = *(const uint32_t *)relief_letters;
  uint32_t left_side_val = *(const uint32_t *)left_side_letters;
  uint32_t right_side_val = *(const uint32_t *)right_side_letters;  
  int w = zbyte_32(relief_val ^ s_msk);
  if (w != -1) 
    return 0;
  w = zbyte_32(right_side_val ^ s_msk);
  if (w != -1)
    return w + 1;
  w = zbyte_32(left_side_val ^ s_msk);
  if (w != -1)
    return -w - 1;
  __builtin_unreachable();
} int zbyte_32(uint32_t x) {
  // for 0 byte set 0x7f, for other bytes - 0xff
  uint32_t y = (x & 0x7f7f7f7f) + 0x7f7f7f7f;
  // inverting gives 0x80 where 0 byte was and 0 for other bytes
  y = ~(y | x | 0x7f7f7f7f);
  
  //This check is necessary because 0 as an argument of __builtin_ctz is undefined behavior
  // without this check gcc/clang compilers change the weight function just to return 0;     
  // statement.
  if (y == 0) {
    return -1;
  }
  // find index of first non zero bit in int32_t
  int n = __builtin_ctz(y);
  // divide this index by 8 to get byte index (instead of bit index)
  return n >> 3;
}

int weight(char s) {
  uint32_t s_msk = (uint32_t)s * 0x01010101;
  uint32_t relief_val = *(const uint32_t *)relief_letters;
  uint32_t left_side_val = *(const uint32_t *)left_side_letters;
  uint32_t right_side_val = *(const uint32_t *)right_side_letters;  
  int w = zbyte_32(relief_val ^ s_msk);
  if (w != -1) 
    return 0;
  w = zbyte_32(right_side_val ^ s_msk);
  if (w != -1)
    return w + 1;
  w = zbyte_32(left_side_val ^ s_msk);
  if (w != -1)
    return -w - 1;
  __builtin_unreachable();
} I also tried to optimize the zbyte_32 function. if (y == 0) return -1; - this check seemed excessive. The BFS function scans the source operand for the first bit set. Sets ZF if a bit is found set and loads the destination with an index to the first set bit. Clears ZF if no bits are found set. So why should I check Y before calling this function? I can use BSF and then check the ZF flag and return -1 if it is set. if (y == 0) return -1; So I tried this implementation: .intel_syntax noprefix
.text
.global zbyte_32_asm

# Function prototype:
# extern int zbyte_32_asm(uint32_t x);

zbyte_32_asm:
  # Input: rdi -> input uint32_t
  mov eax, edi
  and eax, 0x7f7f7f7f
  add eax, 0x7f7f7f7f

  or eax, edi
  or eax, 0x7f7f7f7f
  not eax

  bsf eax, eax
  jz not_found
  shr eax, 3
  ret

not_found:
  mov eax, -1
  ret .intel_syntax noprefix
.text
.global zbyte_32_asm

# Function prototype:
# extern int zbyte_32_asm(uint32_t x);

zbyte_32_asm:
  # Input: rdi -> input uint32_t
  mov eax, edi
  and eax, 0x7f7f7f7f
  add eax, 0x7f7f7f7f

  or eax, edi
  or eax, 0x7f7f7f7f
  not eax

  bsf eax, eax
  jz not_found
  shr eax, 3
  ret

not_found:
  mov eax, -1
  ret It works 10 times slower than what compilers generate. See the profiling results. Profiling results To profile the function, I tried to get the weight of each symbol of the test string sbpwzdqm -|sbpwzdqm -|sbpwzdqm -|sbpwzdqm -| 10,000,000 times. Here are the results: sbpwzdqm -|sbpwzdqm -|sbpwzdqm -|sbpwzdqm -| slow() took 1.2938900000 seconds to execute
fast()  took 0.1967720000 seconds to execute
asm()   took 1.6532540000 seconds to execute slow() took 1.2938900000 seconds to execute
fast()  took 0.1967720000 seconds to execute
asm()   took 1.6532540000 seconds to execute In most cases, micro-optimizations are a waste of time, as it's much more useful (and sometimes easier) to reduce complexity, add a cache, change a memory allocator etc. However, in rare cases, micro-optimizations are the only means of achieving the necessary service performance.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

How to Quickly Index a Character in Short String

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Ditch the AI for a Second: Image Recognition Without Neural Networks

Demystifying Registers

The Pitfalls of Software Abstractions

5 Practical Ways AI Can Boost Productivity for Web Developers

30-Day .NET Challenge - Day 26: Loop Unrolling

Ditch the AI for a Second: Image Recognition Without Neural Networks

Demystifying Registers

The Pitfalls of Software Abstractions

5 Practical Ways AI Can Boost Productivity for Web Developers

30-Day .NET Challenge - Day 26: Loop Unrolling

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps