Пентадекатлон мечты

[EUgeneUS]

Dmitriy40 в сообщении #1585840 писал(а):

Ну и сравнивать незаконченные счёты не совсем корректно.

Незаконченные счёты - только в первом пункте, про влияние ключа -p. И их планируется закончить.

Dmitriy40 в сообщении #1585840 писал(а):

Проверьте сами: возьмите интервал поменьше (типа 1e31 или 1e30) в разных местах (скажем 7e31 и 28e31) и сравните время его счёта.

Это проверено. Вот пример:

001 pcoul(12 14) -p500 -f13 -g10 -x70000000000000000000000000000000 -b1673 *RT*
305 17^2 2.11^2 3.13^2 2^2.7 5.29^2 2.3^2 19^2 2^5 3.59^2 2.5^2 7^2 2^2.3 11.53^2 2.71^2: 86 / 1121 (598.30s)
...
305 83^5 2.11^2 3.13^2 2^2.7 5.233^2 2.3^2 23^2 2^5 3.173^2 2.5^2 7^2 2^2.3 11.29^2 2 (382480.82s)
367 coul(12, 14): recurse 18204937503, walk 36193728459, walkc 11267017416 (382578.14s)

001 pcoul(12 14) -p500 -f13 -g10 -x70000000000000000000000000000000:140000000000000000000000000000000 -b1673 *RT*
305 17^2 2.11^2 3.13^2 2^2.7 5.53^2 2.3^2 19^2 2^5 3.31^2 2.5^2 7^2 2^2.3 11.61^2 2.23^2: 14126 / 17502 (598.78s)
...
305 47^5 2.11^2 3.13^2 2^2.7 5.43^5 2.3^2 23^2 2^5 3 2.5^2 7^2 2^2.3 11.131^2 2 (453189.86s)
367 coul(12, 14): recurse 39680658921, walk 39209013082, walkc 24584726073 (453730.00s)

001 pcoul(12 14) -p500 -f13 -g10 -x140000000000000000000000000000000:210000000000000000000000000000000 -b1673 *RT*
305 17^2 2.11^2 3.13^2 2^2.7 5.23^2 2.3^2 19^2 2^5 3.41^2 2.5^2 7^2 2^2.3 11.61^2 2.67^2: 9222 / 9391 (598.31s)
...
305 71^5 2.11^2 3.13^2 2^2.7 5.151^2 2.3^2 37^2 2^5 3.337^2 2.5^2 7^2 2^2.3 11.23^2 2 (512175.09s)
367 coul(12, 14): recurse 16111246180, walk 15919922916, walkc 3230541205 (512523.59s)

Мы видим, что время для диапазона такого же размера несколько растёт, от того, с насколько больших чисел начинается диапазон.
Поэтому, мы как бы (при линейной зависимости от величины диапазона) можем ожидать, что время расчета диапазона 7-21e31 (не разбитого на два) будет на меньше удвоенного времени расчета диапазона 0-7e31, а оно заметно меньше.

Dmitriy40 в сообщении #1585840 писал(а):

Насчёт зависимости от -p я вот делал специальные тесты: post1574922.html#p1574922

Спасибо! Это важная информация, наличие которой я упустил. $5+11$ - это как раз "Группа Б" и есть.

[Dmitriy40]

EUgeneUS в сообщении #1585904 писал(а):

Мы видим, что время для диапазона такого же размера несколько растёт, от того, с насколько больших чисел начинается диапазон.

По моему важнее где интервал заканчивается. Понятно что одно с другим связано, но для сравнения полезнее всё же конец интервала, а не начало, как мне думается, ведь именно он участвует в вычислении порога перебора простых.

EUgeneUS в сообщении #1585904 писал(а):

Поэтому, мы как бы (при линейной зависимости от величины диапазона) можем ожидать, что время расчета диапазона 7-21e31 (не разбитого на два) будет на меньше удвоенного времени расчета диапазона 0-7e31, а оно заметно меньше.

Ну вот Вы и увидели что там нет линейной зависимости ... В принципе при наличии автовыбора момента переключения с квадратичного на линейный режим априорные ожидания могут и не оправдываться, хоть одни, хоть другие. Ну либо мне просто лень думать какие из ожиданий более практичные.
Я бы сказал что функция времени - от двух аргументов, и длины интервала, и расположения его на числовой оси (диапазона). Вот скажем длина линейного перебора зависит линейно от размера интервала, а длина квадратичного перебора - как корень из конца интервала (разница корней из конца и начала интервала), и соответственно момент переключения режимов тоже зависит от расположения интервала в диапазоне, а от него и общее время. Лучше бы это конечно прямо проверить, но мысли такие. Так что не вижу ничего особо удивительного в странном поведении функции времени при игнорировании одного из аргументов.

PS. Сравнивать диапазоны от нуля вообще малоосмысленно, слишком часто там простые попадаются и это сильно искажает статистику, надо брать хотя бы от 1-10% верхней границы (не от 0e31 до 7e31, а хоть от 1e31 или 1e30 до 7e31, или от 1e31 до 8e31 если хочется длиной именно 7e31).

-- 18.03.2023, 19:45 --

И да, похоже линейная зависимость есть от -x, но не от длины интервала, для которой она лишь для близких и относительно малых интервалов. Т.е. должно быть линейно для 0-1e31, 0-1e32, 0-1e33, 0-1e34, и например 20-21e31, 20-22e31, 22-24e31, и постоянно для например 26-27e30, 27-28e30, 28-29e30, и т.д., но не для столь огромных (относительно своего расположения) как 0-7e31, 7-14e31, 14-21e31. Чтобы интервал 7e31 вышел на константу (или на линейность от размера интервала) надо брать диапазон где-нибудь 200e31 и дальше.

[EUgeneUS]

Dmitriy40
У меня вопросы сугубо практичные.

Есть цель посчитать все паттерны "группы Б" ($5+11$) до 21e31.

1. Сколько будут потери времени, если этот диапазон делить на три куска по 7e31 или на два по 10.5e35, а не считать целиком?
2. Сколько будет выигрыш по времени, если ключ -p500 уменьшить до -p200, или до -p150?

При этом прямые эксперименты осложнены тем, что расчет диапазона 0-7e31 с -p500 занимает 2 миллиона секунд (на один паттерн)

[Dmitriy40]

Надеюсь ответы на них Вы уже получили (сами, в процессе тестов). Потому что так вот априори на первый я не отвечу, тестировать надо (не обязательно на столь огромных кусках, но тогда в сравнимых условиях, брать и диапазоны меньше, а насколько меньше это тоже вопрос непростой), а на второй частичный ответ есть в том моём сообщении, но его тоже придётся проверить прямо (что зависимость вышла на "плато" (стабильность, не обязательно линейно) и прошла начальные пертурбации). В общем не занимался я столь долгими исследованиями, может Hugo что скажет.

[EUgeneUS]

Dmitriy40

По первому вопросу ответа точного у меня нет. Но есть ощущение, что считать "цельным куском" будет не медленнее, а скорее - будет быстрее.

По второму вопросу будет более-менее понятно, когда закончится считаться паттерн с ключами -p200 и -p150. (Правда он считается на другом компе, чем паттрены с ключом -p500).

[Huz]

@EugeneUS Sorry for the delay, it has been so quiet here that I have been checking less frequently for new messages.

In respect of "-p", it is expected that it affects things sub-quadratically precisely because the switching from quadratic to linear search optimizes things to be sub-quadratic.

In respect of using -x<start>:<finish> to slice the search space, please note this section from the compile-time options in the README:

Цитата:

-DLARGE_MIN: add extra checks to cope better with runs where the minimum value to check is relatively large (as specified with -x<min>:<max>). For the majority case where min is 0 or small, we assume these checks are an unnecessary expense; hence we do not enable them by default.

The main difference is that in a build without LARGE_MIN, the code does not subtract the "start" value to determine the true size of the range, so if "start" is a large-enough proportion of "finish" it will be suboptimally reluctant to switch to linear.

If you wish I can ask DemIS to additionally make a LARGE_MIN build for this and future releases.

@Dmitriy40 Did you have a chance to look at the new options to control assignment of different powers? Do they give you the level of control you had wanted?

[Dmitriy40]

Мрак, неужели пара проверок, пусть даже во всех циклах, столь медленны?! Вот уж не подумал бы, там же по любому в проверке на простоту (или количество делителей) этих проверок уж точно не одна и даже не десяток. Мне как-то вообще странны некоторые из принятых решений, я бы сделал по другому (более оптимально на свой взгляд - правда далеко не факт что получилось бы).

Huz в сообщении #1585929 писал(а):

@Dmitriy40 Did you have a chance to look at the new options to control assignment of different powers? Do they give you the level of control you had wanted?

Judging by their description, yes, they do. But I didn't really check them because I was busy with other things and now I don't really remember why I wanted them so much... Or rather, so far I've abandoned the idea of brute force (there was an idea to move some of the brute force cycles from pcoul to an external program). Maybe as soon as I hit another threshold (which is very close), so again I will try to figure it out and use it.

[Huz]

Dmitriy40 в сообщении #1585940 писал(а):

Мрак, неужели пара проверок, пусть даже во всех циклах, столь медленны?!

I do not imagine it is a huge speed up, but every little helps - at the time I added the option nobody (including me) was asking for runs with a non-zero starting point. Also, I am used to an environment in which people that want to use my code are able to compile it, so making something a compile-time option is enough to make the option itself available.

I am still hopeful that one day either you or Eugene will acquire the setup to compile the code; to the best of my understanding it is not particularly difficult (see the README for details).

[Dmitriy40]

Huz
Trying to run several copies of pcoul simultaneously under Win10 (of course with different -b) leads to the fact that only about 60% of pcoul is actually started, the rest are kicked out by error with creating pcoul.exe.stackdump file:

Используется синтаксис Text

Stack trace:
Frame        Function    Args
000FFFFCD30  00180061E2E (00180285420, 00180270E81, 00000000058, 000FFFFB700)
000FFFFCD30  0018004849A (00180000000, 00100000000, 00000000000, 00000000001)
000FFFFCD30  001800484D2 (00000000000, 00000000000, 00000000058, 000FFFFC838)
000FFFFCD30  0018006D766 (00180045353, 00180355110, 00000000000, 0000000000D)
000FFFFCD30  0018006D779 (001800451A0, 000FFFFCD30, 001800448F2, 000FFFFC900)
000FFFFCD30  001800700B4 (00000000013, 00000000001, 000FFFFC900, 00180273615)
000FFFFCD30  0018005AACF (000FFFF0000, 00000000000, 00000000000, 000FFFFFFFF)
000FFFFCD30  0018005B215 (00000000002, 00800018318, 00800000010, 00000795F60)
000FFFFCD30  0018005B727 (001800DE88E, 00000000000, 0008013F180, 00000000000)
000FFFFCD30  0018005BA66 (000007826B6, 00000000000, FFFFFFFFFFFFFFBF, 00000000000)
000FFFFCD30  00180048C3F (00000000000, 00000000000, 00000000000, 00000000000)
000FFFFFFF0  00180047746 (00000000000, 00000000000, 00000000000, 00000000000)
000FFFFFFF0  001800477F4 (00000000000, 00000000000, 00000000000, 00000000000)
End of stack trace

Adding a 0.5s pause between pcoul launches does not significantly change anything.
Running the startup procedure again runs about 60% more of the remaining instances, and so on.

Besides, I haven't found any mechanism to detect if a particular pcoul instance is running, except for hacking OS with getting process list and analyzing it. I.e. there is no simple way to automate the process of calculating patterns list to avoid running two or more copies of pcoul with the same -b and at the same time to run an instance of pcoul for each -b of the list. If it is possible to determine the start of work by the create of a log file, there is no standard way to determine the fact of resume with existing log file.

[Huz]

Dmitriy40 в сообщении #1588227 писал(а):

Trying to run several copies of pcoul simultaneously under Win10 (of course with different -b) leads to the fact that only about 60% of pcoul is actually started, the rest are kicked out by error with creating pcoul.exe.stackdump file

I'm sorry to hear that. I have no immediate idea why that would happen, and without debug symbols the stack trace does not help me.

Dmitriy40 в сообщении #1588227 писал(а):

If it is possible to determine the start of work by the create of a log file, there is no standard way to determine the fact of resume with existing log file.

Is the recovery line written to the log file not sufficient, or the time of last modification of the file?

I see there are tools that may let me get a disassembly, I'll see if I can use those to get anything useful out of the stackdump.

Update Hmm, looks like there are debug symbols available, is there any way you can get the stackdump to use them? An object dump here works fine to disassemble, but the addresses don't obviously match up. For example, here's the line where main() calls recurse():

   10047217d:   e8 ee ef f9 ff          callq  100411170 <recurse>

.. so I'd expect to see either that calling address (10047217d) or something earlier in main() (which starts at 100472010) near the bottom of the stack.

Please also show the command-line corresponding to the stacktrace: the first argument for the call to main() should be the number of command-line arguments.

[Dmitriy40]

Huz в сообщении #1588233 писал(а):

Is the recovery line written to the log file not sufficient, or the time of last modification of the file?

Perhaps something of this will work, but the launch code is more complex and I have not tested it yet.

Huz в сообщении #1588233 писал(а):

Please also show the command-line corresponding to the stacktrace: the first argument for the call to main() should be the number of command-line arguments.

for /f %f in (D12n13) do start /min /belownormal pcoul.exe -f13 -v -x6e26 -g10 -p2e5 -b%f -rD12n13-b%f.txt 12 13

There is no other information besides pcoul.exe.stackdump. Maybe if I do not run pcoul at once, but rather a batch with a pause at the end, something will appear in the console window ... But this also needs to be tested.

[Huz]

Dmitriy40 в сообщении #1588234 писал(а):

for /f %f in (D12n13) do start /min /belownormal pcoul.exe -f13 -v -x6e26 -g10 -p2e5 -b%f -rD12n13-b%f.txt 12 13

There is no other information besides pcoul.exe.stackdump. Maybe if I do not run pcoul at once, but rather a batch with a pause at the end, something will appear in the console window ... But this also needs to be tested.

Ok, so there are 9 arguments, there should be a (decimal) 10 passed as the first argument to main(), and I don't see anything like that in the stack. Is it at all possible this is a stacktrace from "start" rather than from pcoul?
Do you have a debugger that would let you run pcoul and try to determine what those addresses in the stack correspond to?
I've added the disassembly to the release page as pcoul.asm.zip in case it is helpful

[Dmitriy40]

Huz в сообщении #1588235 писал(а):

Do you have a debugger that would let you run pcoul and try to determine what those addresses in the stack correspond to?

It looks like all addresses 001800xxxxx are in cygwin1.dll:

Address    Size      Info                                                       Content                         Type         Protectio Initial
180010000  00010000  Reserved                                                                                   PRV                    -----
180020000  00009000                                                                                             MAP          -RW--     -RW--
180030000  0000E000                                                                                             MAP          -RW--     -RW--
180040000  00001000  cygwin1.dll                                                                                IMG          -R---     ERWC-
180041000  001E6000   ".text"                                                   Executable code                 IMG          ER---     ERWC-
180227000  00001000   "/4"                                                                                      IMG          ERW--     ERWC-

What exactly are the functions is not quite clear, these addresses 180047xxx and similar ones is not exist at export table of dll:

.00000001`80042870 aio_error
.00000001`80042C50 aio_return
.00000001`800433F0 __assert_func
.00000001`80043550 __assert
.00000001`80048000 __main
.00000001`80048790 _dll_crt0
.00000001`80048850 dll_crt0__FP11per_process
.00000001`800488B0 cygwin_dll_init
.00000001`80057310 dlerror
.00000001`80058F30 dll_dllcrt0
.00000001`80058FC0 dlfork
.00000001`8005D8F0 getenv
.00000001`8005D930 secure_getenv
.00000001`80063E40 setcontext
.00000001`800645E0 getcontext
.00000001`80064630 swapcontext
.00000001`80064690 makecontext
.00000001`80065420 cygwin_internal
.00000001`80066CF0 _feinitialise
.00000001`800D8640 setgrent
.00000001`800D86C0 endgrent
.00000001`800DA870 dll_entry

When running under the debugger with the parameters "F:\2\pcoul.exe" -f13 -v -x6e26 -g10 -p2e5 -b5227 -rD12n13-b5227.txt 12 13 an exception occurs in the dll code, log of debugger:

Используется синтаксис Text

Thread 198C created, Entry: cygwin1.0000000180046AF0
Thread 2778 exit
Process stopped with exit code 0x0
Saving database to C:\Program Files\x64dbg\x64\db\pcoul.exe.dd64 16ms
Debugging stopped!
Debugging: F:\2\pcoul.exe
Database file: C:\Program Files\x64dbg\x64\db\pcoul.exe.dd64
Loading commandline...
Process Started: 100400000 F:\2\pcoul.exe
Loading database from C:\Program Files\x64dbg\x64\db\pcoul.exe.dd64 0ms
Skipping unsupported debug type IMAGE_DEBUG_TYPE_CODEVIEW in module pcoul.exe...
Did not find any supported debug types in module pcoul.exe!
Breakpoint at 100401000 (entry breakpoint) set!
DLL Loaded: 77840000 C:\Windows\System32\ntdll.dll
DLL Loaded: 77620000 C:\Windows\System32\kernel32.dll
DLL Loaded: 7FEFDAF0000 C:\Windows\System32\KernelBase.dll
Skipping unsupported debug type IMAGE_DEBUG_TYPE_CODEVIEW in module cygwin1.dll...
Did not find any supported debug types in module cygwin1.dll!
DLL Loaded: 180040000 F:\2\cygwin1.dll
Skipping unsupported debug type IMAGE_DEBUG_TYPE_CODEVIEW in module cyggmp-10.dll...
Did not find any supported debug types in module cyggmp-10.dll!
DLL Loaded: 3FFB60000 F:\2\cyggmp-10.dll
System breakpoint reached!
DebugString: "cYgFFFFFFFF 18026E780 0"
DLL Loaded: 7FEFDBE0000 C:\Windows\System32\advapi32.dll
DLL Loaded: 7FEFE170000 C:\Windows\System32\msvcrt.dll
DLL Loaded: 7FEFE850000 C:\Windows\System32\sechost.dll
DLL Loaded: 7FEFF6B0000 C:\Windows\System32\rpcrt4.dll
DLL Loaded: 7FEFD6C0000 C:\Windows\System32\cryptbase.dll
Thread 26F4 created, Entry: cygwin1.0000000180046AF0
INT3 breakpoint "entry breakpoint" at <pcoul.EntryPoint> (100401000)!
SetThreadName(26F4, "sig")
EXCEPTION_DEBUG_INFO:
           dwFirstChance: 1
           ExceptionCode: 406D1388 (MS_VC_EXCEPTION)
          ExceptionFlags: 00000000
        ExceptionAddress: 000007FEFDAFA49D kernelbase.000007FEFDAFA49D
        NumberParameters: 3
ExceptionInformation[00]: 000001000
ExceptionInformation[01]: 1802A33B3 cygwin1.1802A33B3
ExceptionInformation[02]: 0000026F4
First chance exception on 000007FEFDAFA49D (406D1388, MS_VC_EXCEPTION)!
 

Используется синтаксис ASM

000007FEFDAFA460 | 48:81EC C8000000 | sub rsp,C8 |
000007FEFDAFA467 | 83E2 01 | and edx,1 |
000007FEFDAFA46A | 48:8D05 EFFFFFFFF | lea rax,qword ptr ds:[<RaiseException>] |
000007FEFDAFA471 | 894C24 20 | mov dword ptr ss:[rsp+20],ecx |
000007FEFDAFA475 | 33C9 | xor ecx,ecx |
000007FEFDAFA477 | 48:894424 30 | mov qword ptr ss:[rsp+30],rax |
000007FEFDAFA47C | 895424 24 | mov dword ptr ss:[rsp+24],edx |
000007FEFDAFA480 | 48:894C24 28 | mov qword ptr ss:[rsp+28],rcx |
000007FEFDAFA485 | 4D:85C9 | test r9,r9 |
000007FEFDAFA488 | 0F85 A0040000 | jne 7FEFDAFA92E |
000007FEFDAFA48E | 894C24 38 | mov dword ptr ss:[rsp+38],ecx |
000007FEFDAFA492 | 48:8D4C24 20 | lea rcx,qword ptr ss:[rsp+20] |
000007FEFDAFA497 | FF15 23FE0300 | call qword ptr ds:[<&RtlRaiseException>] |
000007FEFDAFA49D | 48:81C4 C8000000 | add rsp,C8 |
000007FEFDAFA4A4 | C3 | ret |

With this in the stack (RSP=00000000006FCB20):

Используется синтаксис ASM

00000000006FCAF0 0
00000000006FCAF8 00000001802387E0 cygwin1.00000001802387E0
00000000006FCB00 00000000006FCD50  
00000000006FCB08 00000000006FCE00  
00000000006FCB10 0000000180270C10 "erroneous thread activation, name is NULL"
00000000006FCB18 000007FEFDAFA49D return to kernelbase.000007FEFDAFA49D from ?
00000000006FCB20 00000000000028B0  
00000000006FCB28 00000001802A33B3 "sig"
00000000006FCB30 0000000180270BE8 "static DWORD cygthread::stub(void*)"
00000000006FCB38 0
00000000006FCB40 00000000406D1388  
00000000006FCB48 0
00000000006FCB50 000007FEFDAFA49D return to kernelbase.000007FEFDAFA49D from ?

Unfortunately it looks like this exception has nothing to do with creating the pcoul.exe.stackdump file and just some internal exception, even normally handled, because if you ignore it and continue execution, it gets here 5 more times, and then runs a normal calculation.

How to catch in the debugger when pcoul.exe.stackdump file is created, I do not understand, and to run dozens and hundreds of instances, waiting for which of them will pop up ...

[Huz]

Dmitriy40 в сообщении #1588245 писал(а):

It looks like all addresses 001800xxxxx are in cygwin1.dll

Ah, that makes sense.

Disassembly shows a bunch of internal names in that area, here are the relevant calls in the stack (reverse order):

_ZN7_cygtls4callEPFjPvS0_ES0_ (1800477c0):
    1800477ef:   e8 1c ff ff ff          callq  180047710 <_ZN7_cygtls5call2EPFjPvS0_ES0_S0_>
_ZN7_cygtls5call2EPFjPvS0_ES0_S0_ (180047710):
    180047744:   ff d3                   callq  *%rbx
_Z10dll_crt0_1Pv (180048a70):
    180048c3a:   e8 a1 2d 01 00          callq  18005b9e0 <_ZN6dtable10stdio_initEv>
_ZN6dtable10stdio_initEv (18005b9e0):
    18005ba61:   e8 da f7 ff ff          callq  18005b240 <_ZN6dtable25init_std_file_from_handleEiPv>
_ZN6dtable25init_std_file_from_handleEiPv (18005b240):
    18005b722:   e8 e9 f9 ff ff          callq  18005b110 <_Z12build_fh_devRK6devicePKc>
_Z12build_fh_devRK6devicePKc (18005b110):
    18005b210:   e8 ab e9 ff ff          callq  180059bc0 <_Z11build_fh_pcR9path_conv>
_Z11build_fh_pcR9path_conv (180059bc0):
    18005aaca:   e8 81 55 01 00          callq  180070050 <_ZN16fhandler_consoleC1E10fh_devices> 
_ZN16fhandler_consoleC1E10fh_devices (180070050):
    1800700af:   e8 bc d6 ff ff          callq  18006d770 <_ZN16fhandler_console5setupEv>
_ZN16fhandler_console5setupEv (18006d770):
    18006d774:   e8 e7 fc ff ff          callq  18006d460 <_ZN16fhandler_console8set_unitEv>
_ZN16fhandler_console8set_unitEv (18006d460):
    18006d761:   e8 4a ad fd ff          callq  1800484b0 <api_fatal>

So I guess it is trying to initialize the console (or possibly a console interrupt handler), but I'd need to dig out the cygwin source to have any hope of understanding what's actually going wrong.

[Dmitriy40]

Huz
This is some little-understood problems with the Windows, this is what it says when you try to manually run one of the failed variant:

C:\2>pcoul -f13 -v -x6e26 -g10 -p2e5 -b1123 -rD12n13-b1123.txt 12 13
      0 [main] pcoul 1126 C:\2\pcoul.EXE: *** fatal error - console device allocation failure - too many consoles in use
    251 [main] pcoul 1126 cygwin_exception::open_stackdumpfile: Dumping stack trace to pcoul.EXE.stackdump

Maybe because I am not running normal Win10, but Win10PE.