Сравниваю скорость

[shoorick]

Решил как-то написать робота, чтоб он следил, не появилась ли на OSM очередная порция пригодного к обрисовке спутникового снимка Bing высокого разрешения. Попутно выяснил, что можно легко вычислить номера кусочков снимка (и путь к файлу с картинкой), используемого в OSM — под это, что неудивительно, на CPAN есть модуль Geo::OSM::Tiles. Но на maps.bing.com нумерация другая: адрес тайла фрагмента задаётся не тремя числами, как в OSM (масштаб, смещение по горизонтали и вертикали), а одним длинным числом, где замечательным образом смешано всё. Впрочем, вооружившись отладчиком браузера, вполне можно понять принцип, по которому строится это число. Соответствующего модуля на CPAN я не нашёл — значит, надо реализовать самостоятельно.

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



При 10⁷ итераций получаю предупреждение:

(warning: too few iterations for a reliable count)

и, например, такой результат:

              Rate  @array  BigInt BaseCnv $substr
@array  23255814/s      --    -51%    -53%    -58%
BigInt  47619048/s    105%      --     -5%    -14%
BaseCnv 50000000/s    115%      5%      --    -10%
$substr 55555556/s    139%     17%     11%      --

При 10⁸ предупреждение пропадает, программа на измерение тратит около минуты. Однако результаты продолжают оставаться странными: цифры похожи на случайные, скорость работы функции может меняться в разы.

              Rate  BigInt BaseCnv  @array $substr
BigInt  37174721/s      --    -23%    -24%    -32%
BaseCnv 48309179/s     30%      --     -1%    -12%
@array  48780488/s     31%      1%      --    -11%
$substr 54644809/s     47%     13%     12%      --

              Rate BaseCnv  BigInt  @array $substr
BaseCnv 39682540/s      --     -9%    -24%    -57%
BigInt  43478261/s     10%      --    -17%    -53%
@array  52083333/s     31%     20%      --    -44%
$substr 92592593/s    133%    113%     78%      --

               Rate  @array $substr  BigInt BaseCnv
@array   30303030/s      --    -24%    -46%    -76%
$substr  39840637/s     31%      --    -29%    -69%
BigInt   55865922/s     84%     40%      --    -56%
BaseCnv 128205128/s    323%    222%    129%      --

Неужели 10⁸ итераций мало и надо ещё увеличивать их число?

upd/02:45: Попробовал 10⁹ итераций — потратил почти полчаса. Результат похож на ожидаемый:

              Rate  @array $substr BaseCnv  BigInt
@array  43383948/s      --     -4%    -22%    -26%
$substr 45392646/s      5%      --    -19%    -22%
BaseCnv 55772448/s     29%     23%      --     -5%
BigInt  58411215/s     35%     29%      5%      --

upd/21:15: Засёк время выполнения — действительно полчаса

              Rate  @array BaseCnv $substr  BigInt
@array  18422992/s      --    -40%    -58%    -70%
BaseCnv 30590395/s     66%      --    -31%    -50%
$substr 44052863/s    139%     44%      --    -28%
BigInt  61012813/s    231%     99%     38%      --

Опять результат отличается. Хотя чемпионы остались теми же: метод с разбиением строк на символы и последующим поразрядным сложением элементов получившихся списков — самый медленный, метод, использующий преобразование аргументов между разными системами счисления средствами модуля Math::BigInt — самый быстрый.