2021年のスライド資料だけど、たまたま𝕏に流れているを見かけました。 このスライドでEytzinger Layoutという配列をはじめて知ったのでメモ。 Eytzinger Layout 16世紀のオーストリアの貴族Michaël Eytzingerが考案したことから、この名前がついたそうです。 もともとはヨーロッパの王様の家系図に番号をつけるための方法です。 ある人物の番号が$k$のとき、父親に$2k$、母親に$2k+1$と番号をつけます。 このルールを使うと家系図に登場するすべての人物にユニークな番号をふることができます。 この番号付けのルールをバイナリツリーに応用すると、ツリー構造をポインターを使わずに表現できます。 二分ヒープを配列で表現するときの実装としてよく登場するのを目にします。 こういう名前がついているのは知らなかった。 バイナリサーチとEytzinger Layoutの関係 イマドキのCPUは非常に高速で、CPUの動作速度と比べてメモリーへの読み書きすら遅い、というレベルです。 この速度差を解消すべく、イマドキCPUはコア上にキャッシュと持っています。 読み書きの頻度の多いメモリー領域をキャッシュ上に保存することで、高速な動作を保っています。 さて、バイナリサーチはソート済みの配列から$\log n$オーダーで要素を検索する方法です。 しかし、通常のバイナリサーチはメモリーのアクセスパターンが複雑なため、CPUのキャッシュと非常に相性が悪いです。 そこでEytzinger Layoutの出番です。 Eytzinger Layoutを利用するとよくアクセスされる要素が隣接するようになります。 これによりCPUキャッシュのヒット率をあげようという作戦です。 冒頭のスライドや、以下の記事で詳しく説明されています（図があるとわかりやすいけど、面倒で力尽きた）。 Eytzinger Binary Search キャッシュフレンドリーな二分探索 ー データ構造を再考する Cache-friendly binary search 実装 Goで実装してみました。 shogo82148/go-eytzinger ソート済みの配列からEytzinger Layoutへの変換は、再帰を使うと簡単に実装できます。 （参考: Eytzinger Binary Search） // https://github.com/shogo82148/go-eytzinger/blob/cd9c2f8a9657333f29a6b645cb2587322295ef3a/eytzinger.go#L8-L34 // Eytzinger rearranges the elements of a slice into a cache friendly binary tree // as known as [Eytzinger Layout]. // The slice must be sorted in increasing order.

AWS::LambdaがResponse Streamingに対応しました。 Response Streaming 2023年4月に発表されたAWS Lambdaの新機能です。 AWS Lambda レスポンスストリーミングの紹介 Introducing AWS Lambda response streaming 従来のLambda関数は処理がすべて完了したあとでないと結果を返すことができませんでした。 Response Streamingを利用すると、処理の途中であっても段階的に処理結果を返すことができます。 使い方 通常のLambda関数のなかで使う CODEリファレンスを返すことでResponse Streamingを使うことができます。 sub handle { my ($payload, $context) = @_; return sub { # とりあえずヘッダーだけ返す my $responder = shift; my $writer = $responder->('application/json'); # ...なんか長い処理... # 最終的な結果を返す $writer->write('{"foo": "bar"}'); $writer->close; }; } もちろん処理の途中で$writer->writeを複数回呼んで、途中結果を返すことも可能です。 Function URLsと一緒に使う AWS::Lambda::PSGIを使えばFunction URLsを一緒に使うこともできます。 PSGIのDelayed Response and Streaming Body方式に対応しています。 sub app { return sub { # とりあえずヘッダーだけ返す my $responder = shift; my $writer = $responder->([200, ['Content-Type' => 'application/json']]); # .

Go言語にいよいよ構造化ログ用パッケージlog/slogが追加される、と各所で話題になってますね。 Go 1.21連載始まります＆slogをどう使うべきか しかし、どんなにドキュメントをみても、ロガーを出し入れする関数はありません。そういう使い方を議論する issue もありましたが　現状はハンドラーにそのまま渡しているだけです。 よくよく考えればトレーシングIDなどは、コンテキストに格納されているはずで、ロガーにも属性として持つと2重持ちになってしまいます。出力時だけハンドラ自身がそれを取り出して書き出せば良い、という思想に思えます。 そのためにはハンドラーを自分でつくることになります。 (強調は筆者によるもの) たしかにトレーシングIDを2重に持つのは効率が悪いかもしれない。 そうかもしれないけど・・・でもやっぱり毎回ハンドラーを書くのは面倒・・・もうちょっと汎用的にはならないものか・・・ と結局書いちゃいました。 shogo82148/ctxslog 使い方 slogではログ関数がcontext.Contextを受け取るようになりました。 ここで渡したcontext.Contextはキャンセル処理には使用されず、値の受け渡しのみに使用されます。 このことを利用してctxslog.WithAttrsでコンテキストに値を埋め込むことができます。 ここで埋め込んだ値をctxslog.Newで作成したハンドラーが受け取って、ログに表示します。 import ( "context" "log/slog" ) func main() { // ログに出力するためにロガーをカスタマイズ handler := slog.NewTextHandler(os.Stderr, nil) slog.SetDefault(slog.New(ctxslog.New(handler))) ctx := context.Background() // このコンテキスト内のログすべてに my_context=foo-bar を埋め込む ctx = ctxslog.WithAttrs(ctx, slog.String("my_context", "foo-bar")) slog.InfoContext(ctx, "hello", "count", 42) // ログ出力、ここで `ctx` を渡しているのがポイント slog.InfoContext(ctx, "world") // Output: // time=2023-08-03T18:10:20.424+09:00 level=INFO msg=hello count=42 my_context=foo-bar // time=2023-08-03T18:10:20.424+09:00 level=INFO msg=world my_context=foo-bar } 実装 slog.

AWS::Lambda v0.1.1が利用可能になりました。 今回のリリースでは、以下の 5 つのリージョンを新たに追加しました。 欧州（チューリッヒ）(eu-central-2) 欧州（スペイン）(eu-south-2) アジアパシフィック（ハイデラバード）(ap-south-2) アジアパシフィック（メルボルン）(ap-southeast-4) イスラエル（テルアビブ）(il-central-1) 久しぶりにリージョン一覧を眺めていたら、いっぱい増えていてびっくりしました・・・ 欧州（チューリッヒ）、欧州（スペイン）、アジアパシフィック（ハイデラバード）リージョンは去年の 11 月、 アジアパシフィック（メルボルン）は今年の 1 月にオープンでした。長いこと気が付かず申し訳ない。 イスラエル（テルアビブ）リージョンに関しては、なんと！今日オープンです！ Now Open – AWS Israel (Tel Aviv ) Region もちろん 7 月 2 日にリリースされた Perl 5.38 にも対応済みです。 perl5380delta レイヤー ARN は以下のとおりです。 今回追加した 5 つのリージョンと、中東（アラブ首長国連邦）リージョンに関しては ARM 未対応なので注意してください。 x86_64 architecture arn:aws:lambda:af-south-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-east-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-northeast-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-northeast-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-northeast-3:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-south-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-south-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:1 arn:aws:lambda:ap-southeast-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-southeast-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-southeast-3:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:ap-southeast-4:445285296882:layer:perl-5-38-runtime-al2-x86_64:1 arn:aws:lambda:ca-central-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:eu-central-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:eu-central-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:1 arn:aws:lambda:eu-north-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:eu-south-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:eu-south-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:1 arn:aws:lambda:eu-west-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:eu-west-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:eu-west-3:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:il-central-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:1 arn:aws:lambda:me-central-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:me-south-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:sa-east-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:us-east-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:us-east-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:us-west-1:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arn:aws:lambda:us-west-2:445285296882:layer:perl-5-38-runtime-al2-x86_64:2 arm64 architecture arn:aws:lambda:af-south-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-east-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-northeast-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-northeast-2:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-northeast-3:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-south-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-southeast-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-southeast-2:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ap-southeast-3:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:ca-central-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:eu-central-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:eu-north-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:eu-south-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:eu-west-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:eu-west-2:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:eu-west-3:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:me-south-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:sa-east-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:us-east-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:us-east-2:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:us-west-1:445285296882:layer:perl-5-38-runtime-al2-arm64:2 arn:aws:lambda:us-west-2:445285296882:layer:perl-5-38-runtime-al2-arm64:2 参考 スイスに新しい AWS リージョンがオープン A New AWS Region Opens in Switzerland スペインに新しい AWS リージョンがオープン Now Open–AWS Region in Spain インドに 30 番目の AWS リージョン — アジアパシフィック (ハイデラバード) リージョンをオープンしました Now Open the 30th AWS Region – Asia Pacific (Hyderabad) Region in India 新規開設 – オーストラリアの AWS アジアパシフィック (メルボルン) リージョン Now Open — AWS Asia Pacific (Melbourne) Region in Australia Now Open – AWS Israel (Tel Aviv ) Region perl5380delta

ドラゴンクエストシリーズ第一作目に登場する「ふっかつのじゅもん」っぽいBase64亜種を書いてみました。 shogo82148/base64dq 使い方 簡単に使えるようコマンドラインインターフェイスも用意しました。go installでインストール可能です。 $ go install github.com/shogo82148/base64dq/cmd/base64dq@latest base64dqコマンドが使えるようになります。 Coreutilsのbase64コマンドと同様に使えます。 $ echo 'こんにちは' | base64dq づづきとづづさとづづきわづづきめづづきげうむ・・ $ echo 'づづきとづづさとづづきわづづきめづづきげうむ・・' | base64dq --decode こんにちは ふっかつのじゅもん 「ふっかつのじゅもん」はドラゴンクエストシリーズ第一作目で採用されたゲームのセーブ方式です。 ゲームを中断するときには、再開したときに同じ状態からゲームを始められるよう、ゲームの状態を保存しておく必要があります。 しかしドラクエIが発売されたのは1986年5月。 当時ドラクエIはファミコン向けに発売されたのですが、ファミコンにはフラッシュROMのような贅沢なハードウェアはついていません。 電源を落とすと簡単にデーターは失われてしまいます。 そこでゲームの状態を20文字の「ふっかつのじゅもん」にエンコードし、 再開時には「ふっかつのじゅもん」をプレイヤーに入力してもらう、というセーブ方式が編み出されました。 プレイヤーはゲームを中断するたびに「ふっかつのじゅもん」を書き写す必要がありました。 当時は液晶ディスプレイなどあるはずもなく、一般の家庭にあるのはブラウン管のアナログディスプレイです。 解像度が荒く読み取るのが大変なため、「ふっかつのじゅもん」を間違え散っていったプレイヤーも多くいたと聞いています（筆者はまだ生まれていないのでよく知らない）。 ふっかつのじゅもんとBase64の関係 今では有志による解読も進みふっかつのじゅもんのジェネレーターも開発されています。 DQ1 復活の呪文解析日記によると、「ふっかつのじゅもん」は64種類のひらがなで構成されているそうです。 64。実に切りのいい数字です。 1文字で6ビットの情報を表し、合計で120ビットのセーブデータを表現しています。 このエンコード方法はBase64とまったく同じですね！ 「ふっかつのじゅもん」は、64種類のASCII文字の代わりに、64種類のひらがなを使ったBase64の亜種、と考えることができます。 ちなみにBase64がRFCに登場したのは1987年4月のRFC 989だそうです。 当時はBase64という言葉すらなく、printable encodingと呼ばれていたようです。 ドラクエIが発売されたのは1986年5月なので、Base64が一般に広まる前に「ふっかつのじゅもん」は世に公開されたわけですね。 すごい！ もちろん規格化されていないだけで「64種類の文字で情報をエンコードする」というアイディア自体はもっと昔からあったのでしょう。 でも似たようなものがゲームに使われていたのはおもしろいですね。 base64dq そういうわけで「ふっかつのじゅもん」の影響を受けて作ったのが shogo82148/base64dq です。 64種類のASCII文字の代わりに、以下の64種類のひらがなを使います。 あいうえお かきくけこ さしすせそ たちつてと なにぬねの はひふへほ まみむめも やゆよ らりるれろ わ がぎぐげご ざじずぜぞ だぢづでど ばびぶべぼ ・（パディング） 「ふっかつのじゅもん」にはパディングはないので、適当に「・」を選びました。

GitHubのプロジェクトを見に行くと、サイドバーに「Used by（数字）」と書かれたセクションがあります。 これの設定方法を知ったのでメモ。 TL;DR レポジトリのナビゲーションバーから「Setting」をクリックし設定画面を開きます サイドバーから「Code security and analysis」を選択します 「Used by counter」という項目で、たくさん使ってもらっていそうなパッケージを選択します 背景 GitHub Actions上でFuzzingを実行するアクションを書いたでshogo82148/actions-go-fuzzというGitHub Actionを作りました。 このために作ったレポジトリの概要を眺めていると、いつの間にか「Used by 3」という表示が増えてました。 これ自体はおかしなことではありません。お試しで自分が過去に作ったレポジトリにshogo82148/actions-go-fuzzを導入したので、依存しているレポジトリは存在します。 ずっと不思議だったのは、自分の作った他のGitHub Actionにはこの表示がないこと。 たとえば「actions-setup-perl」でGitHubを検索すると、それなりに使用例が出てきます。 しかし、shogo82148/actions-setup-perlには（この文章を書く前の時点では）「Used by（数字）」のセクションはありませんでした。 原因 ただの趣味でやっているので別に利用者がいなくたって構わないんですが、 やっぱり利用者がいるとモチベーションが変わってくるじゃないですか。 そういうわけで、表示方法を探したところ公式ドキュメントにたどり着きました。 Changing the “Used by” package ドキュメントによると、ひとつのレポジトリで複数のパッケージを提供していると、 このようなことが起こるそうです。 shogo82148/actions-setup-perlの場合、GitHubの依存解析によって「JavaScriptのパッケージ」「GitHub Actionのパッケージ」の2つが検出されました。 shogo82148/actions-setup-perlはTypeScriptで実装されているので「JavaScriptのパッケージ」として認識されるのは仕方のないことです。 しかし、利用者はみんなGitHub Actionとして利用するので、実際に「JavaScriptのパッケージ」として利用する人はいません。 というかそういう使い方は想定していないので、使われていないのは正しい。 利用者がいないので、「Used by（数字）」の表示がなかったんですね。 ドキュメントに記載されている通り、「Used by counter」の設定を変更すれば無事表示されます。 shogo82148/actions-setup-perlも「GitHub Actionのパッケージ」としてカウントされるよう設定を変更したので、 この記事を書いている時点では利用者数が表示されるようになりました。 まとめ GitHubのレポジトリで利用者数が表示されるアレは「Used by counter」という名前らしい 設定の「Code security and analysis」から変更できるよ 個人的に「Code security and analysis」から変更できるというのは盲点でした。 「security」の文字だけ見て「セキュリティー関連の設定かー」と思っていたんですが、 なるほど「Code analysis（コード分析）」の設定も含まれているんですね。 レポジトリの設定多すぎて覚えきれないよ・・・。 参考 Changing the “Used by” package GitHub Actions上でFuzzingを実行するアクションを書いた shogo82148/actions-setup-perl

Go 1.18からGo Fuzzingの機能が追加されました。 僕もいくつかのパッケージに導入してみたのですが、予期していなかったテストパターンを見つけられて役にやっている気がします。 Fuzzテストが増えてきたので、毎回手元でFuzzテストを実行するのも大変になってきました。 簡単にFuzzテストを実行する環境を作れないかと、GitHub Actions上でFuzzテストを実行するActionを書いてみました。 shogo82148/actions-go-fuzz 使い方 Fuzzingのチュートリアルのコードで試してみましょう。 テスト対象の関数を書く main.go に文字列を反転させるコードを書きます。 // main.go package main func Reverse(s string) string { b := []byte(s) for i, j := 0, len(b)-1; i < len(b)/2; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } return string(b) } チュートリアルを進めていくとわかるのですが、このコードは「マルチバイト文字を正しく処理できない」というバグがあります。 このバグをFuzzingを使って見つけてもらいましょう。 Fuzzテストを書く Reverseを2回実行すると同じ文字列に戻るはずです。 このことを確認するテストを書きます。 さらに、入力がUTF-8としてValidであるなら、出力もValidであって欲しいです。 これもテストで確認します。 package main func FuzzReverse(f *testing.F) { testcases := []string{"Hello, world", " ", "!12345"} for _, tc := range testcases { f.

GitHub Actionsの利用量をまとめるではGitHub Actionsの使用量をGoogle Spreadsheetにまとめるスクリプトを書きました。 このときは動作確認ができればよかったので、自分のGoogleアカウントで認証して書き込みを行いました。 しかし、このスクリプトを定期的に実行するのも面倒です。 そこでGitHub Actionsのスケジュール実行機能を使い、毎日使用量を記録する設定を行いました。 イマドキAPIキーを使うのはリスクが高いので、Google CloudのWorkload Identity連携を使ってアクセスします。 Workload Identity 連携の構成 GitHub Actions からのキーなしの認証の有効化を参考にGoogle Cloud側の設定を行います。 設定内容をバージョン管理したいので、設定にはTerraformを使用します。 意外と作成するリソースが多くて大変なので、GitHub OIDC Terraform ModuleとProject API Activation Terraform Moduleを利用してみましょう。 provider "google" { batching { enable_batching = false } } # Google Cloudのプロジェクト resource "google_project" "my_project" { name = "my-project" project_id = "my-project" } # サービスアカウント resource "google_service_account" "github_actions" { project = google_project.my_project.id account_id = "github-actions" } # サービスAPIの有効化設定 module "project_services" { source = "terraform-google-modules/project-factory/google//modules/project_services" version = "14.

dependabot の更新グループ化（Grouped version updates）機能がパブリックベータになりました。 Grouped version updates for Dependabot public beta AWS SDK for Go v2の更新設定をしてみたのでメモ。 設定内容 グループ化したい依存をgroupsに設定します。 AWS SDK for Go v2関連のバージョンアップを、aws-sdkという名前でプルリクエストを出すよう設定しました。 updates: - package-ecosystem: gomod directory: "/" schedule: interval: daily groups: # AWS SDK for Go v2 関連のバージョンアップをまとめる aws-sdk: patterns: - github.com/aws/aws-sdk-go-v2 # `*` が空文字にマッチするのかよく分からなかったので・・・ - github.com/aws/aws-sdk-go-v2/* AWS SDK for Go v2 アップデートの困りごと AWS ではたくさんのサービスが公開されているので、毎日のようにサービスのアップデートが入り、 それに合わせて AWS SDK の更新が入ります。 dependabot のような自動アップデートの仕組みを入れておくと、本当に毎日のようにプルリクエストが来るのでとても大変です。 しかし、実際使う AWS のサービスなんて、全体に比べればほんの一部です。 ほとんどが自分の使っているサービスとは無関係な更新で、dependabot が送ってくるプルリクエストのほとんどはムダなものです。 AWS SDK for Go は v2 からマルチモジュール構成になり、サービス毎に go.

GitHub Actionsの利用量はsettings/billingから確認できます。 それはいいんですが、問題は今月分しか確認できないこと！ 「先月は〇〇分使ったから上限いくらに設定しておくか〜〜」ということができません。 APIは見つけたので、取得スクリプトを組んでみました。 Get GitHub Actions billing for an organization 集計スクリプト GitHub REST APIをたたいて、結果をGoogle Spreadsheetにまとめます。 GitHub REST APIを叩く部分はGitHub CLIを使えばすぐにできるんですが、 Google Spreadsheetへの書き込みをシェルスクリプトで組むのはちょっと大変です。 今回はGoで書いてみました。 package main import ( "context" "encoding/json" "fmt" "io" "log" "net/http" "os" "time" "google.golang.org/api/sheets/v4" ) func main() { ctx := context.Background() token := os.Getenv("GITHUB_TOKEN") if token == "" { log.Fatal("GITHUB_TOKEN is required") } sheetID := os.Getenv("SHEET_ID") if sheetID == "" { log.Fatal("SHEET_ID is required") } org := os.