Soramichi's blog

Some seek complex solutions to simple problems; it is better to find simple solutions to complex problems

City of Berkeley will use gender neutral languages

According to an article in San Fransisco Chronicle, the city of Berkeley, CA, USA, will "replace gendered language in the city’s municipal code with neutral terms" as "an effort to be more inclusive". The article provides a link to what seems like the official document of the city, where the new municipal code with the edit history begins from page 4.

This is truly a big step for real inclusion, because they do not say anything like that they will include both men and women, but they say they will go "gender neutral". From page 6 of the document, the list of words / phrases to be placed and how to place them are shown, among which there are a couple of outstanding ones:

  • "Fireman", "Firewoman", "Foremen" and "Firewomen" to be replaced by "Firefighter" or "Firefighters"
  • "Male and female" to be replaced by "People of different genders"
  • "Men and women" to be replaced by "People"
  • "The masculine pronoun includes the feminine" to be replaced by "“Words referring to a specific gender may be extended to any other gender"

These policies prove that they really try to be neutral, with non-majority people truly taken into account.

In contrast, in many so-called "equality" or "diversity" acts, they assume that there are only "he" and "she", or "male" and "female", and the association between biological sex and cultural gender is always the same as what they assume.

This is not only wrong and doesn't help minority people, but it also sometimes amplifies existing discrimination. For example, many people believe that adding a women into a men-only team (or the other way around, adding a man into a women-only team) is THE best thing for diversity. However, this relies on an assumption that the added woman (or man) has different way of thinking than the existing members, which stems from another assumption that the existing men (or women) have similar ways of thinking just because they have same biological sex. This is nothing but discrimination!

Another example might be these "women in XX" or "XX for girls" events, where the organizers often associate the biological sex of the participants and cultural biases generated by discrimination. For example they often say like "different way of thinking that women have", or they use pink color which they never use in any of their other events. Although these things might comfortably be accepted by "normal" people who were born as women and are happy to be "female", they are perfect discrimination which never achieve true inclusion (please carefully note, that I'm not saying that supporting discriminated people is bad, but what I'm saying is that these "supports" sometimes amplify discrimination if they are not well-considered).

"Inclusion" should be "we don't care whoever you are or whatever way of thinking / characteristics you have", but should not be "we only accept those who we are comfortable with".

Anyway, the step taken by the city of Berkeley is a very big deal, and I hope other cities, states, and countries will follow it soon.

How to Install Acroread into 64 bit Debian

I like Evince because it works very well in most of the cases and it's very lightweight, but there are some cases where I still need a pdf reader from Adobe, for example when I have to check a pdf with annotations.

Although Adobe does not provide Acroread (a.k.a. Acrobat Reader) for Linux anymore, it somehow still hosts .deb files of old versions and you can install them into modern distributions as well.

Download an old version

$ wget http://ardownload.adobe.com/pub/adobe/reader/unix/9.x/9.5.5/enu/AdbeRdr9.5.5-1_i386linux_enu.deb

Allow 32 bit debs to be installed

In the default configurations, a 64 bit version of Debian does not accept 32 bit deb files. Enable multiarch support to install 32 bit debs.

$ sudo dpkg --add-architecture i386
$ sudo apt-get update
...
$ sudo apt-get upgrade

Install Acroread deb and dependencies

Install the .deb file downloaded from the adobe website. Execute apt-get install -f after that to automatically install dependencies.

$ sudo dpkg -i AdbeRdr9.5.5-1_i386linux_enu.deb
$ sudo apt-get install -f

You can now run it with the acroread command. In some case, it may yield an error due to lack of some libraries. You should install the 32 bit version of the required library by adding :i386 suffix to the package name.

$ acroread
# an error may happen requiring libxml2 (or whatever other libraries)
$ sudo apt-get install libxml2:i386     # don't forget to add ':i386'!
...
$ acroread
# should work

Some tips to simulate cache behaviors using Intel PIN

I've been working on simulating behaviors of CPU caches using Intel PIN, and faced some tricky things. This post gives ideas on what kind of troubles you may face and some hints to solve the issues.

I used Cache Pintools as a basis and expanded it to really read/write cached data from/to memory (the original version only counts the number of cache misses). However, I believe the same things apply for any other cache simulation code.

Always use PIN_Safecopy() to access application memory

PIN can actually access to the application's data using raw pointers. For example, the code below does work.

VOID InterceptMemRead(VOID* addr) {
    *(int*)addr = 0; // overwrite the data pointed by addr by 0
}

VOID Instruction(INS ins, VOID* v) {
  if (INS_IsMemoryRead(ins)) {
    INS_InsertPredicatedCall(
                ins, IPOINT_BEFORE,  (AFUNPTR)InterceptMemRead,
                IARG_MEMORYREAD_EA,
                IARG_END);
    }
  }
}

int main() {
  ...
  INS_AddInstrumentFunction(Instruction, 0);
  ...
}

If you simulate reads/writes of caches from/to memory, you may need to read somewhere outside of legal address ranges. For example, if the target address of a load is 0x123456, the starting address of the cache line that includes the data is 0x123440 (assume that a cache line is 64-byte long).

Using PIN_Safecopy() solves this issue by guaranteeing a safe return:

The function guarantees safe return to the caller even if the source or destination regions are inaccessible (entirely or partially).

Some instructions implicitly touch memory data

There are some instructions that do not have memory operands as their explicit arguments but do write to/read from memory. Namely, push, pop, call and ret. Note that a call writes the return address to the stack, and a ret reads the return address from the stack.

Therefore, you should NOT write code like

if (INS_IsMemoryRead(ins) &&
    INS_OperandIsReg(ins, 0) &&
    INS_OperandIsMemory(ins, 1)) {
  INS_InsertCall(...);
}

as tools/source/ManualExamples/safecopy.cpp does. You should only use INS_IsMemoryRead(ins) to detect memory loads in order not to miss these implicit memory operations.

Do not use system calls when cache simulation is enabled

This was the thing I spent most of my time to debug. The situation was that my program looked reading some data that it had never written. It turned out that the data was written by system calls, which PIN cannot instrument.

PIN cannot instrument inside system calls by nature because how it works is that it adds some code to the binary of the target application when the application is loaded into the memory space. The executable of system calls (more precisely, the executable inside the OS kernel, but not the wrapper functions of system calls inside libc) is loaded at the boot time of the OS, and there is no chance for PIN to instrument it (it neither has a privilege to do so I guess).

Therefore, if a system call is called, you never know which memory page it reads from/writes to. This is not a serious problem if you only count the number of cache misses, assuming that system calls you use do not pressure the cache that much. However, in order to simulate reads/writes of caches from/to memory, even a single bit of data written by a system call will result in data inconsistency.

A possible way of solving this is to define region(s) of interest inside your program, enable tracking only inside the region(s), and never use system calls inside them. This could be done by adding effect-less pieces of binary at the beginning and the end of your regions of interest and let PIN use them as triggers. Be careful that recent gcc is too clever to delete effect-less binary even if you inject it with asm volatile. In my case, adding a special value to a register and then substituting the same value immediately after it survived gcc optimizations even with -O3.

スイス（チューリッヒ）の食費とスーパー事情

チューリッヒに来て2週間経った。今までに分かっているところでチューリッヒの食費事情を日本より安いもの、あまり変わらないもの、日本より高いもの に分けてまとめる。なおスイスでは物価がそもそも高いので、下で「安い」か「同じくらい」と書いていないものは「高い」に入れていなくても基本的に全て高いと思ってもらえばよい。

来るときの紆余曲折については過去記事を参照（次回入国についてはまだ解決できていない）。 sorami-chi.hateblo.jp

日本より安いもの

チーズ

チーズの種類にもよるが、ものによっては日本の数倍安い。例えば COOP というスーパーでは 300 g のカマンベールチーズが 1.85 フラン（200円ちょい）で売っている。 日本でスーパーに行かないのであまり日本のチーズの値段が分からないけど、雪印のカマンベールチーズが Amazon で 100 g で 450 円だったので、それより6倍安い！日本に住んでいるヨーロッパ人が「日本のチーズは高すぎる」と言っているのを聴いたことがあるけど、なるほど確かにという感じである。

パン

パンも日本より少し安い。パンといっても加工されたサンドイッチ等ではなく、でかい塊のまま売っているものである。これも種類によるが、一番安いものだと 400 g の塊で 2 フランくらいで買える。

水

水は安いというより「買わない」が正しい。東京だと水道水が美味しくないのでミネラルウォーターを買っている人が多いと思うが、チューリッヒでは湧水やアルプスの雪解け水？がとても綺麗なので、みんな水道水を飲んでいる。職場や外でも再利用したペットボトルとかタンブラーに水道水を（トイレの水道とかから）補充してみんな飲んでいる。

あまり変わらないもの

ペットボトルのジュース

コーラとかファンタとかスイスオリジナルの Rivella というジュースは、500 ml ペットボトルがスーパーで 1.3～1.5 フランで買える（まとめ買いするともっと安い）。日本のコンビニで 150 円くらいなのでほぼ同じくらいである。

ただし、空港や動物園などの観光地価格では異常に高くなる。日本だと観光地価格でも 150 円が180円とか200円になるくらいだと思うが、空港や動物園ではコーラ 500ml が 3.5 フランとかで売っていたりする。

果物

これも物によるが、（スイス基準で）安いものは日本とあまり変わらないように思う。例えばブドウ 2 房（300gくらい？）が3フランくらいだった。しかしリンゴは小さいのが1個で 3.5 フランとかなので高いものは高いようだ。スイスはワインもたくさん作っているらしいのでブドウは安いのかもしれない。

日本より高いもの

外食

外食は異常に高い。こちらの友人の話によるとスイスでは人件費がめちゃくちゃ高いので「調理してもらう」「サーブしてもらう」ことで高くなっているらしい。だいたい1フラン=100円だと思って日本の2倍くらいの値段である。実際には1フランはほぼイコール1ドルなので100円より高いこともある。

例えばチューリッヒに来た次の日に友人と3人で中心街のレストランで bratwurst というソーセージを食べたのだが、ソーセージ + つけあわせのパスタ + ドリンク で3人で 77 フランだった。1人約 25 フランとして、25フランを2500円だと思ってさらに2で割るとちょうどいいくらいの値段である。

f:id:sorami_chi:20190421031942j:plain

また hauptbahnhof（中央駅）のバーガーキングではワッパーのセット（ワッパー、ポテト、ジュース）が 15.9 フランだった。日本のバーガーキングでは 840 円らしいのでこれも 1 フラン = 100円と思ってさらに2で割ると日本の値段くらいになる。

日本食

日本食は普通の外食よりさらに異常に高い。例えば zurich ramen で検索すると出てくる店では担々麺が 24 フランと書いてある（高すぎて行っていないので味は分からない）。また Izakaya では Edamame が 6 フランとかで出てくるようである。

またスーパーでパック寿司などを売っているがこれもめちゃくちゃ高い。例えばマグロとサーモン2貫ずつ（計4個）と鉄火巻きのパックが 13 フランなどで売っている。スーパーで売っている寿司がどんな味がするか試しに買ってみたいのだが、あまりにも高くてまだ挑戦できていない。

スーパー事情

チューリッヒにはおもに COOP と Migro という二つのスーパーがある。COOP の方がたくさんあって、多いところでは二つの COOP が100メートルくらいしか離れていないこともある。朝7時からあいているので朝食を買うのにもよい。また COOP の方が賞味期限が近いものを安売りしていることが多い気がする。別に夜遅くではなくても 50% オフのソーセージが置いてあったりするので、これで食費を節約できる。

スーパーでは有人レジと無人レジがあって、日本とは違って無人レジをみんなちゃんと使っている。日本のコンビニだと有人レジは並んでいても無人レジは誰も使っていないことがあるが、それとは違うようである。基本的に全てクレジットカードで払うが、アメリカであるような "cash back" （Nドルの買い物に対して N + M ドルをカードで払って、余分の M ドルを現金でもらうことで ATM に行かなくても現金が手に入る）はできないようである。

ドイツ経由スイスへの長期滞在で危うく入国できず詰みかけた話

今月から半年間スイスに長期滞在している。 成田 - チューリッヒの直行便は1日1本だけあるが時間が悪いのか値段が高すぎたのか検索で出てこなかったのでドイツ経由のチケットを取ったら、あやうく入国できず詰むところだったので誰か（自分含む）が同じミスを犯さないようにメモしておく。

前提知識

まず、スイスとドイツはともにシェンゲンエリアに入っている。 シェンゲンエリア内では人や物が自由に移動できることになっていて、エリア内の移動にパスポート検査や関税はない。 さらに、エリア外からエリア内に入る場合は最初に入国する国でパスポート検査をするらしい。 つまり、日本からドイツ経由でスイスに行く場合はドイツで入国審査を受ける。

また、シェンゲンエリアの国に日本パスポート保有者が観光や仕事（現地でお金を稼ぐわけではなく、日本の組織にやとわれた身としていく場合）は 90 日以内はビザなしで滞在できる。逆に 90 日を超える場合はなんらかの許可が必要で、今回はこれにあたる。

なおシェンゲンエリアはEUとは微妙に違う。スイスはEUには入っていないがシェンゲンエリアには入っている。逆にイギリスはEUにはまだ入っているがシェンゲンエリアには元々入っていないので、ユーロスターでドーバー海峡を越えるときにはパスポート検査がある。

持っていたもの

スイスに長期滞在するにあたり、自分が持っていたものは以下。

詰みかけた経緯

羽田でチェックインの際に長期滞在なのでビザを持っているか聞かれ、上記のようにお金をもらって働くわけではないのでチューリッヒの滞在許可しか持ってないがこれ以外に取得できないのでこれでいけるはずと伝えた。 すると、スイスに直行の便なら問題ないが、フランクフルト経由でドイツで入国審査をするのでもしかしたら拒否されるかもしれないとのこと。さらに念のため確認しますといってフランクフルト空港に電話で問い合わせたところ、ダメとの回答を得たらしい。ここで一旦詰んだかと思った。

話をまとめると次のようなことだった。

  • チューリッヒの滞在許可証を持っているので、スイスの入国は問題ない（とフランクフルト空港にも言われたらしい）。従って、直行便かシェンゲンエリアの国以外での乗り継ぎなら問題ない。
  • しかし今回はドイツで入国審査があり、ドイツはシェンゲン国の中でも最近特に入国審査が厳しくこれでははじかれる。
  • シェンゲンエリアの国でもドイツ以外での乗り換えならいける「かも」しれない。

同じシェンゲンエリアの国なのに特に厳しいとかいけるかもとかの違いがなぜ存在するのか分からないが、フランクフルト空港に電話で聞いてダメと言われたなら少なくともドイツ経由でダメなことは間違いなさそうである。

確かにチケットを買うときに直行とかシェンゲンエリア以外で乗り継ぎにしてスイスで入国審査が行われるようにした方がいいなかとは思ったが、スイスに直行便がない国もあるわけだしこれでいけるだろうと思っていた。

助かった経緯

これまでのところ唯一の手はフランクフルト経由をキャンセルして他の便を取り直すことである。実際に羽田でも最初はそれを薦められた。なおANAでは渡航書類のトラブルで旅行ができない場合には全額払い戻しされるらしい。ただ、今回は旅行会社経由でとっているのでANAでは直接手続きができないとのことだった。

キャンセルしようにも旅行会社が土日で電話がかからない、職場も土日で指示をあおげないので途方にくれていたところ、チケット2の存在を思い出した。チケット2は 6/20 に戻ることになっており、90 日以内なのでノービザ扱いで入国できるのでは？と思い聞いたところ、これでいけるとのことだった（ただし 6/20 以降の旅程については別途考慮が必要である）。

実際にフランクフルトのパスポート検査でも 6/20 に戻ると言ったら隣の検査官となにやら会話していて（たぶん90日以内だよね？と確認していたと思われる）、帰りのチケットを見せろと言われたので 6/20 のチューリッヒ発成田行きの eTicket を見せたら無事に入国できた。

今後の展開

ひとまず無事にフランクフルトで入国できスイスに到着できた。法的にもこちらでお金を稼ぐわけではないので 6/20 まではこの状態で全く問題ないはずである。

しかし、90 日以内ノービザシステムは正確には 180 日の間で 90 日以内 なので、次回はこの手は使えない。 チューリッヒに到着後 14 日以内に居住者登録をすることになっていて、こちらの人の話によるとそれをしたあとは自由に入出国できるそうなので、その登録証のようなものが他のシェンゲンエリアの国でも通用すればOKのはずである。 もしダメそうなら他のチケットをいったんキャンセルして取り直すか、次回はウィーン経由で厳しいドイツではないのでいけると祈るしかない。

今回の教訓：シェンゲンエリアの国に長期滞在するときには、直行便かシェンゲンエリアではない国で乗り継ぐことで長期滞在する目的の国で入国審査が行われるようにする。

ちなみに似たような話として、予定を決めない放浪の旅をする人が入国審査で帰りが 90 日以内であることを証明しないとはじかれることを避けるために、片道のチケットを「貸す」サービスがあるらしい。 でもこれはたぶん法的にアウトな気がする・・・ 7 Ways To Provide Proof of Onward Travel - Goats On The Road

List of top conferences named "Symposium"

Some people occasionally judge the quality of international conferences based on their names, saying that "symposium"s are not as proper as "conference"s. I heard that it is the case in some areas of study, but it is definitely not true in research areas I've been involved in and nearby fields.

So, here I list up top international conferences that have "symposium" on their names, so that I can give the list when someone says the same thing in the future. The list only shows real top conferences, but not top-ish ones.

  • Operating Systems / System Software

    • ACM Symposium on Operating Systems Principles (SOSP)
    • USENIX Symposium on Operating Systems Design and Implementation (OSDI)
    • USENIX Symposium on Networked Systems Design and Implementation (NSDI)

  • Parallel Computing

    • ACM Symposium on High-Performance Parallel and Distributed Computing (HPDC)
    • IEEE International Parallel & Distributed Processing Symposium (IPDPS)

  • Computer Architecture

    • IEEE/ACM International Symposium on Microarchitecture (Micro)
    • International Symposium on Computer Architecture (ISCA)
    • IEEE International Symposium on High-Performance Computer Architecture (HPCA)

  • Programming Language

    • ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)

  • Security

    • IEEE Symposium on Security and Privacy (IEEE S&P)
    • USENIX Security Symposium (USENIX Security)

A side note for those who have never heard of "USENIX"; it is an academic organization that hosts international conferences and related events (like ACM and IEEE) especially for the operating systems and system software fields. It is considered as a highly reliable organization and the conferences it hosts are normally very high quality.

Deciding the probability of a coin to show its head from the expected number of heads for N tosses

A couple of weeks ago I hit a small math problem related to probabilistic and I thought it was trival (it took me a few hours to solve, though :p ). However I could not find a good stack exchange post or whatever that answers my problem, so I put it here for the sake of my future reference and possibly some people who happen to hit the same problem.

Note that the "short answer" itself really is short and trival, but the point of this post is the last section that describes the relationship between the "short" and the "long" answers.

Problem Definition

Let the probability that a coin shows its head in a coin toss be x (0 < x < 1) and the expected number of heads after N tosses be M, compute x using N and M.

Short Answer

The expected number of heads for one toss is obvisouly x. Because the expected value of the sum of two independent probablistic variables is equal to the sum of the expected value of each probablistic variable (E[X + Y] = E[X] + E[Y]), the expected number of heads for N tosses is Nx.

Therefore, M = Nx and x = \frac{M}{N}.

Long Answer (kind of)

By definition, the expected number of heads M can be expressed using x and N as follows:

{ \displaystyle M = \sum_{n=1}^{N} ( n \times p(n) ) }

where p(n) is the probability that exactly n coins show their heads and defined as:

{ \displaystyle p(n) \\ = C(N,n) \times x^{n}(1-x)^{N-n} \\ = \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} }

Therefore,

{ \displaystyle M = \sum_{n=1}^{N} \Bigl( n \times \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} \Bigr) }

We can compute x from M and N by solving this equation for x..... but how??? (this is an N-th order equation of x!)

What's Behind

Both the short and the long answers say correct stuff, which means one thing:

{ \displaystyle \sum_{n=1}^{N} \Bigl( n \times \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} \Bigr) = Nx }

And below is a proof:

{ \displaystyle \sum_{n=1}^{N} \Bigl( n \times \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} \Bigr) }

{ \displaystyle = Nx \times \sum_{n=1}^{N} \frac{(N-1)!}{(n-1)!(N-n)!} x^{n-1}(1-x)^{N-n} }

{ \displaystyle = Nx \times \sum_{k=0}^{K} \frac{K!}{k!(K-k)!} x^{k}(1-x)^{K-k} }

where n-1 = k and N-1 = K. Note that N-n = (N-1) - (n-1) = K-k. The term after Nx is equal to 1 as shown below:

{ \displaystyle \sum_{k=0}^{K} \frac{K!}{k!(K-k)!} x^{k}(1-x)^{K-k} }

{ \displaystyle = \sum_{k=0}^{K} \Bigl( C(K, k) \times x^{k}(1-x)^{K-k} \Bigr) \\ = (x + (1-x))^{K} \\ = 1 }

Let's Check Numerically

For those who may suspect the proof above, here are Ms calculated by the short and the long answers for N = 100 (there are small differences by numerical errors, but they are pretty much the same).

x M_short M_long
0.0 0.0 0.0
0.04 4.0 3.9999999999999862
0.08 8.0 8.000000000000032
0.12 12.0 11.999999999999998
0.16 16.0 15.99999999999996
0.2 20.0 20.00000000000012
0.24 24.0 23.999999999999993
0.28 28.000000000000004 28.0
0.32 32.0 31.99999999999981
0.36 36.0 35.99999999999999
0.4 40.0 39.99999999999999
0.44 44.0 44.00000000000023
0.48 48.0 47.99999999999998
0.52 52.0 52.0
0.56 56.00000000000001 56.00000000000001
0.6 60.0 59.99999999999997
0.64 64.0 64.0
0.68 68.0 68.0
0.72 72.0 71.99999999999999
0.76 76.0 75.99999999999997
0.8 80.0 80.0
0.84 84.0 84.00000000000001
0.88 88.0 88.00000000000001
0.92 92.0 92.00000000000001
0.96 96.0 96.0

Here is the code used to generate the table above. Note that M_long(x) does not work for a large N due to overflow.

import scipy.special as sp

N = 100

def M_short(x):
    return N * x

def M_long(x):
    ans = 0
    for n in range(1, N+1):
        ans += n * sp.comb(N, n) * pow(x, n) * pow(1 - x, N-n)
    return ans

print("|x|M_short|M_long|")
print("|-|-------|------|")
for i in range(0, 25):
    x = i / 25
    print("|", x, "|", M_short(x), "|" , M_long(x), "|")