8000 CVC5: String performance · Issue #11537 · cvc5/cvc5 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

CVC5: String performance #11537

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
Avg 8000 or46 opened this issue Jan 17, 2025 · 1 comment
Open

CVC5: String performance #11537

Avgor46 opened this issue Jan 17, 2025 · 1 comment
Assignees
@ajreynol

Comments

@Avgor46
Copy link
Avgor46 commented Jan 17, 2025

Hi!

I am using cvc5 version 1.2.1-dev.46.d0dd73740 [git d0dd737 on branch main]. I have the following list of constraints:

(set-logic ALL)
(declare-fun Ljava/lang/String_0 () String)
(assert (< (str.to_code (str.at Ljava/lang/String_0 0)) 123))
(assert (< (str.to_code (str.at Ljava/lang/String_0 1)) 123))
(assert (< (str.to_code (str.at Ljava/lang/String_0 2)) 123))
(assert (< (str.to_code (str.at Ljava/lang/String_0 3)) 123))
(assert (< (str.to_code (str.at Ljava/lang/String_0 4)) 123))
...
(assert (< (str.to_code (str.at Ljava/lang/String_0 31)) 123))
(assert  (= (str.to_code (str.at Ljava/lang/String_0 32)) 123))
(check-sat)

Solving this problem with cvc5 takes about 1 minute on my system, but z3 can solve it instantly. And as the string length increases, the solution time also increases, but this increase has minimal impact on the z3 solver.
@ajreynol
Copy link
Member

Thanks for the example, I can confirm the performance. At a high level, the problem is that cvc5 has a suboptimal treatment for many disjoint str.at and spends time finding a consistent arrangement.

I will keep you posted if we improve on this example.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@ajreynol ajreynol

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@ajreynol @mpreiner @Avgor46
0