Какие реализации соответствуют для постоянной отправки std :: visit? - PullRequest
Новая
       45

Какие реализации соответствуют для постоянной отправки std :: visit?

3 голосов
/ 30 октября 2019

Часто цитируется, что C ++ s std::variant имеет худшую производительность, чем варианты в других языках. См., Например, https://pbackus.github.io/blog/beating-stdvisit-without-really-trying.html

Одной из причин является состояние exception, другой считается требование стандарта о том, что std::visit сложность не зависит от количества типов , что вынуждает разработчиков использовать диспетчерскую таблицу указателей функций, которая запрещает определенные оптимизации, такие как встраивание.

Вопросы:

  1. Было бы законно реализовать std::visit как цепочкуif-elseif где каждый чек похож на if(v.index() == I) return visitor(get<I>(v));? Кажется, что это не так, потому что отправка на более высокие индексы потребует большего количества проверок для индекса.
  2. Законно ли это реализовать с помощью переключателя, подобного switch(v.index()) case I: return visitor(get<I>(v));? Это выглядит как «независимое от количества типов», поскольку поток управления переходит непосредственно к случаю, и именно так, например, Microsoft реализовала его для менее чем 64 (или около того) типов.
  3. Если коммутатор допустим,законно ли оптимизатору конвертировать небольшие переключатели в лестницы if-elseif? Опять же, компилятор MSVC делает это: https://godbolt.org/z/D2Q5ED. Но IMO это нарушает сложность "не зависит от количества типов", предписанную стандартом, хотя на практике это будет быстрее.

Явопрос, основанный на обсуждении на reddit, где кто-то заявил «Постоянное время», снова относится к поведению в пределе. , с которым я не совсем согласен. IMO «Постоянное время» означает, что время постоянно, независимо от того, какой вход для if-elseif -цепи не соответствует действительности.

Но я не уверен, как это применимо здесь. Кажется, 1. недопустимо, 2. законно, но оптимизатор (может) преобразует его в 1., что означает, что 2. также незаконно. По крайней мере, если следовать стандарту к букве.

1 Ответ

2 голосов
/ 30 октября 2019

Вы путаете сложность времени и время выполнения. См., Например, здесь .

При этом важно понимать, что такие выражения, как «постоянное время» и «не зависит от», означают, когда речь идет о сложности: в этом контексте обаиз них просто синонимы для O (1) . Таким образом, утверждение в комментарии reddit действительно верно.

В случае visit это означает, что существует некоторая постоянная C, такая, что visit никогда не занимает больше, чем C CPU-циклов, даже длябезумное количество типов в variant. В частности, конечно, разрешено оставаться ниже этого числа C.

Итак, чтобы фактически ответить на ваш вопрос: использование if - else if цепочки исключительно обычно будет иметь линейный(то есть O (n)) сложность, как вы правильно заявили. Таким образом, если разработчик не знает, что компилятор оптимизирует его до чего-то постоянного, это недопустимо.

A switch с большой вероятностью будет скомпилировано в таблицу переходов, которая работает в O (1),Это особенно вероятно, если case s - это последующее число целых чисел, как здесь. Таким образом, реализация с использованием switch должна быть законной. Однако обратите внимание, что для сложного распределения case sa switch будет скомпилировано как двоичный поиск, который является O (log n). См., Например, здесь .

И, наконец, учитывая то, что я сказал ранее, конечно, разрешается применять любые виды оптимизаций, если это не приводит к ухудшению алгоритмакласс сложности. Даже если это означает, что фактическое время выполнения зависит от количества типов, сложность времени не зависит.

Обновление:

На основев ваших комментариях позвольте мне привести примеры функции, по сложности , независимой от n (иначе "константа" или O (1)), в то время как фактическое время выполнения *Конечно, 1041 * зависит от n: 

int get_max_of_first_50(std::vector<int> const& v)
{
    int max = std::numeric_limits<int>::min();
    for (int i = 0; i < 50; ++i)
        if (v[i] > max)
            max = v[i];

    return max;
}

Эта функция всегда будет выполнять 50 итераций или меньше, независимо от того, насколько большим может быть v.size(). Следовательно, по сложности, он классифицируется как константный алгоритм, независимый от n или O (1);все три утверждения эквивалентны.

Это может выглядеть как мошенничество, и в некоторой степени я могу понять это рассуждение, но важно понимать, что именно по этой причине сложность былаВведенный таким образом в первую очередь:

  • Позволяет некоторые упрощения при анализе алгоритмов. Это может легко стать очень трудным, иначе
  • Забота только об огромных затратах. Обычно никого не волнует, что будет сделано за 5 или 10 мс. Но 5 дней против 10 дней имеют значение.

Кстати, этот способ "обмана" очень распространен. Другой известный пример - реализация std::sort. В основном, большинство библиотечных реализаций, о которых я слышал, используют Quicksort (с некоторыми хитростями, поэтому это O (n log (n)) даже в худшем случае). Но для небольших последовательностей они обычно переключаются на сортировку вставкой, которая значительно быстрее в очень малых диапазонах, даже если это алгоритм со сложностью O (n ^ 2). Но, как уже объяснялось, с точки зрения сложности, это нормально, если его использование связано с константой. И с точки зрения фактического времени выполнения, это, конечно, также хорошо, так как это быстрее.

...