Negando la truthiness di una valutazione booleana causando 5x rallentamento?

Question

Sto cercando di implementare un octree, e per questo, ho bisogno di un algoritmo di intersezione AABB-ray veloce. Dopo qualche ricerca, mi sono imbattuto in questo documento che sembrava offerta quello. Dal codice sorgente, disponibile qui , ho tradotto la funzione pluecker_cls_cff a C # come questo:

public bool Intersect_2(ref RayPluecker r)
{
  switch (r.Classification)
  {

    // 7 same-ish cases snipped

    case Classification.PPP:

      return !((r.Position.X > this.Max.X) || (r.Position.Y > this.Max.Y) || (r.Position.Z > this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X < 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z > 0));
  }

  return false;
}

Questo sembra funzionare bene, ma sembrava piuttosto lento a me (250 ms per fare 10 milioni interseca) così ho provato un po 'di micro-analisi comparativa con diverse varietà. In uno, ho rimosso la negazione che è giusto dopo la dichiarazione return e invertito tutti i confronti (> a < e viceversa).

E 'ora:

case Classification.PPP:

      return ((r.Position.X < this.Max.X) || (r.Position.Y < this.Max.Y) || (r.Position.Z < this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X > 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z < 0));

Questo dovrebbe dare lo stesso risultato, giusto? Sembrava così, in quanto restituisce gli stessi risultati come la versione negata con un paio di casi di test. Tuttavia, nel benchmark, è stato 5 volte più veloce (50ms per fare 10 milioni interseca)! Sono sicuro che non era stato ottimizzato fuori, il mio aspetto di riferimento come questo:

for (int i = 0; i < 10000000; i++)
{
  if (!box.Intersect_3(ref ray))
  {
    throw new Exception();
  }
}

Che cosa può spiegare questa differenza enorme? Sono in esecuzione di .NET 4.0 su x86.

Answer 1

Il secondo codice non fare la stessa cosa come prima.

Oltre alle modifiche già apportate, è necessario attivare tutte le sale operatorie in AND. (Vedere di De Morgan leggi ).

scommetto che dopo aver effettuato la correzione, i tuoi due versioni verrà eseguito alla stessa velocità.

Answer 2

In particolare relative alle prestazioni, scommetto l'istruzione return è corto circuito prima nel secondo caso rispetto al primo. Può valere la pena cercare di cambiare l'ordine dei confronti, se alcuni sono più probabilità di altri di essere vero. Se si modificano i calcoli per essere equivalente utilizzando && invece di || nel secondo caso, allora si vorrebbe quelli che hanno più probabilità di essere falso venire prima.