sort

goshが便利になった件
sort -R
- 戦わずして勝つ
sort at linux
- 潜行準備
- shuf
ctagsはsortするか？
vi vs emacs for tag

goshが便利になった件

全くメインのタイトルと関係ない亊を載せているんで、某からは嫌われていると思うんだけど、許せ。犬も歩けば棒にあたるを期待してるからね。いわゆるびっくり箱。何が出て来るか、読んでみるまでわからないを、あえて期待してるんで。

で、今回はちょいと出遅れたけど、gaucheが新しくなった。

vbox$ gosh -V
Gauche scheme shell, version 0.9.12 [utf-8,pthreads], i386-unknown-openbsd7.1
(version "0.9.12")
  :
vbox$ gosh
gosh$ open-TAB
open-coding-aware-port     open-output-buffered-port
open-input-buffered-port   open-output-fd-port
open-input-fd-port         open-output-file
open-input-file            open-output-string
open-input-string

何が嬉しいって、REPLで補完が效くようになった亊。長年待ち望んでいたので、嬉しいぞ。内部的には、GCが新しくなったという亊で、OpenBSDでは門前払いになるかと思ったら、何とか上記のように動いている。

但し、OpenBSDの持病により、テストでハングアップする。ここには触れないように注意だな。

gmake[2]: Entering directory '/tmp/Gauche-0.9.12/ext/threads'
GAUCHE_TEST_RECORD_FILE="../../test.record" "../../src/gosh" -ftest -I"." -I. "./test.scm" > test.log
Testing threads ...

debianでは、問題なし。FreeBSDでも問題はない。

make[1]: Leaving directory '/tmp/Gauche-0.9.12/src'
Total: 35004 tests, 35004 passed,     0 failed,     0 aborted.

最新のやつを提供してると自慢のArch Linuxには、やっと来た。１月以上の遅れだ。

[sakae@arch tmp]$ pacman -Qi gauche
  :
Build Date      : Thu 04 Aug 2022 09:01:31 PM JST
Install Date    : Fri 05 Aug 2022 03:19:51 PM JST

sort -R

前回、ファイルのシャッフルに直交問題を解いた。もう少し深入りして、どう実現されてるかみておく。それって、ソースを眺める亊だ。こういう用途にはOpenBSDが最適。ソースはいつでも見られるし、綺麗に整理されてるし、もう呼吸をするがごとく自然な亊だ。その点、あのOSは苦労するぞ。これから読むぞと、気合を入れて所在を確認、取寄せ。まるで、スキューバダイビングするみたいに、準備万端整えなきゃいけないからね。以後、特に断りがない限り、ソースの出所はOpenBSDって亊にしとく。なお、manもソースの一部だからね。

vbox$ cp -r /usr/src/usr.bin/sort /tmp
vbox$ cd /tmp/sort/
vbox$ ls
Makefile     coll.c       file.h       radixsort.c  sort.c       vsort.h
bwstring.c   coll.h       mem.c        radixsort.h  sort.h
bwstring.h   file.c       mem.h        sort.1       vsort.c

格納場所で見てもいいんだけど、手を加える可能性があるんで、/tmpにコピーしてる。必要なら、debug用に手軽にコンパイルも出来るしね。

お約束通り、sort.hを閲覧。

/*
 * MD5 context for random hash function
 */
extern MD5_CTX md5_ctx;

もう、ヒントが出てきた。ハッシュにはMD5を使ってるとな。sortは Version 1 AT&T UNIXで現れたそうなので、その時代には、sha256なんて、無かったんだな。現代になっても、昔のまま。まあ、厳密に考える亊はないよって亊なんだろうね。

後は md5_ctx あたりをキーにして、使ってる所を探せばいいんだな。

sort.c

/*
 * Set random seed
 */
static void
set_random_seed(void)
  :
                unsigned char rsd[1024];

                arc4random_buf(rsd, sizeof(rsd));
                MD5Update(&md5_ctx, rsd, sizeof(rsd));

ふむ、ここでイニシャライズしてるのね。種は、–random-sourceで指示がある場合はそれを使うし、指示がなければ、OpenBSDの自慢の種 arc4ramdomを使うとな。

次は、いよいよ本番。coll.c

/*
 * Implements random sort (-R).
 */
static int
randomcoll(struct key_value *kv1, struct key_value *kv2,
    size_t offset __unused)

この関数の中で、核となると思われる関数が呼び出されている。自由に飛び廻りたいので、覚えたばかりの、cscopeとctagsを使って、飛び回る準備をする。

vbox$ cscope-indexer
vbox$ cat cscope.files | xargs ctags
Duplicate entry in file coll.c, line 613: LSCDEF
Second entry ignored
vbox$ vim
:cs add cscope.out

vimでq: と言う便利なコマンドを知った。コマンドヒストリーが出て来て、自由に選んだコマンドを編集して、再度実行出来る。

で、cscopeとかを使って追っていくのは、木を見て森を見ずになっていないか？樹海に埋もれて方向違いの所を見てしまって遭難って亊も考えられる。ここはきちんと、道筋を確認しておく必要があるな。そう、gdbしておけ。

Makefileに下記の一行を追加して、ガイドを雇えばよい。

PROG=   sort
CFLAGS= -g -O0  ## <== add this line
SRCS=   bwstring.c coll.c file.c mem.c radixsort.c sort.c vsort.c

.include <bsd.prog.mk>

そしてコンパイル。後はBPを張って、実行するだけ。ああ、その前に試運転しておいた方がいいかな。

vbox$ cat z.txt
AAA
BBBB
CCCCC
DDDDDD
EEEEEEE
vbox$ sort -c z.txt
vbox$ sort -R z.txt
CCCCC
AAA
DDDDDD
EEEEEEE
BBBB

sort -c は、ちゃんとsortされたファイルか確認するコマンドだった。sort(1)して、初めて知ったと言うのは、内緒だ。ついでに -c の検証って亊で、BBBBの後ろに111を追加して実行。

vbox$ sort -c z.txt
sort: z.txt:2: disorder: 111

なる程、2行目の次に番狂わせな111てデータが来ていますよ、て理解するのね。-cの同類で-Cってのもある。こちらは、番狂わせがあると、sortが失敗って亊で$?が1になった。

vbox$ gdb -q ./sort
Reading symbols from ./sort...
(gdb) b randomcoll
Breakpoint 1 at 0x7cdf: file coll.c, line 955.
(gdb) r -R z.txt

Breakpoint 1, randomcoll (kv1=0x499c07f4, kv2=0x49993e34, offset=0)
    at coll.c:955
955             s1 = kv1->k;
(gdb) bt
#0  randomcoll (kv1=0x499c07f4, kv2=0x49993e34, offset=0) at coll.c:955
#1  0x15fc82db in key_coll (ps1=0x499c07f4, ps2=0x49993e34, offset=0)
    at coll.c:471
#2  0x15fc869b in list_coll_offset (ss1=0x4b0f300c, ss2=0x4b0f3010, offset=0)
    at coll.c:549
#3  0x15fc8829 in list_coll (ss1=0x4b0f300c, ss2=0x4b0f3010) at coll.c:577
#4  0x0ae60d6c in _libc_heapsort (vbase=0x4b0f3000, nmemb=5, size=4,
    compar=0x15fc87f0 <list_coll>) at /usr/src/lib/libc/stdlib/heapsort.c:159
#5  0x15fcc438 in sort_list_to_file (list=0xcf7d6e90, outfile=0x15fc1655 "-")
    at file.c:1124
#6  0x15fcf58e in main (argc=0, argv=0xcf7d6f90) at sort.c:1110

これで、地図が入手できた。この地図をファイルに落しておいて、後はvimで開いて、観光開始。好きな関数の所で、tagするなり、cscopeすればよい。cscopeで困った時は、:cs helpだ。

また、gdbを走らせる時、r -R z.txt > /dev/null とかやると結果が闇に葬られるので、余計な奴が出てこなくなる。sort特有な機能として出力先を指定出来るので、r -R -o z.txt z.txtとするのも有りだ。

整列のアルゴリズムって亊で、ヒープソートの説明が出てた。その前に、manと言う手も有るな。

SYNOPSIS
     #include <stdlib.h>

     void
     qsort(void *base, size_t nmemb, size_t size,
         int (*compar)(const void *, const void *));

     int
     heapsort(void *base, size_t nmemb, size_t size,
         int (*compar)(const void *, const void *));

     int
     mergesort(void *base, size_t nmemb, size_t size,
         int (*compar)(const void *, const void *));

最後の引数は、２つのオブジェクトの大小関係を判定する関数。大小によって、正、ゼロ、負を返すという亊になってる。coll.cには、各種の判定関数が集められていた。

static int wstrcoll(struct key_value *kv1, struct key_value *kv2, size_t offset);
static int gnumcoll(struct key_value*, struct key_value *, size_t offset);
static int monthcoll(struct key_value*, struct key_value *, size_t offset);
static int numcoll(struct key_value*, struct key_value *, size_t offset);
static int hnumcoll(struct key_value*, struct key_value *, size_t offset);
static int randomcoll(struct key_value*, struct key_value *, size_t offset);
static int versioncoll(struct key_value*, struct key_value *, size_t offset);

純粋な数値としての判定、英語流の月による判定(MayはAugより前とか)、単位を含んだ数値での判定とか、バリエーションが豊富だ。

最初、ランダムにさせるのにハッシュって、どう実現するのって色々想像したけど、決定打を見出せず。どう実現してるか、調べた次第。

これらの関数に、比較したいオブジェクトを渡し、後は自由に比較して、大小関係を返すだけってのが、最大の味噌なんですな。月の比較なら、MayとAugは、どちらが大きいって判定するだけ。random化なら、"AAA","BBB"の比較を、md5("AAA")とmd5("BBB")の比較に置き換えてしまえばよい。

戦わずして勝つ

ソース解析の極意として、深入りするなってのがあるそうです。今回のsortには、–debugオプションなんてのが用意されてるので、ちょいと使ってみる。

vbox$ sort --debug -R z.txt
Memory to be used for sorting: 1073451008
sort_method=heapsort
; k1=<DDDDDD>, k2=<EEEEEEE>; s1=<DDDDDD>, s2=<EEEEEEE>; cmp1=5
; k1=<DDDDDD>, k2=<BBBB>; s1=<DDDDDD>, s2=<BBBB>; cmp1=1
; k1=<DDDDDD>, k2=<CCCCC>; s1=<DDDDDD>, s2=<CCCCC>; cmp1=2
; k1=<DDDDDD>, k2=<AAA>; s1=<DDDDDD>, s2=<AAA>; cmp1=-43
; k1=<DDDDDD>, k2=<CCCCC>; s1=<DDDDDD>, s2=<CCCCC>; cmp1=2
; k1=<EEEEEEE>, k2=<BBBB>; s1=<EEEEEEE>, s2=<BBBB>; cmp1=-4
; k1=<BBBB>, k2=<CCCCC>; s1=<BBBB>, s2=<CCCCC>; cmp1=1
; k1=<EEEEEEE>, k2=<BBBB>; s1=<EEEEEEE>, s2=<BBBB>; cmp1=-4
; k1=<CCCCC>, k2=<EEEEEEE>; s1=<CCCCC>, s2=<EEEEEEE>; cmp1=3
EEEEEEE
CCCCC
 :

比較に使われている部分と、その結果が出てきましたねぇ。

vbox$ sort --debug  z.txt
Memory to be used for sorting: 1073451008
sort_method=radixsort
AAA
 :

今度は普通に実行。ソート方法が変った。そして、比較級の結果が出てこない。って、比較していないの？それでソートが出来るの？その前に、勝手にソートアルゴリズムを選んでくれるsortアプリって、AIみたいだなって言ったら、大袈裟過ぎるか。次から次に疑問が出てきて、興味は尽きないな。

ちょいと息抜きしてたら、ソースコード探険隊なんていうかっこいいサイトに遭遇した。オイラーの注目は、ナンバーズ予想で学ぶ統計学という所です。

sort at linux

sort -R をやった時、比較関数内でmd5を使っている亊が分った。それって、ものすごい負荷にならないか？とんでもない回数md5されるはずだから。

だから、多分リナでは専用コマンドを用意したんだろうね。そんな仮説を検証してみるって亊で、debian(64Bit)に舞台を移して実験する。

sakae@pen:/tmp$ time sort TAGS > /dev/null
real    0m6.492s
user    0m19.573s
sys     0m0.409s
sakae@pen:/tmp$ time sort -R TAGS > /dev/null
real    1m54.062s
user    5m49.654s
sys     0m0.260s

普通なソートとランダム化の比較。やっぱり、とんでもなく遅い。

sakae@pen:/tmp$ time shuf TAGS > /dev/null
real    0m0.511s
user    0m0.454s
sys     0m0.057s

今度は、専用コマンド。専用っていうぐらいだから、普通のsortに比べても爆速だ。この秘密は？ソースお取寄せだな。

まて、その前にsort –debug してみるか。

sakae@pen:/tmp$ sort --debug -R z.txt
sort: text ordering performed using ‘en_US.UTF-8’ sorting rules
EEEEEEE
_______
 :

OpenBSDと違って、役立たずの情報は、某Windowsのごとしだなあ！

潜行準備

心して、用意をせいだな。

sakae@pen:/tmp$ mkdir t; cd t
sakae@pen:/tmp/t$ apt-file search bin/shuf
bedtools: /usr/bin/shuffleBed
biosquid: /usr/bin/shuffle
coreutils: /usr/bin/shuf
emboss: /usr/bin/shuffleseq
idba-extra: /usr/bin/shuffle_reads

shufがどのパッケージに入っているか調べる。そしてお取寄せ。ね、面倒でしょ。

sakae@pen:/tmp/t$ apt source coreutils
Reading package lists... Done
Need to get 5,584 kB of source archives.
Get:1 http://ftp.riken.jp/Linux/debian/debian bullseye/main coreutils 8.32-4 (dsc) [2,096 B]
  :
dpkg-source: info: applying 99_kfbsd_fstat_patch.patch
dpkg-source: info: applying restore-ls-behavior-8.31.patch

付属品と言うか、デブリ(ごみ)が有るので、専用空間をあらかじめ用意して、その中で作業を実施したのさ。後始末が簡単だからね。で、めざすやつは、dirになってる。

sakae@pen:/tmp/t$ ls -F
coreutils-8.32/                 coreutils_8.32.orig.tar.xz
coreutils_8.32-4.debian.tar.xz  coreutils_8.32.orig.tar.xz.asc
coreutils_8.32-4.dsc

とんでもなく、色々なコマンドが詰っているぞ。sortも一本のソースになってた。一本にまとめられてしまうと、解析が大変、ってか、見るものじゃないぞって暗黙のうちに告げられている。

後は普通に、configure; make すればよい。 CFLAGS= -g -O2 でコンパイルされるんで、普通にgdb出来る。ここは、後々の亊を考えて、-O0にしておくといいな。

shuf

srcの中では窮屈なので、出来たコマンドを/tmpの下にコピーした。そして実行。

sakae@pen:/tmp$ gdb ./shuf
 :
(gdb) b main
Breakpoint 1 at 0x24e0: file src/shuf.c, line 397.
(gdb) r z.txt
Starting program: /tmp/shuf z.txt
 :
(gdb)                 
562         permutation = randperm_new (randint_source, ahead_lines, n_lines);
(gdb)
564       if (outfile && ! freopen (outfile, "w", stdout))
(gdb)
586             i = write_permuted_output_reservoir (n_lines, reservoir, permuta
tion);
(gdb)
587           else if (input_range)
(gdb)
591             i = write_permuted_lines (ahead_lines, line, permutation);
(gdb)
AAA
DDDDDD
 :

このあたりなんですかね。それはそうと、同じ亊をDebian(32Bit)で実行しようとすると、コンパイルが失敗する。もう、32Bit版は、野晒しの刑になってるのか。いえね、ずっと熱いものだから、32Bit機をクーラーのある所で使ってたんで、こんな亊が発覚したのさ。

ctagsはsortするか？

ctagsって、成果物がソートされてる。それって、どんな仕組みになってるの？ sort繋がりで、調べてみる。まずは、文中にsortなんていう語句が表れるかの予備調査。研究を始めるには、背景をしっかり把握しておくに越した亊はありませんから。

ob$ grep sort *.[ch]
ctags.c:NODE    *head;                  /* head of the sorted binary tree */
ctags.h:typedef struct nd_st {                  /* sorting structure */
ctags.h:extern NODE     *head;                  /* head of the sorted binary tree */
tree.c:         warnx("too many entries to sort");

はあ、出てきましたねぇ。次は軽くgdbで核心ぽい所を炙り出し。(nextして出て来るトレース情報を編集した。)

(gdb)
131             for (exit_val = step = 0; step < argc; ++step)
132                     if (!(inf = fopen(argv[step], "r"))) {
137                             curfile = argv[step];
138                             find_entries(argv[step]);
139                             (void)fclose(inf);
132                     if (!(inf = fopen(argv[step], "r"))) {
131             for (exit_val = step = 0; step < argc; ++step)
142             if (head) {
143                     if (xflag)
146                             if (!(outf = fopen(outfile, aflag ? "a" : "w")))
148                             put_entries(head);
149                             (void)fclose(outf);
151             }
(gdb)
152             exit(exit_val);

ヘッダーにある、この情報から、二分(探索)木って分る。子供をsonsと称しているけど、それでいいのか？男女別け隔てなく使える、siblingが宜しい表現と思われるぞ。

typedef struct nd_st {                  /* sorting structure */
        struct nd_st    *left,
                        *right;         /* left and right sons */
        char    *entry,                 /* function or type name */
                *file,                  /* file name */
                *pat;                   /* search pattern */
        int     lno;                    /* for -x option */
        bool    been_warned;            /* set if noticed dup */
        bool    dynfile;                /* set if file will need freed */
} NODE;

NODEへの登録をやってる、 add_node にBPをおいて調べる。

#0  add_node (node=0x451ea640, cur_node=0x451eba60) at tree.c:117
#1  0x18e5eb05 in pfnote (name=0xcf7c6c5e "begtoken", ln=48) at tree.c:88
#2  0x18e5bb28 in hash_entry () at C.c:418
#3  0x18e5ac21 in c_entries () at C.c:130
#4  0x18e5d5b1 in find_entries (file=0xcf7c7048 "ctags.h") at ctags.c:239
#5  0x18e5cc81 in main (argc=1, argv=0xcf7c6f78) at ctags.c:138

核心部分は、

  static void
  add_node(NODE *node, NODE *cur_node)
  {
          int     dif;

B         dif = strcmp(node->entry, cur_node->entry);
          :
          else if (dif < 0)
                  if (cur_node->left)
                          add_node(node, cur_node->left);
                  else
                          cur_node->left = node;
  =>      else if (cur_node->right)
                  add_node(node, cur_node->right);

登録したいやつと、現在のやつを比べる。その正負によって、左側にするか右側にぶら下げるか決定。これで、知らず知らずのうちに、大小関係を満したツリーが出来上がる。

(gdb) p cur_node
$6 = (NODE *) 0x451eba60
(gdb) p *$
$7 = {
  left = 0x0,
  right = 0x451d2720,
  entry = 0x451cd220 "GETC",
  file = 0xcf7c7048 "ctags.h",
  pat = 0x451dcf40 "#define\tGETC(op,exp)\t((c = getc(inf)) op (int)exp)",
  lno = 45,
  been_warned = 0 '\000',
  dynfile = 0 '\000'
}

今度は、そのツリーの出力、 put_entries

  put_entries(NODE *node)
  {

B =>      if (node->left)
                  put_entries(node->left);
     :
           fprintf(outf, "%s\t%s\t%c^%s%c\n",
                 node->entry, node->file, searchar, node->pat, searchar);
          if (node->right)
                  put_entries(node->right);

このように、通りがけ順にツリーをなぞれば、昇順に、すなわちソートされた結果が得られる。このなぞりの再帰が美しいな。lisper好みだ。

vi vs emacs for tag

強引に作ったOpenBSDのカーネル用TAGSを開く。

Visit tags table (default TAGS): /usr/src/sys/
File TAGS is large (139.9 MiB), really open? (y)es or (n)o or (l)iterally
Starting a new list of tags tables

こんな風にmini-bufferに出てきた。警告だ。この時、emacsのメモリー消費状況はどうなってる？ topで監視。

 PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
1757 sakae     20   0   89272  41824  14060 S   0.0   1.7   0:01.27 emacs
1757 sakae     20   0  233620 186084  14120 S   0.0   7.5   0:03.13 emacs

上は、開く前、下は開いた後。単位は4kかな。RESは実メモリー、VIRTは仮想メモリーだな。いずれも大幅に増加してる。

この確認は、debian(64Bit)環境でやってる。今度はviでやりたいんだけど、今の環境はviと言いつつ実体は、vim-tinyだ。この際だから、vim-tinyを消してnviにしよう。nviを入れたら、ちゃんとviと認識して、リンクが貼られた。

こういうの勝手にやってくれるのは便利なようで不便。注意していないと見過してしまうぞ。BSD系みたいに、手動で設定を促してくれる方が良いと思われる。

sakae@pen:/usr/src/sys$ wc TAGS tags
  1485342   4577037 146663406 TAGS
  1469952   7048230 153532442 tags

tagsは、ctags -R して作ったもの。TAGSは、元から入っていたもの。2017年に苦労して作ったものだ。tag jump サイズが違うから、新たに作ったのかな。

 PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
2040 sakae     20   0    8408   4648   4196 S   0.0   0.2   0:00.00 vi
2040 sakae     20   0    8496   5004   4324 S   0.0   0.2   0:00.00 vi

上はtagする前、下はtagした後。メモリーの利用度はほとんど変らない。まあ、viでのtagの利用方法は、mmapしてtagを貼り付け、検索、終ったら廃棄してるんで、幾ら巨大なtagファイルを使っても、メモリー負担は無いんだな。

その点、emacsの方は、しっかりとメモリー展開してるのかな？詳しくは、xref.elにある (xref-find-definitions IDENTIFIER) を見ておけって亊か。まて、その前にTAGSをロードする作業が有るだろう。

TAGSを普通のファイルとして開いてみたら(C-X C-F)ファイルが大きすぎるけど開く？って聞いてきた。という亊は、emacsが持って生れた特製って亊になるな。

ああ、特製と言えば、nviの場合、 nvi -t sys_open みたいに、いきなりtag-nameを指定してファイルを開けるぞ。これ、なかなか便利。

そろそろvim指とemacs指が喧嘩を始めたみたいなので、今後のために整理された資料を用意しておく。 vimとemacsのコマンド比較

This year's Index

Home