Skip to content
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.

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

ast.Array should cache groundness bit to avoid unnecessary computation #3679

Closed
tsandall opened this issue Jul 26, 2021 · 2 comments · Fixed by #4151
Closed

ast.Array should cache groundness bit to avoid unnecessary computation #3679

tsandall opened this issue Jul 26, 2021 · 2 comments · Fixed by #4151

Comments

@tsandall
Copy link
Member

The ast.Array structure does not memoize groundness. As a result, checks for groundness have to recompute for all elements which can be expensive for large arrays.

Related: 00be8a2

@srenatus
Copy link
Contributor

This is a little hairier with arrays compared to sets: when slicing an array, the elements are still shared. So

  1. the slice could have a different groundness than the original
  2. changes to the slice could change the original's groundness

Still worth improving, of course. 👍

@srenatus
Copy link
Contributor

srenatus commented Aug 2, 2021

Looking further into this, the evalTerm's get/next/enumerate code path isn't the same for array as it is for sets and objects,

opa/topdown/eval.go

Lines 2709 to 2731 in 8fc2ba1

case *ast.Array:
for i := 0; i < v.Len(); i++ {
k := ast.IntNumberTerm(i)
err := e.e.biunify(k, e.ref[e.pos], e.bindings, e.bindings, func() error {
return e.next(iter, k)
})
if err != nil {
return err
}
}
case ast.Object:
return v.Iter(func(k, _ *ast.Term) error {
return e.e.biunify(k, e.ref[e.pos], e.termbindings, e.bindings, func() error {
return e.next(iter, e.termbindings.Plug(k))
})
})
case ast.Set:
return v.Iter(func(elem *ast.Term) error {
return e.e.biunify(elem, e.ref[e.pos], e.termbindings, e.bindings, func() error {
return e.next(iter, e.termbindings.Plug(elem))
})
})
}

we'll get a Number term for the index here, and feed that into get,

opa/topdown/eval.go

Lines 2777 to 2782 in 8fc2ba1

case *ast.Array:
term := v.Get(plugged)
if term != nil {
return e.termbindings.apply(term)
}
}

without any checks for groundness.

srenatus added a commit to srenatus/opa that referenced this issue Dec 17, 2021
I had been believing that we couldn't do this, since many methods
allow changing an array's elements in ways that would invalidate
the cached groundness bit. However, if we don't do that, we're OK.

To get the tests to pass, the walk builtin implementation had
implicitly depended on array plugging returning a copy; that's now
made explicit.

In topdown/bindings, this adds a few more shortcuts where applicable
(array/set). Previously, only objects had a ground?- shortcutin
plugging and namespacing vars.

Fixes open-policy-agent#3679.

Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
srenatus added a commit that referenced this issue Dec 17, 2021
I had been believing that we couldn't do this, since many methods
allow changing an array's elements in ways that would invalidate
the cached groundness bit. However, if we don't do that, we're OK.

To get the tests to pass, the walk builtin implementation had
implicitly depended on array plugging returning a copy; that's now
made explicit.

In topdown/bindings, this adds a few more shortcuts where applicable
(array/set). Previously, only objects had a ground?- shortcutin
plugging and namespacing vars.

Fixes #3679.

Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Done
Development

Successfully merging a pull request may close this issue.

2 participants