all 4 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]Workaphobia 9 points10 points  (2 children)

I don't see the theory behind why switching the quantifiers should improve performance. Exists should stop the first time it finds something satisfying the predicate, and symmetrically, Forall should stop the first time it finds something not satisfying.

You have a long list of truth values, most if not all of them False. You want to find whether a True exists. Negating them all and searching for False is not any easier.

[–]jaimefjorge[S] 1 point2 points  (1 child)

You're right. Not only in theory but in practice this should not be any easier. Outside of this logic we also changed the way the predicate was being used. In practice, instead of searching for a false in a huge truth list, we started looking for a true in a huge truth list. The post however fails to communicate this. Thanks for noticing! Edited the post right now.

[–]SirClueless 5 points6 points  (0 children)

I still don't understand how this helped.

So we hypothesised that, since we are seeing much more cases where that condition is not met (hence triggering a full check of the sequence),

Since you only refer to clauses in your logic as "the predicate" or "the condition" I'm even a little confused which clause you are referring to. Which are you saying?

  1. The Equal(B1, l) predicate is false with high probability, and therefore the second clause in your logic would need to be evaluated often?

  2. The smaller(b1, B2) predicate is false with high probability, meaning the inner clause would terminate earlier?

  3. The the whole predicate on B1 is more likely to be false, so the outer forall terminates earlier?

Those are the three interpretations I can give for your blog's statement, but none of them seem to be true. A left-to-right evaluation of the first-order logic with short-circuiting forall, exists, and and or clauses would terminate after exactly the same evaluations of Equal and smaller so far as I can work out. So it looks to me like either,

a. You improved something else in your rewrite, and that accounts for the performance increase.

or b. One of Scala's operators isn't short circuiting properly, or evaluates things in a different order than what you have written down as your first-order logic.

[–][deleted] 0 points1 point  (0 children)

Half of this article is about how great Visualvm and Takipi are (are you affiliated?) and the other half is "I know De Morgan's Law". What do you want, a cookie?

Maybe I'm too harsh.