[verify] apple siliconでのoj-verifyがスタックの上限にひっかかり失敗する

haruyama480 commented 8 months ago

oj-verifyが失敗していました

環境

% nim --version
Nim Compiler Version 1.6.14 [MacOSX: amd64]
Compiled at 2023-10-17
Copyright (c) 2006-2023 by Andreas Rumpf

active boot switches: -d:release

失敗したverify

% oj-verify run -j 8
(略)
ERROR:onlinejudge_verify.verify:11 tests failed
ERROR:onlinejudge_verify.verify:failed: verify/extra/geometry/aoj_cgl_2_d_distance_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/graph/centroid_decomposition_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/math/pow_of_formal_power_series_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/math/yosupo_factorization_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/aoj_grl_5_a_tree_diameter_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/aoj_grl_5_c_2_heavy_light_decomposition_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/rerooting_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/yosupo_lowest_common_ancestor_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/tree/yosupo_tree_diameter_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/scc_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/twosat_test.nim

chaemon commented 8 months ago

ありがとうございます！その辺は確認しているんですが、パソコンをMacに変えて環境が変わったりして直せずにいます。。。

また、サーバー側のtravisが時間制限（30分くらい？）みたいなのがあって途中で止まってしまったりもしています。もし、直し方をご存知でしたら教えていただけたらと思います。

haruyama480 commented 8 months ago

調査していたらrosetta errorと出たので、Rosettaかnimコンパイラが吐くバイナリが悪いか、がありそうです(根が深そう)

以下調査ログとりあえず代表的にscc_test.nimを実行。large_cycle_00.out が失敗している

``` % oj-verify run verify/scc_test.nim INFO:onlinejudge_verify.config:no config file WARNING:onlinejudge_verify.verify:failed to increase the stack size ::warning ::failed to ulimit INFO:onlinejudge_verify.verify:verify: verify/scc_test.nim WARNING:onlinejudge_verify.languages.special_comments:use "verification-helper:" instead of "verify-helper:": verify/scc_test.nim INFO:onlinejudge_verify.verify:problem: https://judge.yosupo.jp/problem/scc INFO:onlinejudge_verify.languages.nim:$ nim cpp -p:. -o:.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out --nimcache:.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782 -d:release --opt:speed verify/scc_test.nim Hint: used config file '/Users/xxx/.choosenim/toolchains/nim-1.6.14/config/nim.cfg' [Conf] Hint: used config file '/Users/xxx/.choosenim/toolchains/nim-1.6.14/config/config.nims' [Conf] Hint: used config file '/Users/xxx/ghq/github.com/haruyama480/Nim-ACL/config.nims' [Conf] ...........................................................git version 2.37.1 (Apple Git-137.1) INFO:onlinejudge.service.library_checker:$ git -C /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems pull Already up to date. INFO:onlinejudge.service.library_checker:$ /Users/xxx/venv3.10/bin/python3.10 /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/generate.py /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/info.toml --compile-checker 23:37:23 [WARNING] --compile-checker is deprecated. Checker is compiled in default 23:37:23 [INFO] Start scc 23:37:23 [INFO] generate params.h 23:37:23 [INFO] Test cases are already generated 23:37:23 [INFO] The checker is already compiled INFO:onlinejudge_verify.verify:$ oj test -c .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out -d .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test --print-input --tle 60 --judge-command /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker [INFO] online-judge-tools 11.5.1 (+ online-judge-api-client 10.10.1) [INFO] 12 cases found [WARNING] GNU time is not available: gtime [HINT] You can install GNU time with: $ brew install gnu-time [INFO] example_00 [INFO] time: 0.079939 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/example_00.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpm4hnvxhh/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/example_00.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] large_cycle_00 rosetta error: unexpectedly need to EmulateForward on a synchronous exception x86_rip=0x4344920000 arm_pc=0x4345113368 num_insts=4 inst_index=2 x86 instruction bytes: 0x6215344901283465301 0x9604197274868732993 [INFO] time: 0.136231 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/large_cycle_00.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmp46slob4i/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/large_cycle_00.out wrong output format Unexpected end of file - int32 expected judge's output: (empty) [FAILURE] RE: return code -5 input: 377668_377668 327196_304484 304484_289438 289438_337113 337113_303989 303989_90818 90818_126010 126010_44309 44309_356080 356080_288092 288092_218239 218239_144647 144647_167405 167405_303695 303695_13560 13560_156179 156179_339598 339598_248766 248766_331289 331289_202621 ... (377639 lines) ... 322016_266841 266841_118886 118886_37919 37919_130059 130059_322386 322386_102742 102742_222605 222605_156235 156235_52375 52375_327196 output: (empty) expected: 1 377668_181753_53810_160554_209096_195897_367108_218182_49301_372989_202058_19471_134062_174411_369487_202544_311222_67960_67343_140202_350594_376289_227587_234594_95338_24846_9028_370753_26907_343365_308626_372623_167129_69014_110215_46117_169392_16172_134721_77346_268146_261352_361105_283378_262650_251199_306443_228900_79506_1069_251068_189556_26501_313486_334477_213693_264141_269260_147893_297451_274712_215642_271985_266323_199970_345618_41007_59769_305432_64588_313946_48050_8592_340360_215603_51753_139204_248590_207655_147352_260902_245879_368117_293321_50141_174658_226937_7123_12137_290963_149675_191298_102573_321560_331933_175742_226281_71367_249189_148969_366060_240817_85310_240192_270056_206838_36893_114463_178179_177567_198410_97388_278681_134433_89394_188005_308526_94566_132766_28343_93650_177320_290846_253513_100479_304038_61263_223759_139047_373337_213398_194680_226251_90127_31748_13260_152564_107418_352459_112653_126585_96527_175246_194906_191519_227914_232393_65252_314721_59468_124974_161043_222569_49060_287474_7201_98232_295558_328654_55424_147628_300413_206599_29155_245574_99454_368301_275991_62135_145642_372728_84667_125736_231421_305019_368250_319311_354431_4369_87982_315334_62324_15477_293847_211242_246571_25531_311474_32062_357120_276290_371980_345545_5796_372691_8510_14923_312219_35643_210699_26404_37456_307539_272482_246872_369478_218002_158335_207803_231308_953_303383_97997_121295_154633_299807_66656_116020_174856_306848_255719_151046_308478_209935_208104_67562_193064_145338_86161_26628_42381_176771_172441_133525_189760_120986_20360_347396_180264_83685_231644_111479_1527_88856_93289_332013_153555_36730_353105_329037_176292_113747_108339_58572_263297_80743_22692_2749_299990_173943_15647_57876_169242_143314_181926_194722_268582_307949_374587_248124_25363_123911_165470_144776_129391_364733_231782_41274_183228_305596_187361_87289_7749_105703_196589_313983_267151_9718_366648_183754_182820_30763_215507_200989_106132_274269_36525_304640_284623_27710_304540_341278_182922_125678_242658_228557_203332_199561_131928_288048_14054_186563_61852_235545_19520_12928_212111_299592_230729_123195_122366_330987_123928_170912_373768_97090_273132_203521_42047_316213_373900_249868_368955_212501_220480_232196_197817_156061_346819_72756_224_138583_154714_370989_307469_32530_99815_333657_67175_288623_177256_66856_311633_131182_218961_332498_324489_55459_354310_278027_72498_62701_93808_241280_178033_109729_132538_65021_14... (2528885 chars) ...3551_28682_187699_157905_210023_326525_240308_207180_238435_144367_279485_332138_295699_181188_359014_189410_197550_133629_52578_337104_364737_270038_363952_102329_51184_76617_10110_65737_243970_84997_274631_78933_51972_351267_327635_358853_316426_215771_283241_232441_11634_214712_77056_108487_376861_3680_349291_47513_303862_319535_228189_12244_44705_295057_86636_366183_291887_129513_115008_341680_287069_326585_55797_36345_69721_356068_241888_153567_95537_294961_91710_366990_270057_41031_147129_17990_8173_303011_136422_52821_184040_105586_366975_151886_98391_205824_307139_261580_112296_99734_269586_125624_200298_52342_337636_46907_229243_231176_305081_5841_181524_249323_77326_355408_277360_119861_37866_5365_366976_327947_35700_235293_210078_263760_41731_40866_82214_143496_96782_23359_139878_112325_266590_322166_266851_167946_332624_358219_377482_168467_28391_283621_172954_206203_371713_185884_216660_99289_358672_179685_96612_181655_359602_308414_190816_75336_149686_238569_207225_94935_371341_238227_276461_312090_60843_335008_235264_369517_235281_317325_37405_29765_33662_82845_34080_182660_51187_24292_289747_196525_193265_331537_8369_352887_262307_271528_278850_140605_339576_242138_362890_175282_132221_292717_0 [INFO] max_random_00 [INFO] time: 0.677122 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_00.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpan03o6yi/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_00.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] max_random_01 [INFO] time: 0.677982 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_01.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpo6vr2zj1/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_01.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] max_random_02 [INFO] time: 0.684570 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_02.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpxine2r44/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_02.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] max_random_03 [INFO] time: 0.683222 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_03.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpw9wh3010/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_03.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] max_random_04 [INFO] time: 0.707716 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_04.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpbhizjztj/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/max_random_04.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] random_00 [INFO] time: 0.558253 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_00.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpslcwrbkt/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_00.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] random_01 [INFO] time: 0.614418 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_01.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmp257wkcc6/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_01.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] random_02 [INFO] time: 0.114075 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_02.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpe2hbgbgs/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_02.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] random_03 [INFO] time: 0.468222 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_03.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmp9d08a8f4/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_03.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] random_04 [INFO] time: 0.319047 sec [INFO] $ /Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_04.in /private/var/folders/30/zw80dxvd191gs471jg1llzc00000gr/T/tmpnm2j24uh/actual.out /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/random_04.out ok OK judge's output: (empty) [SUCCESS] AC [INFO] slowest: 0.707716 sec (for max_random_04) [FAILURE] test failed: 11 AC / 12 cases Traceback (most recent call last): File "/Users/xxx/venv3.10/lib/python3.10/site-packages/onlinejudge_verify/verify.py", line 112, in verify_file exec_command(command) File "/Users/xxx/venv3.10/lib/python3.10/site-packages/onlinejudge_verify/verify.py", line 42, in exec_command subprocess.check_call(command) File "/opt/homebrew/Cellar/python@3.10/3.10.13/Frameworks/Python.framework/Versions/3.10/lib/python3.10/subprocess.py", line 369, in check_call raise CalledProcessError(retcode, cmd) subprocess.CalledProcessError: Command '['oj', 'test', '-c', '.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out', '-d', '.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test', '--print-input', '--tle', '60', '--judge-command', '/Users/xxx/Library/Caches/online-judge-tools/library-checker-problems/graph/scc/checker']' returned non-zero exit status 1. ::error file=verify/scc_test.nim::failed to verify ERROR:onlinejudge_verify.verify:1 tests failed ERROR:onlinejudge_verify.verify:failed: verify/scc_test.nim ```

rosetta error: unexpectedly need to EmulateForward on a synchronous exception

% .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out < /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/example_00.in   
4
1 5
2 1 4
1 2
2 0 3

% .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out < /Users/xxx/ghq/github.com/haruyama480/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/large_cycle_00.in
rosetta error: unexpectedly need to EmulateForward on a synchronous exception x86_rip=0x4304811968 arm_pc=0x4305005336 num_insts=4 inst_index=2 x86 instruction bytes: 0x6215344901283465301 0x9604197274868732993
zsh: trace trap  .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out <

chaemon commented 8 months ago

Mac使っていますか？

前にUbuntuを使っていた頃は通っていたはずなので環境依存かもしれません。Apple Siliconだとlong doubleが64bitになってしまうみたいな罠とかもあったと思います。

haruyama480 commented 8 months ago

はい、M1 Macです

chaemon commented 8 months ago

やはりそうでしたかーこちらはM2 Macを使っていて同じように前通っていたものが通らなくなって原因もわからない状態でしたね。誤差ジャッジ系が落ちることが多いので、浮動小数を使わないsccとかtwosatとかは通っても良さそうです。

haruyama480 commented 8 months ago

M2もだめなんですね😞

確かにfloat使ってないので浮動小数点は関係ないかもですね

haruyama480 commented 8 months ago

(rosetta周りを疑っていたんですけど、かなり辛そうでした😇)

nimはCPUをx86-64系 (少なくとも非arm)と認識していそう

% nim --version Nim Compiler Version 1.6.14 [MacOSX: amd64]

下のエラーログを見るに、x86の命令をarmの命令にエミュレートし、その実行時に同期例外?というのが出ているよう

rosetta error: unexpectedly need to EmulateForward on a synchronous exception x86_rip=0x4304811968 arm_pc=0x4305005336 num_insts=4 inst_index=2 x86 instruction bytes: 0x6215344901283465301 0x9604197274868732993

事前知識として以下の記事を思い出しました。 apple siliconはRosetta2によりx86-64バイナリをAArch64(arm)のバイナリに変換し、TSOモードによってパフォーマンス良く実行している、ということだけ読み取っています。正直よくわかっていませんが、エミュレーションしているというのは事実です。 https://yamasa.hatenablog.jp/entry/2020/12/07/041649

変換前のバイナリが悪いのか、変換後のバイナリが悪いのか...

前者であれば、以下の命令周辺の命令列が正しくなさそうです。

x86 instruction bytes: 0x6215344901283465301 0x9604197274868732993

後者であれば、変換後のarmの命令列が正しくなさそうなのですがこれはどうやって確認できるのかそもそもバイナリが見れても正しくない、と判定することが可能なのか

かなりしんどそうで何もわからないかもしれませんが、暇なときにx86-64のバイナリを見てみようと思います

haruyama480 commented 8 months ago

objdumpで逆アセンブルしましたが、なんにもわかりませんでした

% objdump -d -S -M intel .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out > out

chaemon commented 8 months ago

もっと簡単なプログラムで再現できないですかねー

chaemon commented 8 months ago

そういえば、amd64と表示される件についてはこちらを見つけましたよ

https://forum.nim-lang.org/t/7823

拙者のM2 mac miniもamd64となっていますね。

このページのbuild.shをやると最初CPU: amd64と表示されますね。。。

chaemon commented 8 months ago

macなのにターミナルでuname -mを実行するとx86_64となるのですが、これはおかしいですかね

haruyama480 commented 8 months ago

nimコンパイラをarmバイナリにビルドすることができるんですね!

公式からダウンロードするとx86_64バイナリのダウンロードになるので、結果が変わりそうですね https://nim-lang.org/install_unix.html

試してみます

chaemon commented 8 months ago

choosenimではなくbrew install nimでやればいいんですかね

haruyama480 commented 8 months ago

2.0.0が入りましたね!

% which nim
/opt/homebrew/bin/nim
(venv3.10) R-MBP14UBN-0441 [which nim] ~/ghq/github.com/nim-lang/nim    12:12AM
% nim --version
Nim Compiler Version 2.0.0 [MacOSX: arm64]
Compiled at 2023-08-01
Copyright (c) 2006-2023 by Andreas Rumpf

active boot switches: -d:release -d:nimUseLinenoise

Araq氏曰く

The next major release will officially support the M1. (I use Nim on it successfully on a daily basis.)

version 2.0.0 から公式でサポートしているので、1.6の場合は自分でビルドしないといけない？ choosenim便利なんですけどね

chaemon commented 8 months ago

一応、提出前にローカルで試すとかのときはatcoderとバージョンを統一したいですねー2.0.0でoj-verifyやるとどうなるのでしょうか？

haruyama480 commented 8 months ago

失敗しました

しかし、エラーがセグフォに変わっていました

% .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out < ~/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/large_cycle_00.in
zsh: segmentation fault  .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out <

バイナリはarm64が吐かれていることを確認

% lipo -archs .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out
arm64

1.6.14 amd6の場合

% .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out < ~/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/large_cycle_00.in
rosetta error: unexpectedly need to EmulateForward on a synchronous exception x86_rip=0x4329093056 arm_pc=0x4329286428 num_insts=4 inst_index=3 x86 instruction bytes: 0x6215344901283465301 0x9604197274868732993
zsh: trace trap  .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out <

% lipo -archs .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out
x86_64

chaemon commented 8 months ago

セグフォなら、debugモードでコンパイルすればどこでセグフォかを調べることができますかねーこちらでも再現するか試してみますかね。

haruyama480 commented 8 months ago

lldbよくわかってませんが、lldbからセグフォが見れました

% lldb .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out
(lldb) target create ".verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out"
Current executable set to '/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out' (arm64).
(lldb) settings set target.input-path /Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/large_cycle_00.in
(lldb) process launch
Process 38813 launched: '/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out' (arm64)
Process 38813 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x16f603fd0)
    frame #0: 0x0000000100009658 a.out`add__OOZatcoderZinternal95scc_u732(tySequence__qwqHTkRvwhrRyENtudHQ7g&, long long)
a.out`add__OOZatcoderZinternal95scc_u732:
->  0x100009658 <+0>:  stp    x24, x23, [sp, #-0x40]!
    0x10000965c <+4>:  stp    x22, x21, [sp, #0x10]
    0x100009660 <+8>:  stp    x20, x19, [sp, #0x20]
    0x100009664 <+12>: stp    x29, x30, [sp, #0x30]
Target 0: (a.out) stopped.

chaemon commented 8 months ago

debugモードでコンパイルするとNimのコードの何行目がセグフォになってるみたいなのわかってそっちの方が手がかりになりませんかね？

haruyama480 commented 8 months ago

逆アセンブルすると、__Z34add__OOZatcoderZinternal95scc_u732R34tySequence__qwqHTkRvwhrRyENtudHQ7gx のstack popで死んでる?

% otool -tvV .verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/a.out | grep -C 5 100009658
0000000100009648    ldp x29, x30, [sp, #0x20]
000000010000964c    ldp x20, x19, [sp, #0x10]
0000000100009650    ldp x22, x21, [sp], #0x30
0000000100009654    ret
__Z34add__OOZatcoderZinternal95scc_u732R34tySequence__qwqHTkRvwhrRyENtudHQ7gx:
0000000100009658    stp x24, x23, [sp, #-0x40]!
000000010000965c    stp x22, x21, [sp, #0x10]
0000000100009660    stp x20, x19, [sp, #0x20]
0000000100009664    stp x29, x30, [sp, #0x30]
0000000100009668    add x29, sp, #0x30
000000010000966c    mov x19, x1

debugモードでコンパイル試してみます

chaemon commented 8 months ago

わからないですけど、配列の範囲外アクセスとかですかねーarmの場合だけセグフォになるというのがわかりませんが。。。

haruyama480 commented 8 months ago

% nim c --debugger:native -o:a.out verify/scc_test.nim

% ./a.out < ~/ghq/github.com/zer0-star/Nim-ACL/src/.verify-helper/cache/a335ee98513bf56941c9dd2906bfa782/test/large_cycle_00.in
Traceback (most recent call last)
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/verify/scc_test.nim(13) scc_test
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/scc.nim scc
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/internal_scc.nim(59) scc
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/internal_scc.nim(53) scc_ids
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/internal_scc.nim(40) dfs
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/internal_scc.nim(40) dfs
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/internal_scc.nim(40) dfs
(略)
(1874 calls omitted) ...
(略)
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/internal_scc.nim(40) dfs
/Users/xxx/ghq/github.com/zer0-star/Nim-ACL/src/atcoder/internal_scc.nim dfs
Error: call depth limit reached in a debug build (2000 function calls). You can change it with -d:nimCallDepthLimit=<int> but really try to avoid deep recursions instead.

haruyama480 commented 8 months ago

オプション変えてビルドし直します

chaemon commented 8 months ago

debugモードだと2000回しか再帰できないですね

haruyama480 commented 8 months ago

なるほどです..

% nim c --debugger:native -d:nimCallDepthLimit=100000 -o:a.out verify/scc_test.nim
Hint: used config file '/opt/homebrew/Cellar/nim/2.0.0_1/nim/config/nim.cfg' [Conf]
Hint: used config file '/opt/homebrew/Cellar/nim/2.0.0_1/nim/config/config.nims' [Conf]
Hint: used config file '/Users/kazusaku/ghq/github.com/zer0-star/Nim-ACL/config.nims' [Conf]
...............................................
/opt/homebrew/Cellar/nim/2.0.0_1/nim/lib/system/excpt.nim(558, 21) Error: cannot convert 100000 to int16

65536にしても溢れちゃいました

chaemon commented 8 months ago

65536以上にはできないんでしたっけ？競プロで使われるN=200000くらいは必要で余裕を持って1千万くらいにしといたほうがいいのではないですかねー

haruyama480 commented 8 months ago

デバッグモードを使うと例外をスタックする関係であまり大きいのは許容してないんですかね >int16

haruyama480 commented 8 months ago

dfsでコケているわけではなく大きいテストケースでデバッグモードが動かない小さいテストケースあると良さそう

あとは、lldb 習得して落ちるケースを見つける方針もある

chaemon commented 8 months ago

やっぱり再帰し過ぎ（スタック積みすぎ？）るとARMだとなにか問題が起こるということなんですかね。

haruyama480 commented 8 months ago

ありえそうですね EXC_BAD_ACCESS (code=2, address=0x16f603fd0)とやらを見るにポインタが壊れているようにも見えます明日また見てみます

haruyama480 commented 8 months ago

ulimitに引っかかっていただけでした〜〜〜

無事scc_testと一部のテストは通りました

ulimitでstack sizeを大きくすればよかった

以下を指定するとscc_testなどは通るようになりました。また、x86-64版のnimコンパイラ(1.6.6)でも通りました。

ulimit -s 65000

https://stackoverflow.com/questions/13245019/how-to-change-the-stack-size-using-ulimit-or-per-process-on-mac-os-x-for-a-c-or

原因

そもそもoj-verifyがulimitについてのwarningを出していましたどうやらmacOS catalina(10)以降で、python のresource.setrlimit()が失敗するようでした https://bugs.python.org/issue40518

このため深いスタックが作れずにセグフォが起きていたようです。(デバッグモードはnimコンパイラの制約なので別の話)

armで起きてintelで失敗しなかった理由は、想像なんですが、命令セットとアーキテクチャが違うのでarmのほうがスタックが深くなる可能性があるのかと思いました。intel cpuでもulimitに同じ制約があったので、テストケースによってはひっかかっていたかもしれません。

スタックポインタでセグフォが起きていたあたりから疑えればよかったです。rosettaにバイアスかかってしまいましたすみませんmm

まだ通らないverify

以下のverifyがまだ通っていないので引き続き調査する必要がありそうです

ERROR:onlinejudge_verify.verify:3 tests failed
ERROR:onlinejudge_verify.verify:failed: verify/extra/geometry/aoj_cgl_2_d_distance_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/math/pow_of_formal_power_series_test.nim
ERROR:onlinejudge_verify.verify:failed: verify/extra/math/yosupo_factorization_test.nim

haruyama480 commented 8 months ago

他の問題は別のissueに分けようと思います

このissueは、ulimitの件として引き続き開いておきます Nim-ACLできることは、verifyの前にulimit -sしましょうなREADME.mdを追記するぐらい？

haruyama480 commented 8 months ago

https://github.com/zer0-star/Nim-ACL/issues/50

verify/extra/math/yosupo_factorization_test.nimが通りました

haruyama480 commented 8 months ago

以前伺った、apple siliconだとlong doubleが倍精度になってしまうという話は本当ですね..

Armの Procedure Call Standard for the Arm 64-bit Architecture ではlong doubleはbinary128（四倍精度）と定められていますが、Appleはこの規定を上書きして、long doubleはbinary64（倍精度、doubleと同じ）としました。 https://qiita.com/mod_poppo/items/fb18f2a1441e74af29a3

アーキテクチャはlong doubleを4倍精度としているのに、OSが倍精度と上書きしてしまっているため回避策もなさそう

verify/extra/geometry/aoj_cgl_2_d_distance_test.nim通すのは諦めよう

haruyama480 commented 8 months ago

verify/extra/math/pow_of_formal_power_series_test.nimは別issueにしました https://github.com/zer0-star/Nim-ACL/issues/52

chaemon commented 8 months ago

以前伺った、apple siliconだとlong doubleが倍精度になってしまうという話は本当ですね..

Armの Procedure Call Standard for the Arm 64-bit Architecture ではlong doubleはbinary128（四倍精度）と定められていますが、Appleはこの規定を上書きして、long doubleはbinary64（倍精度、doubleと同じ）としました。 https://qiita.com/mod_poppo/items/fb18f2a1441e74af29a3

アーキテクチャはlong doubleを4倍精度としているのに、OSが倍精度と上書きしてしまっているため回避策もなさそう

verify/extra/geometry/aoj_cgl_2_d_distance_test.nim通すのは諦めよう

Nim側ではlong doubleは公式にはサポートしていなくて使っていない(C++コードを埋め込めば使えなくもない)はずなのですが、正解データを生成する際のC++側でlong double使っているんですかね？

haruyama480 commented 8 months ago

@chaemon long double関係なさそうだったのでReopenします

haruyama480 commented 8 months ago

直したいケースを特定できました

include atcoder/header
import atcoder/extra/geometry/geometry_template
import atcoder/extra/other/internal_complex

var p = newSeqWith(4, initPoint(0.0,0.0))
p[0] = initPoint(100.0, 9)
p[1] = initPoint(-51.0, -42)
p[2] = initPoint(24.0, 99)
p[3] = initPoint(-107.0, 15)
let
  s1 = initSegment(p[0], p[1])
  s2 = initSegment(p[2], p[3])
echo distance(s1, s2) # 実際の出力 79.90619500389191
let r = s1.b.projection(s2) 
echo abs(r - (s1.b)) # 期待出力 78.21068534399855
echo intersect(s2, s1.b) # false. trueになってほしい
echo ccw(s2.a, s2.b, r) # CLOCKWISE. ON_SEGMENTになってほしい

haruyama480 commented 8 months ago

floatの精度は不完全なので、(float, float)の3点がうまく直線判定できません。言い換えると、floatで扱う以上、SegmentとPointのintersectは必然的に不完全な実装になってしまいます。

https://github.com/zer0-star/Nim-ACL/blob/52da2feaf2beb4fc8b980616ed9681c03ff235c3/src/atcoder/extra/geometry/geometry_template.nim#L168-L169

なので、SegmentとPointのdistanceは上記のintersect無しに実装するのが良さそうです。

https://github.com/zer0-star/Nim-ACL/blob/52da2feaf2beb4fc8b980616ed9681c03ff235c3/src/atcoder/extra/geometry/geometry_template.nim#L215

具体的には、以下で修正できそう?

(r - s.a, s.b - s.a)という内積が、0以上 |s.b-s.a|^2 以下なら、intersect とする

chaemon commented 8 months ago

頂いたサンプルで調べてみたところ、EPSが10^-12と非常に小さく設定されていてccwの判定においてON_SEGMENTではなく、CLOCKWISEとなってしまっていることがわかりました。10^-10くらいにすると全部通るようです。EPSをいくつにするのがいいか悩みどころです。

幾何の実装についてあまり詳しくないのですが、修正いただいたような方法ですとfloatの比較でEPSを使っていなくてロバスト性がなくて問題が起こる気がします（うまく言い表せないですが）

また、現状のditanceの実装でON_SEGMENTかCLOCKWISEかの違いで値が飛んじゃう実装になっているのでそこも直さないとかもです。

zer0-star / Nim-ACL