今更気が付いたのだが、全部魔法使いの話だった。因みに私はこよみより嘉穂が好き。両手の指で1023まで数えられるというあたりとても好感が持てる。
プログラムを書く上で、メンテナンス性の良い物を作るというのは非常に重要な事である。もしメンテナンス性の悪いプログラムを書けば、修正や改変に多大な労力が掛かる事になる。場合によってはソースコードを全て破棄し、1から書き直さなければいけない。
では、どのようなプログラムがメンテナンス性が良くて、どのようなプログラムがメンテナンス性が悪いのだろうか。
私は、メンテナンス性の良いプログラムは、問題全体を完全に独立した小さな問題に分けて解いているのだと考えている。もし問題を分割していても、それぞれが完全に独立していなければ、1つの問題に変更を加えるはずなのに全体を改変しなければならないという事になりかねない。美しいプログラムというのは、常に全ての処理がモジュール化されている。
結論から言うと、ツリー的な構造をしている。根が問題全体で、末端のノード程小さい問題である。このような構造を持っていれば、ノード同士が互いに干渉し合うような事は全く無い。
この構造は、プログラミング言語に於ける関数,メソッド,マクロの呼び出しに対応している。根に近いノードが呼び出し元で、末端に近いノードが呼び出した関数等である。
何故グローバル変数や static 変数を使うのが良くないのだろうか。参照可能なスコープが広がるという程度の事を理由に挙げる人がいるが、私はそれは違うと考えている。私がグローバル変数を嫌っている理由は、その特性故にツリー構造を無視したプログラムが書けてしまうからである。
なんだか収集が付かなくなってきたので、とりあえずここで切ります。今度続きを書くかも知れません。
データを書き換える操作の途中で、エラーを返し得る(操作に失敗し得る)関数やメソッドを使わない事。これさえ守れれば、操作に失敗した場合にデータは操作を適用する前と同じ物になり、破壊されないはず。
それなのに、なんでそこで malloc 呼ぶんですかと問い詰めたくなるようなコードが Web 上には山ほどある。戻り値をチェックしていないのは論外。
エラーを返す分には構わないが、データを破壊しないでくれ。
何故か diary.stricter.org の更新をはてなアンテナが捕捉してくれないようなのですが、どなたかこの問題を解決できないでしょうか。サーバのログを見る限りでは、
59.106.108.117 - - [27/Mar/2009:15:11:59 +0900] "GET /latest HTTP/1.1" 302 - "-" "Hatena Antenna/0.5 (http://a.hatena.ne.jp/help)" 59.106.108.117 - - [27/Mar/2009:15:11:59 +0900] "GET /2009/03 HTTP/1.1" 206 30989 "-" "Hatena Antenna/0.5 (http://a.hatena.ne.jp/help)"
という感じでちゃんとコンテンツをダウンロード出来ているようなのですが、はてなアンテナを見ると、
Gone The requested resource /latest is no longer available on this server and there is no forwarding address.Please remove all references to this resource.
という、どう見てもエラーメッセージとしか取れないコンテンツを受け取っているというような表示になっています。去年の11月からずっとこの状態だったらしい。
3月23日に友人と秋葉原に行ってきた。Yoko さんが告知されていた通り、RebRank の五月雨がメッセサンオーにて再販されていたので購入。
Linux Cafe で昼食を食べた後、ゲーマーズ本店で enigmatic LIA を購入。なんとこの CD 、既に殆ど売り尽くされた限定品であるが為に Amazon.co.jp にて新品が10万円になっているのだが、何故かゲーマーズに在庫があったので普通に3000円程度で買えてしまった。(ただ、会計の時に店員が後ろの棚を見て取替え用の品は無かったようなので、私が買ったのが最後の1枚だったのかも。)
その後、ヨドバシカメラで環境構築の為に La Fonera+ とか PLC アダプターとか8ポートイーサネットハブを購入。抜け止めタイプのコンセント(タップとかではなく、壁に埋め込まれてるあれ)が欲しかったのだが、ヨドバシカメラの店員に聞いてみたら無いと答えられてしまったので、電気街口側の総武線のガード下の露店にて2つ購入。なんでもあるんだなここ……。
私は au の携帯電話を利用している。au では設定により未承諾広告やドメイン偽装のメールを弾くように出来る。
しかし、私にとってはこの機能がとても邪魔になっている。何故かと言うと、自前で用意した転送用メールアドレスに送られてきたメールが、ドメイン偽装として弾かれてしまうからである。
そういう事情がある為、私はこのメールフィルタを利用せず、転送用メールアドレスに強力なスパムフィルタ(と言っても Gmail のフィルタだけど)を付け、携帯電話自体のメールアドレスを晒さないようにする事でスパムを防いでいた。(因みに、転送用メールアドレスを晒したとしてもスパムは全てほぼ確実に弾かれる為、オフ会とかでとても役に立つ)しかしそれが何故か、迷惑メールが直接携帯電話のメールアドレスに来るようになってしまった。
それでふと思い出したのだが、私は TwitterMail というサービスを利用している。これはメールを送るとその中身が Twitter に書き込まれるというサービスで、携帯電話から Twitter に書き込むのにこれを利用している。もしかしたらここからメールアドレスが洩れたのかも知れない。
転送用メールアドレスは受信用だけでなく、こういう信頼性の面で微妙なサービスに対しては送信用の物も用意した方が良いのだな、と気が付いた。
因みに私は、転送用メールアドレスの運用に、独自ドメインと Google Apps を利用している。大量のメールアドレスを作るのに向いているので、こういう用途ではとても役に立つ。
3月21日の TANO*C 9th STRIKE EAST 参加してきた。少し行くのが遅れたのだけど、無事タオルとTシャツと CD 数枚を手に入れた。
kenta-v.ez. さんの gAbbArENbo shoguN がネタとしてはとても印象的だった。あと、とても可愛かった(何)。enigmatic LIA3 に収録された楽曲も何曲か。Saya's Song - REDALiCE Remix は素晴らしいと思う。
ところで、なんでこういう場所のドリンクって恐ろしく高いのだろうか。未成年なのに殆ど酒しか無いから飲める物がかなり限定されるし、コップ一杯分のジンジャーエールで500円って常識的に考えれば相当高い。ただ、それくらいお金を取らないと運営出来ないのだろうとは思う。
明日は TANO*C 9th STRIKE EAST に参加してきます。イベント限定Tシャツが素晴らしい。
あと、会場の近くにバーガーキングがあるらしいので、気が向いたら行きます。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 0x00100000
void mergesort1_(void *base,void *temp,const size_t element_num
,const size_t element_size,int (*compare)(const void *,const void *))
{
size_t partition = element_num>>1,counter_a = 0,counter_b = 0;
if(2 > element_num){
return;
}
mergesort1_(base,temp,partition,element_size,compare);
mergesort1_(base+element_size*partition
,temp,element_num-partition,element_size,compare);
while(counter_a != partition && partition+counter_b != element_num){
if(0 >= compare(base+element_size*counter_a
,base+element_size*(partition+counter_b))){
memcpy(temp+element_size*(counter_a+counter_b)
,base+element_size*counter_a,element_size);
counter_a++;
}
else{
memcpy(temp+element_size*(counter_a+counter_b)
,base+element_size*(partition+counter_b),element_size);
counter_b++;
}
}
memcpy(base+element_size*(counter_a+counter_b)
,base+element_size*counter_a,element_size*(partition-counter_a));
memcpy(base,temp,element_size*(counter_a+counter_b));
}
int mergesort1(void *base,const size_t element_num
,const size_t element_size,int (*compare)(const void *,const void *))
{
void *temp;
if(2 <= element_num){
temp = malloc(element_size*element_num);
if(!temp){
return -1;
}
mergesort1_(base,temp,element_num,element_size,compare);
free(temp);
}
return 0;
}
void mergesort2_(void *base,void *temp,const size_t element_num
,const size_t element_size,int (*compare)(const void *,const void *))
{
size_t partition = element_num>>1,counter_a = 0,counter_b = 0;
if(2 > element_num){
return;
}
mergesort2_(temp,base,partition,element_size,compare);
mergesort2_(temp+element_size*partition,base+element_size*partition
,element_num-partition,element_size,compare);
while(counter_a != partition && partition+counter_b != element_num){
if(0 >= compare(temp+element_size*counter_a
,temp+element_size*(partition+counter_b))){
memcpy(base+element_size*(counter_a+counter_b)
,temp+element_size*counter_a,element_size);
counter_a++;
}
else{
memcpy(base+element_size*(counter_a+counter_b)
,temp+element_size*(partition+counter_b),element_size);
counter_b++;
}
}
memcpy(base+element_size*(counter_a+counter_b)
,temp+element_size*(counter_a == partition?(partition+counter_b)
:counter_a)
,element_size*(element_num-counter_a-counter_b));
}
int mergesort2(void *base,const size_t element_num
,const size_t element_size,int (*compare)(const void *,const void *))
{
void *temp;
if(2 <= element_num){
temp = malloc(element_size*element_num);
if(!temp){
return -1;
}
memcpy(temp,base,element_size*element_num);
mergesort2_(base,temp,element_num,element_size,compare);
free(temp);
}
return 0;
}
int compare_integer(const void *a,const void *b)
{
return *(unsigned int *)a-*(unsigned int *)b;
}
int main(void)
{
unsigned int array[ARRAY_SIZE];
unsigned seed = time(NULL);
size_t counter;
int errcode;
clock_t time;
srand(seed);
counter = 0;
while(counter != ARRAY_SIZE){
array[counter] = rand()%1024;
counter++;
}
time = clock();
mergesort1(array,ARRAY_SIZE,sizeof(unsigned int),compare_integer);
if(errcode < 0){
return -1;
}
printf("mergesort1 : %d\n",clock()-time);
srand(seed);
counter = 0;
while(counter != ARRAY_SIZE){
array[counter] = rand()%1024;
counter++;
}
time = clock();
mergesort2(array,ARRAY_SIZE,sizeof(unsigned int),compare_integer);
if(errcode < 0){
return -1;
}
printf("mergesort2 : %d\n",clock()-time);
return 0;
}
mergesort1 関数がマージソートの愚直な実装、mergesort2 関数がマージソートの高速な実装です。
10回実行して実行時間を出力し平均実行時間を求めたところ、mergesort1 関数で497ms、mergesort2 関数で470msとなりました。
試しに IE8 を入れてみたのだけど、なんでまだ application/xhtml+xml 対応してくれないんですか。まあ IE で Stricter.org を見られないお陰で私は IE ユーザーにサイトの表示が変だとか言われなくて済んでいるのだが……。
表示速度競う前にやる事がまだ残っているのではないだろうか。
友人と3人で秋葉原に行ってきました。とりあえずゲーマーズで CD 2枚購入。
そして昼飯はいつも通りバーガーキングへ。予告通り、ワッパーを「ピクルスとトマト抜きでケチャップ増量」で頼んできました。見た目で明らかにトマトとピクルスは抜かれていました。ケチャップが実際どうなのか良く分からなかったのですが、レシートを見ると……。
と、このように、ケチャップが増やされているというような事が書かれています。
折戸さんが Key らじで絶賛しているバーガーキングでは、美味しいハンバーガーが食べられるだけでなく、このようにゲーム内でのネタも実践できるのですね。
atomic bool __sync_bool_compare_and_swap(type *ptr,type oldval,type newval)
{
if(*ptr == oldval){
*ptr = newval;
return true;
}
return false;
}
atomic type __sync_val_compare_and_swap(type *ptr,type oldval,type newval)
{
type temp = *ptr;
if(*ptr == oldval){
*ptr = newval;
}
return temp;
}一昨日のプログラムの修正版です。__sync_bool_compare_and_swap を使用するようにしてみました。
#include <stdio.h>
#include <pthread.h>
#define compare_and_swap(pointer,old,new) \
__sync_bool_compare_and_swap(pointer,old,new)
void *thread_function(void *global_counter_)
{
unsigned int *global_counter = global_counter_;
unsigned int local_counter = 0,temp;
while(counter != 0x04000000){
do{
temp = *global_counter;
}while(!compare_and_swap(global_counter,temp,temp+1));
local_counter++;
}
return NULL;
}
int main(void)
{
unsigned int global_counter = 0;
pthread_t threads[4];
pthread_create(&threads[0],NULL,thread_function,&global_counter);
pthread_create(&threads[1],NULL,thread_function,&global_counter);
pthread_create(&threads[2],NULL,thread_function,&global_counter);
pthread_create(&threads[3],NULL,thread_function,&global_counter);
pthread_join(threads[0],NULL);
pthread_join(threads[1],NULL);
pthread_join(threads[2],NULL);
pthread_join(threads[3],NULL);
printf("0x%x\n",global_counter);
return 0;
}因みに、以下の様に書き換えると結果が少し小さくなります。
#include <stdio.h>
#include <pthread.h>
#define compare_and_swap(pointer,old,new) \
__sync_bool_compare_and_swap(pointer,old,new)
void *thread_function(void *global_counter_)
{
unsigned int *global_counter = global_counter_;
unsigned int local_counter = 0;
while(counter != 0x04000000){
while(!compare_and_swap(global_counter
,*global_counter,*global_counter+1));
local_counter++;
}
return NULL;
}
int main(void)
{
unsigned int global_counter = 0;
pthread_t threads[4];
pthread_create(&threads[0],NULL,thread_function,&global_counter);
pthread_create(&threads[1],NULL,thread_function,&global_counter);
pthread_create(&threads[2],NULL,thread_function,&global_counter);
pthread_create(&threads[3],NULL,thread_function,&global_counter);
pthread_join(threads[0],NULL);
pthread_join(threads[1],NULL);
pthread_join(threads[2],NULL);
pthread_join(threads[3],NULL);
printf("0x%x\n",global_counter);
return 0;
}恐らく、この書き方では1回のインクリメントで global_counter を2回レジスタにロードしていて、その間に別のスレッドで global_counter が書き換えられてしまっている。アセンブリコードを読んで検証したわけではない。
昨日の続きです。
ドキュメントを読んだ訣でもなく GCC のソースコードを読んだ訣でもなく、かなり中途半端な理解しかしていないので、 GCC 4.3.3 のマニュアル から該当箇所を探して読む事にしました。
5.47 Built-in functions for atomic memory access に該当箇所が含まれている。私はあまり英語が得意ではない為、英語が得意だという方はこんな記事を読まずに原文を参照。
このマニュアルによると、 CAS の機能は以下の2つの組み込み関数で提供されている。
bool __sync_bool_compare_and_swap(type *ptr,type oldval,type newval,...)type __sync_val_compare_and_swap(type *ptr,type oldval,type newval,...)マニュアルには以下のような説明がある。
These builtins perform an atomic compare and swap. That is, if the current value of
*ptrisoldval, then writenewvalinto*ptr.The "bool" version returns true if the comparison is successful and
newvalwas written. The "val" version returns the contents of*ptrbefore the operation.
これを日本語に訳すと、以下のようになる。
これらの組み込み関数は不可分な比較と置換(CAS)を行う。それは、もし *ptr の現在の値が oldval であれば、 newval を *ptr に書き込む。
"bool" 版は、比較が成功してnewvalが書き込まれていれば真を返す。 "val" 版は操作の直前の *ptr の中身を返す。
最初の文はまあ理解していた通りなので全く問題無いとして、次の文で "bool" 版を使えば良かったと思いました。全く理解していなかった。
複数のスレッドで1つの変数を決まった回数インクリメントするようなプログラムを考える。正しく動作すれば、全てのスレッドでインクリメントした分の合計だけ変数の値は増えているはず。インクリメント演算子を使って書けば以下のようになる。
#include <stdio.h>
#include <pthreads.h>
void *thread_function(void *arg_)
{
unsigned int *arg = arg_;
unsigned int counter = 0,temp;
while(counter != 0x04000000){
(*arg)++;
counter++;
}
return NULL;
}
int main(void)
{
unsigned int arg = 0;
pthread_t threads[4];
pthread_create(&threads[0],NULL,thread_function,&arg);
pthread_create(&threads[1],NULL,thread_function,&arg);
pthread_create(&threads[2],NULL,thread_function,&arg);
pthread_create(&threads[3],NULL,thread_function,&arg);
pthread_join(threads[0],NULL);
pthread_join(threads[1],NULL);
pthread_join(threads[2],NULL);
pthread_join(threads[3],NULL);
printf("0x%x\n",arg);
return 0;
}この例では、4つのスレッドで1つの変数を0x04000000回インクリメントしている。結果は0x10000000となるはずである。しかし実行してみるともっと小さい数値になる。なぜだろうか。
そもそも、通常のインクリメント演算というのは、以下のような手順で実現されている。
これが複数スレッドで実行される場合、以下のような手順で実行される場合がある。
このような順序で命令が実行された場合、変数は2回インクリメントされているはずなのに変数は1しか増えないのである。しかし、CAS という命令を使う事でこの問題を解決する事ができる。この命令は、あるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納するという操作をアトミックに実行する。また、この命令は操作が成功したかどうかを返す。この命令で変数を今の値から今の値に1加算した値に置き換える事によって、確実にインクリメントする事が可能となる。実装例を以下に示す。
#include <stdio.h>
#include <pthreads.h>
#define compare_and_swap(pointer,old,new) \
__sync_val_compare_and_swap(pointer,old,new)
void *thread_function(void *arg_)
{
unsigned int *arg = arg_;
unsigned int counter = 0,temp;
while(counter != 0x04000000){
while(1){
temp = *arg;
if(compare_and_swap(arg,temp,temp+1) == temp){
break;
}
}
counter++;
}
return NULL;
}
int main(void)
{
unsigned int arg = 0;
pthread_t threads[4];
pthread_create(&threads[0],NULL,thread_function,&arg);
pthread_create(&threads[1],NULL,thread_function,&arg);
pthread_create(&threads[2],NULL,thread_function,&arg);
pthread_create(&threads[3],NULL,thread_function,&arg);
pthread_join(threads[0],NULL);
pthread_join(threads[1],NULL);
pthread_join(threads[2],NULL);
pthread_join(threads[3],NULL);
printf("0x%x\n",arg);
return 0;
}この例では、 __sync_val_compare_and_swap という CAS を実行する為の GCC 拡張を利用している。これに関しては shinh さんが詳しく書いているので非常に助かりました。第1引数がポインタ、第2引数が現在の値、第3引数が新しい値、戻り値は CAS を実行する直前の時点でのポインタが指す場所の値となる。
そして何をやっているのかと言うと、値のインクリメント1回分を CAS を成功するまで繰り返すループに置き換えている。これによって複数スレッドでデータを正しく扱う事が出来る。
と、自分なりに第2回1000人スピーカーカンファレンスのnyaxtさんの発表(Lock-free Queueについて)を浅く理解して実践してみた。
アカウント名はpi8027。
因みに、 diary.stricter.org で日記を書くことはもう無いとかそんな事は全くありません。併用する事になると思います。
Google AdSense と HTML 妥当性で述べられている通り、 application/xhtml+xml な文書では Google AdSense をそのままでは利用出来ないようなので、自分で JavaScript を書かなければなりません。もし書けたら使います。面倒ですね。
第6回博麗神社例大祭に参加してきた。
正直、2週連続イベントであまりやる気が無く、会場に行くのも遅かったのだが、無事東方星蓮船 ～ Undefined Fantastic Object. 体験版を手に入れた。
あと、るくしあ大陸の同人誌の表紙が物凄く綺麗なのでうっかり全部買ってしまった。
2月28日,3月1日の KEY 10th MEMORIAL FES, に参加してきた。
1日目は行くのが遅く、予想外の人の多さで整理券は手に入らず、入場出来たのは夕方。グッズも OTSU:Blasterhead しか手に入らず、2日目も参加する事に……。
2日目は無事659番の整理券を獲得し、午前中に入場。画集などの欲しかったグッズを全て揃え、会場で配布されていた Visual Style も手に入れた。
展示イベントでは、Key の10年分の年表と共に AIR アナログコレクターズエディション 『鳥の詩／Farewell song』等の非常に希少価値の高いグッズが展示されてたり、多くの原画を見る事が出来た。(リトルバスターズ！原画展で見た原画も幾つか。)
午前中に会場を離れ、秋葉原に寄って折戸さんがKeyらじでお勧めしていたバーガーキングに行きました。ワッパーチーズベーコンを食べたのだが、聞いた通り非常に大きく、食べ難い物でした。バーガーキングではお好み通りに具材の増減を出来るそうなので、次行った時はリトルバスターズ!エクスタシーの二木佳奈多さんと同じように「ピクルスとトマト抜きでケチャップ増量」と頼もうと思います。
符号付き整数型向けのCの実装をしてみた。
static void mergesort_(int *array,const size_t size,int *temp)
{
size_t counter_a = 0,counter_b = 0;
if(size != 1){
mergesort_(array,size>>1,temp);
mergesort_(&array[size>>1],size-(size>>1),temp);
while(counter_a != size>>1 && (size>>1)+counter_b != size){
if(array[counter_a] <= array[(size>>1)+counter_b]){
temp[counter_a+counter_b] = array[counter_a];
counter_a++;
}
else{
temp[counter_a+counter_b] = array[(size>>1)+counter_b];
counter_b++;
}
}
if(counter_a != size>>1){
memcpy(&array[counter_a+counter_b],&array[counter_a]
,sizeof(int)*(size-counter_a-counter_b));
}
memcpy(array,temp,sizeof(int)*(counter_a+counter_b));
}
}
int mergesort(int *array,const size_t size)
{
int *temp = malloc(sizeof(int)*size);
if(!temp){
return -1;
}
mergesort_(array,size,temp);
free(temp);
return 0;
}
マージソートはクイックソートと同様に、非常に高速なソートアルゴリズムとして知られている。クイックソートと違い、安定ソートである為、とある規則でソート済みである配列を別の規則で元の規則を残したままソートする時などに有用である。
また、クイックソートと比べると最悪計算量が少ないが、ランダムな数値で実験するとクイックソートの方が速い場合が多い。
符号付き整数の配列のソートにマージソートを利用してもクイックソートに比べて利点が無い為、このような場合に於いてはクイックソートを使用する方が好ましい。