glibc strlen コードリーディング

この間のget_next_lineの記事で標準Cライブラリのstrlen()が自分が書いたものより圧倒的に速いという話をしました.

jun-networks.hatenablog.com

なぜ標準ライブラリのstrlen()が速いか調べてみたら結構奥が深かったので今回はGNU Cライブラリ(glibc)の strlen() について書きたいと思います.

愚直な実装とglibcの実装の速度の比較

愚直な実装

まずstrlen()を実装する時にとりあえず思いつく実装は以下のようなものでしょう.

size_t my_strlen(char *str)
{
  size_t len = 0;
  while (str[len])
    len++;
  return (len);
}

glibcの実装

で, glibcの実装は以下のような感じ.

/* Copyright (C) 1991-2018 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Torbjorn Granlund (tege@sics.se),
   with help from Dan Sahlin (dan@sics.se);
   commentary by Jim Blandy (jimb@ai.mit.edu).
   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.
   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.
   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, see
   <http://www.gnu.org/licenses/>.  */

#include <string.h>
#include <stdlib.h>

#undef strlen

#ifndef STRLEN
# define STRLEN strlen
#endif

/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time.  */
size_t
STRLEN (const char *str)
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
     the "holes."  Note that there is a hole just to the left of
     each byte, with an extra at the end:
     bits:  01111110 11111110 11111110 11111111
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
     The 1-bits make sure that carries propagate to the next 0-bit.
     The 0-bits provide holes for carries to fall into.  */
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();

  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      longword = *longword_ptr++;

      if (((longword - lomagic) & ~longword & himagic) != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
        a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

github.com

速度の比較

今回は100万文字をstrlen()に渡すというのを10回行い平均を取り, どの程度実行時間に差があるか見てみる.

プログラムは以下のようなものを使う

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <time.h>
#include <stdint.h>
#include <stdlib.h>
#include <unistd.h>

size_t    nori_strlen(const char *str);
size_t    glibc_strlen(const char *str);
size_t    my_strlen(const char *str);

int main(int argc, char *argv[])
{
    char *file_name = "bigfile.txt";

    int fd = open(file_name, O_RDONLY);
    char*str = malloc(1000000);
    size_t read_bytes;
    if ((read_bytes = read(fd, str, 1000000)) < 0) return 1;
    close(fd);
    str[1000000-1] = '\0';
    printf("read_bytes: %lu\n", read_bytes);
    int loop_max = 10;
    double sum;
    clock_t start,end;
    for (int i = 0; i < loop_max; i++){
            start = clock();
                strlen();  // ここを置き換える
        end = clock();
        printf("%.6f秒かかりました\n",(double)(end-start)/CLOCKS_PER_SEC);
        sum += (double)(end-start)/CLOCKS_PER_SEC;
    }
    double avg = sum / loop_max;
    printf("平均%.6f秒かかりました\n", avg);
}

まずは my_strlen() から

$ gcc main.c && ./a.out
read_bytes: 1000000
0.003180秒かかりました
0.003249秒かかりました
0.003306秒かかりました
0.003202秒かかりました
0.002920秒かかりました
0.003203秒かかりました
0.003230秒かかりました
0.003312秒かかりました
0.003164秒かかりました
0.002752秒かかりました
平均0.003152秒かかりました

100万文字読むのにかかった時間は平均 0.003152秒でした.

次は glibcのstrlen()をみてみます.

$ gcc main.c && ./a.out
read_bytes: 1000000
0.000359秒かかりました
0.000330秒かかりました
0.000302秒かかりました
0.000293秒かかりました
0.000289秒かかりました
0.000298秒かかりました
0.000313秒かかりました
0.000317秒かかりました
0.000318秒かかりました
0.000320秒かかりました
平均0.000314秒かかりました

100万文字読むのにかかった時間は平均 0.000314秒でした.

愚直な実装に比べて10倍くらい速いですね!

glibc strlen() の解説

glibc の strlen() は初見では意味不明なので解説していきたいと思います.

まず glibc の strlen() は大まかにいくつかのパートに分けることができます.

1. ヌル文字があるか調べながらロングワードの境界まで移動する
2. ロングワード単位でヌル文字が含まれているか調べる
3. ヌル文字が見つかった場合はヌル文字の具体的な場所を調べて, そこから文字列の長さを算出し, 返す.

ヌル文字があるか調べながらロングワードの境界まで移動する

  for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr)
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

ここではヌル文字があるか調べながらロングワード境界にポインタを移動させ, もし途中でヌル文字を見つけたら その時点のポインタ - 文字列の初めのポインタ で文字列の長さを算出してreturnしています.

ここの部分のコードは比較的素直ですが, ロングワード境界とはなんぞやって感じなので解説すると, ロングワード境界はアライメントのようなものという認識で良いと思います.

アライメントというのを説明すると, まずメモリというのは基本的に1バイト(8bit)ごとにアドレスが振られていて, 1バイトがメモリアクセスの最少単位なのですが, 1バイト単位でのアクセス以外にも, 32bitCPUの場合は4バイト(32bit), 64bitCPUの場合は8バイト(64bit) のデータを一度にレジスタとメモリ間で読み書き出来ます. このように1命令でアクセス出来るデータの大きさのことをワードサイズと呼び, そして多くの場合レジスタのサイズと等しくなります. また, ワードサイズは sizeof(long)で取得することが出来ます. そしてそのような複数バイトのレジスタメモリ間の読み書きのパフォーマンスを上げるためには4バイトの場合はメモリアドレスを4の倍数に, 8バイトの時はメモリアドレスを8バイトに合わせる必要があります. そこで, ここでは sizeof(long) の倍数になるようにメモリアドレスを進めつつ, もし途中でヌル文字があったらそこで文字数を返すようにしています.

データ型とアライメントの設定

Word (computer architecture) - Wikipedia

ロングワード単位でヌル文字が含まれているか調べる

  longword_ptr = (unsigned long int *) char_ptr;
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();


  int i = 0;
  for (;;)
  {
    longword = *longword_ptr++;

    if (((longword - lomagic) & ~longword & himagic) != 0)
    {

longword_ptr = (unsigned long int *) char_ptr; で char*型をlong int*型にキャストし, ロングワード単位(4バイトもしくは8バイト)でデータを取得出来るようにします.

また, この後使う定数なども用意します. if (sizeof (longword) > 4) のif文内で64bit用に定数を拡張しています. if (sizeof (longword) > 8) は64bitを超えるのCPUアーキテクチャはこの関数はサポートしていないことを表し, もし64bitを超える場合はプログラムが終了するようになっています.

longword = *longword_ptr++; 4バイトもしくは8バイトを取得し, if (((longword - lomagic) & ~longword & himagic) != 0) の条件式で取得した4or8バイト内にヌル文字が含まれているか判定しています.

ロングワード単位でヌル文字を検出するロジック

(((longword - lomagic) & ~longword & himagic) != 0) の条件式が真の場合はヌル文字が文字列内に含まれていることを示します. ではこれがどのように動いているか説明していきたいと思います.

himagic と lomagic ですが, これは全てのバイトに対して同じ操作をしているのでそれぞれ1バイト分取り出して試してみるとわかりやすいと思います.

// 1バイト分
himagic = 0x80;  // == 0b10000000
lomagic = 0x01;  // == 0b00000001

まずは (longword - lomagic) の部分に注目してみましょう.

// (longword - lomagic)

// NULL文字じゃないとき (0x80以下)
(0b01100001 - 0b00000001) == 0b01100000;

// NULL文字の時
(0b00000000 - 0b00000001) == 0b11111111;

// NULL文字じゃない時 (0x81以上)
(0b10000001 - 0b00000001) == 0b10000000;

ここではヌル文字, もしくは 0x80 より大きい場合のみ, 最上位ビットが1になります.

次に (~longword & himagic) の部分を見てみます.

// (~longword & himagic)

// NULL文字じゃないとき (0x80以下)
(~0b01100001 & 0b10000000) == (0b10011110 & 0b10000000) == 0b10000000;

// NULL文字の時
(~0b00000000 & 0b10000000) == (0b11111111  & 0b10000000) == 0b10000000;

// NULL文字じゃない時 (0x81以上)
(~0b10000001 & 0b10000000) == (0b01111110 & 0b10000000) == 0b00000000;

ここではヌル文字, もしくは0x80以下の場合のみ最上位ビットが1になります.

そして, (longword - lomagic) & (~longword & himagic) をすると

// ((longword - lomagic) & (~longword & himagic))

// NULL文字じゃないとき (0x80以下)
(0b01100000 & 0b10000000) == 0b00000000;

// NULL文字の時
(0b11111111 - 0b10000000) == 0b10000000;

// NULL文字じゃない時 (0x81以上)
(0b10000000 - 0b00000000) == 0b00000000;

これでヌル文字の場合のみ != 0 になりました!

ではこれを64bitに拡張して見てみましょう.

               str       : jun_networks
               str_len   : 12
               src       : 0x55f436a8f02b
               aligned   : 0x55f436a8f030
               alignment :       +5

                               7           6           5           4           3           2           1           0
               src       : 0111 0111 | 0111 0100 | 0110 0101 | 0110 1110 | 0101 1111 | 0110 1110 | 0111 0101 | 0110 1010
               longword  : 0000 0000 | 0111 0011 | 0110 1011 | 0111 0010 | 0110 1111 | 0111 0111 | 0111 0100 | 0110 0101
               lomagic   : 0000 0001 | 0000 0001 | 0000 0001 | 0000 0001 | 0000 0001 | 0000 0001 | 0000 0001 | 0000 0001
    longword - lomagic   : 1111 1111 | 0111 0010 | 0110 1010 | 0111 0001 | 0110 1110 | 0111 0110 | 0111 0011 | 0110 0100
              ~longword  : 1111 1111 | 1000 1100 | 1001 0100 | 1000 1101 | 1001 0000 | 1000 1000 | 1000 1011 | 1001 1010
               himagic   : 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000
    ~longword & himagic  : 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000
(lw - lmgc) & ~lw & hmgc : 1000 0000 | 0000 0000 | 0000 0000 | 0000 0000 | 0000 0000 | 0000 0000 | 0000 0000 | 0000 0000

このようにアライメントがしっかり行われ, 8バイト単位でヌル文字が含まれているか調べられていることがわかります.

graphics.stanford.edu

ヌル文字が見つかった場合はヌル文字の具体的な場所を調べて, そこから文字列の長さを算出し, 返す.

   if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }

この部分は何も難しいことはなくて, ただ単にヌル文字がロングワードの中に見つかったらその8バイトを1バイトずつヌル文字がどうか比較して, ヌル文字だったらそこまでの文字数を返しているだけです.

完走した感想

完走した感想(激うまギャグ)ですが... 標準ライブラリは偉大だなぁ〜という感じです.

自分は多分こんな実装思いつかないと思うので, 本当に凄いです. ロングワード単位でのメモリアクセスだったり, ループ展開(?)などのテクニックを駆使しているのを見ると実装した人はコンピューターの気持ちを知り尽くしてるなぁと思いました.

最後のヌル文字が具体的にどのバイトに入っているかを検出する部分ですが, どうやらループ展開を使っているっぽいのですが, コンパイルされたアセンブリを見ても正直forループを使ったものとの違いがわからず, 実際実行してみても殆ど差がなく, なぜループを使わずに書いているかはわからなかったので, 今回の記事の中ではそこには触れませんでした.

今回の記事を書くにあたり, 42の学生に色々協力してもらったので助かりました. やはり友達とこういうプログラミング関係の話題で盛り上がれるのは良いですね.

記事を書こうとすると曖昧な理解だったり, 言葉の正確な意味を調べながら書くことになるので理解がより深く明確になるのでやはりアウトプットは素晴らしいですね.

記事内にちょくちょくネットミームが出てきてオタク臭い感じがしますが, まぁそれもこのブログの味ということで.

それでは今日はこのへんで. ではでは〜👋👋

参考にしたサイト

• glibc/strlen.c at master · lattera/glibc · GitHub
• c - Understanding code in strlen implementation - Stack Overflow
• Bit Twiddling Hacks
• 時間の計測 - C言語 - 碧色工房
• アライメントとか、ワード境界とか
• memory - What is the word size of a RAM in 32/64 bit machine (processor) - Super User
• 64ビットプログラミングのポイント (3/3) - ITmedia エンタープライズ
• strlen.cは4バイトもしくは8バイト単位で文字列の長さを数える - yarbの日記
• ビット，バイト，ワードの概念
• Word (computer architecture) - Wikipedia
• 一週間で身につくコンピュータリテラシ|ハードウェア編第2日目：CPUの仕組み
• Data structure alignment - Wikipedia
• コンパイルされたマシン語とCPUの挙動（実行サイクル数）まで意識した高速化プログラミング | 勤怠管理のバイバイ タイムカード
• https://www.agner.org/optimize/instruction_tables.pdf
• https://www.intel.co.jp/content/dam/www/public/ijkk/jp/ja/documents/developer/ia32.pdf
• ループ展開 - Wikipedia
• データ型のアラインメントとは何か，なぜ必要なのか？
• SSE4.2の文字列処理命令の紹介
• SIMD - Wikipedia
• X86アセンブラ/x86アーキテクチャ - Wikibooks
• Arm64(ARMv8) Assembly Programming (04) ロード命令
• 「Hello World！」の中身を探る意義と環境構築、main（C言語）のアセンブラコードの読み方 (4/4)：main()関数の前には何があるのか（1） - ＠IT
• Tips IA32（x86）命令一覧 Mから始まる命令 MOVSX命令
• [ ] 演算子
• https://www.cc.u-tokyo.ac.jp/public/VOL10/No4/200807tuning.pdf
• よくあるご質問 －レジスタとキャッシュメモリ | ITパスポートのスペシャリストによるこっそり裏講義
• Assembly Programming on ARM Linux(04)
• x64のレジスタ拡張 (1/2) - ITmedia エンタープライズ
• 汎用レジスタ