Почему уже всплывающие области влияют на время проверки в последующих областях?

Question

Общая проблема

Я заметил несколько раз, что push-pop области, которые уже были вытолкнуты, влияют на время check-sat в последующем объеме необходимо.

То есть, предположим, что программа имеет несколько (потенциально произвольно вложенных) областей push-pop, каждая из которых содержит команду check-sat. Кроме того, предположим, что вторая проверка занимает 10 секунд, тогда как первая проверка занимает всего 0,1 секунды.

...
(push)
  (assert (not P))
  (check-sat) ; Could be sat, unsat or unknown
(pop)
...
(push)
  (assert (not Q))
  (check-sat) ; Could be sat, unsat or unknown
(pop)

После комментирования первой области push-pop, вторая check-sat занимает только 1 с. Это почему?

• AFAIK, Z3 переключается на инкрементные решатели, если используются области push-pop. Есть ли (концептуальная) причина, почему они могут вести себя так?

• Однажды мне сказали, что Z3 присваивает символам значимость, что влияет на поиск доказательства (и важность символа также может изменяться во время поиска доказательства). Может ли это быть причиной? Можно ли сбросить значение (между областями)?

• Может ли это быть ошибкой? Я нашел этот пост, где Леонардо упоминает ошибку, которая кажется связанной (хотя его ответ с 2012 года).

Частный случай

К сожалению, у меня есть только довольно длинные (автоматически сгенерированные) файлы SMTLib, которые иллюстрируют поведение, один из которых вы можете найти в этом разделе. Он использует квантификаторы и неинтерпретированные функции, но ни mbqi ни массивы или битовые векторы. Пример состоит из 148 вложенных областей push-pop и 89 check-sats, и для его обработки у Z3 4.3.2 требуется около 8 секунд. Последний чек-сат (с префиксом echo) занимает намного больше времени

Я случайно прокомментировал несколько областей push-pop (по одному, а не последний, убедитесь, что вы не комментируете объявления символов), и в большинстве случаев общее время выполнения уменьшилось до менее 1 с. То есть последняя проверка была выполнена значительно быстрее.

Чтобы получить более подробную информацию, я сравнил прогон Z3 со всеми областями действия (медленный, 8 с) с прогоном Z3, где область, отмеченная [XXX] был прокомментирован (быстро, 0,3 с). Результаты можно увидеть в этой разнице (слева медленно, справа быстро).

Разница показывает, что все чек-саты ведут себя одинаково (я фальсифицировал закомментированный, повторяя "unsat"), из чего я заключаю, что закомментированный объем влияет на поиск доказательства, но не на его окончательный результат.

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

• grobner (383 против 36) и nonlinear-horner (342 против 25), поэтому кажется, что более медленный прогон выполняет больше операций, связанных с арифметикой. Область с комментариями действительно имеет дело с нелинейной арифметикой (как и многие другие), но конкретное доказательство в области с комментариями должно быть "тривиальным", оно, по сути, показывает, что x != 0 для x о котором 0 < x был предположен явно.

• memory (40 против 7), который я интерпретирую как указывающий на то, что Z3 исследует большее пространство поиска в медленной версии программы

• quant-instantiations (43 КБ против 51 КБ), что меня удивило, потому что значительно более быстрый запуск, тем не менее, вызвал заметно большее количество определителей.

Answer 1

Я не совсем уверен, это наблюдение или вопрос? Да, Z3 будет вести себя по-разному для разных входов, и push/pop не являются "невинными", то есть они будут оказывать значительное влияние на производительность. Это наиболее очевидно, если их можно полностью удалить, поскольку это позволяет Z3 переключаться на совершенно разные вспомогательные решатели, которые не поддерживают приращения (но часто работают быстрее). Например, для формул с чистой обработкой битов без определения области действия Z3 будет использовать быстрый новый SAT-решатель, но если требуется push/pop, он возвращается к гораздо более старому и медленному SAT-решателю (реализации этих двух решателей полностью не пересекаются).

Кроме того, удаление некоторых областей видимости между другими также может иметь огромное влияние, поскольку позволяет Z3 сохранять больше промежуточных лемм, а также эвристических состояний. Если по какой-то причине желательно, чтобы каждый запрос вел себя так, как если бы там не было других, то, возможно, лучше просто сгенерировать независимые запросы и запустить Z3 с нуля для каждого из них.

Более подробная информация о конкретных упомянутых проблемах:

"Эвристические состояния" означают всевозможные эвристические данные, которые использует Z3, и существует целое множество различных эвристик, а не только один конкретный, например, порядок символов. "Хорошо" ли хранить эту информацию между запросами, полностью зависит от ваших проблем - эвристика работает над некоторыми проблемами, но не над всеми, как это имеет характер эвристики. Тем не менее, вся концепция инкрементальности построена на этом: если эвристика не поможет, то нам будет лучше выполнять независимые запросы. Однако в некоторых приложениях сброс Z3 иногда лучше, чем отсутствие перезагрузки или независимых запросов, например, когда у вас огромное количество крошечных запросов.

Концептуальная причина перехода на другой решатель: первый не поддерживает нужные вам функции. Смотрите комбинированную_солвер.cpp, функцию check_sat, Если solver1 не используется (например, если предоставлены предположения или если включен инкрементный режим), то будет использоваться solver2.

combined_solver.solver2_timeout установит тайм-аут решателя2. Что происходит, когда время ожидания решателя2 задается параметром combined_solver.solver2_unknown, Так что, да, вы можете запустить solver1 после solver2, но solver1 также может потерпеть неудачу, то есть вернуть неизвестное. Глядя на код, он вполне может быть неправильным (например, игнорируя предположения), если он используется.

Re: отчет об ошибке, о котором упоминалось: это была ошибка исправности, а не ошибка производительности; один из решателей сказал SAT, а другой сказал UNSAT.