2.13.2015

Running Time-consuming Command in Travis CI

Travis CI で時間のかかるコマンドを実行する

 

目的

C++ でコンパイル時計算を多用すると、ビルドだけで 10分以上かかってしまうことも珍しくない。

しかし、Travis CI では 10分間何も出力がないと強制終了となってしまう。

No output has been received in the last 10 minutes,
this potentially indicates a stalled build or something wrong with the build itself.
 
The build has been terminated

 

対応

途方に暮れていたら、なんと公式アカウントから直々にメンションをもらった。

このような目的のために、travis_wait という bash の関数が用意されているらしい。

 

before_script:
  - travis_wait make build

こう書けば、20分間無出力の状態が続いても、Travis CI は待っていてくれる。

しかしそれでも時間が足りないと、やはりタイムアウトとなってしまう。

Still running (20 of 20): make build
 
Timeout (20 minutes) reached. Terminating "make build"
 
The command "travis_wait make build" failed and exited with 1 during .
 
Your build has been stopped.

こんな場合は、以下のように待機時間(分)をパラメータに付け加えればよい。

before_script:
  - travis_wait 60 make build

これで、ビルドのタイムアウトが 60分に延長された。

 

References

 

 

投稿者 mog project 時刻: 0:34 0 コメント
ラベル:

2.12.2015

Scala: Fibonacci Number Calculation with Tail Recursion

Scala: 末尾再帰でフィボナッチ数を求める

 

第４回 Functional Programming in Scala読書会＠渋谷 - connpass でも練習問題として登場したので復習。

再帰なし - O(n)

まずは手続き型っぽい(Scala っぽくない)書き方で書いてみる。

1
2
3
4
5
6
7
8
def fib(n: Int): Int = {
  val a = Array.fill(math.max(2, n + 1))(0)
  a(1) = 1
  for (i <- 2 to n) {
    a(i) = a(i - 1) + a(i - 2)
  }
  a(n)
}
scala> (0 to 10).map(fib)
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

n 番目のフィボナッチ数を求めるために必ずしも全てのフィボナッチ数をメモする必要はない。
直近2つだけを保持すればよい。

1
2
3
4
5
6
7
8
9
10
def fib(n: Int): Int = {
  var a = 0
  var b = 1
  for (i <- 1 to n) {
    val next = a + b
    a = b
    b = next
  }
  a
}

再帰バージョン - O(n)

上記の2個目のアイデアから再帰関数を導くことができる。

1
2
3
4
5
6
7
8
9
def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(n: Int, a: Int, b: Int): Int =
    if (n <= 0)
      a
    else
      loop(n - 1, b, a + b)
  loop(n, 0, 1)
}

再帰バージョン - O(log(n))

行列累乗のテクニックを使って計算量を削減する。これも再帰で書けた。

1
2
3
4
5
6
7
8
9
10
11
def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(n: Int, a: Int, b: Int, c: Int, d: Int, e: Int, f: Int): Int =
    if (n == 0)
      b
    else if ((n & 1) == 1)
      loop(n >> 1, a*d+b*e, b*d+c*e, b*e+c*f, d*d+e*e, d*e+e*f, e*e+f*f)
    else
      loop(n >> 1, a, b, c, d*d+e*e, d*e+e*f, e*e+f*f)
  loop(n, 1, 0, 1, 1, 1, 0)
}
scala> (0 to 10).map(fib)
res20: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

 

公式の正答例は References 参照。

Stream を使ったワンライナーなどは過去のエントリを参照。

 

 

References
投稿者 mog project 時刻: 3:25 0 コメント
ラベル:

2.02.2015

C++: How to Build with clang 3.5 in Travis CI

C++: Travis CI で clang 3.5 を使う

 

gcc には、関数ポインタが constexpr 性を失うという致命的なバグがあり、
現時点の最新バージョン 4.9 でもまだ対応されていない。(5.0 で対応予定のようだ)

メッセージ出力例

src/xxx.hpp:24:29: error: expression 'xxx::yyy::zzz' does not designate a constexpr function

gcc が使えないのであれば、clang を使うより詮方無い。

ところがMac では問題なかったものの、Travis.CI (Ubuntu 12.04) で動作させると別の問題が発生した。

In file included from /usr/local/include/boost/config/select_stdlib_config.hpp:18:
/usr/lib/gcc/x86_64-linux-gnu/4.9/../../../../include/c++/4.9/cstddef:51:11: error:
      no member named 'max_align_t' in the global namespace
  using ::max_align_t;
        ~~^
1 error generated.

gcc 4.9 以降の libstdc++ を clang で使うと max_align_t が見つからないというエラーが出る、という事象のようだ。

libstdc++ がダメなら libc++ か、と思って試してみた(コンパイルオプションに -stdlib=libc++ を追加)が、
これまた別の問題が発生して使い物にならない。

/usr/local/include/boost/config/select_stdlib_config.hpp:18:12: fatal error:
      'cstddef' file not found
# include <cstddef>
          ^
1 error generated.

かといって libstdc++ のバージョンを下げても別のエラーが出るだけである。

In file included from /usr/local/include/boost/smart_ptr/detail/shared_count.hpp:30:
/usr/local/include/boost/smart_ptr/detail/sp_counted_impl.hpp:229:31: error: no
      type named 'allocator_traits' in namespace 'std'
        typedef typename std::allocator_traits&ltA>::template rebind_alloc...
                ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

というわけで、clang のバージョンを上げることにしたいのだが、これもまた一筋縄ではいかない。

.travis.yml にこんな風に書いたがダメ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
env:
  global:
    - LIBSTDC_VERSION=4.9
    - CLANG_VERSION=3.5
 
before_install:
  - sudo add-apt-repository -y ppa:ubuntu-toolchain-r/test
  - wget -O - http://llvm.org/apt/llvm-snapshot.gpg.key | sudo apt-key add -
  - sudo add-apt-repository -y 'deb http://llvm.org/apt/precise/ llvm-toolchain-precise main'
  - sudo apt-get -qq update
 
install:
  - sudo apt-get -qq install build-essential
  - sudo apt-get -qq install libstdc++-${LIBSTDC_VERSION}-dev
  - sudo apt-get -qq install clang-${CLANG_VERSION}
$ if [ "$TRAVIS_OS_NAME" = "linux" ]; then sudo apt-get -qq install clang-${CLANG_VERSION}; fi
E: Package 'clang-3.5' has no installation candidate

もう、どうにもダメかと諦めかけてきた時、偶然流れてきた Travis CI の画面に clang 3.5 の文字が。

マネをしたら、インストールは成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
env:
  global:
    - LIBSTDC_VERSION=4.9
    - CLANG_VERSION=3.5
 
before_install:
  - echo "deb http://llvm.org/apt/precise/ llvm-toolchain-precise main" | sudo tee -a /etc/apt/sources.list
  - echo "deb http://llvm.org/apt/precise/ llvm-toolchain-precise-3.5 main" | sudo tee -a /etc/apt/sources.list
  - echo "deb http://ppa.launchpad.net/ubuntu-toolchain-r/test/ubuntu precise main" | sudo tee -a /etc/apt/sources.list
  - sudo apt-get update -qq
 
install:
  - sudo apt-get -qq install build-essential
  - sudo apt-get -qq --allow-unauthenticated install libstdc++-${LIBSTDC_VERSION}-dev
  - sudo apt-get -qq --allow-unauthenticated install clang-${CLANG_VERSION}
 
script:
  - clang++ --version

しかしまだ、バージョン表示が 3.4 のまま。

$ clang++ --version
clang version 3.4 (tags/RELEASE_34/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix

clang++-3.5 のようにバージョン付きのコマンドを使ってようやく解決。

$ clang++-3.5 --version
Ubuntu clang version 3.5.0-svn217304-1~exp1 (branches/release_35) (based on LLVM 3.5.0)
Target: x86_64-pc-linux-gnu
Thread model: posix

 

ここまで長かった。。。

この周辺、ぐぐっても情報が見つかりにくいのが何ともつらい。

 

 

References
投稿者 mog project 時刻: 0:47 0 コメント
ラベル:
登録: 投稿 (Atom)