ByteMachine.doTransition takes 50% execution time with linear increase in latency with rule count increase

[payalm08]

Latency tends to increase linearly with increase in rules from 3k to 10k

To Reproduce

Steps to reproduce the behavior:
Create Machine instance with 3k/6k/10k rules as below, and run the example query. Results can be captured using jmh.

Example Rule:

{"data.id":["44422","23232","34325"], // size can be in range of 2-50
"data.id.333":[{"exists":false}] // size can be in range of 2-50
}

Example Query:

{"data.id": ["44422", "23232", "34325"]}. // size in range of 1000 or high

Expected behavior

Benchmark are run with 3k/6k/10k rules with query that has array of 1000 or more. Latency increased by 60% or more for every run. For the same query, the increase in latency must be gradual with change in rule count.

Environment:

Java 8 / Mac OS Sonoma 14.7

[timbray]

Question: All the values you're providing look like numbers, but they're actually strings of digits, correct?

The expected latency of Ruler as a function of rule count/shape is (I believe) very similar to that of Quamina, which has a fairly detailed discussion in that repo. One key aspect is the dependency on the number of unique keys. Anyhow, see https://github.com/timbray/quamina?tab=readme-ov-file#flattening-and-matching and especially https://github.com/timbray/quamina?tab=readme-ov-file#matchesforevent-performance

[payalm08]

Yes they are strings of digits - does it work differently when compared with string of alphabets.

…

On Thu, Oct 3, 2024, 4:22 PM Tim Bray ***@***.***> wrote: Question: All the values you're providing look like numbers, but they're actually strings of digits, correct? The expected latency of Ruler as a function of rule count/shape is (I believe) very similar to that of Quamina, which has a fairly detailed discussion in that repo. One key aspect is the dependency on the number of unique *keys*. Anyhow, see https://github.com/timbray/quamina?tab=readme-ov-file#flattening-and-matching and especially https://github.com/timbray/quamina?tab=readme-ov-file#matchesforevent-performance — Reply to this email directly, view it on GitHub <#193 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AXMHTLH5QAIRJKKO2CJNGKTZZXGTFAVCNFSM6AAAAABPKNPKECVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGOJSGUYDCMRUGE> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[timbray]

I don't think that should make a difference, but the value being 1634 vs "1634" might. But apparently that's not what's happening here.

[payalm08]

I went through the performance section. For our use case - number of fields are fixed on pattern. As per the explanation the performance is O(N) where for our case N is less than 10. However, each field is a value array, with variable size array. Is there any explanation on how the performance vary when array value size changes both on event and on pattern

…

On Thu, Oct 3, 2024, 8:33 PM Tim Bray ***@***.***> wrote: I don't think that should make a difference, but the value being 1634 vs "1634" might. But apparently that's not what's happening here. — Reply to this email directly, view it on GitHub <#193 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AXMHTLFOJBEN4ATHY5F3BRLZZYEBBAVCNFSM6AAAAABPKNPKECVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGOJSG4ZDMMBWGM> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[payalm08]

Also for our use case when exist false gets added to pattern, it increases the number of unique fields on the pattern. So that explains it. On Thu, Oct 17, 2024, 9:36 PM payal maheshwari ***@***.***> wrote:

…

I went through the performance section. For our use case - number of fields are fixed on pattern. As per the explanation the performance is O(N) where for our case N is less than 10. However, each field is a value array, with variable size array. Is there any explanation on how the performance vary when array value size changes both on event and on pattern On Thu, Oct 3, 2024, 8:33 PM Tim Bray ***@***.***> wrote: > I don't think that should make a difference, but the value being 1634 vs > "1634" might. But apparently that's not what's happening here. > > — > Reply to this email directly, view it on GitHub > <#193 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AXMHTLFOJBEN4ATHY5F3BRLZZYEBBAVCNFSM6AAAAABPKNPKECVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDGOJSG4ZDMMBWGM> > . > You are receiving this because you authored the thread.Message ID: > ***@***.***> >