fixedpoint.jp - Linux v4.13でのbsearch(3)の速度改善




Linux v4.13でのbsearch(3)の速度改善

bsearch(3)stdlib.hで定義されているC89の標準関数で、与えられた比較関数を用いて整列済みの配列からキーを二分探索します。

Linuxではlib/bsearch.cで実装されていますが、v4.13向けに取り込まれたパッチでこの関数の時間性能が若干改善するようです: commit 166a0f780a8fdb67f232c85e9905ba84f7247da9

ベンチマークによると、ピボット位置の計算で実行されるインストラクション数が単純に減っています。コードを見比べると、*BSDでの実装やGNU libibertyでの実装とほぼ同じになったと言えます。

参考:


© 2006-2017 fixedpoint.jp