JUNのブログ

JUNのブログ

活動記録や技術メモ

Toggl で時間配分を可視化することにした.

自分は多くの時間をネットサーフィンとTwitterYouTubeに費やしており, 生産性の低い毎日を送ってます.

現在ずっと実家におり, 可処分時間という点では高専在学時より増えているはずですが, どうも高専在学時ほど生産的な毎日を送っている実感を得られていません.

なので, 自分がどれくらい時間を使っているのか可視化するために Toggl Track というものを始めようと思います. (丁度この記事を書いているのは2月1日ということで月始めですし丁度良いですね)

toggl.com

使い方は以下の記事を参考に, ゆるく長く続けるためにTagは設定せず, 大雑把にプロジェクトを分けるような感じで使いたいと思います.

www.wantedly.com

また, 実は昔一度このツールを使ったことが合ったんですが, 1日で辞めてしまいました. その時の理由として

  • タスク入力がめんどい
  • タスクの粒度が荒くて結局何しているかよくわからない

みたいな感じだったので, 今回は

  • Chrome拡張, デスクトップアプリ, モバイルアプリ全て導入し, 心理的障壁を下げて気軽に入力できるようにする.
  • プロジェクトは大雑把に区切り, タスクは日本語で気軽に頭に思い浮かんだ言葉で書く. (考えるのは疲れるので)

という感じで, ゆるく長く続けて行きたいですね.

f:id:JUN_NETWORKS:20210201030230p:plain
プロジェクトの分け方はこのくらいの雑さの方が続くかな

f:id:JUN_NETWORKS:20210201030059p:plain
Chrome拡張便利です.

これが続いたら, 1ヶ月の振り返りとか書きたいですね.

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

4Kモニタを買ったが使いこなせていない話

「素晴らしーーー!!!!」とか言っていますが, 確かにP2721Qは文句なしに素晴らしいです. 画質は綺麗だしベゼルは細いし, メニューは使いやすいし.

でも, 自分のPCのスペックが足りなくて快適4K生活が送れていないんだなぁ〜〜

P2721Q について

とりあえずモニタ本体について少し書きます.

www.dell.com

セールで4.5万円くらいで買いました.

以下の点で優れていると思います.

  • 画面が綺麗(4Kなので)
  • ベゼルが薄い
  • メニュー操作がとてもしやすい
  • 電源内蔵だからコードがスッキリ
  • 付属スタンドが優秀
  • USBハブ代わりになる.
  • 27インチ4Kにしては安い

ちょっと残念のポイントとしては

  • スピーカーが付いてない(まぁ付いてても使わんけど)
  • 下のベゼルが他の3辺に比べて太い (気にならんけど)

と言った感じでほぼ完璧です.

実際弟の MacBook Air (2020) とつないだ画面を見たときにはめっちゃ感動しました.

じゃあ何が駄目かというと自分のPC側なんすね〜〜

自分のPCで使いこなせない問題

自分のPCは Ubuntu on Thinkdpad X1 Carbon 2017 みたいな環境です. もちろんプロセッサ内蔵GPUです.

で, UbuntuMacのようにいい感じに倍率とか画面輝度とかフォントサイズとか調整してくれないのでその結果このようになります.

小っっっっっっっっっっっっっっっっっさ

というわけで本当にただ全ての要素が1/4のサイズになっただけなのでマジで見えないです.

で, 一応これには解決策があって, 画面拡大倍率を125%にして, Chromeの拡大率も125%にしたら一応ギリまともに見れるくらいにはなります.

f:id:JUN_NETWORKS:20210117015145p:plain

ただ, これをすると画面倍率を125%にしたせいか, PCの動作がめっちゃ重くなって, Twitterもまともにできないくらい重くなるので100%で我慢しているわけなのです.

これから

この先の予定としては

  • MacBookAir (2020) を買う
  • デスクトップPCを組む

の2択かなぁ... (もしくは両方)

M1チップのMBA, スペック的にはとても魅力的なんだけど, Virtualbox や Docker などの仮想環境が今の所使えないというのが痛すぎる... 仕事にならんし42Tokyoもできん... だからと言ってIntelMBAなどを買う気にはなれないんですわ...

デスクトップPCは前から一度組んで見たいとは思っていたので組むのありだけど, 時間と金がかかるのと, Macの方が結局開発環境として優れているんだよな. まぁUbuntuとのデュアルブートにすれば良いという話かもしれんが. (WSLで開発できそうならWindowsだけでもいいかもしれん)

まぁどちらにせよまた何か進展があったらブログに記事とか書くと思います.

ではでは.

2020年振り返り

激動の2020年も今日で終わり!! なので毎年恒例1年の振り返りをするんじゃ!

去年はこちら

jun-networks.hatenablog.com

今年もツイートを漁りつつ, 思い出して書いてきます.

では早速やっていくぞー!

月ごとの振り返り

1月

  • 自分がバイトしている会社でインタビュー記事が公開されました.

www.wantedly.com

  • 計算理論の本を読んでオートマトンとか字句解析とかその辺について少し勉強していました. (結局この本は1/3くらいまで読んで放置してしまったので, またいつか読み直したい...)

  • 春高専カンファレンス初風 に行ったしましたね.

2月

jun-networks.hatenablog.com

読んだけど結局生活に活かせているか言われればあまり生かせれていないですね...

それよりも, 書評はブログには書いていないけれども, アウトプット大全という本がかなり良くて, 自分の今のアウトプットの考え方やアウトプットの仕方に影響を与えてくれたので良かったです.

jun-networks.hatenablog.com

3月

  • 42Tokyoの入学試験が新型コロナウィルスのせいで延期になりました.

  • N予備校プログラミング入門コース修了しました.

jun-networks.hatenablog.com

  • 少しだけAtCoderしてました

  • 30日OSにも手を出したものの1週間ほどで離脱してしまった...

4月

  • 新型コロナウィルスのせいで高専の授業がオンラインになりました.

  • リングフィットを買いました.

  • iPad Pro を買った
  • AirPods Pro を買った.
  • MacBookAirを買った.

5月

  • MacBookAirを売った

理由としてはとにかく動作が重くてまともに作業出来なかったからです.

  • MacからUbuntuに戻るにあたりOSをUbuntu20.04にして新たな環境にした.

6月

楽天カード, ポイント付くのは良いが, 正直デビットカードの方が即時に請求が来るので家計簿が付けやすいんだよな...

  • Teraformを業務で触ったりしていました.

  • AWSの設計などについても勉強して, この月で少しAWSに詳しくなった気がする.

7月

  • 家電制御プログラムの作成 (現在放置してて未完成)

github.com

  • "100分de名著"シリーズの「カント純粋理性批判」を読んだ. よくわからなかった.

8月

  • 42Tokyoの入学試験を受けた.

  • 名古屋歩いてたらチャリに轢かれてスマホ壊れた.

9月

めっちゃ楽しかったし, めっちゃいい会社でした. 制度や仕組みなども整っていてリモートでも働きやすくて素晴らしかったです.

使った技術としてはRailsとReactでした.

  • 42Tokyoに合格した.

jun-networks.hatenablog.com

  • 3分間ネットワークを一通り読んで, ネットワークの知識を付けた.

www5e.biglobe.ne.jp

このサイト, FlashPlayer使われまくってるので, 来年以降どうやって見よう...

10月

  • 久しぶりに電子工作して楽しかった.

  • リングフィット1週目クリアした.

  • Oculus Quest買った. VRC楽しい.

  • Nand2Tetris の課題の1つでアセンブリをバイナリに変換するプログラムをGoで書いた.

github.com

11月

  • GoでAPIサーバー書いてた.

  • どの4kモニターを買うか迷いまくって10時間くらい無駄にした

  • VSCode使いからVimmerになった. (nvim)

  • ハッカソン出ようと思ったけど作品が期限までに完成せず諦め.

  • 業務でReactを触ることになったのでReact勉強した.

jun-networks.hatenablog.com

12月

  • 42関連で2つ記事を書いた.

jun-networks.hatenablog.com

jun-networks.hatenablog.com

  • 42のおかげで低レイヤーに詳しくなった.

    • CPUの実行効率
    • メモリアクセス効率
    • 標準Cライブラリの実装
  • 生活リズムが崩壊してて多くの時間を虚無に費やしてしまった.

  • スタンディングデスクを買った.

  • クリーンアーキテクチャの考え方を少し知った. (コードに落とし込めるとは言っていない)

全体の振り返り

今年は短期的な視点から見れば最低, 長期的な視点から見れば上々といった感じですね.

短期的な視点では, 完遂出来たことがとても少なく, 自己嫌悪に苦しめられました.

長期的には, 42Tokyoに合格出来たということで, これから楽しくなってきそうです.

去年の目標の達成具合

ちなみに去年の1年振り返り記事の中で

2020年は人生の大きな転換期になる気がしています.

とりあえず今ある2020年の目標は

  • CPU, コンパイラ, OSを作る (つまりはシステムプログラミング!)
  • 自分のポートフォリオサイトを作成する.
  • 毎日充実した日々を送り, 好きなことをいっぱい勉強する.
  • いろんな分野をやってみて自分の進みたい道を探す
  • 定期的に運動する.
  • 42Tokyoに受かる!!

今年は低レイヤーなどを中心とした含めたCS系の基礎固めの年になりそうです.

プログラミングを初めて3年くらいが経とうとしていて, 最近になってやっとこCSといものを知りしっかりと勉強したいと思うようになりました. 今年は"勉強したい"ではなく"勉強する"年に出来たらいいなと思います. そして来年のこの時期に1年の振り返りをした時に今年よりも充実し満足し幸せな1年を送れたらいいなと思います.

って書いてありますが, 最終的には以下のようになりました.

  • CPU, コンパイラ, OSを作る (つまりはシステムプログラミング!) → Nand2Tetris, 30日OS, 両方とも途中で放置. CPU作りは結局何もやっていない.
  • 自分のポートフォリオサイトを作成する. → 何もしてない.
  • 毎日充実した日々を送り, 好きなことをいっぱい勉強する. → 自堕落に過ごして非生産的な時間が多かった.
  • いろんな分野をやってみて自分の進みたい道を探す→ MLから離れて, クラウドインフラ, サーバー, 低レイヤー, フロントエンド と多くの分野を触った. しかし, 結局自分の進みたい道はわからなかった.
  • 定期的に運動する. → リングフィットのおかげで達成.
  • 42Tokyoに受かる!! → 受かった.

と, 基本的に何かしらに手を出したはいいものの途中で放棄してしまうことが多い一年でした.

何かしようと思いハッカソンに出ようとしたものの結局期限までに完成せず出られませんでしたし, 本当に中途半端で完遂しない1年でした.

ただ, 良いことも少しはあって, 念願の42Tokyoに合格したのは今年のマイナスを全て帳消しにするくらい良かったです.

今年の反省点としては

  • 家にいる時間が長く, だらだらする時間が多くなってしまい, やりたいことに時間を割けなかった.
  • 興味の対象がコロコロ変わるせいで何かを完遂せずに別のことをしてしまい, その結果完遂できなかったという結果のみが残り辛くなった.
  • Twitter, YouTube, ネットサーフィンに時間を費やしすぎた.
  • 生活にメリハリがなく惰性で生きてしまった.

と言った感じです. 完遂継続が出来なかった年でした.

よかった事

今年の振り返り記事はあまりにも暗すぎるのでここで頑張って明るい話題も探したいと思います.

42Tokyoに合格した

今年良かったことといえばとりあえずこれです.

ずっと独学でカリキュラムとかも特になく書籍とWebサイトを頼りにほぼ1人で勉強していたプログラミングですが, ついにカリキュラムとコミュニティを見つけました.

最近書いた標準Cライブラリのstrlen()の実装についての記事も42Tokyoの学生と一緒に色々試しながら書きました.

jun-networks.hatenablog.com

やっと自分のプログラミングの話を理解してくれて, 一緒に手を動かしてくれる人が出来てとても嬉しいです. (42Tokyo入る前にも2,3人くらいいたけども)

プログラミングの話ができて, ちゃんと理解してくれる(理解しようと努めてくれる)人が多くいるのは素晴らしいですね.

React触った.

今年の後半はもっぱら Typescript + React を触ってました.

Reactは数年前のインターンシップで触った時に難しすぎて挫折したフレームワークですが, 今年触ってみたら書きやすくなっていてびっくりしました. おそらくクラスベースから関数コンポーネントベースにReactの主軸が移ったからというのもありますし, 単純に自分が色々と経験を詰んだので理解できるようになったというのもあると思います.

Reactは最初何も考えずVueと同じような感じで1コンポーネントに色々詰めていたのですが, "りあクト!"という本を読んでそのやり方が間違いだと気づけて, 今年の終わりくらいにはちゃんとコンポーネント設計などを意識したテスタビリティが高いコードが書けるようになったかなぁと思います. "りあクト!" おすすめです.

jun-networks.hatenablog.com

低レイヤーを触った.

去年立てた目標にまでは達しませんでしたが, 去年の自分に比べてかなり低レイヤーに詳しくなったと思います.

42Tokyoのカリキュラムではしばらくは低レイヤーが続きそうなので, それらの課題を楽しみつつ, 趣味でCPUやOS作成など出来たらいいなぁと思います.

触った技術など

Python

コンテナで動かすサーバープログラムをFlaskで書いた

AWS

初めてAWSを使ったクラウドインフラの設計というのをしました.

VPC, ECS, CloudWatch, SageMaker, EC2, ECS, SQS, Lambda など沢山のサービスを調べて, 使いました.

Terraform

Infrastructure as a Code を実現するためTerraformを書いてました.

TypeScript

React書く用

React.js

今年初めて本格的に勉強して書き始めましたが, かなり書けるようになったと思います.

しかし, Atomic Design の分け方の粒度とかその辺はまだしっかりと理解出来ていないです.

Next.js

今年はReactを書いたという話をしましたが, React単体で使うことはほとんど無く, 実際にはNext.jsを使うことが多かったです.

Next.js, 色々と便利なんですよね...

C++

今年の初めAtCoder用に書いてた.

C

今年の下半期, TypeScriptと並ぶくらい書いた言語です.

42の課題は低レイヤーが多く, 序盤の多くの課題はC言語で書くことになります.

Makefileなども初めて書きましたが, めっちゃ便利ですね.

多分2021年もかなりの時間C言語を書くことになりそうです.

Go

今年勉強しはじめて, APIサーバーなどを書いていました.

Goは書き方が今まで触ってきた言語と結構違うのでどうやって書いたらいいかわからないんですよね...

2021年の目標

目標は高くすると年末に振り返った時に悲しくなるので2021年は今年の反省も踏まえ以下のように設定したいと思います.

  • 生産性の高い日々を送れるように努力する. 具体的には1ヶ月単位で目標を立てて, それを達成するような方針で生きる. (もしかしたら変わるかも)
  • Twitter, YouTube などを触らないようにし, メリハリのある生活をする.
  • 30日OS本, Nand2Tetris, アルゴリズムイントロダクションを完遂する.
  • 42Tokyoの退学システム(通称ブラックホール)に飲まれないようにする.

2021年は振り返った時に, 完遂したものが今年より多くなれるように頑張りたいと思います.

2020年買ってよかったもの

#買って良かった2020

今年から1年の中で買ってよかったものを紹介したいと思います.

ランキング形式みたいなのは苦手なので, 特に順位などは決めず列挙して一言添えるだけですがw

ではではスタートです.

iPad Pro (10.5インチ)

これはマジで買って良かった. QoL爆上がりです.

とにかく電子書籍が快適過ぎます.

iPad Pro で電子書籍読むの快適過ぎてやばいです. 電子書籍否定派から賛成派になりました.

ただiPad Proで電子書籍を読む際の欠点があるとすれば, 他のアプリに気を取られて本を読み始めるのが難しくなることですかね. なのでiPad Proで電子書籍を読む際にはiPad Proのロックを解除する前に「俺は本を読むぞ!」という強い決意を抱いてロックを解除しなくてはいけません.

あと, 積読が見えにくいのでいつの間にか読んでない本が溜まりがちですね

NINTENDO SWITCH & リングフィットアドベンチャー

任天堂は神.

今年は新型コロナウィルスの影響で殆ど家から出ておらず, ずっと椅子に座ってパソコンばかりしているのに太らず, むしろ筋肉量が増えて痩せたのはリングフィットのおかげです.

ありがとうリングフィット. ありがとう任天堂.

モンダミン

自分は1ヶ月のうち2週間は口の中に口内炎があるという, えげつないくらい口内炎ができやすい体質なのですが, 去年の終わりくらいからモンダミンを毎日歯磨きの後にするようになってから口内炎できる頻度が3ヶ月に1週間ほどとめちゃくちゃ改善されました.

口内炎軟膏やサプリメントなど数年間に渡り色々試してきましたが行き着いた答えはこれです.

ちなみに自分が使ってるのはモンダミンプレミアムというやつで, 1本800円くらいするんですが, 月額800円で口内炎の苦しみから解放されるなら安いもんです. (ドラッグストアだともっと安いかも?)

完走した感想

1年振り返り記事の執筆を完走した感想ですが, 暗い.

毎年振り返り記事を書くのですが, 例年なら「今年何もやってないと思ったけど, 意外と色々やってんなぁ.」って感じですが, 今年は「ほんまに何もやってへんやん...1年なにしてててん...」という逆のパターンになってしまいました.

いや, 暗いわ. 最後の感想まで暗いわ. もう少し明るくしようや.

来年は明るくて眩しいくらいの振り返り記事が書けるように努力したいですね.

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

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秒でした.

次は glibcstrlen()をみてみます.

$ 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() の解説

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

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

  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) の条件式が真の場合はヌル文字が文字列内に含まれていることを示します. ではこれがどのように動いているか説明していきたいと思います.

himagiclomagic ですが, これは全てのバイトに対して同じ操作をしているのでそれぞれ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の学生に色々協力してもらったので助かりました. やはり友達とこういうプログラミング関係の話題で盛り上がれるのは良いですね.

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

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

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

参考にしたサイト

C言語でファイル(ファイルディスクリプタ)から1行ずつ取得する関数を作った

10月から42Tokyoで学んでいるのですが, そこでやった課題の内容及びコードの公開がOKってことなんで, これから気が向いたら42の課題と自分の解答を記事にしていこうと思います. (ただし, 課題PDF自体は再配布や外部への公開が禁止されているので, 課題内容はあくまで自分が要約したものであることをご了承頂きたい)

今回の課題に対する自分の解答のソースコードは以下のリポジトリにうpしてある.

github.com

まえがき (for 42 students)

42の学生で get_next_line の課題が終了していない方は今すぐブラウザバックすることを強くおすすめします.

本記事には実装レベルでの説明が多く含まれており, 盛大なネタバレを食らうことになります.

課題内容

渡されたファイルディスクリプタ(以降 fd と呼ぶ)からデータを読み込み, 関数を呼び出す度に1行ずつ(改行文字は除く)渡されたバッファー変数に格納し, 処理結果(正常=1, 異常=-1 or 終了=0)を返す関数を作成する.

読み込む際には事前に #define された BUFFER_SIZE という定数分を一度に読み込む必要がある. read(fd, &buf, BUFFER_SIZE);

プロトタイプ宣言は以下のようにすること.

int get_next_line(int fd, char **line);

課題の意図としては以下の2つがメインみたいです.

  • 行ごとに読み込むという汎用性の高い関数を実装する
  • C言語のstatic変数について理解する

制約

今回使用可能な標準Cライブラリで定義されている関数は以下の通りです.

また, 42にはNorminetteというLinterプログラムがあり, Linterプログラムがエラーを吐いた場合, 課題は問答無用で0点となる.

Norminetteが課す制約はいくつもあり, すべて列挙するのは大変なのだが, 大きな制約としては以下の通りである.

  • 各行は最大80文字
  • 各関数には最大25行まで
  • 各関数内で定義出来る変数は5つまで
  • 各関数内で受け取れる名前付きパラメータ4つまで
  • 1行につき1命令 (例えばint a= 0は宣言と代入を同時に行っているので不可)
  • 列挙型には e_プレフィックスを付けるなどのいくつかの命名規則
  • 以下の命令の使用禁止
    • for
    • do..while
    • switch
    • case
    • goto

これ以外にも複数の制約があり, もし自分のコード内で 「なんでこんな面倒くさい書き方してるんだ?」って思うことがあったら恐らくそれはNorminetteのエラーを消すためにそのように書いてる場合が多い. (そうじゃないときもあるので遠慮なくコメントください)

また, 本来はNorminette違反ですが, ブログのためにコメントを複数追加しています.

提出ファイル

  • get_next_line.c
  • get_next_line_utils.c
  • get_next_line.h

この3つのファイルのみを提出すること.

実装

get_next_line.h

# include <stdlib.h>
# include <unistd.h>

# define SUCCESS       1
# define END_OF_FILE   0
# define ERROR         -1
# define CONTINUE_READ -2

# ifndef BUFFER_SIZE
#  define BUFFER_SIZE 256
# endif

int        get_next_line(int fd, char **line);
char   *ft_strdup(const char *s);
char   *ft_substr(char const *s, unsigned int start, size_t len);
size_t ft_strlen(const char *s);
char   *ft_strchr(const char *s, int c);
char   *ft_strjoin(char const *s1, char const *s2);

基本的には定数の定義と get_next_line_utils.cの関数のプロトタイプ宣言入っているだけ.

get_next_line.c

get_next_line.c では以下の関数を定義している

int get_next_line(int fd, char **line);
static int read_process(int fd, char **line, char **save);
static int join_line_and_save(char **line, char **save);
static int    join_line_and_buf(char **line, char *buf);
static int split_by_newline(char **line, char **save, char *buf);

int get_next_line(int fd, char **line);

get_next_line.c 内で定義している他の関数を呼び出して動作する. 読み込んだ文字列でlineに結合しなかった残りの文字列を char*型のstatic変数 save で次回関数が呼ばれた時のために保管している.

int            get_next_line(int fd, char **line)
{
    int            ret;
    static char   *save;

    if (fd < 0 || !line || BUFFER_SIZE <= 0 || !(*line = ft_strdup("")))
        return (ERROR);
    ret = CONTINUE_READ;
    if (save)
        ret = join_line_and_save(line, &save);
    if (ret == CONTINUE_READ)
        ret = read_process(fd, line, &save);
    return (ret);
}

やっていることとしては

  • char*型のstatic変数 save を宣言
  • 以下の条件の時は問答無用でエラーとして返す
    • fd が負の値
    • line がNULL
    • BUFFER_SIZE が0以下
    • line の初期化処理に失敗 (!(*line = ft_strdup("")) の部分)
  • もし前回読み込んだ文字列が残っていたら join_line_and_save(line, &save) を呼び出して前回読み込んだ残りの文字列を line に格納する. もしsave内に改行が入っていた場合, ret には SUCCESS が入る. 改行が入っていない場合は CONTINUE_READ が入る.
  • 前回読み込んだ文字列の残りの中に改行がない場合はfdから新たに読み込む.

といった感じです.

基本的にはバリデーションと前回読み込んだ文字列の保持などを行っています. 実際にfdから読み込んだり, 文字列から改行を検出して文字列を分割するのは他の関数の仕事です.

static int join_line_and_save(char **line, char **save);

前回 get_next_line() が呼び出された時に保存した saveline に何文字コピーするかを計算し, コピーする.

static int join_line_and_save(char **line, char **save)
{
    char   *tmp;
    char   *newline_ptr;

    if ((newline_ptr = ft_strchr(*save, '\n')))
    {
        tmp = *line;
        *line = ft_substr(*save, 0, newline_ptr - *save);
        free(tmp);
        if (!(*line))
            return (ERROR);
        tmp = *save;
        *save = ft_substr(newline_ptr + 1, 0, ft_strlen(newline_ptr + 1));
        free(tmp);
        if (!(*save))
            return (ERROR);
        return (SUCCESS);
    }
    else
    {
        tmp = *line;
        *line = *save;
        *save = NULL;
        free(tmp);
        return (CONTINUE_READ);
    }
}

やってることとしては

  • 前回読み込んだ文字列の残り save に改行が入っている場合は line に改行文字までの文字列をコピーし, 残りの文字列を save に代入してSUCCESSを返す.
  • 前回読み込んだ文字列の残り save に改行が入っていない場合は linesave の文字列を全てコピーする.

static int read_process(int fd, char **line, char **save);

read() 関数を呼び出し, 読み込まれたデータを save に保存する. 読み込んだ文字列に改行が入っていた場合にはそこまでを line に入れて, 残りを save に入れる.

static int read_process(int fd, char **line, char **save)
{
    ssize_t        read_size;
    int            ret;
    char       *buf;

    ret = CONTINUE_READ;
    if (!(buf = malloc(BUFFER_SIZE + 1)))
        return (ERROR);
    while (ret == CONTINUE_READ && (read_size = read(fd, buf, BUFFER_SIZE)) > 0)
    {
        buf[read_size] = '\0';
        if (ft_strchr(buf, '\n'))
            ret = split_by_newline(line, save, buf);
        else
            ret = join_line_and_buf(line, buf);
    }
    free(buf);
    if (ret == CONTINUE_READ && read_size == 0)
        ret = END_OF_FILE;
    else if (ret == CONTINUE_READ && read_size == -1)
        ret = ERROR;
    return (ret);
}

やっていることとしては

  • ret == CONTINUE_READ だったら fdからBUFFER_SIZE分文字を読み込み buf に入れる.
  • もし buf の中に改行文字が入っていたら split_by_newline() を呼び出して改行文字までを line と結合し, 残りを save に入れてループを抜ける. (ret == SUCCESS になるから)
  • もし buf の中に改行文字が入っていなかったら join_line_and_buf() を呼び出して単純に linebuf を結合する.
  • ループ処理終了後, もし ret == CONTINUE_READ && read_size == 0 だったら, これすなわち改行は見つからずにfdがEOFに達したということを意味するので END_OF_FILE を返す.
  • read_size == -1 ということは読み込みに失敗しているのでERRORを返す.
  • 上記2つのif文の条件を通過したということは正常に終了したかEOFに到達したということなのでそのまま ret を返す.

static int split_by_newline(char **line, char **save, char *buf);

buf 内で最初に出現した改行文字より前を line に, それより後ろを save に格納する.

static int split_by_newline(char **line, char **save, char *buf)
{
    char   *old_line;
    char   *tmp;
    char   *newline_ptr;

    newline_ptr = ft_strchr(buf, '\n');
    if (!(tmp = ft_substr(buf, 0, newline_ptr - buf)))
        return (ERROR);
    old_line = *line;
    *line = ft_strjoin(*line, tmp);
    free(old_line);
    free(tmp);
    if (!(*line))
        return (ERROR);
    if (!(*save = ft_substr(newline_ptr + 1, 0,
                                ft_strlen(newline_ptr + 1))))
        return (ERROR);
    return (SUCCESS);
}

やっていることとしてはこの関数の説明をそのままコードにしただけなので詳細な説明は省く.

static int join_line_and_buf(char **line, char *buf);

linebuf を単純に結合するだけ.

static int join_line_and_buf(char **line, char *buf)
{
    char   *tmp;

    tmp = *line;
    *line = ft_strjoin(*line, buf);
    free(tmp);
    if (!(*line))
        return (ERROR);
    return (CONTINUE_READ);
}

やっていることとしてはこの関数の説明をそのままコードにしただけなので詳細な説明は省く.

get_next_line_utils.c

以下の関数が定義されている.

char    *ft_strdup(const char *s);
char   *ft_substr(char const *s, unsigned int start, size_t len);
size_t ft_strlen(const char *s);
char   *ft_strchr(const char *s, int c);
char   *ft_strjoin(char const *s1, char const *s2);

基本的には ft_ というプレフィックスを取った標準ライブラリ関数と同じ動きをする. (例: ft_strdup() -> strdup())

これらに関しては標準ライブラリ関数とほぼ同じなので実装レベルで説明は行わない.

詳細を知りたい場合は以下のリンクから見ることが出来る.

github.com

動作例

実際の動きを見ていく.

以下のような main.c を用意する.

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include "get_next_line.h"

int main(int argc, char *argv[])
{
    char *file_name;
    if (argc == 1)
    {
        file_name = "test.txt";
    }
    else
        file_name = argv[1];
    int fd = open(file_name, O_RDONLY);
    // int fd = 999999;
    char *line;
    int status;

    printf("\n[START] %s\n\tfd: %d\n\n", file_name, fd);
    do{
        status = get_next_line(fd, &line);
        printf("status:  \t%d\n", status);
        printf("read txt:\t%s\n", line);
        free(line);
    }while (status == 1);
    printf("\n[FINISH] %s\n\tstatus: %d\n\n", file_name, status);
    
    close(fd);
}

そしてこれをコンパイルする gcc -D BUFFER_SIZE=256 main.c get_next_line.c get_next_line_utils.c

./a.out で実行するとtest.txtから1行ずつ読み込めていることがわかるだろう.

ちなみに./a.out の引数としてファイル名を指定することもでき, ./a.out main.c とすると main.c 自身が1行ずつ読み込まれて出力される.

[START] main.c
        fd: 3

status:         1
read txt:       #include <stdio.h>
status:         1
read txt:       #include <sys/types.h>
status:         1
read txt:       #include <sys/stat.h>
status:         1
read txt:       #include <fcntl.h>
status:         1
read txt:       #include "get_next_line.h"
status:         1
read txt:
status:         1
read txt:       int main(int argc, char *argv[])
status:         1
read txt:       {
status:         1
read txt:               char *file_name;
status:         1
<---------------------  長いので中略  ------------------------------->
read txt:               }while (status == 1);
status:         1
read txt:               printf("\n[FINISH] %s\n\tstatus: %d\n\n", file_name, status);
status:         1
read txt:
status:         1
read txt:               close(fd);
status:         1
read txt:       }
status:         0
read txt:

[FINISH] main.c
        status: 0

BUFFER_SIZE による実行時間とシステムコール呼び出し回数の変化

また, コンパイル時に指定していた定数BUFFER_SIZEを変更することで一度のread()で読み込む量が変わる.

実際にBUFFER_SIZEの値を変更するとどのくらい変わるのか, システムコールが呼び出された回数が見れるコマンド strace を使って計測してみた.

$ gcc -D BUFFER_SIZE=1 main.c get_next_line.c get_next_line_utils.c && strace -c -e trace=read  ./a.out main.c
[START] main.c
<---------------------  長いので中略  ------------------------------->
[FINISH] main.c
        status: 0

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
100.00    0.001448           2       634           read
------ ----------- ----------- --------- --------- ----------------
100.00    0.001448                   634           total

BUFFER_SIZE=1の時, システムコールread() が 634回呼ばれています.

BUFFER_SIZE=10に設定して同様のコマンドでコンパイルして実行すると

$ gcc -D BUFFER_SIZE=10 main.c get_next_line.c get_next_line_utils.c && strace -c -e trace=read  ./a.out main.c
[START] main.c
<---------------------  長いので中略  ------------------------------->
[FINISH] main.c
        status: 0

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  0.00    0.000000           0        66           read
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000                    66           total

BUFFER_SIZE=100にすると以下のようになります.

$ gcc -D BUFFER_SIZE=100 main.c get_next_line.c get_next_line_utils.c && strace -c -e trace=read  ./a.out main.c
[START] main.c
<---------------------  長いので中略  ------------------------------->
[FINISH] main.c
        status: 0

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
100.00    0.000038           4         9           read
------ ----------- ----------- --------- --------- ----------------
100.00    0.000038                     9           total

BUFFER_SIZE を大きくするとシステムコール read() が呼ばれる回数が少なくなっているのがわかりますね!

試しにめっちゃでかいファイルを作って, それの読み込み速度を比較してみましょう.

$ for i in `seq 1 1000000`  # めっちゃでかいファイルを作る
do
echo "${i}" >> big_file.txt
done
$
$ ls -lh big_file.txt  # ファイルサイズは6.6MB
-rw-rw-r-- 1 jun jun 6.6M 12月 18 06:45 big_file.txt
$
$ wc -m big_file.txt  # 文字数は6888896文字
6888896 big_file.txt

BUFFER_SIZE を変えてテストしてみましょう.

なお, このテストでは main.c 内にあるwhileループ内のprintfコメントアウトして実行するようにしています.

テストは以下のような形で行い, total の時間を見ます. ついでに read() が呼ばれた回数も見ます.

$ gcc -D BUFFER_SIZE=100 main.c get_next_line.c get_next_line_utils.c && time ./a.out big_file.txt && strace -c -e trace=read  ./a.out big_file.txt

[START] big_file.txt
        fd: 3


[FINISH] big_file.txt
        status: 0

./a.out big_file.txt  1.03s user 0.02s system 99% cpu 1.050 total

[START] big_file.txt
        fd: 3


[FINISH] big_file.txt
        status: 0

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
100.00    0.058994           0     68891           read
------ ----------- ----------- --------- --------- ----------------
100.00    0.058994                 68891           total

BUFFER_SIZE=1 の時は 5.56秒でした.

このような感じで何回かBUFFER_SIZEを変更して実行時間の変化を見ます.

BUFFER_SIZE 実行時間[s] read()が呼ばれた回数
1 5.6 6888898
10 0.742 688892
100 1.051 68891
1000 9.4 6891
10000 101 691

うーむ, BUFFER_SIZE=10 が一番速いですね...

イメージとしてはBUFFER_SIZEが大きくなればなるほど早くなると思ったのですが...

プロファイルツールを用いたボトルネックの特定

gcc 付属のプロファイルツール gprof を使ってどの関数がどれくらい呼ばれて, どのくらい時間がかかったかを計測してみました.

$ gcc -pg -D BUFFER_SIZE=1000 main.c get_next_line.c get_next_line_utils.c && ./a.out big_file.txt && gprof ./a.out 

  %   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 78.50      7.14     7.14  6012695     1.19     1.19  ft_strlen
 21.31      9.08     1.94  2000000     0.97     3.34  ft_substr
  0.33      9.11     0.03  1013778     0.03     0.03  ft_strchr
  0.22      9.13     0.02  1000001     0.02     9.14  get_next_line
  0.11      9.14     0.01  1000000     0.01     7.86  join_line_and_save
  0.00      9.14     0.00  1000001     0.00     1.19  ft_strdup
  0.00      9.14     0.00     6890     0.00    10.31  read_process
  0.00      9.14     0.00     6889     0.00     2.38  ft_strjoin
  0.00      9.14     0.00     6889     0.00    10.28  split_by_newline

おおぉ... 自分としてはてっきりメモリコピー系が時間かかっているかと思ったのですが, まさかのft_strlenが一番のボトルネックだったとは...

ft_strlen() の実行回数が多いのは, get_next_line_utils.c 内で大量に ft_strlen() 呼んでいるからでしょうな...

ちょっとgrepして, ft_strlen() を使用している場所を抜き出してみた

get_next_line.c:28:             *save = ft_substr(newline_ptr + 1, 0, ft_strlen(newline_ptr + 1));
get_next_line.c:60:                                                             ft_strlen(newline_ptr + 1))))
get_next_line_utils.c:31:       s_len = ft_strlen(s);
get_next_line_utils.c:53:       if (start >= ft_strlen(s))
get_next_line_utils.c:56:       s_len = ft_strlen(s);
get_next_line_utils.c:92:       total_len = ft_strlen(s1) + ft_strlen(s2);

なるほど, 意外と呼び出していないように見えますね... しかし, 多分呼び出し元の関数がかなりの回数呼ばれていて, それが累積してこの結果になったんだと思います.

ここでスパッと解決出来ればかっこいいのですが, ちょっと解決策が思い浮かばないので高速化の方法がある人はぜひ教えてください.

(2020/12/22 追記) ft_strlenを標準ライブラリ実装に置き換えてみる

先程ft_strlen()の実行時間がプログラム全体の実行時間の中で大きな割合を示すことを調査しました.

じゃあ標準Cライブラリのstrlen()使ったコードに置き換えたらどうなるか調べてみました.

BUFFER_SIZE 実行時間[s](ft_strlen) 実行時間[s](strlen)
1000 9.4 2.6
10000 101 18.9

めっちゃ速くなった!!

BUFFER_SIZE=1000 の時の実行時間内訳ではft_strlen()が7秒かかっていたのですが, 標準実装に変えたらプログラム全体の実行時間が7秒減ったことを考えるとft_strlen()でかかっていた7秒がまるまる速くなった感じですね.

ちなみにgprofを使って実行時間の内訳を見ると...

$ gcc -pg -D BUFFER_SIZE=1000 main.c get_next_line.c get_next_line_utils.c && ./a.out big_file.txt && gprof ./a.out

  %   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
 98.70      1.68     1.68  2000000     0.84     0.84  ft_substr
  1.18      1.70     0.02  1000000     0.02     1.69  join_line_and_save
  0.59      1.71     0.01                             main
  0.00      1.71     0.00  1013778     0.00     0.00  ft_strchr
  0.00      1.71     0.00  1000001     0.00     0.00  ft_strdup
  0.00      1.71     0.00  1000001     0.00     1.70  get_next_line
  0.00      1.71     0.00     6890     0.00     1.68  read_process
  0.00      1.71     0.00     6889     0.00     0.00  ft_strjoin
  0.00      1.71     0.00     6889     0.00     1.68  split_by_newline

ft_strlen()が7秒かかっていたのが消えて, 一番時間がかかった関数がft_substr()になってますね.

ちなみに自分の ft_strlen()は以下のようになっており, 特別遅いことをやっているわけでは無いと思うので, 標準Cライブラリの実装が恐ろしく速いのだと思います.

size_t  ft_strlen(const char *s)
{
    size_t ans;

    ans = 0;
    while (s[ans])
        ans++;
    return (ans);
}

ちなみに標準Cライブラリ(glibc)の実装は以下のリンクに載っています. 自分は読んでも何をしているかわからなかったので, わかったらまた記事にしたいと思います.

github.com

ボーナス課題 (複数fd対応)

42の課題にはボーナスというものがあります. これは今までの必須パートをクリアした人で余裕があれば挑戦してね〜って感じの内容です.

今回の課題のボーナスは複数fd対応です.

どういうことかというと, fd=3, fd=4, fd=5 を順番にget_next_line()に渡して呼び出した際に, 今の実装だったら save が1つしかないので順番に呼び出すと他のfdsaveを上書きしてしまって上手くいかないので, なんとかして動くようにしましょう! という課題です.

実装

今回は以下の線形リストを表す構造体を定義し, これをうまく使って実装しました.

typedef struct s_list
{
    int                fd;
    char           *save;
    struct s_list  *next;
}               t_list;

基本的に実装は必須パートと同じなのですが, get_next_line() を結構変更したのと, 線形リスト用の関数(create_fd_elem())を作成したのでその2つだけ説明します.

t_list *create_fd_elem(t_list **lst, int fd);

t_list   *create_fd_elem(t_list **lst, int fd)
{
    t_list *new;

    if (!lst)
        return (NULL);
    if (!(new = malloc(sizeof(t_list))))
        return (NULL);
    new->fd = fd;
    new->save = NULL;
    if (!(*lst))
    {
        *lst = new;
        new->next = NULL;
    }
    else
    {
        new->next = *lst;
        *lst = new;
    }
    return (new);
}

create_fd_elem() は新しいfdが来た時に構造体を動的に確保し, それを初期化してlstの先頭要素にして, 作成した要素を返す関数です.

int get_next_line(int fd, char **line)

int         get_next_line(int fd, char **line)
{
    int                ret;
    static t_list  *save_list_head;
    t_list          *target_save_list;

    if (fd < 0 || !line || BUFFER_SIZE <= 0 || !(*line = ft_substr("", 0, 0)))
        return (ERROR);
    target_save_list = save_list_head;
        // fd のリスト要素を探す
    while (target_save_list && target_save_list->fd != fd)
        target_save_list = target_save_list->next;
        // 見つからなかった場合はリスト要素を作成
    if (!target_save_list)
        if (!(target_save_list = create_fd_elem(&save_list_head, fd)))
            return (ERROR);
    ret = CONTINUE_READ;
    if (target_save_list->save)
        ret = join_line_from_save(line, &target_save_list->save);
    if (ret == CONTINUE_READ)
        ret = read_process(fd, line, &target_save_list->save);
    if (ret == END_OF_FILE || ret == ERROR)
    {
        free(target_save_list->save);
                // 今回のfdが先頭要素だった場合, 先頭要素を次の要素に変更
        if (save_list_head == target_save_list)
            save_list_head = target_save_list->next;
        else
        {
                        // 要素を削除した上でその要素の前後の要素を接続する
            t_list *tmp = save_list_head;
            while (tmp->next != target_save_list)
                tmp = tmp->next;
            tmp->next = target_save_list->next;
        }
        free(target_save_list);
    }
    return (ret);
}

注意: if (ret == END_OF_FILE || ret == ERROR) 直下の else文 は提出時ありませんでした. なので提出後に修正したものなのでこのままだとNorminetteの行数制限に引っかかります.

今回は行数が多く, 説明が少しむずかしかったのでコメントという形で説明しました.

動作例

複数ファイルを並行して読み込むようなmain.cを作成します.

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include "get_next_line_bonus.h"

int main()
{
    char *line;
    int fd1 = open("./get_next_line.h", O_RDONLY);
    int fd2 = open("./get_next_line.c", O_RDONLY);
    int fd3 = open("./get_next_line_utils.c", O_RDONLY);
    int status;
    printf("fd1: %d\n", fd1);
    printf("fd2: %d\n", fd2);
    printf("fd3: %d\n", fd3);
    int finish_count = 0;
    int idx = 0;
    while (finish_count < 3)
    {
        if (idx % 3 == 0)
        {
            printf("\n---------- fd1: %d ----------\n", fd1);
            
            status = get_next_line(fd1, &line);
            printf("status:  \t%d\n", status);
            printf("read txt:\t%s\n", line);
            free(line);
            if (status == 1)
                finish_count = 0;
            else
                finish_count++;
        }
        else if(idx % 3 == 1)
        {
            printf("\n---------- fd2: %d ----------\n", fd2);
            status = get_next_line(fd2, &line);
            printf("status:  \t%d\n", status);
            printf("read txt:\t%s\n", line);
            free(line);
            if (status == 1)
                finish_count = 0;
            else
                finish_count++;
        }
        else if (idx % 3 == 2)
        {
            printf("\n---------- fd3: %d ----------\n", fd3);
            status = get_next_line(fd3, &line)  ;
            printf("status:  \t%d\n", status);
            printf("read txt:\t%s\n", line);
            free(line);
            if (status == 1)
                finish_count = 0;
            else
                finish_count++;
        }
        idx++;
    }
    close(fd1);
    close(fd2);
    close(fd3);
    return 0;
}

そしてこの main.cコンパイルして実行すると複数ファイル並列で行ごとに読み込めていることがわかると思います.

$ gcc -D BUFFER_SIZE=1000 main_multiple_fd.c get_next_line_bonus.c  get_next_line_utils_bonus.c && ./a.out
fd1: 3
fd2: 4
fd3: 5

---------- fd1: 3 ----------
status:         1
read txt:       #ifndef GET_NEXT_LINE_H

---------- fd2: 4 ----------
status:         1
read txt:       #include "get_next_line.h"

---------- fd3: 5 ----------
status:         1
read txt:       #include "get_next_line.h"

---------- fd1: 3 ----------
status:         1
read txt:       # define GET_NEXT_LINE_H

---------- fd2: 4 ----------
status:         1
read txt:

---------- fd3: 5 ----------
status:         1
read txt:

---------- fd1: 3 ----------
status:         1
read txt:

---------- fd2: 4 ----------
status:         1
read txt:       static int      join_line_and_save(char **line, char **save)

---------- fd3: 5 ----------
status:         1
read txt:       size_t  ft_strlen(const char *s)

---------- fd1: 3 ----------
status:         1
read txt:       # include <stdlib.h>
<-----------長いので中略----------->
---------- fd1: 3 ----------
status:         0
read txt:

---------- fd2: 4 ----------
status:         1
read txt:               return (ret);

---------- fd3: 5 ----------
status:         0
read txt:

---------- fd1: 3 ----------
status:         0
read txt:

---------- fd2: 4 ----------
status:         1
read txt:       }

---------- fd3: 5 ----------
status:         0
read txt:

---------- fd1: 3 ----------
status:         0
read txt:

---------- fd2: 4 ----------
status:         0
read txt:
status: 0

static変数について

今回の課題の意図の1つとして static変数 を理解するというのがあるので, 自分なりに調べたり試したりした結果も書いておく. なお, ここでいう static変数 とは関数内のものを指す点に留意して頂きたい.

  • static変数はグローバル変数と同じメモリの静的領域に配置される.
  • static変数は宣言されたと同時に初期化する必要がある. 例: static a = 10
    • 明示的に初期化しない場合は0で初期化される.

以下のサイトがメモリ領域についてわかりやすかったです.

www.momoyama-usagi.com

あとWikipediaの以下の説明もわかりやすいです.

ローカル変数宣言にstaticキーワード(静的記憶クラス指定子)を付加すると、「静的ローカル変数」[3]となり、変数寿命はプログラムの生存期間と同一となる。C言語では静的ローカル変数はグローバル変数と同じくプログラム開始処理以前に一度だけ初期化される

ja.wikipedia.org

完走した感想

完走した感想(激うまギャグ) ですが, 我ながらうまく書けたと思います.

特にボーナスパートに関しては, 42Tokyo内でもリストを使った実装をした人は少なかったので, ドヤッ! って感じです. ちなみに点数は線形リストの後始末にミスがあり 113/115 点でした (必須パート100点 + ボーナス15点 計算)

自分は基本的に何かしら実装をしたり, 何か開発したりした際にはブログにこうやってアウトプットしたいマンなのですが, 当初42Tokyo内では課題についてどこまで公開してよいか明確な基準は無く, 記事を書くかためらっていました. しかし, 1ヶ月ほど前に公式からルールを守ればOKというのを得たので遠慮なくコードの解説を書きまくりました.

しかし, 書いた本人が言うのもなんですが, 42の課題は自分で考えて調べてやり方を試して実装して, そしてクリア! というのが一番楽しい42の課題の遊び方だと思います. なので申し訳程度にまえがきで注意喚起をしました.

本記事に関してですが, ここまで書くのに5時間ほどかかりました. もともとこんなにかかる予定では無かったのですが, BUFFER_SIZE による時間とシステムコールの呼び出し回数, プロファイラによるパフォーマンス解析などに手を出したらこんなに時間がかかりました.

あとは単純に最近ブログでこういう技術系の記事を書くことが少なかったので, 綺麗な文章を一発で書けなくなってるんですよね. まぁ, アウトプット量を増やせば自然にある程度早く記事が書けるようになるので, これからもいっぱいアウトプットしていきます. ただ, このレベルの文量を毎回書くのはしんどい(特にコードの解説とかインデントの修正とか)ので次からは多分文量が減ると思います.

42ではこのような課題が沢山あり, 人と一緒に相談したり楽しみながらコンピューターサイエンスを手を動かして学べる環境が整っているので自分としては最高に楽しいです. (この課題がまだLv1というのが最高にワクワクしますね)

42は名前だけは調べれば出てくるけど, 中で何をやっているかは正直謎に包まれている部分が多いと思います(課題の情報をアウトプットする人も多くはないですし). なので, 自分の記事を呼んで「へ〜42ってこういう感じなんだな」というのを感じて貰えれば良いなと思います.

42に興味があればとりあえず42の入学試験である Piscine だけでも受けて見ると良いと思います.

参考にしたサイト

りあクト! を読んだ

読んだ本

「りあクト! TypeScriptで始めるつらくないReact開発 第3版」を読んだのでそれの読書感想文です.

booth.pm

感想

大変素晴らしいReactの本でした.

ES6以降のJSの文法から始まり, 環境構築, Reactで重視されている関数型プログラミングの考え方, TypeScriptの文法, Linterなどのコード整形ツール, Reactとその他フレームワークの歴史, Hooksとこれから登場する新機能について, etc...

はい. 最高でした. Reactをこんなにも詳細にわかりやすく具体的に歴史や経緯, 周辺技術も含め説明している本やサイトはなかなかないと思います.

自分は普段業務で特に意識せず React を TypeScript で書いていたのですが, この本を読んでから, しっかりReactの内部の動作やコンポーネント設計を意識してコードを書けるようになったように思えます. Reactの思想や大事にしていることなども知れたので, React公式ドキュメントを読んだときの理解度も上がったような気がします.

React自体に関しても, 2年前インターンシップで触った時はHooksなどは無くクラスベースで書いていて, 副作用処理もReduxを使っていたりして挫折したものですが, 最近はHooksやContextProviderなどを使って関数コンポーネントで書けるようになってるのでかなりわかりやすくなっていて良いですね. (まぁこの本読めばクラスベースでも書けるようになりますけどね)

ReactはVueのテンプレートベースのフレームワークではなく, コンポーネントベースなのでテンプレートベースのフレームワークと同じように書くことはあまり良くありません. しかし, それを教えてくれる人やサイトはあまり無いように感じます. そういった意味ではこの本は貴重な本と言えます.

ReactはVueなどに比べて敷居が高いですが, この本を読めばかなり敷居は下がると思います. React初めたい人におすすめの本やサイト教えてって言われたらとりあえずこの本のリンクを送っておけばいいと思います.

Reactを書く多くの人にとって何かしらの学びがある本だと思うのでとてもおすすめです.

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

ERROR: Couldn't connect to Docker daemon at http+docker://localhost - is it running? の解決法

docker-compose up --build しようとしたら以下のようなエラーが出た.

ERROR: Couldn't connect to Docker daemon at http+docker://localhost - is it running?

If it's at a non-standard location, specify the URL with the DOCKER_HOST environment variable.

とりあえずggったらユーザーがdockerグループに追加されてないから追加すれば良い的なこと書いている記事が多かった.

www.virment.com

でも, 自分の場合は既にユーザーがdockerグループに所属していて, 解決方法が違ったのでメモとして残しとく.

結論から言えばDocker-Daemonが落ちてただけでした. なのでとりあえず sudo systemctl status docker.service で状態を見る

● docker.service - Docker Application Container Engine
     Loaded: loaded (/lib/systemd/system/docker.service; enabled; vendor preset: enabled)
     Active: inactive (dead) since Tue 2020-12-01 06:13:07 JST; 8h ago
TriggeredBy: ● docker.socket
       Docs: https://docs.docker.com
   Main PID: 1739 (code=exited, status=0/SUCCESS)

案の定Dockerデーモンが動いていないので, Dockerデーモンをsudo systemctl restart docker.serviceで再起動する. そしたら動くようになりました.