Although reducing the space requirement generally implies certain “minor” sacrifices in the theoretical speed of the algorithm, Helfgott believes that in certain ranges the deficit could be offset or exceeded by the possibility of mainly or exclusively using the cache memory—which is smaller but faster than main memory or RAM. “It depends on the application,” he says.
В теперешней модели CPU эффективность работы во многом упирается в чтение из памяти. Разница между поместились все данные в кеш процессора или нет может быть радикальна.
В блочном решете нужно не менее O(n^(1/2)) бит памяти. А в приведенном алгоритме O(n^(1/3) * log(n)^(2/3)). Ясно, что вероятность попадания в кеш должна быть больше у нового алгоритма при достаточно больших n. К тому же он имеет O(n) по времени: «y tiempo aun esencialmente linear en N».
На воркере каждый запуск задачи порождает процесс. Пара fork+exec занимает порядка 10 мс. Т.е. приблизительно 100 запусков hello-world задачи с одного ядра. Такие ограничения для воркера.
Есть синтетический нагрузочный тест ptest_load, который проверяет отдельно алгоритм планирования мастера. Этот тест симулирует планирование 100k задач на 10k воркеров. Это однопоточный тест и на моем железе планировалось где-то 4.5k задач в секунду.
Можно воспользоваться ручкой max_failed_nodes для ограничения длины такой эстафеты затаймаученых задач.
Если пытаться решать эту проблему, тогда нужно динамически менять таймаут в сторону увеличения. Для этого нужна обратная связь от запущенного процесса. Как понять процесс завис в infinite loop или уперся в железо? А если увеличить таймаут, то возникает вопрос: нужно ли уменьшать таймаут после того, когда ресурсы освободятся? Не совсем ясно как решать проблему с каскадным отключением автоматически в общем случае.
В теперешней модели CPU эффективность работы во многом упирается в чтение из памяти. Разница между поместились все данные в кеш процессора или нет может быть радикальна.
В блочном решете нужно не менее O(n^(1/2)) бит памяти. А в приведенном алгоритме O(n^(1/3) * log(n)^(2/3)). Ясно, что вероятность попадания в кеш должна быть больше у нового алгоритма при достаточно больших n. К тому же он имеет O(n) по времени: «y tiempo aun esencialmente linear en N».
Даже если пофиксите, то память будет не O(logN)
Есть синтетический нагрузочный тест ptest_load, который проверяет отдельно алгоритм планирования мастера. Этот тест симулирует планирование 100k задач на 10k воркеров. Это однопоточный тест и на моем железе планировалось где-то 4.5k задач в секунду.
Если пытаться решать эту проблему, тогда нужно динамически менять таймаут в сторону увеличения. Для этого нужна обратная связь от запущенного процесса. Как понять процесс завис в infinite loop или уперся в железо? А если увеличить таймаут, то возникает вопрос: нужно ли уменьшать таймаут после того, когда ресурсы освободятся? Не совсем ясно как решать проблему с каскадным отключением автоматически в общем случае.