KVM TLB Shootdown Preemption メモ

KVM FORUM 2018 で発衚されたTowards a more Scalable KVM Hypervisorに぀いおのメモ。 [PATCH v8 0/4] KVM: X86: Add Paravirt TLB Shootdown ゲストOSはOSレベルの同期機構であるTLB shoot downやRCUの凊理においお、ホストOSのスケゞュヌラの圱響を受ける。ベアメタル環境であればすぐに完了する操䜜であっおも、仮想環境䞊ではその遅延を無芖するこずができなくなる。 TLBTranslatoin Lookaside bufferは仮想メモリアドレスず物理メモリアドレスのマッピングをキャッシュするために䜿われる。あるCPUがそのマッピングを切り替えたずき、その以倖のCPUでTLBをflushしなかればならない。これを TLB shoot down ず呌ぶ。 モダンなOSでは、TLB shoot down はパフォヌマンスクリティカルな箇所ずしお䜍眮づけされ、この凊理によっお遅延が発生しないようチュヌニングされおいる。TLBのflushはすぐさた完了するずいう前提で、IPIInter Processor Interruptで実装されおいる。Remote CPUのTLB flushの完了は busy wait で埅っおいるため、ベアメタル環境ずは盞性が良い。䞀方で、仮想環境ではvCPUが別のゲストに暪取りされたり、実行がブロックされたり、ずいうこずが起きるため、長時間にわたっお busy wait が継続するこずになる。 この問題は、準仮想化TLB shoot down によっお解決できる。準仮想化TLB shoot down では、動䜜しおいないvCPUに察する操䜜を遅延させおおいお、次回そのvCPUが起動するずきに、KVMがTLB flushを担圓する。特にオヌバコミットされた環境で顕著なパフォヌマンス向䞊が芋られる。 ゲストずホストどちらからも参照できるメモリ領域に「あるvCPUが preempt されたかどうか」を瀺すフラグを甚意しおおく。pv_mmu_ops.flush_tlb_others関数は、アクティブなvCPUに察しおはIPI経由でTLB Flushの通知を送り、そうでないvCPUに察しおはKVM_VCPU_FLUSH_TLBフラグを付䞎しおおく。その埌、KVMはKVM_VCPU_FLUSH_TLBフラグが぀いおいるvCPUを起動する際に、INVVPIDを発行する。VM数が増えるに埓っおこのチュヌニングの効果が顕著に珟れる。

July 1, 2020

Civilization VI 初心者のメモ

䞀床Civilization VIを友人ずやった結果、どうやらこのたただず勝おそうにもないので、ちょっず調べおみる。 このゲヌムは遞択の連続なので、仕組みを知らずになあなあで進めおしたうず勝぀のは難しそう。 あくたでも初心者が自分のために曞いおいくメモなのであしからず。 詳しく知りたい方は CIVILIZATION VI wiki を芋おください。 たず、マップオプションから、グリッド、資源アむコン、算出アむコンを衚瀺するよう蚭定しおおく。 郜垂そのものを匷化するリ゜ヌスが、食料ず生産力。食料を増やすこずで人口が増え、生産力を増やすこずで区域・建造物の生産に぀ながる。生産力は、劎働者が鉱山を䜜るこずで埗られる。ゎヌルド・科孊力・文化力は、垂堎商業ハブ区画、図曞通キャンパス区画、円圢闘技堎劇堎広堎区画から埗られる。 序盀の戊闘に有利なアステカ、アメリカ、シュメヌル、ヌビア、ロヌマ、クリヌ、むンカが、初心者に向いおいる。 初期配眮に癖のあるヌビア、゚ゞプト、マリ、ロシア、カナダ、むギリス、むンドネシア、スペむン、ノルりェヌ、オランダ、フェニキア、マオリなどは難しい。たた、宗教メむンな文明や、特殊なプレむングが必芁な文明も向いおない。 ドむツが扱いやすいそうに感じる。固有区域ハンザが単玔に匷い。区域はハンザキャンパス商業ハブくらいで立おおいく。 序盀は、斥候、劎働者、戊士、開拓者で進めおいく。 郜垂が川や湖に隣接しおいるず䜏宅+3なのでよく吟味する。ナニットの䞭ではチャリオットのちの戊車、匓兵のちの野戊砲が匷い。 䞘陵地垯は生産力が匷力なので、そこを狙っお郜垂を䜜る。 郜垂を䜜った埌は、垂民管理で手動で人をどのタむルに配眮するか決めるこずができるので、定期的に芋盎すず良い。 劎働者はむやみに䜿わず、必芁な時たで眠らせおおけばよい。 åž‚æ°‘+2の䜏宅が必芁で、それを䞋回るずペナルティが発生しお、郜垂の成長が劚げられる。 亀易商は匷力なので、䜜れるタむミングなら優先しお䜜る。 倪叀の遺産はピラミッド、アポロン神殿が匷い。 それ以降の時代では、ペトラ、コロッセオ、アルハンブラ宮殿、チチェン・むツァ、 グレヌト・ゞンバブ゚遺跡、玫犁城、ポタラ宮、アルセナヌレ・ディ・ノェネツィア、ビッグベンが匷い。 戊争䞭は勝぀たで兵の増匷をやめない。盞手も兵の生産に集䞭しおいるはずなので。 遠距離攻撃する堎合は、移動力が1以䞊残っおいれば攻撃可胜なので、ヒットアりェむで戊う。 その他 最初期の探玢は重芁 郜垂で圹割分担 郜垂数ペナルティがないので、単玔に倧量に郜垂を䜜るず匷い 郜垂の人口は䜏宅数に制限されるため、食料よりも1人口あたりの生産力重芖 3぀の山岳があれば、キャンパス区画を䜜る 䞘陵ず鉱山で早期生産 遺産は奪う 高玚資源は売り぀ける

June 30, 2020

ABC 171 F - Strivore

提出したコヌド 解説を持っおみるず、どうやらアルファベットを適圓に$K$回挿入したあずの 長さ$N+K$の文字列の䞭で、$S$の各文字の䜍眮が固定されおいるず考えればうたくいくずいうこずだった。 そう考えるず、あずは長さ$N+K$の文字列で$K$文字をどうやっお挿入しおいくかだけを考えれば良い。 入力䟋1を䜿っお考える。 S = “oof” N = len(“oof”) = 3 K = 5 䟋えば、䜍眮1に’o’、䜍眮3に’o’、䜍眮5に’f’をおいおみる。 たた、長さ$N+K$の文字列を先頭から芋たずきに"oof"がはじめお登堎するのがこれらの䜍眮ずいうこずにする条件1。 このずき、䜍眮0には’o’以倖の25皮のアルファベットを挿入できる。 逆に、䜍眮0に’o’を挿入するのは、条件1を満たさないのでダメ。 同様にしお、䜍眮2にも’o’以倖の25皮のアルファベットを挿入できる。 たた、䜍眮4にも’f’以倖の25皮のアルファベットを挿入できる。 䜍眮6ず7に関しおは、特に制玄がないので、26皮のアルファベットを挿入できる。 たずめるず、‘f’の䜍眮$j$が$N-1 
 N+K-1$たで移動したずき、 2぀の’o’が取れる䜍眮の組み合わせは${}_j C _{N-1}$ ずなる。 たた、25皮のアルファベットを挿入する䜍眮は$j - (N-1) $個、 26皮のアルファベットを挿入する䜍眮は$(N+K-1)$個、ずなる。 ぀たり答えは$\sum_{j=N-1}^{N+K-1} {}_j C _{N-1} \cdot 25^{j-(N-1)} \cdot 26^{(N+K-1)-j}$ずなる。

June 25, 2020

ABC 170 F- Pond Skater

提出したコヌド 解いた埌の振り返りが倧事だず思う。 2次元平面䞊で、スタヌト䜍眮からゎヌル䜍眮たでの最短経路を求める。 ただし、平面䞊にはいく぀かブロックがあり、そのセルは通れない。 さらに、䞀回の移動で、同䞀方向に$1 
 K$の任意の個数のセルを進めるこずができる。 頂点は$(y, x, dir)$ずしお、グラフを考えお、ダむクストラ法で最短経路を算出すればよい。 頂点$(y, x, dir)$からの遷移は以䞋の通り。 移動にかかるコストを$K$倍しお考えるずよい。 方向を倉えるずきは、$K$で切り䞊げ。 $cost(y, x, new dir) \leftarrow ((cost(y, x, dir) + K -1) / K) * K$ 同方向に移動。$dir$は䞊䞋巊右の4皮類。$dx$、$dy$は方向ごずの差分。 $cost(y + dy, x + dx, dir) \leftarrow cost(y, x, dir) + 1$ 蚈算量は$O(HW log(HW))$かな。

June 23, 2020

Educational DP Contest

EDPC を党郚埋めた。 雑倚なメモなので、きれいに解法をたずめたものではない。 W - intervals $dp_i$ を、いく぀かのビットに1が立っおいるずき、最も右偎にある1が$i$であるずきの最終スコアずする。 ここで、$dp_i$は$ max_{j=0 
 i-1} dp_j$ ず $i$ 文字目を1にしたずきに埗られるスコアの和で求められる。 $block_i$を右端$r$が$i$であるブロックの集合ずしお、 $dp_i$を蚈算する際に、 $i$文字目を1にしたずきに埗られるスコアずしお $block_i$ を足しこむ。 $block_i$ は $i$ 未満の $dp$ にも圱響するため、遅延セグメントツリヌを䜿っお、 圱響する $dp$ に区間加算を行う。 最終的な答えは $max_{i=0 
 N} dp_i$ ずなる。 はじめお、遅延セグメントツリヌを䜿った。埩習しおおく。 Z - Frog 3 $dp_i$ を足堎 $i$ に到達するたでの最小コストする。 初期倀は $dp_0 = 0$。 たずは玠盎にDPの曎新匏を䜜るず以䞋のようになる。 $$ \begin{aligned} dp_i &= min_{j=0 
 i-1} (dp_j + (h_j - h_i)^2 + C) \\ &= min_{j=0 
 i-1} (dp_j + h_j^2 - 2 h_i h_j + h_i^2 + C) \\ &= min_{j=0 
 i-1} (-2 h_i h_j + dp_j + h_j^2) + h_i^2 + C \\ \end{aligned} $$...

April 26, 2020

Linux Observability with BPF 読曞メモ

Linux Observability with BPFを読んだので、メモしおおく。 今月、Brendan Gregg氏のBPF本も出るので、 それも読みたいな。 BPFを䜿うこずで、カヌネルのむベントをフックしお安党にコヌドを実行できる そのコヌドがシステムを砎壊したりクラッシュさせたりするこずが無いよう、BPF偎で怜蚌しおくれる カヌネルモゞュヌルず異なり、BPFプログラムはカヌネル再コンパむルの必芁がない BPFコヌドが怜蚌された埌、BPFバむトコヌドは機械呜什にJITされる BPFプログラムは、bpf syscall によっおBPF VMぞずロヌドされる 2014幎前半にAlexei Starovoitov氏がeBPFを導入した 過去のBPFでは2぀の32bit registerのみが䜿えたが、eBPFでは10個の64bit registerたで䜿える 2014幎6月にはeBPFはナヌザスペヌスにも拡匵された BPFプログラムタむプトレヌシングずネットワヌキングに倧きく分類できる Socket Filterカヌネルに最初に入ったプログラムタむプ。芳枬目的のみ Kprobekprobe ハンドラずしおBPFプログラムを動かす。関数に入るずきず出る時が、それぞれSEC(kprobe/sys_exec)ずSEC(kretprobe/sys_exec)に察応する Tracepoint事前にカヌネル偎で定矩されたtracepointに察しおBPFプログラムを動かす。/sys/kernel/debug/tracing/eventsで䞀芧を確認できる XDPパケット着信時に、早い段階でBPFプログラムを動かす。 Perfperf eventに察しおBPFプログラムを動かす。perfがデヌタを吐き出す床にBPFプログラムが実行される Cgroup Socketそのcgroup内のすべおのプロセスにアタッチされる Socket OptionFacebookはデヌタセンタヌ内の接続においお、RTOsrecovery time objectivesの制埡に、これを䜿っおいる。 Socket MapBPFでロヌドバランサを実装するずきに䜿う。CilliumやFacebook Katranはこれを䜿っおいる。 BFP Vefirier CVE-2017-16995 のように、過去BFPをバむパスしおカヌネルメモリをバむパスできる脆匱性があった DFSで、そのプログラムが終了するこず、危険なコヌドパスが存圚しないこずを怜蚌する 無限ルヌプを匟くために、すべおのルヌプを犁止しおいる。ルヌプ蚱可に぀いおは、本曞を曞いおいる時点では、ただ提案の段階。 呜什数は4096に制限されおいる bpf syscall の log_*を蚭定すれば、怜蚌結果を確認できる BPFプログラムは tail calls によっお、他のBPFプログラムを呌び出すこずができる 呌び出し時にすべおのコンテキストは倱われるので、䜕らかの方法で情報を共有する必芁がある BPFマップ 盎接bpf syscall でBPFマップを䜜成するこずができる bpf_map_createヘルパ関数を䜿うのが簡単 bpf_map_update_elem のシグネチャは、カヌネル偎bpf/bpf_helpers.hずナヌザ偎tools/lib/bpf/bpf.hで異なるので泚意する ゚ラヌ番号でsteerror(errno)で文字列にするず䟿利 bpf_map_get_next_keyはそのほかのヘルパ関数ず違っお、ナヌザ偎でのみ䜿えるので泚意する array, hash, cgroup storage maps に぀いおは、スピンロックがあるので、䞊行アクセス可胜 array map は芁玠数だけ事前にメモリが確保されお、れロで初期化される。グロヌバルな倉数確保のために䜿う LRUハッシュやLRMLongest Prefix MatchTrie mapもある Linux 4....

December 14, 2019

Kubernetes完党ガむド 読曞メモ

Kubernetes完党ガむド を読んだので、メモを残しおおく。 普段、意識しおいなかったコマンドや仕組みをたずめおおく。 サむズの小さなむメヌゞを䜜りたければ scratch や apline をベヌスにする ENTRYPOINT ず CMD が蚭定されおいるずきは、$ENTRYPOINT $CMD が実行されるようなむメヌゞ マルチステヌゞビルドビルド専甚のコンテナでだけ凊理を行い、成果物を実行専甚コンテナにコピヌするこずが出来る CNCF ではプロゞェクトの成熟床を「Graduated」「Incubating」「Sandbox」の3段階に蚭定しおいる オンプレで構築する堎合はAWS や GCP でのむンスタンスサむズが目安になる Flannelノヌド間でオヌバヌレむネットワヌクを構成する Docker, Inc. が提䟛するkubernetes のプレむグラりンドがある kubernetes のリ゜ヌスは倧きくわけお5皮類 Workloads, Discoverty &LB, Config & Storage, Cluser, Metadata 特に Metadata はクラスタ内で他のリ゜ヌスを操䜜するためのリ゜ヌスHorizontalPodAutoscaler など Deployment/CronJob > ReplicationController/ReplicaSet/DaemonSet/StatefulSet/Job > Pod ずいう階局構造がある kubectl get allほがすべおのリ゜ヌスを䞀芧取埗 Stateful Set0番目の Pod が最初に䜜られ、最埌に削陀される kubeconfig clusters、users、contexts の3皮類を蚭定どれも耇数登録可胜 context や namespace の切り替えが冗長であれば、kubectx や kubens を䜿うず良いかも kube-ps1 を䜿うず cluster ず namespace をプロンプトに出力できる source <(kubectl completion bash)などで zsh/bash の補完機胜を䜿える コンりェむの法則組織図ず、マニフェストの管理方法やマむクロサヌビスのアヌキテクチャが䌌おいる kubectl scaleReplicaSet, ReplicationController, Deployment, StatefulSet, Job, CronJob でスケヌリング kubectl apply --prune実行時にマニフェストから削陀されたリ゜ヌスを怜知しお、自動で削陀 CI/CDでは、単玔にこのコマンドを投げ続けるだけでよい kubectl apply --prune --allクラスタ内に存圚するすべおのマニフェストを読み蟌たせないず、挏れがあったリ゜ヌスが消えおしたい危険 kubectl apply --prune -l system=a基本的にラベルを指定しおおく デバッグ kubectl cpコンテナずロヌカルマシンの間でファむル転送 kubectl port-forwardコンテナずロヌカルマシンの間でポヌト転送 kubectl -vデバッグ出力 サヌビスディスカバリ spec....

November 23, 2019

TP-Link Archer T3U AC1300をLinuxから䜿う

USB接続の無線LAN子機 TP-Link Archer T3U AC1300 を、Thinkpad X1 Carbon 2015Fedora release 29 (Twenty Nine)、linux 5.3.6-100.fc29.x86_64から䜿えるようにしたので手順を残しおおく。 # 公匏HPではドラむバが配垃されおいなかったので rtl88x2bu を䜿った git clone https://github.com/cilynx/rtl88x2bu cd rtl88x2bu/ git rev-parse HEAD # 962cd6b1660d3dae996f0bde545f641372c28e12 VER=$(sed -n 's/\PACKAGE_VERSION="\(.*\)"/\1/p' dkms.conf) sudo rsync -rvhP ./ /usr/src/rtl88x2bu-${VER} # /usr/src/<module_name>_<module_version> に移動させお dkms で管理する sudo dkms add -m rtl88x2bu -v ${VER} sudo dkms build -m rtl88x2bu -v ${VER} sudo dkms install -m rtl88x2bu -v ${VER} sudo dkms status sudo modprobe 88x2bu 2皮類の子機オンボヌドの子機ずTP-Linkの子機を同䞀のネットワヌクに぀なぐず、metric によっお優先順䜍が決たる。 metric の倀を芋るず、オンボヌドの子機偎を優先しおいた倀が小さいので入れ替えた。...

November 9, 2019

2019 越埌湯沢 秋桜ハヌフマラ゜ン

越埌湯沢で開催された秋桜ハヌフマラ゜ンに参加しおきた。 倧䌚自䜓はすごいよかったけど、コヌスの半分あたりから胃の調子が悪くなり、 13kmでリタむダずいう悔しい結果ずなった。 色々反省点があったので、蚘録ずしお残しおおく。 たず、そもそも食事のタむミングが悪かった。9時30分スタヌトで、8時あたりでおにぎりを食べた。 3時間前たでに取るようにしたい。盎前に口にいれるのであれば、れリヌ状のものにしたい。 6.7kmから15kmたで続く䞋り坂で飛ばしすぎた事も圱響しおいるず思う。 お腹が激しく䞊䞋しお気持ち悪くなっおしたった。 スタヌトから6.7kmたでの䞊り坂は走り方に気を぀けおいたが、それ以降に぀いおは、なんずかなるだろうず考えおいなかった。 加えお、腰にポヌチを巻いおいたので、お腹を圧迫しおいたのかもしれない。 塩风を少量持っおいただけなので、ポケットにいれおおけば事足りおいた。 前半の䞊䞋の坂でも貯金を䜜っおおこうず、い぀も以䞊に早めのペヌスで走っおいたので、 バテおしたったんだろうな。 ただ、自分でリタむダを決断できたのは唯䞀よかったこずだった。 以前膝を故障しおしたったずきは、脚を匕きずりながらも、無理しお走っおいお、 沿道で応揎しおくれた方からリタむダを勧められた。 どうも消化䞍良な感じなので、どこかでリベンゞしたい。

September 29, 2019

TCP技術入門 読曞メモ

TCP技術入門を読んだので、 気になったずころを雑倚な感じだがメモしおおく。たず前半郚分。 ネットワヌクたわりの話は聞いたこずはあるが、䜿わずに忘れおしたっおいるこずが倚い。 1ç«  TCP入門 䌝送効率 Ethernetフレヌム 1500 バむト、TCPヘッダが 60 バむト、IPヘッダが20バむトずする アプリケヌションが䜿えるのは 1420 バむト Ethernetヘッダ 14 バむト、FCSFrame Check Sequence4バむトを考慮するず、䌝送効率は$1420/(1500+18) \times 100=93.5 %$ UDP 実際にUDPがやっおいるこずは、転送先ぞデヌタを送るこずず、チェックサムの確認だけ TCPはナニキャストだが、UDPはナニキャストに加えお、マルチキャストずブロヌドキャストにも察応 シヌケンス番号ずタむムスタンプを远加したRTPReal-time Transport Protocolや、それに加えお再送機胜も远加したRUDPReliable user Datagram Protocolもある QUIC はUDPベヌスで、それを䜿ったHTTP/3HTTP-over-QUIC。コネクション確立ずTLS確立を同時に実斜。 TCP ACKのシヌケンス番号は、次に受信したい番号。圓該セグメントが届くたで、同じシヌケンス番号を返送し続ける。 フロヌ制埡受信偎のバッファ溢れを防ぐために、送信デヌタ量を調敎するこず。TCPでは䞀床に送信可胜なサむズをりィンドりず呌ぶ。特に、送信偎がも぀パラメヌタを swnd send windowず衚蚘する。察しお、受信偎はrwndrecieve wndoe。 TCP茻茳制埡 Loss-basedデヌタの消倱から茻茳を刀断 Delay-basedRTTから茻茳を刀断 特定の甚途向けプロトコル RUDPReliable User Datagram ProtocolUDPベヌスで、シヌケンス番号、ACK、再送、フロヌ制埡を加えたもの DCCPDatagram Congestion Control ProtocolUDPにおける茻茳緩和が目的 2ç«  TCP/IPの倉遷 ARPNETなどではネットワヌクが信頌性を担保しおいたが、TCP/IPは各ノヌドがその圹割を担う NagleアルゎリズムTCP/IPの送出パケット数削枛の方法。茻茳制埡アルゎリズムのはしり Windows95OSR2以降にTCP/IPが搭茉されたこずが普及のきっかけになった IEEE 802.11ではMACレむダヌでCSMA/CAを採甚 3ç«  TCPずデヌタ転送 MTUは、むヌサネットは1500バむト、PPPoEでは1492バむト、ATMは9180バむト。ただ最近は任意に蚭定できる MSSMaximum Segment SizeTCPが区切る最倧パケット長さ MTU1500バむト= IPヘッダ20バむト+ TCPヘッダ20~60バむト+ アプリケヌションデヌタMSS以䞋 MSSは、TCPのペむロヌドのみ MTUは、TCPのペむロヌドからTCPヘッダやIPヘッダたで。Ethernetヘッダは含たない ACKAcknoledgement Number確認応答番号。次に送っおほしいシヌケンス番号 コントロヌルフラグ RSTReset the connectionコネクションを匷制切断。䜿われおいないポヌト番号に送るなど、異垞があれば有効になる CWRCongestion Window Reduced茻茳りィンドりの枛少を通知する。ECNずセットで䜿われる ECEECN echo茻茳が発生したら通知 りィンドり制埡䞀床に送信可胜なりィンドりサむズ $swnd$ を調敎 $swnd = min(rwnd, cwnd)$ フロヌ制埡受信偎から送信偎に送信量を通知しお、調敎する。受信偎は、送信偎ぞ受信可胜なバッファ量$rnwd$を通知 茻茳制埡茻茳りィンドり $cwnd$ を調敎 スロヌスタヌト 通信開始時点で、ACKを受け取るたびに $cwnd$ を1セグメントず぀増やしおいく $cwnd = cwnd + mss$ 指数的に $cwnd$ が拡倧 茻茳回避 スロヌスタヌトを行うず、再び再送が起きやすい 再送が起きた時の $cwnd$ の半分 $cwnd/2$を閟倀ずしお、それを越えた時は曎新を緩やかにする $cwnd = cwnd + mss/cwnd$ RTTごずに線圢に増える 高速リカバリヌ 茻茳のたびに、スロヌスタヌト→茻茳回避ずいう挙動をするのは効率が悪い 重耇ACKを契機ずする Recoで採甚 セグメントの消倱 再送タむマヌがタむムアりトした堎合 重耇ACKが䞀定数届いた堎合

September 25, 2019

ABC139-141

ABC #139 D - ModSum $p_1=N, p_2=1, p_3=2, 
 , p_N=N-1$ ずするず、$m_1=0, m_2=1, m_3=2, 
 , m_N=N-1$ ずなる。 なので、答えは$1, 2, 3, 
, N-1$の総和。 ABC #139 E - League $i$ず$j$の詊合を頂点$(i,j)$ず衚す。ただし、$i$ず$j$をひっくり返したものは同䞀芖する。 各頂点は、盎前にすべき詊合数$prev_{(i,j)}$ず、その次に実行可胜な詊合の䞀芧$next_{(i,j)}$をも぀。 そしお、$prev_{(i,j)} = 0$である詊合を芋぀けるたびに、貪欲にその詊合をしおいくよう、シミュレヌションする。 ここで、ある詊合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントするこずに泚意する。 ABC #139 F - Engines あらかじめ各ベクトルを偏角゜ヌトしおおき、 720床分になるようにそのベクトルを぀なげおおく埌々、楜になる。 そうするず、この問題の答えは、連続したベクトルの和であるこずが分かる。 すべおのベクトルに぀いお、以䞋の操䜜を行う。 あるベクトルを始たりずしお、連続したベクトルを足しおいき、長さが最長ずなるものを芋぀ける。 ABC #140 D - Fce Produces Unhappiness たず、幞犏でない人に泚目しお、それをどれだけ枛らせるかに泚目する。 たずえば、$RLLLLRRRRRLLRRLLRRR$から幞犏でない人を抜きだすず、$RL

.RL..RL
R$ずなる。 連続する人は同時に操䜜できるので、$RLRLRLR$ず考えおよい。 そしお、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> 空のように操䜜を繰り返せば良い。 ABC #140 E - Second Sum Nから1たで、順番に芋おいく。 ある芁玠$i$に぀いお芋た時、巊右には$i+1, i+2, 
 , N$の芁玠が眮かれおいるこずになる。 右偎に最倧倀がある堎合ず、巊偎に最倧倀がある堎合、それぞれに぀いお、組み合わせを蚈算しお、 合算すればよい。最倧倀の䜍眮に぀いおは、setのlower_boundで芋぀けた。...

September 20, 2019

ABC136-138

いく぀かABCの問題を解いたけど、ブログに蚘録するのを忘れおいた。 たずめお曞いおおく。 ABC #136 D - Gathering Children 䞀床RLの組に入るず抜け出せない。 偶数距離を移動させお、RLの組にくっ付ける。 ABC #136 E - Max GCD ゜ヌトしおおいお、小さい倀は0に、倧きい倀は答え$d$に近づける。 前ず埌の䞡方向から、环積和を求めおおく。 ABC #136 F - Enclosed Points ある点$x$がふくたれるような矩圢の数は、その䞊䞋巊右の4぀の領域からそれぞれいく぀の点を遞ぶかによっお蚈算できる。領域ごずに含たれる点の数を$A, B, C, D$ずする。 点$x$を含たない堎合は、それぞれの領域から点を取るかどうかで16個に堎合分けしお考える 点$x$を含む堎合は単玔に$ABCD$ 領域ごずの点数の算出には、平面走査を䜿う。たた、事前に座暙は圧瞮しおおく必芁がある。 ABC #137 D - Summer Vacation アルバむトはどれも䞀日で終るためコストは倉わらず、単玔に支払日だけが異なるだけ。 アルバむトを報酬の倧きい順に芋おいっお、できるだけ埌ろの日皋から埋めおいく。 ABC #137 E - Coins Respawn たず、DFSを䜿っお、始点ず終点どちらからも到達可胜な頂点の集合$S$を求める。 あずはコストに$-1$を掛けお、ベルマンフォヌド法を適甚しお、最長経路を求める。 もし、集合$S$内の頂点が、閉路に含たれおいたら、$-1$を返す。 単玔に、ベルマンフォヌド法で閉路を芋぀けるだけでは䞍十分なこずに泚意する。 ABC #137 F - Polynomial Construction フェルマヌの小定理を䜿う。頻出テクニックだず思うので、埩習しおおきたい。 $a = {0,0,
,0}$の$i$番目を1にした$a’ = {0,0,..,1,
,0}$を考える。 そうするず、$a$を䜿った$f$ず、$a’$を䜿った$f’$は以䞋のような関係になる。 これをすべおの1が立っおいる$i$に぀いお、蚈算すればよい。 $$ f’(x) = f(x) + (1- (x-i)^{P-1}) $$...

August 24, 2019

ABC135

今回はE問題がかなり難しかった。F問題より難しく感じた。 Youtubeの解説攟送を聞いお、やっずわかっおきた。 自分甚のメモなので、日本語が雑になっおいる。。 ABC #135 D - Digits Parade dp[i][j]をi桁目たで芋た時に、あたりがjずなる堎合の数ずしお、求めおいく。 ABC #135 E - Golf 事前に、X>=0,Y>=0にしおおく 1) X+Yが奇数 か぀ Kが偶数 -1を返す。 どうやっおも奇数番地にはたどり着けない 2) X+Y>K n=ceil(X+Y/K)ずしお、X+Y ず nK の偶奇が異ればn++ずする。䜙剰 nK-X-Y のために、冗長な経路を䜜る。 ここで、X=0 だず、序盀の移動においお、マンハッタン距離が正しくないので、swap(X,Y)しおおくもちろん出力時には戻す。 +(X,Y) | Y (0,0)+ - t | | t = (nK-X-Y)/2 |-----| X 3)X+Y<K 3-1) X+Yが偶数 n=2ずなる。それ以降の蚈算は、2) ず同じ。 +(X,Y) | Y (0,0)+ - t | | t = (2K-X-Y)/2 |-----| X 3-2) X+Yが奇数 1) の条件よりKも奇数 n=3になる。これは思い぀かない。この堎合のみ、X, Y䞡方向に冗長な経路を取る必芁がある。 p +----+ (X,Y) | Y (0,0)+ - t | | t = K-X |-----|----| X p = (K+X-Y)/2 4) X+Y==K 䞀発で行ける。...

August 3, 2019

ABC EF問題を埋めた続き

前回の続き。Atcoder Beginner Contest #130 ~ #133を解いたので、たずめおおく。 ただただ解説なしでは解けない。。 ABC #130 F - Minimum Bounding Box dp[i][j]をi,j番目が郚分共通文字列ずなるずきの組み合わせ数ずする。 曎新匏もメモ化しおおくず高速に蚈算できる。 ABC #131 F - Must Be Rectangular! (x,y)座暙を2郚グラフずみなす。 グラフに眮き換えお考えるこずでスムヌズに解ける。 ABC #132 F - Small Products N/xが同じ倀になるxを同じグルヌプずみなしお、グルヌプごずに蚈算を進める。 DPを圧瞮しおいくむメヌゞ。 ABC #133 F - Colorful Tree 朚構造の頂点間の距離はLCA最小共通祖先を䜿うこずで求めるこずができる。 実装解説は蟻本にたずたっおいる。 あらかじめク゚リを先読みしおおき、必芁な頂点ず色を抜出しおおく。 DFSし぀぀必芁な倀を埋めおいく。

July 15, 2019

ABC EF問題を埋めた

Atcoder Beginner Contest #116 ~ #129のCD問題をすべお解いた。 たた、#126 ~ #129に぀いおはEF問題が远加されおいるので、すべお解いた。 F問題は、解説PDF、解説Youtube、解説ブログを参考にした。 ABC #126 F - XOR Matching https://atcoder.jp/contests/abc126/submissions/5909511 M=3ずするず、長さ2^(M+1)の数列は、{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}のような芁玠をも぀。 このずき、{<0,1,...,7からKを陀いた昇順の数列> K <7,6,...,0>からKを陀いた降順の数列 K}ずすれば良い。 K以倖の芁玠に぀いお間にはKだけが残るこずになるので、条件を満す Kに぀いお間には <7,6,...,0>からKを陀いた降順の数列 が残る。XORをずるずKになるので条件を満たす。 ABC #127 F - Absolute Minima https://atcoder.jp/contests/abc127/submissions/5930963 䞭倮倀が最小倀ずなる性質を利甚する。䞭倮倀が぀あるずきには、巊偎を採甚する。 䞭倮倀は、小さいほうず倧きいほうをそれぞれ優先床付きキュヌで管理するず䟿利。 解説動画では、同䞀のaを二床入れおキュヌ間で亀換するテクニックを䜿っおいたが、 ナむヌブに䞀床だけ入れる方法でも問題ない。 キュヌが片方に偏らないように、敎理する必芁がある。 曎新ク゚リのずき、aが最小倀を取る区間のなかに含たれおいれば、最小倀の曎新はない。 䞀方、含たれおいなければ、最小倀を取る区間のなかで、最も近い点ずの差分を、最小倀に远加する。 ABC #128 F - Frog Jump https://atcoder.jp/contests/abc128/submissions/5921198 A、Bをそのたた扱うのではなく、C=A-B ず k=䜕床戻りが発生するか ずいう倉数に眮き換えお考える。 Cを固定するず、kが増えるに぀れお、蓮を倚く螏めるようになる。 同䞀の蓮を二床以䞊通るかどうかは、単玔にsetで管理した。 ABC #129 F - Takahashi’s Basics in Education and Learning https://atcoder.jp/contests/abc129/submissions/5945816 難しかった。たず、等差数列の各芁玠が䜕桁なのかによっお、分割する。たずえば、A=3、B=4であれば、3,7ず11,15,19に分けお考える。分割埌は、sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1)を求めるこずになる。 A sum_i=0^(l-1) 10^k^iずB sum_i=0^(l-1) i*10^k^(l-i-1)にわけお、蚈算する。 どちらも挞化匏に倉換しお解くコヌド䞭のf,gに察応。 解説動画を芋るのがおすすめ。

June 16, 2019

Go蚀語による䞊行凊理 読曞メモ

O’REILLYの「Go蚀語による䞊行凊理」を読んので、自分甚にメモを残しおおく。 たた、折角なのでhttps://godoc.org/github.com/bobuhiro11/gostream に、本文のアむデアをもずに䞊行凊理に䟿利な関数矀をたずめた。 競合状態は二぀以䞊の操䜜を正しい順番で実行しなければいけない状況で、プログラムがその順番を保蚌しおいないずきに発生する。 論的な正圓性を目指すべきで、Sleep関数を挟むような方法では解決しない。 デッドロックが起きる必芁条件は、Coffman条件ずしお知られおいる。 筆者の意芋では、ラむブロックはデッドロックよりも発芋がむずかしい。プログラムの倖郚からリ゜ヌス䜿甚率を芳枬しおも怜出できないから。 䞊行凊理に関わる関数には、適切にコメントを぀ける。誰が䞊行凊理を担っおいるか、どのような䞊行凊理のプリミティブに察応しおいるか、誰が同期凊理を担っおいるか、を蚘述する。関数シグネチャでは䞍十分。 䞊行性concurrentはコヌドの性質、䞊列性parallelは実行䞭のプログラムの性質を指す。 Tony hoare「Communicationg Sequence Process」をもずに、Go蚀語の䞊行凊理プリミティブは蚭蚈された。 CSPのほかにも、䌝統的なメモリアクセス同期のコヌドも曞ける。syncパッケヌゞ䞭にたずめられおいる。 ただ、Goプログラミングスタむルでは、高氎準の技術を䜿うのが掚奚されおいる。ある瞬間に、ただ䞀぀のゎルヌチンのみが特定のデヌタを扱うようにすべき。 メモリ共有のかわりに、チャネルによる通信を行うべき。 メモリサむズに応じお、生成可胜なゎルヌチン数を抂算できる。本文䞭の䟋によるず、RAM 8GBで数癟䞇のゎルヌチンを生成できる。 sync.WaitGroupのAddの呌び出しはできる限り監芖察象のゎルヌチンの盎前に曞くのが良い。 デッドロックを避けるために、Mutexを䜿う時はUnlockの呌び出しをdeferの䞭で行う。 RWMutexはMutexよりも高機胜。曞き蟌みのロックを取っおいるものがいなければ、耇数の読み蟌みロックを取埗できる。 バッファ付きチャネルは早すぎる最適化になりやすい。デッドロックが芋えなくなっおしたう。 チャネルの所有暩のスコヌプは小さくする。 Goランタむムはcase文党䜓に察しお疑䌌乱数による䞀様遞択をしおいる。 空select文 select {}は氞遠にブロックする。 情報をたった䞀぀の䞊行プロセスからのみ埗られるこずを確実にする考え方に、拘束がある。 // チャネルぞの曞き蟌みスコヌプは、関数内にレキシカルに拘束される。 func owner() <-chan int { c := make(chan int) go runc() { defer close(c) for i:=0; i<10; i++ { c <- i } } return c } システムにキュヌを導入するのは䟿利だが、早すぎる最適化になっおしたう。キュヌ導入の利点は、ステヌゞの実行時間が枛るこずはなく、ステヌゞのブロック状態の時間が枛るこず。 キュヌでは、リトルの法則でスルヌプットを予枬できる。 contextを関数の第䞀匕数ずしお枡す。よく䜿われるデヌタぞの参照の保管には䜿わない。 ハヌトビヌトは必ずしも必芁ではない。長時間皌働させる堎合には有甚。

April 22, 2019

BGP in the Data Center 読曞メモ

BGP in the Data Centerの前半郚分を読んだので、気になったずころをメモしおおく。CLOSネットワヌクをどのように蚭蚈するか、BGPをどのように運甚するかに぀いお、実践的な内容が曞かれおいた。普段觊っおいない領域なので、勘違いもあるず思う。 1. Introduction to Data Center Networks ロヌカルネットワヌク内のサヌバ間通信をEast-Westトラフィック、ロヌカルネットワヌクず倖郚のネットワヌクの間の通信をNorth-Southトラフィックず呌ぶ。 倧量のケヌブルを管理する必芁があるので、巚倧なネットワヌクの管理者は、それぞれ管理技術を持っおいる。Prescriptive Topology ManagerPTMずいうOSSもある。 同䞀のスむッチで巚倧なネットワヌクを構成しおおくず、故障した堎合でも、単玔に取り替えるだけで埩旧できる。日々の運甚コストに぀いお考えおおくこずが倧事。 CLOSネットワヌクを倖郚ず接続するために、Border PodあるいはBorder Leavesを配眮する。デヌタセンタ内で䜿われおいるルヌティングプロトコルは倖郚ずは分離しおおく。もし、Border PodやBordor Leavesを配眮できない堎合には、すべおのSpinesを倖郚ず接続させるSpineの察称性を保぀ため。 iBGPに比范し、eBGPは理解やデプロむが容易なので、eBGPを採甚するのが良い。歎史的な芳点から、eBGPのほうが完成床の高い実装が倚い。 2. How BGP Has Been Adapted to the Data Center PublicなASNは䜿わないほうが良い。オペレヌタを混乱させおしたったり、䞇が䞀倖郚に挏れた時にBGPハむゞャックになっおしたったりずいった危険性がある。 2バむトのASNを4バむトぞ拡匵するず、およそ95,000,000個のprivate ASNを利甚できる。 単玔にすべおのBGPスピヌカにナニヌクなASNを割り圓おるず、Path Huntingに苊しむこずになる。 あるPrefixぞの到達性をも぀ノヌドがダりンしたずきに、その情報が収束するたでに時間がかかっおしたう。これは、BGPのベストパス遞択の性質に起因する。 真に到達䞍可胜なのか、それずも別の経路でもっお到達できるのかの区別ができない。 密に接続したCLOSトポロゞでは、顕著な問題ずなる。 Path Hunting問題ぞの察応ずしお、以䞋のASN割り圓おモデルがある。ルヌプを怜出できるので、必芁以䞊にメッセヌゞを送らなくお枈む。ただし、Route Summarizationができないこずに泚意する。 すべおのToRはナニヌクなASN LeafはPodごずにナニヌクなASN。Pod内では同䞀のASN Spineは共通のASN OSPFやIS-ISはBest path遞択のメトリクスを1぀だけ。䞀方、BGPではそれが8぀ある。 Wise Lip Lovers Apply oral medication Every Night. Wight, LOCAL PREFERENCE, Locally originated, ASPATH, ORIGIN, MED, eBGP over iBGP, NextHop IGP Cost これら8぀が等しければ、Equal Costず考えられ、Multipath Selectionできる。 ASPATHの比范に぀いおは、長さに加えお芁玠がすべお等しければ、Equal Costずみなされる。 䟋えば、同䞀のPrefixが異なるASから届いた時には、Multi Pathずはならない。 ただし、bestpath -as-path multipath-relaxの蚭定を行うず、ASPATH長のみで内容には觊れずに比范するよう蚭定できる。 タむマ蚭定を倉曎するこずで、CLOSトポロゞにおける収束を早くする必芁がある。ふ぀うはプロバむダ向けを想定しお、安定性を第䞀にデフォルトが蚭定されおいるこずが倚いので、適宜蚭定する。 Advertisement IntervalこのInterval内に含たれるメッセヌゞは統合されお、送り出される。eBGPの堎合、デフォルト30秒だが、0秒に蚭定すれば良い。 Keepalive and hold Timersある呚期でkeepaliveメッセヌゞをピアず亀換する。Hold timeの期間内に、keepaliveを受け取らなかった堎合は、ノヌドダりンず刀定される。ケヌブル障害の怜知のために、BFD(Bidirectional forwarding Detectiion)を導入しおいる堎合でも、BGPプロセス自䜓の゚ラヌ怜出のために、これらのタむマを調敎する必芁がある。おすすめは、3秒ごずのKeepaliveず9秒間のhold timersである。 Connect Timerピアの接続が切れた時、再接続たでの埅ち時間。 3....

March 21, 2019

東京マラ゜ン2019

京郜マラ゜ンから、2週間が経過し、2019.3.3日東京マラ゜ンに参加した。 こちらも初応募で初参加ずなった。 スタヌト前からゎヌル埌たで、雚が振り続いおいた。 特に、スタヌト前に30分以䞊、屋根のない䞭、埅っおいるのが぀らかった。 埌半は、半分くらい歩いおいお、ペヌスはぐだぐだだったが、無事完走できおよかった。 これで、今冬のマラ゜ン倧䌚参加は䞀旊終わりにする。 次の東京マラ゜ン参加がい぀になるかわからないが、来幎も応募しようかな。

March 4, 2019

京郜マラ゜ン2019

2019.2.17日、京郜マラ゜ン2019に参加した。 初応募で初参加ずなった。 各地点での通過時間をメモしおおく。ハヌフ以降の距離でも、長い距離を歩くこずはなかった。 スポヌツ矊矹、れリヌ、塩风など補絊できるものを倚く持っおいったので、スタミナ切れがなかったのだろう。 他のマラ゜ン倧䌚だず7時間制限が倚い気がするが、 京郜マラ゜ンは6時間制限なのでちょっずきびしい。 特に、前半はスタヌトで出遅れたり坂があったりず遅れがちだが、 関門の制限時間がきびしくため、ギリギリで通過しおいた。 2週間埌に、東京マラ゜ンを控えおいる。そっちも頑匵りたい。

February 20, 2019

ABC CD問題を埋めた

Atcoder Beginner Contest #1 ~ #115 の CD 問題をすべお解いた。 C問題は7割くらい、D問題は半分くらい自分の力で解くこずができた。 特殊なアルゎリズムを䜿うこずはあたりなく、ちゃんず考察できれば、解けるんじゃないかなず思う。 圹立ちそうなこずを残しおおく。 Example の最初の1~2個は手で解いおみる。特に、幟䜕の問題は実際に曞いおみる。 耇数のパラメヌタを総圓たりするずきはどちらか䞀方のパラメヌタを固定しお考える。 あらかじめ゜ヌトや环積和を蚈算しおおく。 その他、Youtube の解説動画が充実しおいお、かなり助けになった。

January 18, 2019