gccの最適化オプションを試してみました。-O3, -Ofast, -ffast-mathではプログラムが壊れる可能性があるので取り扱い注意です。
約24000件処理の時間を測定しました。それなりの効果はあるようです。
-O0 78.3秒
-O1 76.0秒
-O2 75.4秒
-O3 74.1秒
-Ofast 75.8秒
-ffast-math 78.1秒
gcc -S [最適化オプション] [cファイル]
アセンブラファイルを作成後、実行ファイルを作成して測定実施カテゴリー: C言語
[C言語] 08 アセンブラファイルの修正
C言語のアセンブラファイルをチェックしたところ、関数ファイル内の使わない関数を読み込んでいたので削除しましたが、処理時間は変わらずでした。
処理時間の測定にはPythonを使いました。
まあ端折っても最初の読み込みがなくなるだけなのでそんなところでしょう。ループ箇所などをチェックする方がいいようです。
import datetime,time,os,subprocess
start = time.time()
dt_now = datetime.datetime.now()
print('スタート 現在時刻 ' + str(dt_now))
proc = subprocess.run("as -o ./test.o ./test.s; gcc -o ./test ./test.o ; ./test; ECHO 'C言語実行完了'", shell=True, stdout= subprocess.PIPE, stderr = subprocess.PIPE)
process_time = time.time() - start
td = datetime.timedelta(seconds = process_time)
dt_now2 = datetime.datetime.now()
print('テスト 完了 ' + str(td) + ' 現在時刻 ' + str(dt_now2))
# Macのデスクトップ通知
os.system("osascript -e 'display notification \"テスト完了\n\"'")[Python] 293 引数が複数あるC言語モジュール
以前うまくいかなかったC言語モジュールを完成させました。
input(引数)とoutput(戻り値)を自在に設定でき、C言語実行ファイルに必須の処理終了検知が不要なので、こちらを常用することになりそうです。
#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include "fnv_function.c"
static PyObject* horse_id(PyObject* self, PyObject* args)
{
const char* path;
const char* name;
uint32_t id;
if (!PyArg_ParseTuple(args,"ss",&path,&name)){
return NULL;
}
else{
FILE *fp; // horse_listファイル
int horseID[10]; // 1 horseID
uint32_t horse_hash[20]; // 2 馬名ハッシュ
char horse_name[100]; // 3 検索馬名
char horse_name0[100]; // 4 馬名
char status[10]; // 5 稼働
char gender[10]; // 6 性別
char hair[10]; // 7 毛色
char birthday[100]; // 8 生年月日
char trainer[100]; // 9 調教師
char owner[100]; // 10 馬主
char info[100]; // 11 募集情報
char breeder[100]; // 12 生産者
char area[50]; // 13 産地
char price[50]; // 14 セリ取引価格
char prize_money[50]; // 15 獲得賞金
char result[50]; // 16 通算成績
char wining_race[200]; // 17 主な勝鞍
char relatives[200]; // 18 近親馬
uint32_t horse_hash_input_int;
uint32_t horse_hash_int;
char buf[2000]; // fgets用
int i=0; // 行番号
int b=0; // 検索結果有無の識別
fp = fopen(path, "r");
while(fgets(buf,2000,fp ) != NULL ) {
if (i != 0){
sscanf(buf, " %[^,],%[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %s",horseID,horse_hash,horse_name,horse_name0,status,gender,hair,birthday,trainer,owner,info,breeder,area,price,prize_money,result,wining_race,relatives) ;
horse_hash_int = atoi(horse_hash);
horse_hash_input_int = fnv_1_hash_32(name);
if(horse_hash_int - horse_hash_input_int == 0){
id = atoi(horseID);
b ++;
break;
}
}
i ++ ;
}
if (b == 0){
id = 100000000;
}
fclose(fp);
return Py_BuildValue("I", id);
}
}
static PyMethodDef Horseidmethods[] = {
{"horse_id", (PyCFunction)horse_id, METH_VARARGS},
{NULL,NULL,0}
};
static struct PyModuleDef horseid = {
PyModuleDef_HEAD_INIT,
"horseid",
"Python3 C API Module(Sample 1)",
-1,
Horseidmethods
};
PyMODINIT_FUNC PyInit_horseid(void)
{
return PyModule_Create(&horseid);
}
[C言語] 07 数字の文字列をuint64_tに変換する
すぐに忘れそうなのでメモ書きしておきます。
第2引数&endの意味がよく分かりません。適当なポインタを入れておけば良いのでしょうか。
IBMやMicrosoftの資料によると、文字列の読み取りを停止した文字(ヌル文字など)へのポインタを&endに格納するとのことです。読み取り不可の場合は文字列をそこに格納します。char* end = NULLでも問題ないみたいです。
#include <stdlib>
uint64_t numA;
uint64_t numB;
char* end;
＜中略＞
// sscanfで文字列として読み込んだnumAを16進数のuint64_tへ変換する
numB = strtoull(numA,&end,16);[Python] 290 引数ありのC言語モジュール ハッシュ関数 FNV 64bit
ハッシュ関数FNVの32bitで数件衝突が発生したため、64bitでも生成できるようにしました。
PythonのドキュメントにPy_BuildValueの引数について解説があり、unsigned long long intのフォーマットがKであることが分かりました。
unsigned intのフォーマットはiではなく大文字のIなので、32bitの方も修正しました。これでPython側での変換が不要になります。
#define PY_SSIZE_T_CLEAN
#include <Python.h>
extern uint32_t fnv_1_hash_32(const char*);
extern uint64_t fnv_1_hash_64(const char*);
static PyObject* fnv_32(PyObject* self, PyObject* args)
{
const char* s;
unsigned int hash=2166136261U;
if (!PyArg_ParseTuple(args, "s", &s)){
return NULL;
}
else{
while (*s) {
hash*=16777619U;
hash^=*(s++);
}
return Py_BuildValue("I", hash);
}
}
static PyObject* fnv_64(PyObject* self, PyObject* args)
{
const char* s;
unsigned long long hash=14695981039346656037U;
if (!PyArg_ParseTuple(args, "s", &s)){
return NULL;
}
else{
while (*s) {
hash*=1099511628211LLU;
hash^=*(s++);
}
return Py_BuildValue("K", hash);
}
}
static PyMethodDef fnvmethods[] = {
{"fnv_1_hash_32", fnv_32, METH_VARARGS},
{"fnv_1_hash_64", fnv_64, METH_VARARGS},
{NULL,NULL,0}
};
static struct PyModuleDef fnv = {
PyModuleDef_HEAD_INIT,
"fnv",
"Python3 C API Module(Sample 1)",
-1,
fnvmethods
};
PyMODINIT_FUNC PyInit_fnv(void)
{
return PyModule_Create(&fnv);
}from c_module import fnv
name_list = ['シャフリヤール']
for name in name_list:
hash = fnv.fnv_1_hash_64(name)
print(hash)
--------------------------------------------------
出力
--------------------------------------------------
7203286604922561048#include <stdio.h>
#include <stdint.h>
uint32_t fnv_1_hash_32(char *s)
{
unsigned int hash=2166136261U;
while (*s) {
hash*=16777619U;
hash^=*(s++);
}
return hash;
}
uint64_t fnv_1_hash_64(char *s)
{
unsigned long long hash=14695981039346656037U;
while (*s) {
hash*=1099511628211LLU;
hash^=*(s++);
}
return hash;
}from distutils.core import setup, Extension
setup(name='fnv',
version='1.0',
ext_modules=[Extension('fnv', sources = ['fnv.c','fnv_function.c'])]
)＜セットアップコマンド＞
・自作ライブラリに配置するsoファイルを作成するコマンド "from c_module import fnv"
python setup.py build_ext -i
・既存のライブラリにインストールするコマンド "import fnv"
python setup.py install[Python] 289 ハッシュ関数 FNV-1によるハッシュ値のばらつき
FNV-1により生成されたハッシュ値のばらつきをヒストグラムで確認しました。ハッシュ値は自製のC言語モジュールで生成しました。
上のグラフが1986年以降に生まれた競走馬26.2万頭の馬名ハッシュ値、下のグラフが馬名にシルクが含まれる1000頭のハッシュ値をヒストグラムにしたものです。
満遍なくハッシュ値が生成されており、冠名による偏りもほとんど見られませんでした。
ハッシュ値の重複については調査中です。重複があれば他のハッシュ関数を検討します。
import matplotlib.pyplot as plt
import datetime
import pandas as pd
df = pd.read_csv("name_hash.csv",encoding='UTF-8')
df2 = df[df['馬名'].str.contains('シルク',na=False)]
list = df2['horse_hash'].tolist()
datetime_now = datetime.datetime.now()
datetime_now_str = datetime_now.strftime('%y%m%d%H%M')
plt.hist(list, bins=20,color=['#7fffd4'])
plt.savefig(f"{datetime_now_str}_hist_silk.png")[Python] 287 引数ありのC言語モジュール ハッシュ関数 FNV
Pythonでもハッシュ関数FNVを使えるようにするためC言語モジュール化しました。
モジュールからの戻り値は整数の範囲でしか使えず、32ビットのunsigned intには対応できましたが、64ビットではうまくいきませんでした。
初めはPythonからポインタをどうやって渡すのか見当もつかなくて、戻り値の受け取り方もかなり試行錯誤しました。
これでC言語とPythonで同一文字列から同じハッシュ値を作成できるので色々使い道がありそうです。
2021/7/25追記：コードを改良して以下の記事にアップしています。
#define PY_SSIZE_T_CLEAN
#include <Python.h>
extern uint32_t fnv_1_hash_32(const char*);
static PyObject* fnv_32(PyObject* self, PyObject* args)
{
const char* s;
unsigned int hash=2166136261U;
if (!PyArg_ParseTuple(args, "s", &s)){
return NULL;
}
else{
while (*s) {
hash*=16777619U;
hash^=*(s++);
}
return Py_BuildValue("i", hash);
}
}
static PyMethodDef fnvmethods[] = {
{"fnv_1_hash_32", fnv_32, METH_VARARGS},
{NULL,NULL,0}
};
static struct PyModuleDef fnv = {
PyModuleDef_HEAD_INIT,
"fnv",
"Python3 C API Module(Sample 1)",
-1,
fnvmethods
};
PyMODINIT_FUNC PyInit_fnv(void)
{
return PyModule_Create(&fnv);
}from c_module import fnv
name = 'シャフリヤール'
hash = fnv.fnv_1_hash_32(name)
# int から unsigned int 32bitへ変換
hash_unsigned32 = hash & 0xffffffff
print(hash_unsigned32)
--------------------------------------------------
出力
--------------------------------------------------
3687658616#include <stdio.h>
#include <stdint.h>
uint32_t fnv_1_hash_32(char *s)
{
unsigned int hash=2166136261U;
while (*s) {
hash*=16777619U;
hash^=*(s++);
}
return hash;
}from distutils.core import setup, Extension
setup(name='fnv',
version='1.0',
ext_modules=[Extension('fnv', sources = ['fnv.c','fnv_1.c'])]
)＜セットアップコマンド＞
・自作ライブラリに配置するsoファイルを作成するコマンド "from c_module import fnv"
python setup.py build_ext -i
・既存のライブラリにインストールするコマンド "import fnv"
python setup.py install[Python] 286 C言語実行ファイルの併用 その4 文字列のハッシュ化
これまでC言語を学習してきて、この言語は文字列の取り扱いが不得手というのがよく分かりました。そのような仕様でもstrcmp関数は1文字づつの比較しかできないながら相当速くなっていると思います。
さらなる高速化を検討した結果、文字列を数字に変換して加減計算等できるようにすれば処理が速くなるのではと考え、ハッシュ関数によるハッシュ化を試してみました。
データベースに馬名のハッシュ値を格納し検索に用いたところ、24000件の処理を80秒から55秒に短縮しました。
sscanf関数が扱いづらくatoi関数の必要性にもなかなか気がつかなかったため、かなり難航しました。
今回は比較する文字列の片方を前もってハッシュ化しましたが、両方処理していたらさらに速くなるはずです。
＜修正箇所＞
uint32_t horse_hash_int;
while(fgets(buf,2000,fp ) != NULL ) {
if (i != 0){
ret = sscanf(buf, " %[^,],%[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %[^,], %s",horseID,horse_hash,horse_name,horse_name0,status,gender,hair,birthday,trainer,owner,info,breeder,area,price,prize_money,result,wining_race,relatives) ;
horse_hash_int = atoi(horse_hash);
if(horse_hash_int - fnv_1_hash_32(horse_name_in) == 0){
fp3 = fopen(fname3, "a");
fprintf(fp3," %s,%9s\n",horse_name_in,horseID);
fclose(fp3);
b ++;
break;
}
}
i ++ ;
}
[C言語] 06 ハッシュ関数 FNVの外部関数化
FNVをPythonでも使えるようにするため、まずは外部関数化しました。
64バイトハッシュ値のフォーマット指定子は%luです。
#include <stdio.h>
#include <stdint.h>
uint32_t fnv_1_hash_32(char *s)
{
unsigned int hash=2166136261U;
while (*s) {
hash*=16777619U;
hash^=*(s++);
}
return hash;
}
uint64_t fnv_1_hash_64(char *s)
{
long unsigned int hash=14695981039346656037U;
while (*s) {
hash*=1099511628211LLU;
hash^=*(s++);
}
return hash;
}#include <stdio.h>
#include <stdint.h>
#include "fnv_1.c"
int main(void)
{
char *s = "シャフリヤール";
printf("%u\n",fnv_1_hash_32(s));
printf("%lu\n",fnv_1_hash_64(s));
}
--------------------------------------------------
出力
--------------------------------------------------
3687658616
7203286604922561048[C言語] 05 簡易なハッシュ関数 FNV
[Python] 283の記事あたりまで取り組んでいたデータベース検索の高速化ですが、文字列比較ではなくハッシュ値比較でも試してみました。
ハッシュ関数によるハッシュ値算出の時間が余計に掛かっているものの、これまでの最速記録80秒に対して84秒となかなかの健闘でした。正確性も問題ありません。
その他では機械語変換手前のアセンブリ言語コードをチェックしたりもしましたが初級者にいじれるはずもなく、また最近の文字列比較機能(strcmpなど)は優秀のようで小手先の自作関数では歯が立ちませんでした。
ハッシュ関数についてはスキルアップのための余興みたいなもので、ここらで高速化検討は打ち切りにするつもりです。
#include <stdio.h>
#include <stdint.h>
uint32_t fnv_1_hash_32(char *s)
{
unsigned int hash=2166136261UL;
while (*s) {
hash*=16777619UL;
hash^=*(s++);
}
return hash;
}＜該当箇所のみ＞
#include "fnv_1.c"
if (i != 0){
if (fnv_1_hash_32(horse_name) - fnv_1_hash_32(horse_name_in) == 0){
fp3 = fopen(fname3, "a");
fprintf(fp3,"%s,%9s\n",horse_name_in,horseID);
fclose(fp3);
b ++;
break;
}
}