Superlinear scalability

15 February 2010 theory scalability

Как вы думаете во сколько раз может быть быстрее ваша программа, если вам дадут в два раза более “крутое” железо: в два раза более быстрый процессор, в два раза больше памяти и т.д. Интуитивный ответ — в два раза. Раньше я уже писал о том, что не все так безоблачно. Взвесив все аргументы вы можете сказать: “окей, максимум в два раза”. Но что если бы я вам сказал, что при увеличении вычислительной мощности в два раза вы можете получить ускорение больше чем в два раза?

Давайте представим себе обратный случай: у вас есть алгоритм с асимптотической оценкой по времени в O(n). И вы решаете задачу эталонного размера на эталонном компьютере за эталонное время. Увеличим размер задачи в два раза. Скажем вместо 5 миллионов записей надо отсортировать 10 миллионов (например, за O(n) можно сделать топологическую сортировку). Как изменится эталонное время? Увеличится в двое… как минимум. Увеличение времени вдвое нам гарантировано, так как мы выполним в два раза больше операций. Но существуют причины для дополнительного замедления программы. Например, если удвоенный dataset не помещается в оперативную память, то вы получите большое количество page fault’ов и операционной системе прийдется одни страницы выгружать из оперативной памяти на жесткий диск, другие загружать с диска в оперативную память. В общем случае, вы можете получить замедление более чем в два раза.

Но что если теперь мы начнем решать эту “удвоенную задачу” на “удвоенном компьютере”? Во-первых, мы получим двукратный прирост производительности связанный с удвоенной вычислительной способностью нового компьютера. Но также мы избавимся от лишних page in/page out’ов, что безусловно еще более убыстрит нашу программу, так как теперь не надо тратить лишнее время на IO. А это значит что в сумме мы получим более чем двукратный прирост производительности.

Утверждение “при удвоении вычислительных ресурсов можно получить максимум двукратный прирост производительности” имеет силу только в условиях когда задача решается эффективно (то есть не делается лишней работы).